Abstract
The work contained in this paper concerns a novel approach to the n-vehicle collision avoidance problem. The vehicle model used here allows for three-dimensional movement and represents a wide range of vehicles. The algorithm works in conjunction with any desired controller to guarantee all vehicles remain free of collisions while attempting to follow their desired control. This algorithm is reactive and distributed, making it well suited for real time applications, and explicitly accounts for actuation limits. A robustness analysis is presented which provides a means to account for delays and unmodeled dynamics. Robustness to an adversarial vehicle is also presented. Results are demonstrated in simulation.
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
Carbone, C., Ciniglio, U., Corraro, F., & Luongo, L. (2006). A novel 3D geometric algorithm for aircraft autonomous collision avoidance. In Proc. IEEE conference on decision and control.
Chakravarthy, A., & Ghose, D. (1998). Obstacle avoidance in a dynamic environment: A collision cone approach. IEEE Transactions on Systems, Man, and Cybernetics, 28(5), 562–574.
Eby, M., & Kelly, W. (1999). Free flight separation assurance using distributed algorithms. In Proc. IEEE aerospace conference (pp. 429–441).
Eurocontrol (2007). Eurocontrol specifications for the use of military unmanned aerial vehicles as operational air traffic outside segregated airspace (Version 1.0, Doc No. EUROCONTROL-SPEC-0102).
Fasano, G., Accardo, D., & Moccia, A. (2008). Multi-sensor-based fully autonomous non-cooperative collision avoidance system for unmanned air vehicles. Journal of Aerospace Computing, Information, and Communication, 5, 338–360.
Fiorini, P., & Shiller, Z. (1998). Motion planning in dynamic environments using velocity obstacles. The International Journal of Robotics Research, 17(7), 760–772.
Frazzoli, E., Mao, Z., Oh, J., & Feron, E. (2001). Resolution of conflicts involving many aircraft via semidefinite programming. Journal of Guidance, Control, and Dynamics, 24(1), 79–86.
Gazi, V. (2006). Swarm aggregations using artificial potentials and sliding-mode control. IEEE Transactions on Robotics, 21, 1208–1214.
Guy, S. J., Chhugani, J., Kim, C., Satish, N., Lin, M., Manocha, D., & Dubey, P. (2009). Clearpath: Highly parallel collision avoidance for multi-agent simulation. In Proc. ACM SIGGRAPH Eurographics symposium on computer animation.
Hill, J. C., Archibald, J. K., Stirling, W., & Frost, R. L. (2005). A multi-agent system architecture for distributed air traffic control. In Proc. AIAA guidance, navigation and control conference.
Hoffmann, G., & Tomlin, C. (2008). Decentralized cooperative collision avoidance for acceleration constrained vehicles. In Proc. IEEE conference on decision and control.
Hwang, I., & Tomlin, C. (2002). Protocol-based conflict resolution for air traffic control (Tech. Rep. SUDAAR-762). Stanford University.
Kuchar, J., & Yang, L. (2000). A review of conflict detection and resolution modeling methods. IEEE Transactions on Intelligent Transportation Systems, 1(4), 179–189.
Lalish, E. (2009). Decentralized reactive collision avoidance. PhD Thesis, University of Washington.
Lalish, E., & Morgansen, K. A. (2008). Decentralized reactive collision avoidance for multivehicle systems. In Proc. IEEE conference on decision and control.
Lalish, E., Morgansen, K. A., & Tsukamaki, T. (2006). Formation tracking control using virtual structures and deconfliction. In Proc. IEEE conference on decision and control.
Lalish, E., Morgansen, K. A., & Tsukamaki, T. (2008). Decentralized reactive collision avoidance for multiple unicycle-type vehicles. In Proc. IEEE American control conference.
Leitmann, G., & Skowronski, J. (1977). Avoidance control. Journal of Optimization Theory and Applications, 23, 581–591.
Mastellone, S., Stipanovic, D. M., Graunke, C. R., Intlekofer, K. A., & Spong, M. W. (2008). Formation control and collision avoidance for multi-agent non-holonomic systems: Theory and experiments. The International Journal of Robotics Research, 27(1), 107–126.
Melander, A. (2010). Quadrotor implementation of the distributed reactive collision avoidance algorithm. Master’s Thesis, University of Washington.
Melander, A. P., Powel, N. D., Lalish, E., Morgansen, K. A., Jang, J. S., & Vian, J. (2010). Implementation of deconfliction in multivehicle autonomous systems. In 27th international congress of the aeronautical sciences.
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.
Pallottino, L., Scordio, V. G., Bicchi, A., & Frazzoli, E. (2007). Decentralized cooperative policy for conflict resolution in multivehicle systems. IEEE Transactions on Robotics, 23(6), 1170–1183.
Pongpunwattana, A., & Rysdyk, R. (2004). Real-time planning for multiple autonomous vehicles in dynamic uncertain environments. Journal of Aerospace Computing, Information, and Communication, 1, 580–604.
Reif, J. H., & Wang, H. (1999). Social potential fields: A distributed behavioral control for autonomous robots. Robotics and Autonomous Systems, 27(3), 171–194.
Roussos, G. P., Dimarogonas, D. V., & Kyriakopoulos, K. J. (2008). 3D navigation and collision avoidance for a non-holonomic vehicle. In Proc. IEEE American control conference.
Skjetne, R., Moi, S., & Fossen, T. I. (2002). Nonlinear formation control of marine craft. In Proc. IEEE conference on decision and control.
Skogestad, S., & Postlethwaite, I. (2005). Multivariable feedback control. New York: Wiley.
Stanley, A. (2005). Flight path deconfliction of autonomous uavs. In Infotech@Aerospace.
Wang, S., & Schaub, H. (2008). Spacecraft collision avoidance using coulomb forces with separation distance and rate feedback. Journal of Guidance, Control, and Dynamics, 31, 740–750.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lalish, E., Morgansen, K.A. Distributed reactive collision avoidance. Auton Robot 32, 207–226 (2012). https://doi.org/10.1007/s10514-011-9267-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-011-9267-7