Программные продукты и системы

Введение. Высокая эффективность применения беспилотных летательных аппаратов (БпЛА) в ходе локальных и региональных вооруженных конфликтов доказана на практике [1]. Они широко задействованы не только для ведения разведки, но и для нанесения точечных ударов по обороняемым объектам. Возможности БпЛА позволяют эффективно действовать в пределах любого рельефа местности на малых и предельно малых высотах, при этом оставаться малозаметными для средств ПВО.

Способы борьбы с крупно- и среднеразмерными (стратегическими и оперативно-тактическими) БпЛА остаются традиционными. Они ведутся и будут вестись существующими и пер- спективными силами и средствами ПВО [2]. Тем не менее повысить эффективность борьбы с этими классами БпЛА возможно за счет геоинформационного компьютерного моделирования маршрута их полета, в частности, в мо- делирующих комплексах военного назначения.

Основой для проведения геоинформационного компьютерного моделирования являются методы построения маршрутов полета [1–3]. Проведенный анализ позволил выделить методы пространственной декомпозиции, на основе маршрутных сетей, на основе потенциальных полей и методы с использованием технологии ИИ [4].

Наиболее популярными способами определения маршрута являются методы пространственной декомпозиции, идея которых заключается в разделении пространства на области. Методы относительно просты в реализации, однако требуют больших вычислительных затрат, поскольку необходимо детально дискретизировать все пространство и обеспечить высокую точность маршрута [5].

Широкое применение в задачах маршрутизации находят методы навигационного графа  и навигационных сеток. Реализация метода навигационного графа возможна в трехмерном пространстве, но он имеет ряд недостатков:

– высокая вычислительная сложность из-за большого количества вершин графа;

– перемещение динамических объектов по неестественным траекториям, поскольку они следуют по ребрам графа;

– невозможность коррекции пути при пересечении движущимся объектом ребер графа;

– фиксированная дискретизация пространства (не учитываются объекты разных размеров) [6].

Метод навигационных сеток представляет собой дискретизацию трехмерного пространства на основе полигонального разбиения, где полигоном является выпуклая область. Суть выпуклых полигонов заключается в том, что путь, соединяющий любые две вершины, полностью принадлежит данному полигону.

Метод имеет определенные ограничения:

– высокая вычислительная сложность при учете динамических объектов;

– увеличивающиеся требования к памяти при большом количестве объектов сложной формы;

– сложность автоматической генерации метода навигационных сеток, особенно в средах  с нерегулярной структурой, где полная корректность разбиения не всегда достижима [6].

Вторую группу составляют методы на основе маршрутных сетей. В наиболее известных из них применяются графы видимости и используются обобщенные диаграммы Вороного. Недостатком таких диаграмм является существенное усложнение применения маршрутной сети, так как при навигации в евклидовых пространствах размерности выше двух она теряет свойство топологической одномерности [5].  В отличие от этого граф видимости строится на множестве вершин полигонов, моделирующих препятствия сцены, с добавлением начальной  и конечной точек маршрута. Однако преобразование такого топологического графа в практическую маршрутную сеть представляет собой сложную задачу, поскольку ребра графа видимости проходят в непосредственной близости от вершин препятствий, что требует либо коррекции путей, либо предварительного расширения границ препятствий [5].

Третью группу составляют методы на осно- ве потенциальных полей, использующих физическую аналогию движения заряженной части- цы в электростатическом поле [5].

Данный метод демонстрирует ряд ограничений. В частности, формируемые траектории движения в лучшем случае оказываются неестественными. Кроме того, существует вероятность попадания в локальные минимумы потенциального поля [7].

Четвертую группу составляют методы на основе технологии ИИ. Наиболее распространенными являются нейронная сеть Хопфилда, нейронная сеть Кохонена и бионический метод. Нейронная сеть позволяет решать задачи для заранее заложенного в нее при обучении количества пунктов, поэтому задачи большей размерности повышают вычислительную слож- ность. Существенными недостатками нейронной сети Хопфилда являются экспоненциальный рост вычислительной сложности при  увеличении размерности задачи, вероятность сходимости к локальным минимумам и генерация недопустимых маршрутов.

