Исследование свойств алгоритма поиска в ширину для нахождения маршрута передвижения роботов

Цель исследования. Представленное в данной статье исследование нацелено на повышение быстродействия поиска пути для маршрута передвижения роботов. Научной новизной является полученная закономерность отношения времени и размеров поля.

Методы. Для нахождения пути в лабиринте использовались алгоритмы поиска в глубину и поиска в ширину, основой которых является цикличное прохождение смежных не посещенных ранее вершин графа. Быстродействие оценивается в скорости выполнения программного кода на подготовленных образцах. Научная новизна была получена за счет исследования влияния размеров карты на быстродействие алгоритмов поиска в глубину и ширину.

Результаты. Разработана программная реализация алгоритмов поиска в ширину и в глубину. В статье подробнее представлено описание алгоритма поиска в ширину в виде псевдо- и программного кодов, которые основываются на цикле while, где осуществляется обработка очереди проверяемых вершин графа. На основе оценки быстродействия найденного пути сделан вывод, что поиск в ширину не является быстрейшим. На основе оценки влияния различных факторов на скорость работы алгоритма сделан вывод, что увеличение размеров поля, уменьшение количества препятствий и расстояния между стартовой и финальной точками увеличивает время выполнения алгоритма.

Заключение. Был представлен алгоритм поиска в ширину и его программная реализация. В ходе экспериментальных исследований было установлено, что данный алгоритм по времени не является быстрейшим, но во всех тестах находил кратчайший путь. Также была получена закономерность ta = f(w, h) для подготовленных образцов искомого поля, которая выражается в зависимости времени выполнения алгоритма от длины и ширины поля. И можем заключить, что он применим для поиска пути передвижения роботов так как всегда находит кратчайший путь.

1. Panigrahi P.K., Tripathy H.K. Analysis on intelligent based navigation and path finding of autonomous mobile robot // Information systems design and intelligent applications. 2015; № 339: 219–232. http://dx.doi.org/10.1007/978-81-322-2250-7.

2. Luo Q., Wang H., Zheng Y., He J. Research on path planning of mobile robot based on improved ant colony algorithm // Neural Computing and Applications. 2020; № 32: 1555–1566. https://doi.org/10.1177/1729881418774673.

3. Fuzzy Gain-Based Dynamic Ant Colony Optimization for Path Planning in Dynamic Environments / V. Sangeetha, R. Krishankumar, K.S. Ravichandran, F. Cavallaro, S. Kar, D. Pamucar, A. A. Mardani // Symmetry. 2021; №13(2): 280. https://doi.org/10.3390/sym13020280.

4. 3D path planning for the ground robot with improved ant colony optimization / L. Wang, J. Kan, J. Guo, C. Wang // Sensors. 2019; №19(4): 815. https://doi.org/10.3390/s19040815.

5. Energy-efficient green ant colony optimization for path planning in dynamic 3D environments / V. Sangeetha, R. Krishankumar, K. Ravichandran, S. Kar // Soft Computing. 2021; №25(15): 4749–4769. https://doi.org/10.1007/s00500-020-05483-6.

6. Saraswathi M., Murali G.B., Deepak B. Optimal path planning of mobile robot using hybrid cuckoo search-bat algorithm // Procedia Computer Science. 2018; № 133: 510–517. https://doi.org/10.1016/j.procs.2018.07.064.

7. Gilhyun R. Applying asynchronous deep classification networks and gaming reinforcement learning-based motion planners to mobile robots // 2018 IEEE International Conference on Robotics and Automation (ICRA), 2018; https://doi.org/10.1109/ICRA.2018.8460798.

8. Path Planning of multiagent constrained formation through deep reinforcement Learning / Z. Sui, Z. Pu, J. Yi, X. Tian // 2018 International Joint Conference on Neural Networks (IJCNN), 2018; https://doi.org/10.1109/IJCNN.2018.8489066.

9. Continuous control with deep reinforcement learning / T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Y. Tassa, D. Silver, D. Wierstra // Journal of Data Analysis and Information Processing. 2016; №4(4). https://doi.org/10.48550/arXiv.1509.02971.

10. Trust region policy optimization / J. Schulman, S. Levine, P. Moritz, M. I. Jordan, P. Abbeel // 31st International Conference on Machine Learning. 2015; https://doi.org/10.48550/ arXiv.1502.05477.

11. Schulman J., Wolski F., Dhariwal P., Radford A., Klimov O. Proximal policy optimization algorithms. arXiv 2017, arXiv:1707.06347v2. 2017; https://doi.org/10.48550/ arXiv.1707.06347.

