ROBOT PATH PLANNING FOR MULTI-TARGETS BASED ON A HYBRID OF PRM AND AGA ALGORITHM
Abstract
Optimal path planning problems for mobile robots have been particularly actively studied in the last decade. The goal is to find an optimal or near-optimal path from a starting terminal to one or more terminals in an environment with various obstacles, in terms of minimizing robot travel time, distance traveled, energy costs, or other optimization criteria. In this paper, we propose a hybrid algorithm combining a probabilistic roadmap algorithm (PRM) and an adapted genetic algorithm (AGA) to solve a path planning problem with one or more independent objectives. The robot's path length is used as an optimization criterion. Compared with existing approaches used in genetic algorithms (GAs), the proposed approach has two main differences. The first is the environment representation, which relies on image processing and morphological operations, which has proven to be a more efficient method than methods based on cellular representation. In particular, the proposed method eliminates the need to find a trade-off between accuracy and speed of processing geometric information. The second is a new tactic for creating an initial population of the genetic algorithm to accelerate convergence in the presence of multiple objectives. By leveraging the capabilities of a probabilistic roadmap algorithm. Another key feature of the algorithm's implementation is the appropriate (for the domain under study) selection of numerical parameters that determine the characteristics of all stages of the evolutionary strategy, including the time required to complete each stage. This applies in particular to the parameters of the mutation operator and the elite strategy. The proposed algorithm was tested on two real-world maps with varying levels of complexity. Its effectiveness was confirmed by comparison with path planning results for test maps obtained using a standard genetic algorithm and an ant colony optimization algorithm. Experimental results demonstrate that the hybrid algorithm expands the capabilities of a conventional genetic algorithm and finds rational path variants with the best objective function value for single and multiple objectives in significantly less time than other traditional GA implementations.
References
1. Pshikhopov V., Medvedev M., Kostjukov V., Houssein F., and Kadhim A. Trajectory planning algorithms in two-dimensional environment with obstacles, Informatika i avtomatizatsiya [Computer Science and Automation], 2022, Vol. 21, No. 3, pp. 459-492.
2. Cui J., Wu L., Huang X., Xu D., Liu C., and Xiao W. Multi-strategy adaptable ant colony optimization algorithm and its application in robot path planning, Knowledge-Based Syst., 2024, Vol. 288,
pp. 111459.
3. Lacevic B. and Osmankovic D. Improved C-space exploration and path planning for robotic manipulators using distance information, in 2020 IEEE International Conference on Robotics and Automation (ICRA), IEEE, 2020, pp. 1176-1182.
4. Fan X., GuoY., Liu H., Wei B., and Lyu W. Improved artificial potential field method applied for AUV path planning, Math. Probl. Eng., 2020, Vol. 2020, No. 1, pp. 6523158.
5. Diao X., Chi W., and Wang J. Graph Neural Network Based Method for Robot Path Planning, Biomimetic Intelligence and Robotics, 2024, Vol. 4, No. 1, article no. 100147.
6. Tsygankov V.A., SHabalina O.A., Kataev A.V. Issledovanie vozdeystviya razmera populyatsii na by-strodeystvie geneticheskogo algoritma [Study of the impact of population size on the performance of a genetic algorithm], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2024, No. 3.
7. Gladkov L.A., Kravchenko Yu.A., Kureychik V.V., Rodzin S.I. Intellektual'nye sistemy: modeli i metody metaevristicheskoy optimizatsii: monografiya [Intelligent systems: models and methods of metaheuristic optimization: monograph]. Cheboksary: Sreda, 2024, 228 p.
8. Kravchenko D.Yu., Kulieva N.V., Novikova Yu.S., Anchekov M.I. Strukturizatsiya informatsii na osnove kombinatsii geneticheskogo, roevogo i obez'yan'ego algoritmov [Information structuring based on a combination of genetic, swarm and monkey algorithm], Izvestiya KBNTS RAN [Bulletin of the KBSC RAS], 2019, No. 5 (91). Available at: https://cyberleninka.ru/article/n/strukturizatsiya-informatsii-na-osnove-kombinatsii-geneticheskogo-roevogo-i-obezyaniego-algoritmov (accessed 26 October 2025).
9. Liu L., Wang X., Yang X., Liu H., Li J., and Wang P. Path planning techniques for mobile robots: Review and prospect, Expert Syst. Appl., 2023, Vol. 227, pp. 120254.
10. Ab Wahab M.N., Nazir A., Khalil A., Ho W.J., Akbar M.F., M. Noor M.H.M., et al. Improved Genetic Algorithm for Mobile Robot Path Planning in Static Environments, Expert Systems with Applications, 2024, Vol. 249, Part C, article no. 123762.
11. Li J., Hu Y., and Yang S.X. A Novel Knowledge-Based Genetic Algorithm for Robot Path Planning in Complex Environments, IEEE Transactions on Evolutionary Computation, 2025, Vol. 29, No. 2,
pp. 375-389.
12. Heng H. and Rahiman W. ACO-GA-Based Optimization to Enhance Global Path Planning for Autonomous Navigation in Grid Environments, IEEE Transactions on Evolutionary Computation, 2025, pp. 1-15.
13. Sarkar R., Barman D., and Chowdhury N. Domain knowledge based genetic algorithms for mobile robot path planning having single and multiple targets, J. King Saud Univ. Comput. Inf. Sci., 2022, Vol. 34, No. 7, pp. 4269-4283. doi: 10.1016/j.jksuci.2020.10.010.
14. Bandi S. and Thalmann D. Space discretization for efficient human navigation, in Computer Graphics Forum, Wiley Online Library, 1998, pp. 195-206.
15. Mahjoubi H., Bahrami F., and Lucas C. Path planning in an environment with static and dynamic obstacles using genetic algorithm: a simplified search space approach, in 2006 IEEE International Conference on Evolutionary Computation, IEEE, 2006, pp. 2483-2489.
16. Van Truc T. and Korikov A.M. Path planning for mobile objects based on modification of the probabilistic roadmap method, Vestn. Tomsk. Gos. Univ. Upr. Vychislitel’naya Tekhnika i Inform., 2024, No. 67, pp. 106-115. doi: 10.17223/19988605/67/11.
17. Li Q., Xu Y., Bu S., and Yang J. Smart vehicle path planning based on modified PRM algorithm, Sensors, 2022, Vol. 22, No. 17, pp. 6581.
18. Hu Y. and Yang S.X. A knowledge based genetic algorithm for path planning of a mobile robot, in IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004, IEEE, 2004, pp. 4350-4355.
19. Azubairi S., Petunin A., Alwan H.L., Msallam M.M., and Humaidi A. Dynamic Processing 2D Maps Method for Robot’s Trajectory Planning, Proc. Eng. Technol. Innov., 2025, Vol. 30, pp. 79-89.
20. Huang Y., Wang H., Han L., and Xu Y. Robot path planning in narrow passages based on improved PRM method, Intell. Serv. Robot., 2024, pp. 1-12.
21. Liu J., Fu M., Liu A., Zhang W., and Chen B. A Homotopy Invariant Based on Convex Dissection Topology and a Distance Optimal Path Planning Algorithm, IEEE Robot. Autom. Lett., 2023.
22. Sarkar R., Barman D., and Chowdhury N. A cooperative co-evolutionary genetic algorithm for multi-robot path planning having multiple targets, in Computational Intelligence in Pattern Recognition: Proceedings of CIPR 2019. Springer, 2020, pp. 727-740.
23. Tuncer A. and Yildirim M. Dynamic path planning of mobile robots with improved genetic algorithm, Comput. Electr. Eng., 2012, Vol. 38, No. 6, pp. 1564-1572.
24. Alabbadi A. and Kanan A. Genetic Algorithm-Based Path Planning for Autonomous Mobile Robots, in 2023 IEEE Jordan International Joint Conference on Electrical Engineering and Information Technology (JEEIT), IEEE, 2023, pp. 177-180.
25. Yao Z. and Xu Y. An improved genetic algorithm for robot path planning, J. Comput. Methods Sci. Eng., 2024, Vol. 24, No. 3, pp. 1331-1340.
26. Murthy C.A. and Chowdhury N. In search of optimal clusters using genetic algorithms, Pattern Recognit. Lett., 1996, Vol. 17, No. 8, pp. 825-832.
27. Qu H., Xing K., and Alexander T. An improved genetic algorithm with co-evolutionary strategy for global path planning of multiple mobile robots, Neurocomputing, 2013, Vol. 120, pp. 509-517.
doi: 10.1016/j.neucom.2013.04.020.
28. Dorigo M., Maniezzo V., and Colorni A. Ant system: optimization by a colony of cooperating agents, IEEE Trans. Syst. man, Cybern., 1996, Part b, Vol. 26, No. 1, pp. 29-41.