Самоорганизующаяся сеть Кохонена, в отличие от этого, обладает способностью автоматически выявлять кластерные структуры во входных данных. Тем не менее применение данного метода для задач маршрутизации требует модификаций базового алгоритма.

Бионический метод представляет собой подход, основанный на принципах активного взаимодействия подвижного объекта с априори неформализованной внешней средой. Основное отличие данного метода от традиционных подходов заключается в том, что искомая траектория формируется путем физического моделирования на нейронной сети процесса афферентного синтеза, что обеспечивает естественный характер движения. Критически важным аспектом является высокое быстродействие как системы технического зрения, так и ней- ронной сети, что позволяет встроенной систе- ме управления оперативно реагировать на появление динамических препятствий, обеспечивая их своевременный и безопасный обход [7].

Рассмотренные методы решают задачу на- хождения маршрута полета только на плоскости и относительно одного заданного критерия. Однако возможность построения маршрута полета БпЛА в трехмерном пространстве относительно любого из критериев позволит повысить точность определения маршрута.

Результаты анализа существующих методов построения маршрута полета БпЛА позволили сделать вывод, что метод навигационного гра- фа является наиболее подходящим для опре- деления маршрута полета в трехмерном про- странстве [8]. Он позволяет спрогнозировать возможные маршруты полета на основе предварительно обработанных данных о препятствиях и определить маршрут, учитывая различные факторы, такие как время полета, расстояние, ограничения на высоту полета БпЛА.

Для построения трехмерного навигационного графа необходимо представить препятствия искусственного и естественного происхождения в трехмерном пространстве [9, 10]. Одним из способов такого представления может быть функционально-воксельный метод (ФВМ),  который представляет собой инновационный подход к решению задач, связанных с интегральными вычислениями для объектов, заданных аналитическими моделями.

Традиционные методы описания геометрических моделей через интегральные уравнения сталкиваются с серьезными трудностями при работе со сложными или неявными уравнениями. Для таких случаев применяются различные виды аппроксимации, включая численное интегрирование и дифференцирование. Одна- ко сложная геометрия модели требует разработки специальных алгоритмов разбиения на более простые элементы, что существенно усложняет процесс вычислений.

Так, ФВМ предлагает принципиально новый подход к решению данных проблем. Его основные преимущества включают

– регулярность и непрерывность области рассматриваемых точек;

– возможность работы с многомерным пространством;

– высокую точность моделирования;

– эффективное решение задач с неявными или сложными аналитическими выражениями.

В основе ФВМ лежит принцип линейной аппроксимации пространства функции для вычисления его локальных геометрических характеристик, которые являются коэффициентами локальной функции, аппроксимирующей малыми приращениями окрестность исходной функции геометрического объекта.

Классическое уравнение прямой в неявном виде выглядит как

ax + by + c = 0.

Делением на норму вектора нормали  данное уравнение может быть приведено к нормализованной форме:

nxx + nyy = p,

где  – единичный вектор нормали (nx, ny Î [–1, 1]); p – расстояние от прямой до начала координат.

Локальная компьютерная геометрия позволяет описать геометрический объект с помощью однотипных локальных характеристик. Компоненты нормали (nx, ny) являются параметрами наклона прямой на плоскости, а параметр p не может влиять на наклон прямой,  он лишь обеспечивает ее сдвиг относительно начала координат, а значит, его нельзя считать локальной характеристикой.

Так как локальная функция зависит только от локальных геометрических характеристик, уравнение вида

nxx + nyy = 0

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

Под локальной геометрической моделью следует понимать упорядоченное множество локальных функций, описывающих исходную функцию вида 𝑓(𝑥𝑛) = 0 в каждой точке заданной области.

Локальные геометрические характеристики могут быть представлены в виде графического образа-модели (М-образа), который отображает одну из характеристик функции и может быть представлен в виде последовательно организованного пространства точек с целочисленными координатами.

