ПЛАНИРОВАНИЕ ПУТИ РОБОТА ДЛЯ НЕСКОЛЬКИХ ЦЕЛЕЙ НА ОСНОВЕ ГИБРИДНОГО АЛГОРИТМА PRM И AGA
Аннотация
Задачи планирования оптимального пути мобильных роботов особенно активно исследуются в последнее десятилетие. Цель состоит в том, чтобы найти оптимальный или близкий к оптимальному путь от начального терминала до одного или нескольких терминалов в среде с различными препятствиями. С точки зрения минимизации времени перемещения роботов, пройденного расстояния, энергетических затрат или других оптимизационных критериев. В данной работе предлагается гибридный алгоритм, сочетающий алгоритм вероятностной дорожной карты (PRM) и адаптированный генетический алгоритм (AGA) для решения задачи планирования пути с одной или несколькими независимыми целями. В качестве оптимизационного критерия используется длина пути робота. По сравнению с существующими подходами, используемыми в генетических алгоритмах (GA), предлагаемый подход имеет два основных различия. Первое – это представление среды, которое опирается на обработку изображений и морфологические операции, что оказалось более эффективным методом, чем методы на основе клеточного представления. В частности, предложенный способ устраняет необходимость поиска компромисса между точностью и скоростью обработки геометрической информации. Второе – это новая тактика создания начальной популяции генетического алгоритма для ускорения сходимости при наличии нескольких целей. за счёт использования возможностей вероятностного алгоритма дорожной карты. Еще одна особенность реализации алгоритма связана с адекватным (для исследуемой предметной области) выбором числовых параметров, определяющих особенности всех этапов эволюционной стратегии, включая временные затраты на выполнение каждого этапа. В частности, это касается, параметров оператора мутации и элитной стратегии. Предложенный алгоритм был протестирован на двух реальных картах с разной степенью сложности. Эффективность алгоритма подтверждена сравнением с результатами планирования пути для тестовых карт, полученными с помощью стандартного генетического алгоритма и алгоритма оптимизации муравьиной колонии. Экспериментальные результаты показывают, что гибридный алгоритм расширяет возможности обычного генетического алгоритма и находит рациональные варианты пути с лучшим значением целевой функции для одной и нескольких целей за гораздо меньшее время, чем другие традиционные реализации GA
Список литературы
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.
