A cooperative multi-agent approach to free flight

ABSTRACT

The next generation of air traffic control will require automated decision support systems in order to meet safety, reliability, flexibility, and robustness demands in an environment of steadily increasing air traffic density. Automation is most readily implemented in free flight, the segment of flight between airports. In this environment, centralized control is impractical, and on-board distributed decision making is required. To be effective, such decision making must be cooperative. Satisficing game theory provides a theoretical framework in which autonomous decision makers may coordinate their decisions. The key feature of the theory is that, unlike conventional game theory which is purely egotistic in its structure, it provides a natural mechanism for decision makers to form their preferences by taking into consideration the preferences of others. In this way, a controlled form of conditional altruism is possible, such that agents are able to compromise so that every decision maker receives due consideration in a group environment. Simulations demonstrate that reliable performance can be achieved with densities on the order of 50 planes per ten thousand square miles.

REFERENCES

• 1: National Research Council Panel on Human Factors in Air Traffic Control Automation, C. D. Wickens, A. S. Mavor, R. Parasuraman, and J. P. McGee, Eds., The Future of Air Traffic Control: Human Factors and Automation. National Academy Press, 1998.
• 2: Tekla S. Perry, In search of the future of air traffic control, IEEE Spectrum, v.34 n.8, p.18-35, Aug. 1997 [doi>10.1109/6.609472]
• 3: Linda Geppert, A static RAM says goodbye to data errors, IEEE Spectrum, v.41 n.2, p.16-17, February 2004 [doi>10.1109/MSPEC.2004.1265121]
• 4: Wynn C. Stirling, Satisficing Games and Decision Making: With Applications to Engineering and Computer Science, Cambridge University Press, New York, NY, 2003
• 5: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 6: F. R. Kschischang, B. J. Frey, and H.-A. Loeliger, "Factor graphs and the sum-product algorithm," IEEE Transactions on Information Theory, vol. 47, pp. 498--519, 2001.
• 7: J. Krozel, M. Peters, K. D. Bilimoria, C. Lee, and J. S. B. Mitchell, "System performance characteristics of centralized and decentralized air traffic separation strategies," Fourth USA/Europe Air Traffic Management Research and Development Seminar, 2001.
• 8: D. Dugail, E. Feron, and K. Bilimoria, "Stability of intersecting aircraft flows using heading change maneuvers for conflict avoidance," American Control Conference, 2002.
• 9: S. Resmerita, M. Heymann, and G. Meyer, "A framework for conflict resolution in air traffic management," in IEEE Conf. on Decision and Control, 2003, pp. 2035--40.
• 10: S. Resmerita and M. Heymann, "Conflict resolution in multi-agent systems," in IEEE Conference on Decision and Control, 2003, pp. 2537--42.
• 11: L. Pallottino, E. M. Feron, and A. Bicchi, "Conflict resolution problems for air traffic management systems solved with mixed integer programming," IEEE Transactions on Intelligent Transportation Systems, vol. 3, no. 1, pp. 3--11, 2002.
• 12: L. Pallottino, A. Bicchi, and S. Pancanti, "Safety of a decentralized scheme for free-flight ATMS using mixed integer linear programming," in American Control Conference, 2002.
• 13: Z.-H. Mao, E. Feron, and K. Bilimoria, "Stability and performance of intersecting aircraft flows under decentralized conflict avoidance rules," IEEE Transactions on Intelligent Transporation Systems, vol. 2, pp. 101--109, 2001.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Control theory

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Algorithms, Design, Experimentation, Performance, Theory

Keywords:
air traffic control, distributed control, free flight, satisficing