Volume 23, Issue 3 (March 2023)
Modares Mechanical Engineering 2023, 23(3): 161-172 |
Back to browse issues page
Download citation:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
BibTeX | RIS | EndNote | Medlars | ProCite | Reference Manager | RefWorks
Send citation to:
Khanmirza E, Haghbeigi M, Farzan M. A New Incremental Search Method for Multi-robot Path Planning. Modares Mechanical Engineering 2023; 23 (3) :161-172
URL: http://mme.modares.ac.ir/article-15-63177-en.html
URL: http://mme.modares.ac.ir/article-15-63177-en.html
1- Iran University of Science and Technology , khanmirza@iust.ac.ir
2- Iran University of Science and Technology
2- Iran University of Science and Technology
Abstract: (1387 Views)
Multi-robot path planning problem involves some challenges. One of them is the exponential increase in the size of the search space as a result of increasing the number of robots in the operating environment. Therefore, there is a need for algorithms with high computational performance to plan optimal and collision-free paths in a limited time. In this article, a centralized path planning algorithm is presented. The algorithm is a heuristic incremental search, in which the D* Lite algorithm has been adapted for the multi-robot case. The concept of occupancy time has been embedded into the environment model to avoid path interference. A centralized function has been designed to update the environment model and robot data. To evaluate the method, two groups of simulations of static and dynamic types were carried out. The static simulations focused on studying the effect of algorithm parameters, and it was shown that the algorithm can plan paths for up to 40 robots in an environment having 55 percent free space. The dynamic simulations were carried out in Gazebo, a real-time and dynamic physical simulator. The results were compared to a baseline method based on potential fields. The number of robots was increased to 14, and it was demonstrated that for 9 robots and more, the potential field approach either fails or has a rapid increase in computation time, while the proposed method can find feasible solutions in a limited time.
Article Type: Original Research |
Subject:
Robotic
Received: 2022/07/27 | Accepted: 2022/11/27 | Published: 2023/03/1
Received: 2022/07/27 | Accepted: 2022/11/27 | Published: 2023/03/1
References
1. Khanmirza E, Haghbeigi M, Nazarahari M, Doostie S. A comparative study of deterministic and probabilistic mobile robot path planning algorithms. In: 2017 5th RSI international conference on robotics and mechatronics (ICRoM). 2017. p. 534-9. [DOI:10.1109/ICRoM.2017.8466197]
2. Gasparetto A, Boscariol P, Lanzutti A, Vidoni R. Path Planning and Trajectory Planning Algorithms: A General Overview. In: Carbone G, Gomez-Bravo F, editors. Motion and Operation Planning of Robotic Systems: Background and Practical Approaches [Internet]. Cham: Springer International Publishing; 2015 [cited 2021 Oct 25]. p. 3-27. (Mechanisms and Machine Science). Available from: [DOI:10.1007/978-3-319-14705-5_1]
3. Hwang YK, Ahuja N, others. A potential field approach to path planning. IEEE transactions on robotics and automation. 1992;8(1):23-32. [DOI:10.1109/70.127236]
4. Barraquand J, Langlois B, Latombe JC. Numerical potential field techniques for robot path planning. IEEE transactions on systems, man, and cybernetics. 1992;22(2):224-41. [DOI:10.1109/21.148426]
5. Bhattacharya P, Gavrilova ML. Roadmap-based path planning - using the voronoi diagram for a clearance-based shortest path. IEEE Robotics & Automation Magazine. 2008;15(2):58-66. [DOI:10.1109/MRA.2008.921540]
6. Barbehenn M. A note on the complexity of Dijkstra's algorithm for graphs with weighted vertices. IEEE Transactions on Computers. 1998 Feb;47(2):263-. [DOI:10.1109/12.663776]
7. Delling D, Sanders P, Schultes D, Wagner D. Engineering Route Planning Algorithms. In: Lerner J, Wagner D, Zweig KA, editors. Algorithmics of Large and Complex Networks: Design, Analysis, and Simulation [Internet]. Berlin, Heidelberg: Springer; 2009 [cited 2021 Oct 25]. p. 117-39. (Lecture Notes in Computer Science). Available from: [DOI:10.1007/978-3-642-02094-0_7]
8. Koenig S, Likhachev M. Incremental A*. In: Proceedings of the 14th International Conference on Neural Information Processing Systems: Natural and Synthetic. Cambridge, MA, USA: MIT Press; 2001. p. 1539-46. (NIPS'01).
9. Koenig S, Likhachev M. D*lite. In: Eighteenth national conference on Artificial intelligence. USA: American Association for Artificial Intelligence; 2002. p. 476-83.
10. Koenig S, Likhachev M. Fast replanning for navigation in unknown terrain. IEEE Transactions on Robotics. 2005 Jun;21(3):354-63. [DOI:10.1109/TRO.2004.838026]
11. LaValle SM. Planning algorithms. Cambridge university press; 2006. [DOI:10.1017/CBO9780511546877]
12. Zagradjanin N, Pamucar D, Jovanovic K. Cloud-based multi-robot path planning in complex and crowded environment with multi-criteria decision making using full consistency method. Symmetry. 2019;11(10):1241. [DOI:10.3390/sym11101241]
13. Wagner G, Choset H. Subdimensional expansion for multirobot path planning. Artificial intelligence. 2015;219:1-24. [DOI:10.1016/j.artint.2014.11.001]
14. Rathi A, Vadali M, others. Dynamic prioritization for conflict-free path planning of multi-robot systems. arXiv preprint arXiv:210101978. 2021;
15. Tang B, Xiang K, Pang M, Zhanxia Z. Multi-robot path planning using an improved self-adaptive particle swarm optimization. International Journal of Advanced Robotic Systems. 2020;17(5):1729881420936154. [DOI:10.1177/1729881420936154]
16. Matoui F, Boussaid B, Metoui B, Abdelkrim MN. Contribution to the path planning of a multi-robot system: centralized architecture. Intelligent Service Robotics. 2019;13(1):147-58. [DOI:10.1007/s11370-019-00302-w]
17. Standley T. Finding Optimal Solutions to Cooperative Pathfinding Problems. Proceedings of the AAAI Conference on Artificial Intelligence. 2010 Jul 3;24(1):173-8. [DOI:10.1609/aaai.v24i1.7564]
18. Felner A, Goldenberg M, Sharon G, Stern R, Beja T, Sturtevant N, et al. Partial-expansion A* with selective node generation. Proceedings of the AAAI Conference on Artificial Intelligence. 2012 Sep;26(1):471-7. [DOI:10.1609/aaai.v26i1.8137]
19. Yu J, LaValle SM. Planning Optimal Paths for Multiple Robots on Graphs [Internet]. arXiv; 2013 Jan [cited 2022 May 21]. Report No.: arXiv:1204.3830. Available from: http://arxiv.org/abs/1204.3830
20. Wagner G, Choset H. M*: A complete multirobot path planning algorithm with performance bounds. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. p. 3260-7. [DOI:10.1109/IROS.2011.6095022]
21. Ferner C, Wagner G, Choset H. ODrM* optimal multirobot path planning in low dimensional search spaces. In: 2013 IEEE international conference on robotics and automation. 2013. p. 3854-9. [DOI:10.1109/ICRA.2013.6631119]
22. Sharon G, Stern R, Goldenberg M, Felner A. The increasing cost tree search for optimal multi-agent pathfinding. Artificial Intelligence. 2013 Feb 1;195:470-95. [DOI:10.1016/j.artint.2012.11.006]
23. Sharon G, Stern R, Felner A, Sturtevant NR. Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence. 2015 Feb 1;219:40-66. [DOI:10.1016/j.artint.2014.11.006]
24. Luna R, Bekris KE. Efficient and complete centralized multi-robot path planning. In: 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2011. p. 3268-75. [DOI:10.1109/IROS.2011.6095085]
25. Wilde BD, Mors A, Witteveen C. Push and rotate: cooperative multi-agent path planning. In: AAMAS. 2013. [DOI:10.1613/jair.4447]
26. Regele R, Levi P. Cooperative Multi-Robot Path Planning by Heuristic Priority Adjustment. In: 2006 IEEE/RSJ International Conference on Intelligent Robots and Systems. 2006. p. 5954-9. [DOI:10.1109/IROS.2006.282480]
27. Maw AA, Tyan M, Nguyen TA, Lee JW. iADA*-RL: Anytime graph-based path planning with deep reinforcement learning for an autonomous UAV. Applied Sciences [Internet]. 2021;11(9). Available from: https://www.mdpi.com/2076-3417/11/9/3948 [DOI:10.3390/app11093948]
28. Khorshid MM, Holte RC, Sturtevant NR. A polynomial-time algorithm for non-optimal multi-agent pathfinding. In: Fourth annual symposium on combinatorial search. 2011.
29. Matoui F, Boussaid B, Abdelkrim MN. Distributed path planning of a multi-robot system based on the neighborhood artificial potential field approach. Simulation. 2019;95(7):637-57. [DOI:10.1177/0037549718785440]
Send email to the article author
| Rights and permissions | |
 |
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License. |