Decentralized algorithms for collision avoidance in airspace

ABSTRACT

The paper proposes decentralized deconfliction algorithms deployed on multiple autonomous aerial vehicles in freeflight operations. The paper provides two separate algorithms for collision avoidance - one based on the iterative peer-to-peer negotiation solving a singular collision and second based on multi-party negotiation about a cluster of collisions. The presented decentralized algorithms allow the vehicles operating in the same area to utilize the given airspace more efficiently. The algorithms have been developed and tested on a multi-agent prototype and the properties of both algorithms are discussed on a set of large scale experiments.

REFERENCES

• 1: DOD. Unmanned aircraft systems roadmap 2005--2030, 2005.
• 2: 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]
• 3: J. Krozel, M. Peters, K. D. Bilimoria, C. Lee, and J. S. Mitchel. System performance characteristics of centralized and decentralized air traffic separation strategies. In 4th USA/Europe Air Traffic Management R & D Seminar, Stanta Fe, NM, December 2001.
• 4: M. Naor. Bit commitment using pseudorandomness. Journal of Cryptology: the journal of the International Association for Cryptologic Research, 4(2):151--158, 1991.
• 5: Simon Parsons , Michael Wooldridge, Game Theory and Decision Theory in Multi-Agent Systems, Autonomous Agents and Multi-Agent Systems, v.5 n.3, p.243-254, September 2002 [doi>10.1023/A:1015575522401]
• 6: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. The MIT Press, Cambridge, Massachusetts, 1994.
• 7: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 8: R. Schulz, D. Shaner, and Y. Zhao. Free-flight concept. In Proceedings of the AiAA Guidance, Navigation and Control Conference, pages 999--903, New Orelans, LA, 1997.
• 9: D. Šišlák, P. Volf, A. Komenda, J. Samek, and M. Pěchouček. Agent-based multi-layer collision avoidance to unmanned aerial vehicles. In Proceedings of International Conference on Integration of Knowledge Intensive Multi-Agent Systems (KIMAS '07): Modeling, Evolution and Engineering, 2007.
• 10: J. P. Wangermann and R. F. Stengel. Optimization and coordination of multiagent systems using principled negotiation. Journal of Guidance, Control, and Dynamics, 22(1):43--50, 1999.
• 11: S. Wollkind, J. Valasek, and T. R. Ioerger. Automated conflict resolution for air traffic management using cooperative multiagent negotiation. In Proc. of the American Inst. of Aeronautics and Astronautics Conference on Guidance, Navigation, and Control, Providence, RI, 2004.
• 12: Michael Woolridge , Michael J. Wooldridge, Introduction to Multiagent Systems, John Wiley & Sons, Inc., New York, NY, 2001
• 13: G. Zlotkin and J. S. Rosenschein. Negotiation and task sharing among autonomous agents in cooperative domains. In N. S. Sridharan, editor, Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, pages 912--917, San Mateo, CA, 1989. Morgan Kaufmann.

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.6 SIMULATION AND MODELING

General Terms:
Algorithms, Performance

Keywords:
agent-based collision avoidance, autonomous aircrafts, distributed algorithm