12. A Collision-Aware Mobile Robot Navigation in Grid Environment using Improved Breadth First Search / H.K. Tripathy, S. Mishra, H.K. Thakkar, D. Rai // Computers & Electrical Engineering. 2021; №4. https://doi.org/10.1016/j.compeleceng.2021.107327.

13. Panigrahi P.K., Bisoy S.K., Tripathy H.K. Intelligent Path Planning with Improved BFS (I-BFS) Strategy for Mobile Robot in RFID Equipped Unknown Environment // Proceedings of International Conference on Computational Intelligence and Data Engineering. 2022; №99:237-249. https://doi.org/10.1007/978-981-16-7182-1_20.

14. Breadth First Search Approach for Shortest Path Solution in Cartesian Area / R. Rahim, D. Abdullah, S. Nurarif, M. Ramadhan et al. // Journal of Physics: Conference Series. 2018; №1019(1):12-36. https://dx.doi.org/10.1088/1742-6596/1019/1/012036.

15. Zhou C., Huang B., Fränti P. A review of motion planning algorithms for intelligent robots // Journal of Intelligent Manufacturing. 2022; №33: 387–424. https://doi.org/10.1007/ s10845-021-01867-z.

16. Sánchez-Ibáñez J.R., Pérez-del-Pulgar C.J., García-Cerezo, A. Path Planning for Autonomous Mobile Robots: A Review // Sensors. 2021; №21: 7898. https://doi.org/10.3390/ s21237898.

17. Adaptive path finding algorithm in dynamic environment for warehouse robot / Ng MK., Chong, YW., Ko, Km. et al. // Neural Computing and Applications. 2020; №32: 13155–13171. https://doi.org/10.1007/s00521-020-04764-3.

18. Search Methods in Motion Planning for Mobile Robots / L. Paulino, C. Hannum, A.S. Varde, C.J. Conti // Intelligent Systems and Applications. 2021; № 296: 802-822. https://doi.org/10.1007/978-3-030-82199-9_54 2021.

19. Черноскутов М. А. Использование GPU для ускорения поиска в ширину на графах // Параллельные вычислительные технологии 2013 (ПаВТ'2013). 2013. С. 560-565.

20. Колганов А. С. Самая быстрая и энергоэффективная реализация алгоритма поиска в ширину на одноузловых различных параллельных архитектурах согласно рейтингу Graph500 // Параллельные вычислительные технологии (ПаВТ'2018). 2018. С. 273-285.

21. Козик А. А., Побегайло А.П. Ускорение параллельного поиска в ширину в графах при вычислениях на GPU // Вестник БГУ. 2015; № 2: 102-107.

22. Черноскутов М. А. Методы высокопроизводительной обработки графов // Восьмая Сибирская конференция по параллельным и высокопроизводительным вычислениям. Томск, 2015. С. 73-80. DOI 10.17223/978-5-7511-2389-5/11.

23. Черноскутов М. А. Параллельная высокопроизводительная обработка графов // Параллельные вычислительные технологии (ПаВТ'2016). 2016; С. 736-742. 24. Corey L. Lanum. Visualizing Graph Data. New York: Manning Publications Co; 2016.

24. Correll N. Introduction to autonomous robots. Davis: LibreTexts; 2021.

25. Касьянов Я. В., Федотова Е. В., Штыбина К. В. Анализ развития алгоритмов планирования маршрутов мобильных наземных роботов // Автоматизация, мехатрони ка, информационные технологии: материалы X Международной научно-технической интернет-конференции молодых ученых. Омск, 2020. С. 64-70.

26. Бобырь М.В., Титов В.С., Беломестная А.Л. Стабилизация теплового режима в процессе резания // Мехатроника, автоматизация, управление. 2010. № 6. С. 38-41.

27. Bobyr M.V., Titvo V.S. Nasser A.A. Automation of the Cutting-Speed Control Process Based on Soft Fuzzy Logic Computing // Journal of Machinery Manufacture and Reliability. 2015. Vol.44. No7. P. 633-641. DOI 10.3103/S1052618815070067.

28. Титов В.С., Бобырь М.В., Милостная Н.А. Автоматическая компенсация тепловых деформаций шпиндельных узлов прецизионного оборудования с ЧПУ // Промышленные АСУ и контроллеры. 2006. № 11. С. 31-35.

29. Захаров К.С., Савельев А.И. Сглаживание кривизны траектории движения наземного робота в трехмерном пространстве // Известия Юго-Западного государственного университета. 2020; 24(4): 107-125. https://doi.org/10.21869/2223-1560-2020- 24-4-107-125.