Метод находит широкое применение в различных областях:

– инженерные расчеты;

– компьютерное моделирование;

– геометрическое моделирование;

– решение интегральных физических задач;

– дифференцирование и интегрирование алгебраических функций.

Представление с помощью ФВМ препятствий искусственного и естественного происхождения в моделирующих комплексах военного назначения позволит повысить точность определения маршрута полета БпЛА.

Исходными данными для функциональной модели геометрического описания препятствий естественного происхождения (рис. 1) являются цифровая карта местности и значения высот рельефа (матрица рельефа). Далее на основе ФВМ [12] задается уравнение плоскости четвертого порядка, так как препятствия строятся в трехмерном пространстве, вычисляются коэффициенты an заданного уравнения, которые затем нормируются четырехкомпонентной нормой N4.

Локальные геометрические характеристики вычисляются по следующим формулам:

Тогда функциональное описание препятствий естественного происхождения в данной методике рельефа местности имеет вид

f(x,y,z) = n1х+n2у+n3z+n4 = 0,

где x, y, z – координаты точки в пространстве.

Одним из свойств такого представления области функции является ее предикатное проявление в каждой точке относительно знака ее значений. Существует возможность выделения нулевой, положительной и отрицательной областей значений функции.

Для выделения области полета БпЛА с учетом рельефа местности сначала рассчитывается высота рельефа zr в заданной точке пространства:

Чтобы определить, относится ли заданная точка к рельефу местности или к свободной области пространства, вычисляется значение функции u в данной точке пространства:

где z – заданное значение высоты в трехмерном пространстве.

Построение области полета БпЛА происходит по правилу: если функция принимает положительное значение или ноль, то точка v не принадлежит области полета БпЛА, а если функция принимает отрицательное значение, то принадлежит. Следовательно, все точки про- странства, где функция отрицательная, являются вершинами графа.

В функциональной модели геометрического описания препятствий искусственного происхождения (рис. 2) добавляется пятая нормаль n5, так как учитываются не только координаты в трехмерном пространстве, но и угол вращения зон обнаружения, поражения или подавления.

Функция области полета БпЛА с учетом препятствий искусственного происхождения имеет вид

Значение функции в каждой точке пространства вычисляется по следующей формуле:

Построение области полета БпЛА с учетом препятствий искусственного происхождения осуществляется по тому же правилу, что и построение области полета БпЛА с учетом рельефа местности.

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

Выводы

Для повышения точности определения маршрута полета БпЛА необходимо формировать трехмерный навигационный граф, который позволит обрабатывать данные о препятствиях и определять маршрут, учитывая маневренные возможности БпЛА. Современные методы определения маршрутов полета не позволяют в полной мере оценить рельеф местности в совокупности с препятствиями искусственного и естественного происхождения в трехмерном пространстве. Формирование функциональных моделей препятствий позволит обработать все рассматриваемое пространство  и построить трехмерный навигационный граф возможных маршрутов полета БпЛА.

Список литературы

1. Yakovlev K., Andreychuk A. Towards time-optimal any-angle path planning with dynamic obstacles. Proc. ICAPS, 2021, vol. 31, no. 1, pp. 405–414. doi: 10.1609/icaps.v31i1.15986.

2. Vailland G., Gouranton V., Babel M. Cubic bezier local path planner for non-holonomic feasible and comfortable path generation. Proc. IEEE ICRA, 2021, pp. 7894–7900. doi: 10.1109/ICRA48506.2021.9560854.

3. Kontoudis G.P., Vamvoudakis K.G. Kinodynamic motion planning with continuous-time Q-learning: An online, model-free, and safe navigation framework. Proc. IEEE Transactions on Neural Networks and Learning Systems, 2019, vol. 30, no. 12, pp. 3803–3817. doi: 10.1109/TNNLS.2019.2899311.

