Multi-Target Robot Path Planning Using Enhanced Genetic Algorithms and Probabilistic Roadmaps

Shaymaa Alzubairi; Alexander Petunin; Mohammed Majid Msallam; Hussam Lefta Alwan

doi:10.46604/peti.2025.14989

Authors

Shaymaa Alzubairi Institute of New Materials and Technologies, Ural Federal University, Ekaterinburg, Russia
Alexander Petunin Institute of New Materials and Technologies, Ural Federal University, Ekaterinburg, Russia
Mohammed Majid Msallam Control and Systems Engineering Department, University of Technology, Baghdad, Iraq
Hussam Lefta Alwan Production Engineering and Metallurgy, University of Technology, Baghdad, Iraq

DOI:

https://doi.org/10.46604/peti.2025.14989

Keywords:

path planning, genetic algorithm, probabilistic roadmap algorithm, mobile robot

Abstract

Path planning receives considerable attention over the last two decades. This study proposes a hybrid approach that combines the probabilistic roadmap with an enhanced genetic algorithm (EGA), enabling path planning for both single and multiple targets. Compared with existing genetic algorithm (GA) methods, the proposed approach offers three main advantages: (1) it employs an environment representation based on image processing and morphological operations; (2) it introduces a new strategy for creating the initial population of the GA; and (3) it incorporates a novel operator to increase the quality of the generated paths. To demonstrate the effectiveness of the probabilistic roadmap and enhanced genetic algorithm (PRMEGA), multiple simulation experiments are performed, with results compared against the GA, artificial bee colony, and particle swarm optimization. The proposed approach outperforms existing methods by 25.5%, achieving near-optimal paths for both single and multiple targets in fewer generations while also reducing computation time by 14.1%.

References

S. Lu and C. Guo, “Improving Sensing Measurements Using Laser Self-Mixing Interference in Non-Line-of-Sight Optical Communication via Systems,” HighTech and Innovation Journal, vol. 5, no. 4, pp. 1038-1054, 2024.

J. Cornejo, J. Cornejo, M. Vargas, M. Carvajal, P. Perales, G. Rodríguez, et al., “SY-MIS Project: Biomedical Design of Endo-Robotic and Laparoscopic Training System for Surgery on the Earth and Space,” Emerging Science Journal, vol. 8, no. 2, pp. 372-393, 2024.

K. Puentes, L. Morales, D. F. Pozo-Espin, and V. Moya, “Enhancing Control Systems with Neural Network-Based Intelligent Controllers,” Emerging Science Journal, vol. 8, no. 4, pp. 1243-1261, 2024.

J. E. Solanes and L. Gracia, “Mobile Robots: Trajectory Analysis, Positioning and Control,” Applied Sciences, vol. 15, no. 1, article no. 355, 2025.

J. Cui, L. Wu, X. Huang, D. Xu, C. Liu, and W. Xiao, “Multi-Strategy Adaptable Ant Colony Optimization Algorithm and Its Application in Robot Path Planning,” Knowledge-Based Systems, vol. 288, article no. 111459, 2024.

B. Lacevic and D. Osmankovic, “Improved C-Space Exploration and Path Planning for Robotic Manipulators Using Distance Information,” IEEE International Conference on Robotics and Automation, pp. 1176-1182, 2020.

Z. Wu, J. Dai, B. Jiang, and H. R. Karimi, “Robot Path Planning Based on Artificial Potential Field with Deterministic Annealing,” ISA Transactions, vol. 138, pp. 74-87, 2023.

X. Diao, W. Chi, and J. Wang, “Graph Neural Network Based Method for Robot Path Planning,” Biomimetic Intelligence and Robotics, vol. 4, no. 1, article no. 100147, 2024.

S. Lin, A. Liu, J. Wang, and X. Kong, “An Intelligence-Based Hybrid PSO-SA for Mobile Robot Path Planning in Warehouse,” Journal of Computational Science, vol. 67, article no. 101938, 2023.

R. Sarkar, D. Barman, and N. Chowdhury, “Domain Knowledge Based Genetic Algorithms for Mobile Robot Path Planning Having Single and Multiple Targets,” Journal of King Saud University - Computer and Information Sciences, vol. 34, no. 7, pp. 4269-4283, 2022.

M. N. Ab Wahab, A. Nazir, A. Khalil, W. J. Ho, M. F. Akbar, M. H. M. Noor, et al., “Improved Genetic Algorithm for Mobile Robot Path Planning in Static Environments,” Expert Systems with Applications, vol. 249, part C, article no. 123762, 2024.

