On the Use of Q² Abstractions to Lower the Computational Cost of Derivation of Conflict Resolution Advisories in Air Traffic Control

This paper addresses the high computational complexity of generating multistep conflict resolution advisories (RAs) in air traffic control. Because this problem is known to be NP-hard, one cannot expect algorithms that will solve every instance of the problem independent of its size. Thus, the goal is to develop more efficient algorithms that can analyze a wider space of possible RAs, for instance, horizontal maneuvers. This paper presents a study of the use of abstraction to such a problem. However, abstractions can lead to wrong decisions, e.g., to maneuvers that result in unsafe states. Such abstractions are referred to as inconsistent. To avoid these kinds of problems, we use the so-called Q² abstractions, which are derived from the specifications of a problem and are guaranteed to be consistent. To assess the usability of the Q² approach to computing horizontal RAs, we analyze the impact of such abstractions on the computational cost of an exhaustive search algorithm and on the quality of RAs found. The results show that the use of the Q² approach lowers the conflict-resolution computation time without losing much of the quality of solutions.

• Record URL:
  https://doi.org/10.1109/TITS.2010.2058848
• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/oclc/41297384
• Supplemental Notes:
  • Abstract reprinted with permission of IEEE.
• Authors:
  • Li, Mei
  • Kokar, Mieczyslaw M
• Publication Date: 2010

Language

• English

Media Info

• Media Type: Web
• Features: Figures; References; Tables;
• Pagination: pp 954-967
• Serial:
  • IEEE Transactions on Intelligent Transportation Systems
  • Volume: 11
  • Issue Number: 4
  • Publisher: Institute of Electrical and Electronics Engineers (IEEE)
  • ISSN: 1524-9050
  • Serial URL: http://ieeexplore.ieee.org/xpl/RecentIssue.jsp?punumber=6979

Subject/Index Terms

• TRT Terms: Advanced automation systems; Air traffic control; Aircraft separation; Algorithms; Simulation
• Subject Areas: Aviation; Operations and Traffic Management;

Filing Info

• Accession Number: 01333656
• Record Type: Publication
• Source Agency: UC Berkeley Transportation Library
• Files: TLIB
• Created Date: Mar 21 2011 2:15PM