Research of the Properties of the Breadth-First Search Algorithm for Finding the Movement Route of Robots

Purpose of research. The research presented in this article is aimed at improving the speed of finding a path for the movement route of robots. The scientific novelty is the obtained correlation of time and field size.

Methods. To find the path in the maze, the depth-first search and breadth-first search algorithms were used, the basis of which is the cyclic processing of adjacent previously unvisited graph vertices. Performance is estimated in terms of the speed of program code execution on prepared samples. Scientific novelty was obtained by studying the influence of map sizes on the performance of depth-first and breadth-first search algorithms.

Results. A software implementation of breadth-first and depth-first search algorithms has been developed. The article provides a more detailed description of the breadth-first search algorithm in the form of pseudo and program codes, which are based on the while loop, where the queue of checked graph vertices is processed. Based on the evaluation of the speed of the found path, it was concluded that the breadth-first search is not the fastest. Based on the assessment of the influence of various factors on the speed of the algorithm, it was concluded that an increase in the size of the field, a decrease in the number of obstacles and a distance between the starting and final points increases the execution time of the algorithm.

Conclusion. The breadth-first search algorithm and its software implementation were presented. In the course of experimental studies, it was found that this algorithm is not the fastest in time, but in all tests, it found the shortest path. The correlation ta = f(w, h) was also obtained for the prepared samples of the desired field, which is expressed as the dependence of the algorithm execution time on the length and width of the field. And we can conclude that it is applicable for finding the movement path of robots, since it always finds the shortest path.

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

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

5. Sangeetha V., Krishankumar R., Ravichandran K., Kar S. Energy-efficient green ant colony optimization for path planning in dynamic 3D environments. 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. Sui Z., Pu Z., Yi J., Tian X. Path Planning of multiagent constrained formation through deep reinforcement Learning. 2018 International Joint Conference on Neural Networks (IJCNN), 2018; https://doi.org/10.1109/IJCNN.2018.8489066.

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

10. Schulman J., Levine S., Moritz P., Jordan M. I., Abbeel P. Trust region policy optimization. 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. Tripathy H.K., Mishra S., Thakkar H.K., Rai D. A Collision-Aware Mobile Robot Navigation in Grid Environment using Improved Breadth First Search. 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. Rahim R., Abdullah D, Nurarif S., Ramadhan M. et al. Breadth First Search Approach for Shortest Path Solution in Cartesian Area. 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. Ng MK., Chong, YW., Ko, Km. et al. Adaptive path finding algorithm in dynamic environment for warehouse robot. Neural Computing and Applications. 2020; №32: 13155– 13171. https://doi.org/10.1007/s00521-020-04764-3.

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

19. Chernoskutov M. A. Ispol'zovanie GPU dlya uskoreniya poiska v shirinu na grafakh [Using GPU to speed up breadth-first search on graphs]. Parallel'nye vychislitel'nye tekhnologii 2013 (PaVT'2013) = Parallel computing technologies 2013 (PaVT'2013), 2013; pp. 560-565.

20. Kolganov A. S. Samaya bystraya i energoeffektivnaya realizatsiya algoritma poiska v shirinu na odnouzlovykh razlichnykh parallel'nykh arkhitekturakh soglasno reitingu Graph500 [The fastest and most energy-efficient implementation of breadth-first search algorithm on single-node various parallel architectures according to Graph500 rating]. Parallel'nye vychislitel'nye tekhnologii (PaVT'2018) = Parallel computing technologies (PaVT'2018), 2018, pp. 273-285.

21. Kozik A.A., Pobegailo A.P. Uskorenie parallel'nogo poiska v shirinu v gra-fakh pri vychisleniyakh na GPU [Acceleration of parallel breadth-first search in graphs when computing on the GPU]. Vestnik BGU = Bulletin of BSU. 2015, no. 2: 102-107.

22. Chernoskutov M.A. [Methods of high-performance processing of graphs]. Vos'maya Sibirskaya konferentsiya po parallel'nym i vysokoproizvoditel'nym vychisleniyam [Eighth Siberian Conference on Parallel and High-Performance Computing]. Tomsk, 2015; pp. 73-80. DOI 10.17223/978-5-7511-2389-5/11 (In Russ.).

23. Chernoskutov M. A. Parallel'naya vysokoproizvoditel'naya obrabotka grafov [Parallel high-performance processing of graphs]. Parallel'nye vychislitel'nye tekhnologii (PaVT'2016) = Parallel computing technologies (PaVT'2016). 2016; pp. 736-742.

24. Corey L. Lanum. Visualizing Graph Data. New York: Manning Publications Co; 2016.

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

26. Kasyanov Ya. V., Fedotova E. V., Shtybina K. V. [Analysis of the development of route planning algorithms for mobile ground robots]. Avtomatizatsiya, mekhatronika, informatsionnye tekhnologii. Materialy X Mezhdunarodnoi nauchno-tekhnicheskoi internetkonferentsii molodykh uchenykh [Automation, mechatronics, information technology. Proceedings of the X International Scientific and Technical Internet Conference for Young Scientists]. Omsk, 2020, pp. 64-70 (In Russ.).

27. Bobyr M.V., Titov V.S., Belomestnaja A.L. Stabilizatsiya teplovogo rezhima v protsesse rezaniya [Stabilizacija teplovogo rezhima v processe rezanija]. Mekhatronika, avtomatizatsiya, upravlenie = Mehatronika, Avtomatizacija, Upravlenie, 2010, no. 6, pp. 38-41.

28. 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, no.7, pp. 633-641. DOI 10.3103/S1052618815070067.

29. Titov V.S., Bobyr M.V., Milostnaya N.A. Avtomaticheskaya kompensatsiya teplovykh deformatsii shpindel'nykh uzlov pretsizionnogo oborudovaniya s ChPU [Avtomaticheskaja kompensacija teplovyh deformacij shpindel'nyh uzlov precizionnogo oborudovanija s ChPU]. Promyshlennye ASU i kontrollery = Industrial Automatic Control Systems and Controllers, 2006, no. 11,pp. 31-35.

30. Zakharov K. S., Saveliev A. I. Smoothing the Curvature of Trajectory of Ground Robot in 3D Space. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2020; 24(4): 107-125 (In Russ.). https://doi.org/ 10.21869/2223-1560-2020-24-4-107-125.