H. Heng and W. Rahiman, “ACO-GA-Based Optimization to Enhance Global Path Planning for Autonomous Navigation in Grid Environments,” IEEE Transactions on Evolutionary Computation, pp. 1-15, 2025.

J. Li, Y. Hu, and S. X. Yang, “A Novel Knowledge-Based Genetic Algorithm for Robot Path Planning in Complex Environments,” IEEE Transactions on Evolutionary Computation, vol. 29, no. 2, pp. 375-389, 2025.

L. Liu, X. Wang, X. Yang, H. Liu, J. Li, and P. Wang, “Path Planning Techniques for Mobile Robots: Review and Prospect,” Expert Systems with Applications, vol. 227, article no.120254, 2023.

S. Bandi and D. Thalmann, “Space Discretization for Efficient Human Navigation,” Computer Graphics Forum, vol. 17, no. 3, pp. 195-206, 1998.

H. Mahjoubi, F. Bahrami, and C. Lucas, “Path Planning in an Environment with Static and Dynamic Obstacles Using Genetic Algorithm: A Simplified Search Space Approach,” IEEE International Conference on Evolutionary Computation, pp. 2483-2489, 2006.

S. Alarabi, C. Luo, and M. Santora, “A PRM Approach to Path Planning with Obstacle Avoidance of an Autonomous Robot,” 8th International Conference on Automation, Robotics and Applications, pp. 76-80, 2022.

Q. Li, Y. Xu, S. Bu, and J. Yang, “Smart Vehicle Path Planning Based on Modified PRM Algorithm,” Sensors, vol. 22, no. 17, article no. 6581, 2022.

Y. Hu and S. X. Yang, “A Knowledge Based Genetic Algorithm for Path Planning of a Mobile Robot,” IEEE International Conference on Robotics and Automation, pp. 4350-4355, 2004.

Y. Huang, H. Wang, L. Han, and Y. Xu, “Robot Path Planning in Narrow Passages Based on Improved PRM Method,” Intelligent Service Robotics, vol. 17, no. 3, pp. 609-620, 2024.

M. Yu, Q. Luo, H. Wang, and Y. Lai, “Electric Logistics Vehicle Path Planning Based on the Fusion of the Improved A-Star Algorithm and Dynamic Window Approach,” World Electric Vehicle Journal, vol. 14, no. 8, article no. 213, 2023.

J. Liu, M. Fu, A. Liu, W. Zhang, and B. Chen, “A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm,” IEEE Robotics and Automation Letters, vol. 8, no. 11, pp. 7695-7702, 2023.

G. Chen, Y. Du, X. Xi, K. Zhang, J. Yang, L. Xu, et al., “Improved Genetic Algorithm Based on Bi-Level Co-Evolution for Coverage Path Planning in Irregular Region,” Scientific Reports, vol. 15, no. 1, article no. 10047, 2025.

T. Feng, J. Li, H. Jiang, S. X. Yang, P. Wang, Y. Teng, et al., “The Optimal Global Path Planning of Mobile Robot Based on Improved Hybrid Adaptive Genetic Algorithm in Different Tasks and Complex Road Environments,” IEEE Access, vol. 12, pp. 18400-18415, 2024.

A. Alabbadi and A. Kanan, “Genetic Algorithm-Based Path Planning for Autonomous Mobile Robots,” IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology, pp. 177-180, 2023.

Z. Yao and Y. Xu, “An Improved Genetic Algorithm for Robot Path Planning,” Journal of Computational Methods in Sciences and Engineering, vol. 24, no. 3, pp. 1331-1340, 2024.

C. A. Murthy and N. Chowdhury, “In Search of Optimal Clusters Using Genetic Algorithms,” Pattern Recognition Letters, vol. 17, no. 8, pp. 825-832, 1996.

H. Qu, K. Xing, and T. Alexander, “An Improved Genetic Algorithm with Co-Evolutionary Strategy for Global Path Planning of Multiple Mobile Robots,” Neurocomputing, vol. 120, pp. 509-517, 2013.

D. Agarwal and P. S. Bharti, “Implementing Modified Swarm Intelligence Algorithm Based on Slime Moulds for Path Planning and Obstacle Avoidance Problem in Mobile Robots,” Applied Soft Computing, vol. 107, article no. 107372, 2021.

P. B. Fernandes, R. C. L. Oliveira, and J. V. Fonseca Neto, “Trajectory Planning of Autonomous Mobile Robots Applying a Particle Swarm Optimization Algorithm with Peaks of Diversity,” Applied Soft Computing, vol. 116, article no. 108108, 2022.