10.14489/vkit.2025.06.pp.012-018

DOI: 10.14489/vkit.2025.06.pp.012-018

Петров М. Ю., Вишнякова Л. В.
УЧЕТ ОГРАНИЧЕНИЙ ЛЕТАТЕЛЬНОГО АППАРАТА ПРИ ПОИСКЕ МАРШРУТА ПОЛЕТА НА ГРАФЕ
(pp. 12-18)

Аннотация. Представлен алгоритм учета технических ограничений летательного аппарата. Алгоритм основан на переносе ограничений в структуру графа поиска, что позволяет применять стандартные алгоритмы поиска пути на графе. Продемонстрирована его работоспособность в задаче поиска маршрута полета на минимальной высоте.

Ключевые слова: поиск пути; учет ограничений на графе; маршрут летательного аппарата.

Petrov M. Yu., Vishnyakova L. V.
ACCOUNTING FOR AIRCRAFT LIMITATIONS IN ROUTE SEARCH ON GRAPH
(pp. 12-18)

Abstract. Building a flight route is one of the main task, which must be solved before using an aircraft. The most common ways to set a route is to specify a set of points. Graph pathfinding algorithms such as Dijkstra's algorithm or A* are an extremely common means of solving this kind of problem. Not every arbitrary set of points is a valid route because aircraft may have technical limitations. Because of this, basic graph algorithms can sometimes produce incorrect routes. The purpose of this work is to demonstrate the described problem, as well as an algorithm for solving it. This paper presents two options for solving this problem. Both solutions are based on transferring constraints into the search graph structure. The first solution involves a complete reconstruction of the graph in which all invalid transitions are discarded. While the second solution involves a local reconstruction of the graph. Both solution allow using standard path-finding algorithms on new graph without any restrictions. The problem and its solution are demonstrated in the task of finding a flight route at the minimum altitude. The main technical limitation in the example is the minimum turning radius. The optimized function is the minimum flight altitude. The route is searched on a Digital Elevation Map. A Digital Elevation Map is a type of geospatial data that represents the terrain or topography of an area in a digital format. It typically consists of a gridded array of elevations at regular intervals, where each cell contains the height value above sea level for that specific location. The example demonstrates how the minimum turning radius changes the optimal route.

Keywords: Path finding; Constraint handling on graph; Flight route.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

М. Ю. Петров, Л. В. Вишнякова (ФАУ «Государственный научно-исследовательский институт авиационных систем», Москва, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

M. Yu. Petrov, L. V. Vishnyakova (State Research Institute of Aviation Systems, Moscow, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Dijkstra E. W. A Note on Two Problems in Connexion with Graphs // Numerische mathematic. 1959. V. 1, № 1. P. 269–271.
2. Pearl J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Boston: Addison-Wesley Longman Publishing Co, 1984.
3. Harabor D., Grastien A. Online Graph Pruning for Pathfinding on Grid Maps // 25 National Conference on Artificial Intelligence. (AAAI 2011). 7–11 August 2011. San Francisco, California. P. 1114–1119.
4. Köhler E., Möhring R. H., Schilling H. Acceleration of Shortest Path and Constrained Shortest Path Computation // Conference: Experimental and Efficient Algorithms, 4th Workshop on Experimental Algorithms (WEA 05). 10–13 May 2005, Santorini Island. P. 126–138. DOI: 10.1007/11427186_13
5. Петров М. Ю. Построение маршрута полета летательного аппарата на малых высотах // Известия Российской академии наук. Теория и системы управления. 2019. № 3. С. 140–146.
6. Кормен Т. Х., Лейзерсон Ч. И., Ривест Р. Л., Штайн К. Алгоритмы: построение и анализ. 2-е изд. М.: Вильямс, 2007. 459 с.

Eng

1. Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematic, 1(1), 269–271.
2. Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley Longman.
3. Harabor, D., & Grastien, A. (2011). Online graph pruning for pathfinding on grid maps. Proceedings of the 25th National Conference on Artificial Intelligence (AAAI 2011), 1114–1119.
4. Köhler, E., Möhring, R. H., & Schilling, H. (2005). Acceleration of shortest path and constrained shortest path computation. Proceedings of the 4th Workshop on Experimental Algorithms (WEA'05), 126–138. https://doi.org/10.1007/11427186_13
5. Petrov, M. Yu. (2019). Aircraft low-altitude flight path planning. Izvestiya Rossiiskoi Akademii Nauk. Teoriya i Sistemy Upravleniya, (3), 140–146. [in Russian language]
6. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2007). Algorithms: Construction and analysis (2nd ed.). Williams. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

DOI: 10.14489/vkit.2025.06.pp.012-018

Скопируйте DOI статьи и перейдите по ссылке https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

В комментарии к заказу обязательно укажите DOI статьи.

Eng

This article is available in electronic format (PDF).

DOI: 10.14489/vkit.2025.06.pp.012-018

Copy the article DOI and follow the link https://id-spektr.ru/product/pokupka-elektronnoy-stati-iz-zhurnala-vestnik-kompyuternyh-i-informatsionnyh-tehnologiy

Please specify the article DOI in the order comments.