4. Панкова А.Е., Ищенко М.А., Ченцов А.Е. Анализ существующих методов построения маршрутов полета беспилотного летательного аппарата // Вестн. ЯВВУ ПВО. 2023. № 5. С. 91–98.

5. Казаков К.А., Семенов В.А. Обзор современных методов планирования движения // Тр. ИСП РАН. 2016.  Т. 28. № 4. С. 241–294. doi: 10.15514/ISPRAS-2016-28(4)-14.

6. Панкова А.Е., Зубкова А.В. Подходы к формированию навигационного графа // Вестн. ЯВВУ ПВО. 2024.  № 5. С. 96–101.

7. Белоглазов Д.А., Гузик В.Ф., Косенко Е.Ю. и др. Интеллектуальное планирование траекторий подвижных объектов в средах с препятствиями. М.: ФИЗМАТЛИТ, 2014. 304 с.

8. Горкавенко В.С., Шуршев В.Ф. Модель автоматизированного построения навигационного графа пользовательского интерфейса мобильного приложения // Прикаспийский журнал: управление и высокие технологии. 2020. № 3. С. 40–52.

9. Толок А.В., Сычева А.А. Функционально-воксельное моделирование областей столкновения роботов // Управление большими системами: тр. Всерос. школы-конф. молодых ученых. 2021. С. 361–374.

10. Толок А.В., Толок Н.Б. Функционально-воксельное моделирование алгоритма движения к цели на основе R-функций // Проблемы управления. 2024. № 5. С. 49–56.

References

1. Yakovlev, K., Andreychuk, A. (2021) ‘Towards time-optimal any-angle path planning with dynamic obstacles’, Proc. ICAPS, 31(1), pp. 405–414. doi: 10.1609/icaps.v31i1.15986.

2. Vailland, G., Gouranton, V., Babel, M. (2021) ‘Cubic bezier local path planner for non-holonomic feasible and comfortable path generation’, Proc. IEEE ICRA, pp. 7894–7900. doi: 10.1109/ICRA48506.2021.9560854.

3. Kontoudis, G.P., Vamvoudakis, K.G. (2019) ‘Kinodynamic motion planning with continuous-time Q-learning: An online, model-free, and safe navigation framework’, Proc. IEEE Transactions on Neural Networks and Learning Systems, 30(12), pp. 3803–3817. doi: 10.1109/TNNLS.2019.2899311.

4. Pankova, A.E., Ishchenko, M.A., Chentsov, A.E. (2023) ‘Analysis of the existing UAV's flight path modeling methods’, Bull. of the Yaroslavl Higher Military School of Air Defense: Sci. J., (5), pp. 91–98 (in Russ.).

5. Kazakov, K.A., Semenov, V.A. (2016) ‘An overview of modern methods for motion planning’, Proc. ISP RAS, 28(4), pp. 241–294 (in Russ.). doi: 10.15514/ISPRAS-2016-28(4)-14.

6. Pankova, A.E., Zubkova, A.V. ‘Approaches to forming a navigation graph’, Bull. of the Yaroslavl Higher Military School of Air Defense: Sci. J., (5), pp. 96–101 (in Russ.).

7. Beloglazov, D.A., Guzik, V.F., Kosenko, E.Yu. et al. (2014) Intelligent Path Planning of Moving Objects in Obstacle Environments. Moscow, 304 p. (in Russ.).

8. Gorkavenko, V.S., Shurshev, V.F. (2020) ‘Model of automated construction of the navigation graph of the user interface of a mobile application’, Caspian J.: Management and High Tech., (3), pp. 40–52 (in Russ.).

9. Tolok, A.V., Sycheva, A.A. (2021) ‘Functional-voxel modeling of robot collision areas’, Managing Large Systems: Proc. All-Russian School-Conf. of Young Scientists, pp. 361–374 (in Russ.).

10. Tolok, A.V., Tolok, N.B. (2024) ‘Functional-voxel modeling of the target-moving algorithm based on R-functions’, Control Sci., (5), pp. 49–56 (in Russ.).