Evolving distributed agents for managing air traffic

ABSTRACT

Air traffic management offers an intriguing real world challenge to designing large scale distributed systems using evolutionary computation. The ability to evolve effective air traffic flow strategies depends not only on evolving good local strategies, but also on ensuring that those local strategies result in good global solutions. While traditional, direct evolutionary strategies can be highly effective in certain combinatorial domains, they are not well-suited to complex air traffic flow problems because of the large interdependencies among the local subsystems. In this paper, we propose an evolutionary agent-based solution to the air traffic flow problem. In this approach, we evolve agents both to learn the right local flow strategies to alleviate congestion in their immediate surroundings, and to prevent the creation of congestion "downstream" from their local areas. The agent-based approach leads to better and more fault-tolerant solutions. To validate this approach, we use FACET, an air traffic simulator developed at NASA and used extensively by the FAA and industry. On a scenario composed of three hundred aircraft and two points of congestion, our results show that an agent based evolutionary computation method, where each agent uses the system evaluation function, achieves 40% improvement over a direct evolutionary algorithm. In addition by creating agent-specific "difference evaluation functions" we achieve an additional 30% improvement over agents using the system evaluation.

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: E. J. Anderson and M. C. Ferris. Genetic algorithms for combinatorial optimization:The assembly line balancing problem. OSRA Journal on Computing, 6:161--173, 1994.
• 3: 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.
• 4: Karl D. Bilimoria. A geometric optimization approach to aircraft conflict resolution. In AIAA Guidance, Navigation, and Control Conference and Exhibit, Denver, CO, 2000.
• 5: Martin S. Eby and Wallace E. Kelly III. Free flight separation assurance using distributed algorithms. In Proceedings of Aerospace Conference, 1999, Aspen, CO, 1999.
• 6: FAA OPSNET data Jan-Dec 2005. US Department of Transportation website.
• 7: Dario Floreano , Francesco Mondada, Automatic creation of an autonomous agent: genetic evolution of a neural-network driven robot, Proceedings of the third international conference on Simulation of adaptive behavior : from animals to animats 3: from animals to animats 3, p.421-430, July 1994, Brighton, United Kingdom
• 8: F. Gomez and R. Miikkulainen. Active guidance for a finless rocket through neuroevolution. In Proceedings of the Genetic and Evolutionary Computation Conference, Chicago, Illinois, 2003.
• 9: S. Grabbe and B. Sridhar. Central east pacific flight routing. In AIAA Guidance, Navigation, and Control Conference and Exhibit, Keystone, CO, 2006.
• 10: 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]
• 11: 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.
• 12: Daniel Merkle, Martin Middendorf, and Hartmut Schmeck. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6(4):333--346, 2002.
• 13: 2006 NASA Software of the Year Award Nomination. FACET: Future ATM concepts evaluation tool. Case no. ARC-14653-1, 2006.
• 14: 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]
• 15: B. Sridhar, G. Chatterji, and S. Grabbe. Benefits of direct-to in national airspace system. In AIAA Guidance, Navigation, and Control Conference and Exhibit, Denver, CO, 2000.
• 16: Kenneth O. Stanley , Risto Miikkulainen, Efficient Reinforcement Learning Through Evolving Neural Network Topologies, Proceedings of the Genetic and Evolutionary Computation Conference, p.569-577, July 09-13, 2002
• 17: C. Tomlin, G. Pappas, and S. Sastry. Conflict resolution for air tra . c management. IEEE Transaction on Automatic Control, 43(4):509--521, 1998.
• 18: Kagan Tumer , Adrian Agogino, Coordinating multi-rover systems: evaluation functions for dynamic and noisy environments, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA [doi>10.1145/1068009.1068109]
• 19: K. Tumer and A. Agogino. Distributed agent-based air traffic flow management. In Proceedings of the Sixth International Joint Conference on Autonomous Agents and Multi-Agent Systems, Honolulu, Hawaii, May 2007. to appear.
• 20: Kagan Tumer , David H. Wolpert , Kagan Turner, Collectives and Design Complex Systems, SpringerVerlag, 2004

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Aerospace

General Terms:
Algorithms, Performance

Keywords:
air traffic control, evolution, multiagent systems