An Approach to Constructing the Shortest Energy-Efficient Route over Rough Terrain

Maxim Ivanov, Olga Avseeva

Abstract


The problem of route construction in rugged terrain without roads, with elevation changes and impassable sections, is considered. To solve the problem, the terrain is represented as a graph by overlaying a regular grid.
This paper considers two methods for graph construction, of which the chosen method includes both the sides and diagonals of a quadrilateral of the overlaying regular grid. The edge weights of the resulting graph consist of a generalized arc coefficient, which characterizes the relative energy expenditure of movement, and a reduced arc weight. The reduced arc weight is a function of the actual arc length, the terrain, and travel constraints.
To determine the shortest route on the graph, four search algorithms were considered: Dijkstra's algorithm, A*, Theta*, and Lazy Theta*. Lazy Theta* was chosen for this problem, as it achieves a compromise between path quality and throughput. To ensure the algorithm functions correctly in real-world conditions, it was modified to account for geographic features such as terrain, water and marshy obstacles, and acceptable slopes depending on the mode of travel.
The overall algorithm for solving the problem consists of several steps. First, the entire specified area is discretized, taking into account the precise geodetic curvature and a fixed step between nodes, specified in meters. When constructing the grid, data on water bodies within the user-selected area and terrain elevation are taken into account. Then, the start and end points of the route, selected by the user, are linked to the closest available points on the generated grid. Route search is performed using a modified Lazy Theta* algorithm. Bresenham's algorithm is used to verify line-of-sight between route points.
A web application has been developed that allows route construction for both pedestrian and vehicle travel.

Full Text:

PDF (Russian)

References


Kim, J. Fast Route Planner Considering Terrain Information. Sensors. 2022, 22, 4518. https://doi.org/10.3390/s22124518

Saad, S.; Salameh, A.I.; Abdallah, S.; El-Moursy, A.; Cheng, C.-T. A Composite Metric Routing Approach for Energy-Efficient Shortest Path Planning on Natural Terrains. Appl. Sci. 2021, 11, 6939. https://doi.org/10.3390/app 1115693

On terrain traversability analysis in unstructured environments: recent advances in forest applications, Afonso E. Carvalho, David Portugal, Paulo Peixoto, Intelligent Service Robotics (2025) 18:195–213. https://doi.org/10.1007/s11370-025-00591-4

Nash, A., Koenig, S., & Tovey, C. (2010). Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 147-154. https://doi.org/10.1609/aaai.v24i1.7566

R. Rey, J. A. Cobano, L. Merino and F. Caballero, "Generalized Lazy-Theta* for 3D path planning considering non-uniform costs," 2022 International Conference on Unmanned Aircraft Systems (ICUAS), Dubrovnik, Croatia, 2022, pp. 664-669. https://doi.org/10.1109/ICUAS54217.2022.9836069

R. Rey, J. A. Cobano, L. Merino and F. Caballero, "Adaptation of Lazy-Theta* for UAS 3D path planning considering safety costs," 2021 International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 2021, pp. 387-393. https://doi.org/10.1109/ICUAS51884.2021.9476772

Gao, Z.; Wan, L.; Cai, M.; Xu, X. Research on Lazy Theta* Route Planning Algorithm Based on Grid Point Optimization. Appl. Sci. 2022, 12, 10601. https://doi.org/10.3390/app122010601

Faria, M.; Marín, R.; Popović, M.; Maza, I.; Vigur.ia, A. Efficient Lazy Theta* Path Planning over a Sparse Grid to Explore Large 3D Volumes with a Multirotor UAV. Sensors. 2019, 19, 174. https://doi.org/10.3390/s19010174

Meng-shun Yuan, Tong-le Zhou, Mou Chen, Improved lazy theta∗ algorithm based on octree map for path planning of UAV, Defence Technology, Volume 23, 2023, Pages 8-18. https://doi.org/10.1016/j.dt.2022.01.006

Garcia, M., Viguria, A. & Ollero, A. Dynamic Graph-Search Algorithm for Global Path Planning in Presence of Hazardous Weather. J Intell Robot Syst. 69, 285–295 (2013). https://doi.org/10.1007/s10846-012-9704-7

Yuan, M. S., et al. Improved lazy theta∗ algorithm based on octree map for path planning of UAV. Defence Technology. 2022. https://doi.org/10.1016/j.dt.2022.01.006. EDN ORNZTZ.

Chrpa, L., et al. Towards a Trajectory Planning Concept: Augmenting Path Planning Methods by Considering Speed Limit Constraints. Journal of Intelligent and Robotic Systems. 2014. Vol. 75, No. 2. P. 243-270. https://doi.org/10.1007/s10846-013-9886-7. EDN SYBUNY.

Satai, H. Al., et al. Bézier Curves-Based Optimal Trajectory Design for Multirotor UAVs with Any-Angle Pathfinding Algorithms. Sensors. 2021. Vol. 21, No. 7. P. 2460. https://doi.org/10.3390/s21072460. EDN YMLDRK.

Balstrøm, T. (2002). On identifying the most time-saving walking route in a trackless mountainous terrain. Geografisk Tidsskrift-Danish Journal of Geography, 102(1), 51–58. https://doi.org/10.1080/00167223.2002.10649465

Kozub, D.V., Korukhova, Y.S. Off-Road Routing System Based On Visibility Graph. In: Scientific Services & Internet. 2022. No. 24. pp. 340-349. https://doi.org/10.20948/abrau-2022-15. EDN TMHJVH. (In Russ., abstract in Eng.)

