DOI: 10.17587/prin.15.352-361

Algorithms for Route Planning and Navigation of Unmanned Aerial Vehicles

E. A. Petrishchev, Postgraduate Student, arnoa9129@gmail.com, Russian New University, Moscow, 105005, Russian Federation

Corresponding author: Evgeniy A. Petrishchev, Postgraduate Student, Russian New University, Moscow, 105005, Russian Federation E-mail: arnoa9129@gmail.com

A brief overview of the results of recent research published in open sources in the field of route planning and navigation algorithms for unmanned aerial vehicles (UAV) is presented. Works devoted to global and local planning of trajectories taking into account known and detected obstacles in flight, as well as issues of navigation of groups of drones, are considered. Various approaches are analyzed, including graph algorithms (A*, Dijkstra, Rapidly-exploring Random Trees), methods of data mining in real time, potential fields. Special attention is paid to work on the use of neural networks and machine learning, SLAM and multi-agent technologies for planning UAV routes. The advantages and disadvantages of the main groups of algorithms are considered. A conclusion is drawn about the prospects for using hybrid methods, as well as machine learning technologies, to build intelligent UAV traffic control systems.

Keywords: unmanned aerial vehicles, UAV, drones, navigation algorithms, route planning, global navigation, local navigation, SLAM, neural networks

pp. 352—361

For citation:
Petrishchev E. A. Algorithms for Route Planning and Navigation of Unmanned Aerial Vehicles, Programmnaya Ingeneria, 2024, vol. 15, no. 7, pp. 352—361. DOI: 10.17587/prin.15.352-361. (in Russian).

References:

1. Vasil'chenko A. S., Ivanov M. S., Kolmykov G. N. Forma­tion of flight routes for unmanned aerial vehicles taking into account the location of air defense and electronic warfare, Control, Communication and Security Systems, 2019, no. 4, pp. 403—420. DOI: 10.24411/2410-9916-2019-10416 (in Russian).
2. Gen K. K., Chulin N. A. Unmanned aerial vehicle navigation algorithm based on an improved simultaneous localization and mapping algorithm with an adaptive local observation range, Bulletin of the Bauman Moscow State Technical University, Instrument Engineering Series, 2017, no. 3, pp. 76—94. DOI: 10.18698/0236-3933-2017-3-76-94 (in Russian).
3. Ishchuk I. N., Likhachev M. A. Modelling of the optimal route of unmanned aerial vehicles based on infrared video navigation data based on the upgraded Dijkstra algorithm, Journal of Siberian Federal University. Engineering & Technologies, 2021, no. 7, available at: https://elib.sfu-kras.ru/bitstream/2311/144856/1/02a_Ischuk.pdf (date of access 22.01.2024) (in Russian).
4. Mikhailov R.L, Tzulun D. V. Application of shortest path search algorithms in planning unmanned aerial vehicle flight routes, Information Technology and Telecommunications, 2023, vol. 11, no. 1, pp. 26—38. DOI: 10.31854/2307-1303-2023-11-1-26-38 (in Russian).
5. Annaiyan A., Olivares-Mendez M. A., Voos H. Real-time graph-based SLAM in unknown environments using a small UAV, 2017 inter­national conference on unmanned aircraft systems (ICUAS), IEEE, 2017, pp. 1118—1123, available at: https://core.ac.uk/download/pdf/132585788.pdf
6. Goto T., Kosaka T., Noborio H. On the heuristics of A* or A algorithm in ITS and robot path-planning, Proceedings 2003 IEEE, RSJ International Conference on Intelligent Robots and Systems (IROS 2003), IEEE, 2003, vol. 2, pp. 1159—1166. DOI: 10.1109/IROS.2003.1248802.
7. Danielmeier L., Seitz S., Barz I. et al. Modified Constrained Wavefront Expansion Path Planning Algorithm for TiltWing UAV, 2022 International Conference on Unmanned Aircraft Systems (ICUAS), IEEE, 2022, pp. 676-6. DOI: 10.1109/ICU-AS54217.2022.9836126.
8. Nguyen Hoang Thuy Trang, Shydlouski S. Situations in construction of 3D mapping for SLAM, VIIIInternational Scientific and Practical Conference "Information and Measuring Equipment and Technologies". MATEC Web Conf., 2018, vol. 155, article 01055. DOI: 10.1051/matecconf/201815501055.
9. Cabreira T. M., Brisolara L. B., Ferreira P. R. Survey on coverage path planning with unmanned aerial vehicles, Drones, 2019, vol. 3, no. 1, article 4. DOI: 10.3390/drones3010004.
10. Wang Y., Yu B., Zhang Y. et al. TPLinker: Single-stage joint extraction of entities and relations through token pair linking, Proceedings of the 28th International Conference on Computational Linguistics, COLING 2020, pp. 1572—1582.
11. Li Pei, Lingyi Wang, Wei Wu et al. Graph neural network-based scheduling for multi-UAV-enabled communications in D2D networks, Digital Communications and Networks, 2024, vol. 10, no. 1, pp. 45—52. DOI: 10.1016/j.dcan.2022.05.014.