Abstract
Two path planning algorithms dedicated to multiple robots driving simultaneously in a cluttered workspace are defined and compared in this paper. Each robot is assigned an initial position, a goal position and a constant reference speed, and has to drive without colliding with its teammates and the environment. Both approaches are based on an implementation of the widely known A* algorithm and belong to the family of decoupled path planning methods, since robots are considered sequentially and with a predefined priority ranking. The first algorithm is called Prioritized Planning (PP), where the path of each robot is computed sequentially while taking into account static obstacles as well as the previously-planned robot positions. The second algorithm, called Fixed-Path Coordination (FPC), follows a two-step approach: (i) obtaining A* paths of all robots taking into account static obstacles only; (ii) applying a velocity-tuning procedure so that lower-priority robots can stop and restart along their paths to let the higher-priority robots move freely. Both algorithms have been applied on a variety of test-cases through a Monte Carlo setup to evaluate and compare their performances.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Yan, Z., Jouandeau, N., Cherif, A.A.: A survey and analysis of multi-robot coordination. Int. J. Adv. Rob. Syst. 10(12), 399 (2013)
Parker, L.E.: Path planning and motion coordination in multiple mobile robot teams. Encyclopedia of Complexity and System Science, pp. 5783–5800 (2009)
Hoy, M., Matveev, A.S., Savkin, A.V.: Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey. Robotica 33(3), 463–497 (2015)
Bertrand, S., Marzat, J., Piet-Lahanier, H., Kahn, A., Rochefort, Y.: MPC strategies for cooperative guidance of autonomous vehicles. Aerospace Lab J. 8, 1–18 (2014)
LaValle, S.M.: Planning Algorithms. Cambridge University Press, Cambridge (2006)
Švestka, P., Overmars, M.H.: Coordinated path planning for multiple robots. Robot. Auton. Syst. 23(3), 125–152 (1998)
Yu, J., LaValle, S.M.: Planning optimal paths for multiple robots on graphs. In: 2013 IEEE International Conference on Robotics and Automation, pp. 3612–3617. IEEE (2013)
LaValle, S.M., Hutchinson, S.A.: Optimal motion planning for multiple robots having independent goals. IEEE Trans. Robot. Autom. 14(6), 912–925 (1998)
Van Den Berg, J.P., Overmars, M.H.: Prioritized motion planning for multiple robots. In: 2005 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 430–435. IEEE (2005)
Zheng, T., Liu, D., Wang, P.: Priority based dynamic multiple robot path planning. In: International Conference on Autonomous Robots and Agents. Massey University, New Zealand (2004)
Kala, R.: Rapidly exploring random graphs: motion planning of multiple mobile robots. Adv. Robot. 27(14), 1113–1122 (2013)
van Den Berg, J., Snoeyink, J., Lin, M.C., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. Robot. Sci. Syst. 2, 2–3 (2009)
Sánchez, G., Latombe, J.C.: On delaying collision checking in PRM planning: application to multi-robot coordination. Int. J. Robot. Res. 21(1), 5–26 (2002)
Saha, I., Ramaithitima, R., Kumar, V., Pappas, G.J., Seshia, S.A.: Implan: scalable incremental motion planning for multi-robot systems. In: 2016 ACM/IEEE 7th International Conference on Cyber-Physical Systems (ICCPS), pp. 1–10. IEEE (2016)
Gregoire, J.: Priority-based coordination of mobile robots. Ph.D. thesis, Ecole Nationale Supérieure des Mines de Paris (2014)
Čáp, M., Novák, P., Kleiner, A., Seleckỳ, M.: Prioritized planning algorithms for trajectory coordination of multiple mobile robots. IEEE Trans. Autom. Sci. Eng. 12(3), 835–849 (2015)
Siméon, T., Leroy, S., Lauumond, J.P.: Path coordination for multiple mobile robots: a resolution-complete algorithm. IEEE Trans. Robot. Autom. 18(1), 42–49 (2002)
Bae, H., Kim, G., Kim, J., Qian, D., Lee, S.: Multi-robot path planning method using reinforcement learning. Appl. Sci. 9(15) (2019)
Wen, S., Wen, Z., Zhang, D., Zhang, H., Wang, T.: A multi-robot path-planning algorithm for autonomous navigation using meta-reinforcement learning based on transfer learning. Appl. Soft Comput. 110 (2021)
Das, P.K., Jena, P.K.: Multi-robot path planning using improved particle swarm optimization algorithm through novel evolutionary operators. Appl. Soft Comput. 92 (2020)
Tang, B., Xiang, K., Pang, M., Zhanxia, Z.: Multi-robot path planning using an improved self-adaptive particle swarm optimization. Int. J. Adv. Robot. Syst. 17(5) (2020)
Li, Q., Gama, F., Ribeiro, A., Prorok, A.: Graph neural networks for decentralized multi-robot path planning. In: IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 11785–11792 (2020)
Han, S.D., Yu, J.: Effective heuristics for multi-robot path planning in warehouse environments. In: IEEE International Symposium on Multi-Robot and Multi-Agent Systems (MRS), pp. 10–12 (2019)
Acknowledgement
This work was supported by ONERA project PR PARADIS.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bouvier, B., Marzat, J. (2024). A Comparison of Two Decoupled Methods for Simultaneous Multiple Robots Path Planning. In: Bourgeois, J., et al. Distributed Autonomous Robotic Systems. DARS 2022. Springer Proceedings in Advanced Robotics, vol 28. Springer, Cham. https://doi.org/10.1007/978-3-031-51497-5_35
Download citation
DOI: https://doi.org/10.1007/978-3-031-51497-5_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-51496-8
Online ISBN: 978-3-031-51497-5
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)