Abstract
Intelligent air traffic flow management is one of the fundamental challenges facing the Federal Aviation Administration (FAA) today. FAA estimates put weather, routing decisions and airport condition induced delays at 1,682,700 h in 2007 (FAA OPSNET Data, US Department of Transportation website, http://www.faa.gov/data_statistics/), resulting in a staggering economic loss of over $41 billion (Joint Economic Commission Majority Staff, Your flight has been delayed again, 2008). New solutions to the flow management are needed to accommodate the threefold increase in air traffic anticipated over the next two decades. Indeed, this is a complex problem where the interactions of changing conditions (e.g., weather), conflicting priorities (e.g., different airlines), limited resources (e.g., air traffic controllers) and heavy volume (e.g., over 40,000 flights over the US airspace) demand an adaptive and robust solution. In this paper we explore a multiagent algorithm where agents use reinforcement learning (RL) to reduce congestion through local actions. Each agent is associated with a fix (a specific location in 2D space) and has one of three actions: setting separation between airplanes, ordering ground delays or performing reroutes. We simulate air traffic using FACET which is an air traffic flow simulator developed at NASA and used extensively by the FAA and industry. Our FACET simulations on both artificial and real historical data from the Chicago and New York airspaces show that agents receiving personalized rewards reduce congestion by up to 80% over agents receiving a global reward and by up to 90% over a current industry approach (Monte Carlo estimation).
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Agogino, A., & Tumer, K. (2004). Efficient evaluation functions for multi-rover systems. In The genetic and evolutionary computation conference. Seatle, WA, pp. 1–12.
Agogino, A., & Tumer, K. (2005). Multi agent reward analysis for learning in noisy domains. In Proceedings of the fourth international joint conference on autonomous agents and multi-agent systems. Utrecht, Netherlands.
Agogino A. K., Tumer K. (2006) Handling communication restrictions and team formation in congestion games. Journal of Autonomous Agents and Multi Agent Systems 13(1): 97–115
Agogino, A., & Tumer, K. (2008). Regulating air traffic flow with coupled agents. In Proceedings of the seventh international joint conference on autonomous agents and multi-agent systems. Estoril, Portugal.
Agogino A. K., Tumer K. (2009) Learning indirect actions in complex domains: Action suggestions for air traffic control. Advances in Complex Systems 12: 493–512
Bayen A. M., Grieder P., Meyer G., Tomlin C. J. (2005) Lagrangian delay predictive model for sector-based air traffic flow. AIAA Journal of Guidance, Control, and Dynamics 28: 1015–1026
Bertsimas D., Stock-Patterson S. (1998) The air traffic management problem with enroute capacities. Operations Research 46(3): 406–422
Bilimoria, K. D. (2000). A geometric optimization approach to aircraft conflict resolution. In AIAA guidance, navigation, and control conference and exhibit. Denver, CO.
Bilimoria, K., Sheth, K., Lee, H., & Grabbe, S. (2000). Performance evaluation of airborne separation assurance for free flight. In AIAA guidance, navigation, and control conference. Denver, CO.
Bilimoria K.D., Sridhar B., Chatterji G.B., Shethand K.S., Grabbe S.R. (2001) FACET: Future ATM concepts evaluation tool. Air Traffic Control Quarterly 9(1): 1–20
Bonaceto, C., Estes, S., Moertl, P., & Burns, K. (2005). Naturalistic decision making in the air traffic control tower: combining approaches to support changes in procedures. In Proceedings of the seventh international NDM conference. Amsterdam, The Netherlands.
Campbell, K., Cooper, W. J., Greenbaum, D., & Wojcik, L. (2000). Modeling distributed human decision making in traffic flow management operations. In 3rd USA/Europe air traffic management R & D seminar. Napoli.
Christodoulou, M., & Costoulakis, C. (2004). Nonlinear mixed integer programming for aircraft collision avoidance in free flight’. In IEEE MELECON, Vol. 1. Dubrovnik, Croatia, pp. 327–330.
Devasia, S., Heymann, M., & Meyer, G. (2002). Automation procedures for air traffic management: A token-based approach. In Proceedings of American control conference, Vol. 1. pp. 736–741. Atlanta, GA
Donohue, G. L., & Shaver III, R. D. (2008). TERMINAL CHAOS: Why U.S. Air Travel is broken and how to fix it. Webster: American Institute of Aeronautics and Astronautics.
Eby, M. S. & III, W. E. K. (1999). Free flight separation assurance using distributed algorithms. In Proceedings of aerospace conference. Aspen, CO.
Erzberger, H., McNally, D., Foster, M., Chiu, D., & Stassart, P. (1999). Direct-to tool for en route controllers. In IEEE workshop on advanced technologies and their impact on air traffic management in the 21st century. Capri, Italy.
FAA OPSNET Data Jan–Dec 2007. (2007). US Department of Transportation website. http://www.faa.gov/data_statistics/.
Grabbe, S. & Sridhar, B. (2006). Central East Pacific Flight Routing’. In AIAA guidance, navigation, and control conference and exhibit. Keystone, CO.
Heymann, M., Meyer, G., & Resmerita, S. (2004). An agent based framework for control of merging air traffic. In Proceedings 16th IFAC symposium on automatic control in aerospace. St. Petersburg, Russia.
Hill, J. C., Johnson, F. R., Archibald, J. K., Frost, R. L., & Stirling, W. C. (2005). A cooperative multi-agent approach to free flight. In AAMAS ’05: Proceedings of the fourth international joint conference on autonomous agents and multiagent systems. New York, NY, USA, pp. 1083–1090.
Hwang I., Balakrishnan H., Balakrishnan H., Balakrishnan H. (2006) State estimation for hybrid systems: applications to aircraft tracking. IEE Proceedings of Control Theory and Applications 153: 556–566
Joint Economic Commission Majority Staff (2008). Your Flight Has Been Delayed Again’. pp. 1–12.
Jonker, G., Dignum, F., & Meyer, J.-J. (2007). Achieving cooperation among selfish agents in the air traffic management domain using signed money. In Proceedings of the sixth international joint conference on autonomous agents and multi-agent systems. Honolulu, HI.
Kelly, W. I., & Eby, M. (2000). Advances in force field conflict resolution algorithms. In AIAA guidance, navigation, and control conference and exhibit. Denver, CO.
Knight, J. C. & Parikh, S. (2002). Simulation technology for free flight system performance and survivability analysis. In Proceedings of the 21st digital avionics systems conference, pp. 13D5–1–13D5–9. Irvine, CA.
Kohn, W., Remmel, J., Moser, W., & Cummings, B. (1997). Free flight ATC using hybrid agent systems. In Proceedings of the 36th IEEE CDC. San Diego, CA.
Ma Z., Cui D., Cheng P. (2004) Dynamic network flow model for short-term air traffic flow management. IEEE Transaction on Systems, Man, and Cybernetics Part A: Systems and Humans 34(3): 351–358
McNally, D., & Gong, C. (2006). Concept and laboratory analysis of trajectory-based automation for separation assurance. In AIAA guidance, navigation and control conference and exhibit. Keystone, CO.
Menon P. K., Sweriduk G. D., Bilimoria K. D. (2004) New approach for modeling, analysis and control of air traffic flow. Journal of Guidance, Control, and Dynamics 27(5): 737–744
Menon P. K., Sweriduk G. D., Sridhar B. (1999) Optimal strategies for free flight air traffic conflict resolution. Journal of Guidance, Control, and Dynamics 22(2): 202–211
Mueller, E. R., Chatterji, G. B. (2002). Analysis of aircraft arrival and departure delay characteristics. In AIAA aircraft technology, integration and operations (ATIO) conference. Los Angeles, CA.
Pallottino L., Feron E., Bicchi A. (2002) Conflict resolution problems for air traffic management systems solved with mixed integer programming. IEEE Transactions on Intelligent Transportation Systems 3(1): 3–11
Pechoucek M., Sislak D. (2009) Agent-based approach to free-flight planning, control, and simulation. IEEE Intelligent Systems 24(1): 14–17
Pechoucek, M., Sislak, D., Pavlicek, D., & Uller, M. (2006). Autonomous agents for air-traffic deconfliction. In Proceedings of the fifth international joint conference on autonomous agents and multi-agent systems. Hakodate, Japan.
Quinn, C., & Zelenka, R. (1998). ATC/air carrier collaborative arrival planning. In 2nd USA/Europe air traffic management R & D seminar. Orlando, FL.
Raffard, R. L., & Tomlin, C. J. (2005). Second order optimization of ordinary and partial differential equations with application to air traffic flow. In Proceedings of the AACC American control conference, pp. 798–803. Portland, OR.
Raffard, R. L., Waslander, S. L., Bayen, A. M., & Tomlin, C. J. (2005). A cooperative distributed approach to multi-agent Eulerian network control: Application to air traffic management. In AIAA guidance, navigation, and control conference and exhibit. San Francisco, CA.
Sislak, D., Pechoucek, M., Volf, P., Pavlicek, D., Samek, J., Mařík, V., & Losiewicz, P. (2008a). AGENTFLY: Towards multi-agent technology in free flight air traffic control. In M. Pechoucek, S. Thompson, & H. Voss (Eds.), Defense industry applications of autonomous agents and multi-agent systems (Chap. 7, pp. 73–97). Birkhauser Verlag, Basel.
Sislak, D., Samek, J., & Pechoucek, M. (2008b). Decentralized algorithms for collision avoidance in airspace. In Proceedings of seventh international conference on autonomous agents and multi-agent systems, pp. 543–550. Estoril, Portugal.
Sridhar B., Soni T., Sheth K., Chatterji G. B. (2006) Aggregate flow model for air-traffic management. Journal of Guidance, Control, and Dynamics 29(4): 992–997
Sridhar, B., & Swei, S. (2006). Relationship between weather, traffic and delay based on empirical methods. In 6th AIAA aviation technology, integration and operations conference (ATIO). Wichita, Kansas.
Stipanovic D. M., Shankaran S., Tomlin C. J. (2005) Multi-agent avoidance control using an M-matrix property. Electronic Journal of Linear Algebra 12: 64–72
Sutton R. S., Barto A. G. (1998) Reinforcement learning: An introduction. MIT Press, Cambridge, MA
Tomlin, C. (1998). Hybrid control of air traffic management systems. Ph.D. thesis, University of California at Berkeley.
Tomlin C., Pappas G., Sastry S. (1998) Conflict resolution for air traffic management: A study in multiagent hybrid systems. IEEE Transaction on Automatic Control 43(4): 509–521
Tumer, K., Agogino, A. (2007). Distributed agent-based air traffic flow management. In Proceedings of the sixth international joint conference on autonomous agents and multi-agent systems, pp. 330–337. Honolulu, HI.
Tumer K., Agogino A. (2009) Improving air traffic management with a learning multiagent system. IEEE Intelligent Systems 24(1): 18–21
Tumer, K., Wolpert, D. (eds) (2004) Collectives and the design of complex systems. Springer, New York
van Gent, J., Ruigrok, R., & Ruigrok, R. (1998). Conceptual design of free flight with airborne separation assurance. In AIAA guidance, navigation, and control conference, pp. 807–817. Boston, MA.
Wangermann J.P., Stengel R.F. (1999) Optimization and coordination of multiagent systems using principled negotiation. Guidance, Control and Dynamics 22(1): 43–50
Wollkind, S., Valasek, J., & Ioerger, T. (2004). Conflict resolution for air traffic management using cooperative multiagent negotiation. In AIAA guidance, navigation, and control conference. Providence, RI.
Wolpert D. H., Tumer K. (2001) Optimal payoff functions for members of collectives. Advances in Complex Systems 4(2/3): 265–279
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Agogino, A.K., Tumer, K. A multiagent approach to managing air traffic flow. Auton Agent Multi-Agent Syst 24, 1–25 (2012). https://doi.org/10.1007/s10458-010-9142-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10458-010-9142-5