Hybrid Adaptive Greedy Algorithm Addressing the Multi-Robot Path Planning Problem

Authors

Keywords:

Multi-robot path planning, multi-agent systems, route planning, local search, greedy optimization

Abstract

In the past few years, path planning and scheduling became a high-impact research topic due to their real-world applications such as transportation, manufacturing and robotics. This paper focuses on the Multi-robot Path Planning (MPP) problem, which consists of planning the route for a set of robots in a given static environment. The main goal is to navigate the robots from a starting point to a destination point without colliding with other robots or static obstacles. We propose a hybrid method -- H* -- that combines adaptive route planning based on {A*} and local search algorithm to optimize routes in the context of the MPP problem. The {A*} algorithm finds the optimal solution for the route search problem and a heuristic approach is applied to scale up to the multi-agent scenario.
The overall length of determined paths and the number of robot collisions is minimized during the evaluations specific small-scale environments.
Computational experiments are conducted for multi-robot scenarios and the performance of H* is compared to several path-searching algorithms including A* variations extended for the multi-agent scenario and coevolutionary algorithms.
Experimental results demonstrate that H* outperforms the A* based heuristic approaches in terms of path length. H* shows similar performance as the coevolutionary method and performs better on smaller-scale maps.

Downloads

Download data is not yet available.

Author Biographies

Anikó Kopacz, Babeș-Bolyai University

Anik´o Kopacz is currently a PhD student at the Faculty of Mathematics and Computer Science, Babes¸-Bolyai University, Romania, under the supervision of Camelia Chira. Anik´o is a member of the Metaheuristics for Complex Systems research group. Her current research interests include multiagent systems, network analysis, machine learning, and reinforcement learning.

Enol García González, University of Oviedo

Enol Garcia holds a BSc in Software Engineering by the University of Oviedo and MSc in Artificial Inteligence by the Technical University of Madrid. Currently doing my PhD in Computer Science focused in Intelligent Systems. My main research interests are metaheuristics and optimization algorithms. Teaching at the University of Oviedo since 2021.

Camelia Chira, Babeș-Bolyai University

Camelia Chira is professor in computer science at the Faculty of Mathematics and Computer Science, Babes¸-Bolyai University (Romania) and senior researcher in Artificial Intelligence within the Research Institute on Artificial Intelligence, Virtual Reality and Robotics. Current main research interests include evolutionary algorithms, nature-inspired computing, complex networks, machine learning, computer vision and bioinformatics. Her research work has generated important scientific contributions in the field of AI and its applications to complex search and optimization problems. She participated in several international research projects with results disseminated in more than 100 publications.

José Ramón Villar Flecha, University of Oviedo

Jos´e Ram´on Villar is an Industrial Engineer in Electronics and Control (Universidad de Oviedo), and holds a Ph. D. in Computer Science (University of Le´on). Currently, he is an Full Professor with the Department of Computer Science at University of Oviedo. His research lines include i) AI applied to Bio-medical Engineering, ii) Metaheuristics and its applications to real world problems. Main figures in the last 5 years: i) JCR indexed: 22, ii) in international scientific conferences: 30, iii) research projects with public funding: 3, iv) I+D+I projects with private funding: 3. Dr. Villar is a member of the Advisory Committee for the Integrated Computer-Aided Engineering.

References

Q. Tan, M. Denojean-Mairet, H. Wang, X. Zhang, F. C. Pivot, and R. Treu, “Toward a telepresence robot empowered smart lab,” Smart Learning Environments, vol. 6, no. 1, p. 5, May 2019. [Online]. Available: https://doi.org/10.1186/s40561-019-0084-3

S. Solak, ¨O. Yakut, and E. Dogru Bolat, “Design and implementation of web-based virtual mobile robot laboratory for engineering education,” Symmetry, vol. 12, no. 6, 2020. [Online]. Available: https://doi.org/10.3390/sym12060906

D. Huang, H. Jiang, Z. Yu, C. Kang, and C. Hu, “Leader-following cluster consensus in multi-agent systems with intermittence,” International Journal of Control, Automation and Systems, vol. 16, no. 2, pp. 437–451, Apr 2018. [Online]. Available: https://doi.org/10.1007/s12555-017-0345-2

N. V. Kumar and C. S. Kumar, “Development of collision free path planning algorithm for warehouse mobile robot,” Procedia Computer Science, vol. 133, pp. 456–463, 2018, international Conference on Robotics and Smart Manufacturing (RoSMa2018). [Online]. Available: https://doi.org/10.1016/j.procs.2018.07.056

H. Shen, L. Pan, and J. Qian, “Research on large-scale additive manufacturing based on multi-robot collaboration technology,” Additive Manufacturing, vol. 30, p. 100906, 2019. [Online]. Available: https://doi.org/10.1016/j.addma.2019.100906

