Distributed swarm collision avoidance based on angular calculations
Abstract
Collision avoidance is one of the most important topics in the robotics field. In this problem, the goal is to move the robots from initial locations to target locations such that they follow the shortest non-colliding paths in the shortest time and with the least amount of energy. Robot navigation among pedestrians is an example application of this problem which is the focus of this paper. This paper presents a distributed and real-time algorithm for solving collision avoidance problems in dense and complex 2D and 3D environments. This algorithm uses angular calculations to select the optimal direction for the movement of each robot and it has been shown that these separate calculations lead to a form of cooperative behavior among agents. We evaluated the proposed approach on various simulation and experimental scenarios and compared the results with ORCA one of the most important algorithms in this field. The results show that the proposed approach is at least 25% faster than ORCA while is also more reliable. The proposed method is shown to enable fully autonomous navigation of a swarm of Crazyflies.
References
[1]
Abe, Y., & Yoshiki, M. (2001). Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. In Proceedings 2001 IEEE/RSJ international conference on intelligent robots and systems. Expanding the societal role of robotics in the the next millennium (Cat. No. 01CH37180) (Vol. 3). IEEE.
[2]
Alonso-Mora J, Breitenmoser A, Rufli M, Siegwart R, and Beardsley PA Image and animation display with multiple mobile robots The International Journal of Robotics Research 2012 31 6 753-773
[3]
Augugliaro, F., Schoellig, A. P., & D’Andrea, R. (2012). Generation of collision-free trajectories for a quadrocopter fleet: A sequential convex programming approach. In 2012 IEEE/RSJ international conference on intelligent robots and systems (pp. 1917–1922). IEEE.
[4]
Bajcsy, A., et al. (2019). A scalable framework for real-time multi-robot, multi-human collision avoidance. In 2019 international conference on robotics and automation (ICRA). IEEE.
[5]
Chen J, Gauci M, Li W, Kolling A, and Groß R Occlusion-based cooperative transport with a swarm of miniature mobile robots IEEE Transactions on Robotics 2015 31 2 307-321
[6]
Fiorini P and Shiller Z Motion planning in dynamic environments using velocity obstacles The International Journal of Robotics Research 1998 17 7 760-772
[7]
Fulgenzi, C., Spalanzani, A., & Laugier, C. (2007). Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. In Proceedings 2007 IEEE international conference on robotics and automation. IEEE.
[8]
Giernacki, W., et al. (2017). Crazyflie 2.0 quadrotor as a platform for research and education in robotics and control engineering. In 2017 22nd international conference on methods and models in automation and robotics (MMAR). IEEE.
[9]
Guy, S. J., et al. (2009). Clearpath: Highly parallel collision avoidance for multi-agent simulation. In Proceedings of the 2009 ACM SIGGRAPH/Eurographics symposium on computer animation.
[10]
Kuhn HW The Hungarian method for the assignment problem Naval Research Logistics Quarterly 1955 2 1–2 83-97
[11]
Large, F., et al. (2002). Using non-linear velocity obstacles to plan motions in a dynamic environment. In 7th international conference on control, automation, robotics and vision, 2002. ICARCV 2002 (Vol. 2). IEEE.
[12]
Liang, J., et al. (2004). Realtime collision avoidance for mobile robots in dense crowds using implicit multi-sensor fusion and deep reinforcement learning. arXiv e-prints (2020): arXiv.
[13]
Long, P., et al. (2018). Towards optimally decentralized multi-robot collision avoidance via deep reinforcement learning. In 2018 IEEE international conference on robotics and automation (ICRA). IEEE.
[14]
Luis CE and Schoellig AP Trajectory generation for multiagent point-to-point transitions via distributed model predictive control IEEE Robotics and Automation Letters 2019 4 2 375-382
[15]
Pamosoaji AK, Piao M, and Hong K-S Pso-based minimum-time motion planning for multiple vehicles under acceleration and velocity limitations International Journal of Control, Automation and Systems 2019 17 10 2610-2623
[16]
Rubenstein, M., Cabrera, A., Werfel, J., Habibi, G., McLurkin, J., & Nagpal, R. (2013). Collective transport of complex objects by simple robots: Theory and experiments. In Proceedings of the 2013 international conference on Autonomous agents and multi-agent systems (pp. 47–54).
[17]
RVO2 Library: Reciprocal Collision Avoidance for Real-Time Multi-Agent Simulation. (2016). [Online]. https://gamma.cs.unc.edu/RVO2/.
[18]
Schouwenaars, T., De Moor, B., Feron, E., & How, J. (2001). Mixed integer programming for multi-vehicle path planning. In 2001 European control conference (ECC) (pp. 2603–2608). IEEE.
[19]
Semnani, S. H., de Ruiter, A. H. J., & Liu, H. H. (2020). Force-based algorithm for motion planning of large agent. IEEE Transactions on Cybernetics.
[20]
Semnani SH and Basir OA Semi-flocking algorithm for motion control of mobile sensors in large-scale surveillance systems IEEE Transactions on Cybernetics 2015 45 1 129-137
[21]
Siegwart R, Nourbakhsh IR, and Scaramuzza D Introduction to autonomous mobile robots 2011 Cambridge MIT Press
[22]
Singh Y et al. A novel double layered hybrid multi-robot framework for guidance and navigation of unmanned surface vehicles in a practical maritime environment Journal of Marine science and Engineering 2020 8 9 624
[23]
Snape, J., et al. (2009). Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles. In 2009 IEEE/RSJ international conference on intelligent robots and systems. IEEE.
[24]
Van Den Berg, J., Guy, S. J., Lin, M., & Manocha, D. (2011). Reciprocal n-body collision avoidance. In Robotics research (pp. 3–19). Springer.
[25]
Van den Berg, J., Lin, M., & Manocha, D. (2008). Reciprocal velocity obstacles for real-time multi-gent navigation. In 2008 IEEE international conference on robotics and automation (pp. 1928–1935). IEEE.
[26]
Wilkie, D., Van Den Berg, J., & Manocha, D. (2009). Generalized velocity obstacles. In 2009 IEEE/RSJ international conference on intelligent robots and systems. IEEE.
[27]
Wu X, Wang S, and Xing M Observer-based leader-following formation control for multi-robot with obstacle avoidance IEEE Access 2018 7 14791-14798
[28]
Yasin, J., et al. (2021). Swarm formation morphing for congestion-aware collision avoidance (Vol. 7, No. 8). Elsevier, Heliyon.
[29]
Yasin JN et al. Energy-efficient navigation of an autonomous swarm with adaptive consciousness Remote Sensing 2021 13 6 1059
[30]
Zhou D, Wang Z, Bandyopadhyay S, and Schwager M Fast, on-line collision avoidance for dynamic vehicles using buffered Voronoi cells IEEE Robotics and Automation Letters 2017 2 2 1047-1054
Recommendations
Decentralized probabilistic multi-robot collision avoidance using buffered uncertainty-aware Voronoi cells
AbstractIn this paper, we present a decentralized and communication-free collision avoidance approach for multi-robot systems that accounts for both robot localization and sensing uncertainties. The approach relies on the computation of an uncertainty-...
Multi Robot Collision Avoidance with Continuous Curvature Manoeuvres
AIR '13: Proceedings of Conference on Advances In RoboticsIn this paper, we address the problem of reactive collision avoidance among multiple robots. However we impose the constraint of continuous curvature on the collision avoidance manoeuvre which adds to the complexity of the problem but is necessary for ...
Formation Maintenance and Collision Avoidance in a Swarm of Drones
ISCSIC 2019: Proceedings of the 2019 3rd International Symposium on Computer Science and Intelligent ControlDistributed formation control and obstacle avoidance are two important challenges in autonomous navigation of a swarm of drones and can negatively affect each other due to possible competition that arises between them. In such a platform, a multi-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2023. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Kluwer Academic Publishers
United States
Publication History
Published: 22 February 2023
Accepted: 01 December 2022
Received: 05 February 2022
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025