Distributed agent-based air traffic flow management

ABSTRACT

Air traffic flow management is one of the fundamental challenges facing the Federal Aviation Administration (FAA) today. The FAA estimates that in 2005 alone, there were over 322,000 hours of delays at a cost to the industry in excess of three billion dollars. Finding reliable and adaptive solutions to the flow management problem is of paramount importance if the Next Generation Air Transportation Systems are to achieve the stated goal of accommodating three times the current traffic volume. This problem is particularly complex as it requires the integration and/or coordination of many factors including: new data (e.g., changing weather info), potentially conflicting priorities (e.g., different airlines), limited resources (e.g., air traffic controllers) and very heavy traffic volume (e.g., over 40,000 flights over the US airspace).

In this paper we use FACET -- an air traffic flow simulator developed at NASA and used extensively by the FAA and industry -- to test a multi-agent algorithm for traffic flow management. An agent is associated with a fix (a specific location in 2D space) and its action consists of setting the separation required among the airplanes going though that fix. Agents use reinforcement learning to set this separation and their actions speed up or slow down traffic to manage congestion. Our FACET based results show that agents receiving personalized rewards reduce congestion by up to 45% over agents receiving a global reward and by up to 67% over a current industry approach (Monte Carlo estimation).

REFERENCES

• 1: A. Agogino and K. Tumer. Efficient evaluation functions for multi-rover systems. In The Genetic and Evolutionary Computation Conference, pages 1--12, Seatle, WA, June 2004.
• 2: Adrian Agogino , Kagan Turner, Multi-agent reward analysis for learning in noisy domains, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082486]
• 3: Adrian K. Agogino , Kagan Tumer, Handling Communication Restrictions and Team Formation in Congestion Games, Autonomous Agents and Multi-Agent Systems, v.13 n.1, p.97-115, July 2006 [doi>10.1007/s10458-006-6105-y]
• 4: K. D. Bilimoria, B. Sridhar, G. B. Chatterji, K. S. Shethand, and S. R. Grabbe. FACET: Future ATM concepts evaluation tool. Air Traffic Control Quarterly, 9(1), 2001.
• 5: Karl D. Bilimoria. A geometric optimization approach to aircraft conflict resolution. In AIAA Guidance, Navigation, and Control Conf, Denver, CO, 2000.
• 6: Martin S. Eby and Wallace E. Kelly III. Free flight separation assurance using distributed algorithms. In Proc of Aerospace Conf, 1999, Aspen, CO, 1999.
• 7: FAA OPSNET data Jan-Dec 2005. US Department of Transportation website.
• 8: S. Grabbe and B. Sridhar. Central east pacific flight routing. In AIAA Guidance, Navigation, and Control Conference and Exhibit, Keystone, CO, 2006.
• 9: Jared C. Hill , F. Ryan Johnson , James K. Archibald , Richard L. Frost , Wynn C. Stirling, A cooperative multi-agent approach to free flight, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082637]
• 10: P. K. Menon, G. D. Sweriduk, and B. Sridhar. Optimal strategies for free flight air traffic conflict resolution. Journal of Guidance, Control, and Dynamics, 22(2):202--211, 1999.
• 11: 2006 NASA Software of the Year Award Nomination. FACET: Future ATM concepts evaluation tool. Case no. ARC-14653-1, 2006.
• 12: Michal Pěchouček , David Šišlák , Dušan Pavlíček , Miroslav Uller, Autonomous agents for air-traffic deconfliction, Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, May 08-12, 2006, Hakodate, Japan [doi>10.1145/1160633.1160925]
• 13: B. Sridhar and S. Grabbe. Benefits of direct-to in national airspace system. In AIAA Guidance, Navigation, and Control Conf, Denver, CO, 2000.
• 14: B. Sridhar, T. Soni, K. Sheth, and G. B. Chatterji. Aggregate flow model for air-traffic management. Journal of Guidance, Control, and Dynamics, 29(4):992--997, 2006.
• 15: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 16: C. Tomlin, G. Pappas, and S. Sastry. Conflict resolution for air traffic management. IEEE Tran on Automatic Control, 43(4):509--521, 1998.
• 17: Kagan Tumer , David H. Wolpert , Kagan Turner, Collectives and Design Complex Systems, SpringerVerlag, 2004
• 18: D. H. Wolpert and K. Tumer. Optimal payoff functions for members of collectives. Advances in Complex Systems, 4(2/3):265--279, 2001.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

General Terms:
Algorithms, Performance

Keywords:
air traffic control, multiagent systems, optimization, reinforcement learning