E. Stump and N. Michael, “Multi-robot persistent surveillance planning as a vehicle routing problem,” in 2011 IEEE International Conference on Automation Science and Engineering, 2011, pp. 569–575. [Online]. Available: https://10.1109/CASE.2011.6042503

X. Chen and B. Zhou, “A heuristics pulse algorithm with relaxation pruning strategy for resources re-initialized uav path planing,” Journal of Intelligent & Fuzzy Systems, vol. 41, pp. 3541–3553, 2021. [Online]. Available: https://doi.org/10.3233/JIFS-210901

R. Liu, J. Liang, and M. Alkhambashi, “Research on breakthrough and innovation of uav mission planning method based on cloud computing-based reinforcement learning algorithm,” Journal of Intelligent & Fuzzy Systems, vol. 37, pp. 3285–3292, 2019. [Online]. Available: https://doi.org/10.3233/JIFS-179130

Z. Bnaya and A. Felner, “Conflict-oriented windowed hierarchical cooperative a,” in 2014 IEEE International Conference on Robotics and Automation (ICRA), 2014, pp. 3743–3748. [Online]. Available: https://doi.org/10.1109/ICRA.2014.6907401

G. Wagner and H. Choset, “M*: A complete multirobot path planning algorithm with performance bounds,” in 2011 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2011, pp. 3260–3267. [Online]. Available: https://doi.org/10.1109/IROS.2011.6095022

A. Stentz and I. C. Mellon, “Optimal and efficient path planning for unknown and dynamic environments,” International Journal of Robotics and Automation, vol. 10, no. 3, pp. 89–100, 1995. [Online]. Available: https://doi.org/10.1007/978-1-4615-6325-9 11

P. Das, H. Behera, and B. Panigrahi, “A hybridization of an improved particle swarm optimization and gravitational search algorithm for multi-robot path planning,” Swarm and Evolutionary Computation, vol. 28, pp. 14–28, 2016. [Online]. Available: https://doi.org/10.1016/j.swevo.2015.10.011

P. Das, H. Behera, S. Das, H. Tripathy, B. Panigrahi, and S. Pradhan, “A hybrid improved pso-dv algorithm for multi-robot path planning in a clutter environment,” Neurocomputing, vol. 207, pp. 735–753, 2016. [Online]. Available: https://doi.org/10.1016/j.neucom.2016.05.057

E. Garc´ıa, J. R. Villar, Q. Tan, J. Sedano, and C. Chira, “An efficient multi-robot path planning solution using a* and coevolutionary algorithms,” Integrated Computer-Aided Engineering, vol. 30, pp. 41–52, 2023. [Online]. Available: https://doi.org/10.3233/ICA-220695

M. Kiadi, E. Garc´ıa, J. R. Villar, and Q. Tan, “A*-based co-evolutionary approach for multi-robot path planning with collision avoidance,” Cybernetics and Systems, vol. 0, no. 0, pp. 1–16, 2022. [Online]. Available: https://doi.org/10.1080/01969722.2022.2030009

H. Bae, G. Kim, J. Kim, D. Qian, and S. Lee, “Multi-robot path planning method using reinforcement learning,” Applied Sciences, vol. 9, no. 15, 2019. [Online]. Available: https://www.mdpi.com/2076-3417/9/15/3057

Y. Yang, L. Juntao, and P. Lingling, “Multi-robot path planning based on a deep reinforcement learning DQN algorithm,” CAAI Transactions on Intelligence Technology, vol. 5, no. 3, pp. 177–183, 2020. [Online]. Available: https://doi.org/10.1049/trit.2020.0024

Y. Wei and R. Zheng, “Multi-robot path planning for mobile sensing through deep reinforcement learning,” in IEEE INFOCOM 2021 - IEEE Conference on Computer Communications, 2021, pp. 1–10. [Online]. Available: https://doi.org/10.1109/INFOCOM42981.2021.9488669

S. Wen, Z. Wen, D. Zhang, H. Zhang, and T. Wang, “A multi-robot path-planning algorithm for autonomous navigation using meta-reinforcement learning based on transfer learning,” Applied Soft Computing, vol. 110, p. 107605, 2021. [Online]. Available: https://doi.org/10.1016/j.asoc.2021.107605

Ángel Madridano, A. Al-Kaff, D. Mart´ın, and A. de la Escalera, “Trajectory planning for multi-robot systems: Methods and applications,” Expert Systems with Applications, vol. 173, p. 114660, 2021. [Online]. Available: https://doi.org/10.1016/j.eswa.2021.114660

P. E. Hart, N. J. Nilsson, and B. Raphael, “A formal basis for the heuristic determination of minimum cost paths,” IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, pp. 100–107, 1968.

E. G. Gonz´alez, J. R. Villar, C. Chira, E. A. de la Cal, L. S´anchez, and J. Sedano, “Multi-objective optimization for multi-robot path planning on warehouse environments,” in 18th International Conference on Soft Computing Models in Industrial and Environmental Applications (SOCO 2023), ser. Lecture Notes in Networks and Systems, vol. 750, 2023, pp. 279–289. [Online]. Available: https://doi.org/10.1007/978-3-031-42536-3 27