Neydorf, R.A., et al. Study of heuristic algorithms in planning and optimization of routes problem in the environment with obstacles. Izvestiya SFedU. Engineering Sciences. 2016. No. 3(176). pp. 127-143. EDN WABVYL. (In Russ., abstract in Eng.)

Krutko, D.A., et al. Methods for constructing routes outside of settlements on the basis of GPS data. Siberian Aerospace Journal. 2022. Vol. 23, issue 2. Pp. 168-176. https://doi.org/10.31772/2712-8970-2022-23-2-168-176. EDN JARJRY. (In Russ., abstract in Eng.)

Klochkova, E. N. Obosnovanie vybora algoritma poiska puti resheniya zadach postroeniya marshruta k mestu naznacheniya / E. N. Klochkova // Vestnik Moskovskogo universiteta MVD Rossii. – 2015. – № 5. – S. 205-209. – EDN TTZMOP. (In Russ., abstract in Eng.)

Krut'ko, D. A. Problema avtomatizacii postroeniya skhem marshrutov peshego turizma v gornyh massivah Krasnoyarskogo kraya / D. A. Krut'ko // Aktual'nye problemy aviacii i kosmonavtiki, 2021. - T. 2. - S. 260–262. (In Russ., abstract in Eng.)

Krut'ko, D. A. Problema poiska kratchajshego puti v trekhmernom prostranstve na territorii Torgashinskogo hrebta / D. A. Krut'ko // Aktual'nye problemy aviacii i kosmonavtiki: sbornik materialov VIII Mezhdunarodnoj nauchno-prakticheskoj konferencii, posvyashchennoj Dnyu kosmonavtiki: v 3 t., Krasnoyarsk, 11–15 aprelya 2022 goda. Tom 2. – Krasnoyarsk: Federal'noe gosudarstvennoe byudzhetnoe obrazovatel'noe uchrezhdenie vysshego obrazovaniya "Sibirskij gosudarstvennyj universitet nauki i tekhnologij imeni akademika M.F. Reshetneva", 2022. – S. 142-144. – EDN MVZTHK. (In Russ., abstract in Eng.)

Patent № 2594374 C2 Rossijskaya Federaciya, MPK G01C 21/34. sposob postroeniya marshruta peredvizheniya na peresechennoj mestnosti: № 2014145708/28: zayavl. 13.11.2014: opubl. 20.08.2016 / I. I. SHuklin, N. I. Rudnev, A. M. SHlyk; zayavitel' Rossijskaya Federaciya, ot imeni kotoroj vystupaet Ministerstvo oborony Rossijskoj Federacii. – EDN UOPGAJ. (In Russ.)

Tikunov, V. S., Kapralov, E. G. Osnovy geoinformatiki. Kn. 1. – M.: Akademiya, 2008. – 384 s. (In Russ.)

Lajkin, V. I., Uporov, G. A. Geoinformatika: uchebnoe posobie / Lajkin V.I., Uporov G.A. – Komsomol'sk-na-Amure: Izd-vo AmGPGU, 2010. – 162 s. (In Russ.)

Patent № 2439496 C1 Rossijskaya Federaciya, MPK G01C 21/34. sposob prokladyvaniya marshruta peredvizheniya na peresechennoj mestnosti: № 2010129415/28: zayavl. 15.07.2010: opubl. 10.01.2012 / A. I. Muhin, A. M. SHlyk, N. I. Rudnev; zayavitel' Federal'noe gosudarstvennoe unitarnoe predpriyatie "Kurskij nauchno-issledovatel'skij institut" Ministerstva oborony Rossijskoj Federacii. – EDN HDZWBW. (In Russ.)

Ageev P. A., Kudryavcev A. M., Smirnov A. A. Procedury postroeniya marshrutov dvizheniya tekhniki po peresechennoj mestnosti na osnove cifrovyh modelej mestnosti // Izvestiya TulGU. Tekhnicheskie nauki. 2019. Vyp. 9. S. 268–275. (In Russ., abstract in Eng.)

Dejkstra, E. V. Zametka o dvuh zadachah, svyazannyh s grafami // CHislennye metody. – 1959. – T. 1. – S. 269–271. (In Russ., abstract in Eng.)

Hart, P., Nil'sson N., Rafael' B. Formal'nye osnovy evristicheskogo poiska kratchajshego puti // Sistemy upravleniya i kibernetika. – 1968. – T. 4, № 2. – S. 100–107. (In Russ., abstract in Eng.)

Nesh, A., Kyonig, S., Tovi, K. Algoritm Theta*: planirovanie marshruta s proizvol'nymi uglami na reshyotkah // Materialy konferencii po iskusstvennomu intellektu AAAI. – 2007. – T. 22, № 2. – S. 1177–1183. (In Russ., abstract in Eng.)

Brezenhem, D. Algoritm upravleniya cifrovym plotterom // ZHurnal sistem IBM. – 1965. – T. 4, № 1. – S. 25–30. (In Russ., abstract in Eng.)

Nesh, A., Kyonig, S., Tovi, K. Algoritm Theta*: teoriya i primenenie // ZHurnal AI Communications. – 2009. – T. 22, № 1. – S. 39–55. (In Russ., abstract in Eng.)

Nesh, A., Kyonig, S., Tovi, K. Lazy Theta*: algoritm planirovaniya marshruta s uchyotom proizvol'nyh uglov i analiza dliny puti // Materialy konferencii po iskusstvennomu intellektu AAAI. – 2010. – S. 147–153. (In Russ., abstract in Eng.)


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность ИТ-КОНГРЕСС ВМК МГУ 2026 СНЭ

ISSN: 2307-8162