Application of graph algorithms for optimal path planning of mobile robots
Zastosowanie algorytmów grafowych do planowania optymalnej trasy przejazdu robotów mobilnych *
Mechanik nr 04/2025 - Nowe technologie
ABSTRACT: The objective of the research described in this article was to develop a model for planning the optimal traversal route for a wheeled mobile robot based on a Digital Terrain Model (DTM), utilizing graph algorithms. A methodology was developed to transform the DTM into a graph representation, enabling the efficient application of graph algorithms for route determination. Three algorithms were implemented in Python: Prim’s algorithm, Dijkstra’s algorithm, and the A* algorithm. These algorithms were applied to graph-based terrain analysis, comparing their performance in terms of route feasibility, path length, and computation time. Notably, the A* algorithm yielded the most promising computational efficiency results in the conducted tests.
KEYWORDS: mobile robotics, graph algorithms, path planning, global navigation, digital terrain model
STRESZCZENIE: Celem prac opisanych w niniejszym artykule było opracowanie modelu planowania optymalnej trasy przejazdu dla kołowego robota mobilnego na podstawie Numerycznego Modelu Terenu (NMT), z wykorzystaniem algorytmów grafowych. Opracowano metodykę pozwalającą na sprowadzenie NMT do postaci grafowej, dzięki czemu możliwe było efektywne zastosowanie algorytmów grafowych do wyznaczenia trasy. Zaimplementowano trzy algorytmy w języku Python: algorytm Prima, Dijkstry i A*. Zastosowano je do analizy grafowej terenu, porównując wyniki m.in. pod kątem zdolności do wyznaczenia trasy, długości trasy i czasu obliczeń. W przeprowadzonych testach algorytm A* uzyskał najbardziej obiecujące rezultaty czasowe.
SŁOWA KLUCZOWE: robotyka mobilna, algorytmy grafowe, planowanie trasy, nawigacja globalna, numeryczny model terenu
BIBLIOGRAFIA / BIBLIOGRAPHY:
[1] Jiang J., Xin J. „Path planning of a mobile robot in a free-space environment using q-learning”. Progress in Artificial Intelligence. Vol. 8, No. 1 (2019): 133–142.
[2] Mohanan M.G., Salgoankar A. „A survey of robotic motion planning in dynamic environments”. Robotics and Autonomous Systems. Vol. 100, No. 1 (2018): 171–185.
[3] Shreyas V., Bharadwaj S.N., Srinidhi S., Ankith K.U., Rajendra A.B. „Self-driving cars: An overview of various autonomous driving systems”. Advances in Data and Information Sciences: Proceedings of ICDIS 2019. Indie: Springer, 2020.
[4] Williford K.H., Farley K.A., Stack K.M., Allwood A.C., Beaty D., Beegle L.W., Bhartia R., Brown A.J., de la Torre Juarez M., Hamran S.-E. i in. „The NASA Mars 2020 Rover Mission and the Search for Extraterrestrial Life”. From Habitability to Life on Mars. Amsterdam: Elsevier, 2018.
[5] Groves K., Hernandez E., West A., Wright T., Lennox B. „Robotic exploration of an unknown nuclear environment using radiation informed autonomous navigation”. Robotics. Vol. 10, No. 2 (2021): 78.
[6] Wu M. „Robotics applications in natural hazards”. Highlights in Science, Engineering and Technology. Vol. 43, No. 1 (2023): 273–279.
[7] Sasaki T., Otsu K., Thakker R., Haesaert S., Aghamohammadi A.-A. „Where to map? Iterative rover-copter path planning for Mars exploration”. IEEE Robotics and Automation Letters. Vol. 5, No. 2 (2020): 2123–2130.
[8] Numeryczny model terenu (NMT). https://www.geoportal.gov.pl/pl/dane/numeryczny-model-terenu-nmt/ (dostęp: 10 marca 2025).
[9] Tzafestas S.G. „Mobile Robot Control and Navigation: A Global Overview”. Journal of Intelligent & Robotic Systems. Vol. 91, No. 1 (2018): 35–58.
[10] Lazarowska A. „Zastosowanie grafu widoczności w planowaniu trasy przejścia statku”. Scientific Journal of Gdynia Maritime University. R. 98 (2017): 116–121.
[11] Lee G.T., Kim K. „A controllable agent by subgoals in path planning using goal-conditioned reinforcement learning”. IEEE Access. Vol. 11, No. 1 (2023): 33812–33825.
[12] Eapen N.A. „Path planning of a mobile robot among curved obstacles through tangent drawing and trapezoidal decomposition”. Engineering Science and Technology, an International Journal. Vol. 24, No. 6 (2021): 1415–1427.
[13] Vasquez-Gomez J.I., Marciano-Melchor M., Valentin L., Herrera-Lozada J.C. „Coverage path planning for 2D convex regions”. Journal of Intelligent & Robotic Systems. Vol. 97, No. 1 (2020): 81–94.
DOI: https://doi.org/10.17814/mechanik.2025.02.2
* Artykuł recenzowany