E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik, vol. 1, pp. 269–271, 1959. [Online]. Available: https://doi.org/10.1007/BF01386390

R. Bellman, “The theory of dynamic programming,” Bulletin of the American Mathematical Society, vol. 60, pp. 503–515, 1954. [Online]. Available: https://doi.org/10.1090/S0002-9904-1954-09848-8

R. W. Floyd, “Algorithm 97: Shortest path,” Commun. ACM, vol. 5, no. 6, p. 345, jun 1962. [Online]. Available: https://doi.org/10.1145/367766.368168

S. Koenig and M. Likhachev, “Fast replanning for navigation in unknown terrain,” IEEE Transactions on Robotics, vol. 21, no. 3, pp. 354–363, 2005. [Online]. Available: https://doi.org/10.1109/TRO.2004.838026

D. Ferguson and A. Stentz, “Using interpolation to improve path planning: The field d* algorithm,” Journal of Field Robotics, vol. 23, no. 2, pp. 79–101, 2006. [Online]. Available: https://doi.org/10.1002/rob.20109

A. Stentz, “The focussed d* algorithm for real-time replanning,” in Proceedings of the 14th International Joint Conference on Artificial Intelligence - Volume 2, ser. IJCAI’95. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 1995, p. 1652–1659. [Online]. Available: https://doi.org/10.5555/1643031.1643113

S. Lin, A. Liu, J. Wang, and X. Kong, “A review of path-planning approaches for multiple mobile robots,” Machines, vol. 10, no. 9, 2022. [Online]. Available: https://doi.org/10.3390/machines10090773

Y. D. Setiawan, P. S. Pratama, S. K. Jeong, V. H. Duy, and S. B. Kim, “Experimental comparison of a* and d* lite path planning algorithms for differential drive automated guided vehicle,” in AETA2013: Recent Advances in Electrical Engineering and Related Sciences, I. Zelinka, V. H. Duy, and J. Cha, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014, pp. 555–564. [Online]. Available: https://doi.org/10.1007/978-3-642-41968-3 55

F. Gul, W. Rahiman, S. S. N. Alhady, A. Ali, I. Mir, and A. Jalil, “Meta-heuristic approach for solving multi-objective path planning for autonomous guided robot using pso–gwo optimization algorithm with evolutionary programming,” Journal of Ambient Intelligence and Humanize Computing, vol. 12, p. 7873–7890, 2021. [Online]. Available: https://doi.org/10.1007/s12652-020-02514-w

M. Nazarahari, E. Khanmirza, and S. Doostie, “Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm,” Expert Systems with Applications, vol. 115, pp. 106–120, 2019. [Online]. Available: https://doi.org/10.1016/j.eswa.2018.08.008

M. Kiadi, Q. Tan, and J. R. Villar, “Optimized path planning in reinforcement learning by backtracking,” Current Trends in Computer Sciences & Applications, vol. 1, no. 4, pp. 80–90, 2019. [Online]. Available: https://doi.org/10.32474/CTCSA.2019.01.000116

P. W. Mirowski, R. Pascanu, F. Viola, H. Soyer, A. Ballard,A. Banino, M. Denil, R. Goroshin, L. Sifre, K. Kavukcuoglu, D. Kumaran, and R. Hadsell, “Learning to navigate in complex environments,” ArXiv, vol. abs/1611.03673, 2016. [Online]. Available: https://doi.org/10.48550/arXiv.1611.03673

D. Wang, H. Deng, and Z. Pan, “Mrcdrl: Multi-robot coordination with deep reinforcement learning,” Neurocomputing, vol. 406, pp. 68–76, 2020. [Online]. Available: https://doi.org/10.1016/j.neucom.2020.04.028

Y. Mei, S. Li, C. Chen, and A. Han, “A multi-robot task allocation and path planning method for warehouse system,” in 2021 40th Chinese Control Conference (CCC), 2021, pp. 1911–1916. [Online]. Available: https://doi.org/10.23919/CCC52363.2021.9549796

G. Wagner and H. Choset, “Subdimensional expansion for multirobot path planning,” Artificial Intelligence, vol. 219, pp. 1–24, 2015. [Online]. Available: https://doi.org/10.1016/j.artint.2014.11.001

Downloads

Published

2025-08-30

How to Cite

Kopacz, A., García González, E., Chira, C., & Villar Flecha, J. R. (2025). Hybrid Adaptive Greedy Algorithm Addressing the Multi-Robot Path Planning Problem. IEEE Latin America Transactions, 23(10), 856–864. Retrieved from https://latamt.ieeer9.org/index.php/transactions/article/view/9386

Issue

Vol. 23 No. 10 (2025): Ordinary Issue

Section

Computing