ИССЛЕДОВАНИЕ МЕТОДОВ ПЛАНИРОВАНИЯ ТРАЕКТОРНОГО ДВИЖЕНИЯ БЕСПИЛОТНЫХ АППАРАТОВ

Введение

Простые алгоритмы планирования маршрута беспилотных летательных аппаратов (БПЛА) на плоскости неспособны справиться со сложными сценами, содержащими многочисленные объекты с их структурными  ограничениями  и  неопределенностями  воздушной  среды.  Планирование  маршрутов в трехмерных сценах имеет большой потенциал, однако, в отличие от 2D-планирования, становится намного более сложным. Для построения свободного от столкновений пути через загроможденную среду необходим набор специализированных математических инструментов и средств имитационного моделирования [1-3]. Представляется целесообразным в первую очередь дать анализ алгоритмов прокладки маршрутов на плоскости.

Планирование пути

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

В некоторых ситуациях, затраты на взлет могут превосходит затраты на обход препятствия без подъема или спуска с последующим возвратом (при необходимости). Это особенно видно на примере городской среды с небоскребом, где из-за одного здания БПЛА придется подняться на весьма большую высоту. В этом случае более правильным вариантом является облет препятствия.

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

В  настоящей  работе  проводились  эксперименты  с построением  пути  передвижения  БПЛА в ограниченной местности в районе города Переславля-Залесского. Исследуемая сцена представлена на рис.1-3.

На рис.2 указаны начальная (красная) и конечная (зеленая) точки движения БПЛА. Данная область была выбрана из-за наличия в доме арки, что расширяет возможности передвижения БПЛА. Далее приведены результаты тестирования известных алгоритмов планирования пути.

Анализ и тестирование алгоритмов, основанных на выборке

Было выполнение испытание популярного алгоритма RRT (Rapidly exploring Random Trees), обеспечивающего высокую скорость исследования пространства конфигураций, и хорошо зарекомендовавшего себя в задачах большой размерности. Существует множество модификаций данного алгоритма:

– Dynamic Domain RRT (DDRRT) осуществляет распространение маршрутной сети за счет конфигураций, принадлежащих динамической области [5];

– RRT* обеспечивает построение пути с максимальной скоростью движения [6];

– GIRRT уменьшает количество итераций с увеличением ресурсоемкости [7];

– Adaptive RRT [8] учитывает влияние ветра на летательный аппарат.

Пример построения пути алгоритмом RRT* для исследуемой сцены показан на рис.4.


К сожалению, ни один из запусков алгоритма не дал траекторию, проходящую через арку, около которой находится конечная точка маршрута.

Имеются алгоритмы, которые планируют путь в комбинации с дополнительными поисковыми алгоритмами. Одним из примеров алгоритмов данной группы являются диаграммы Воронова, которые по умолчанию строят максимально безопасные пути, так как полученные ребра графа находятся на наибольшем удалении от препятствий. Существует несколько способов построение диаграммы со сложностью от  𝑂(𝑛 ⋅ 𝑙𝑜𝑔(𝑛)) до 𝑂(𝑛4) при построении «в лоб». Пример построения диаграммы для выбранной среды показан на рис.5.

Алгоритм построил маршрут, проходящий через арку, обеспечивающий минимум ресурсоемкости.

В работе [9] диаграммы Воронова были модифицированы для работы с круглыми и невыпуклыми препятствиями. К этой же группе относится PRM с его модификациями: S-PRM [10] и K-PRM [11].

Алгоритмы    на    основе     узлов     представляют     собой     особую     форму динамического программирования [2]. Когда карта или график уже построены, они сначала определяют функцию стоимости, а затем выполняют поиск для выбора минимального по затратам пути. С учетом особенностей летательных аппаратов и критериев оценки, веса у ребер графа могут принимать отрицательные значения. Сюда входят алгоритм Дейкстры, A*, его модификации НСА* [1], Jump Point Search [12], Theta* [13], Lazy Theta* [14], Dynamic A* (D*), D*-Lite [15], Harmony search [16].

Пример построения пути алгоритмом A* для исследуемой сцены показан на рис.6.

Видно, что алгоритм A*, также как и алгоритм Вороного, прошел через арку, однако, построенный путь неоптимален для БПЛА по затратам времени и энергоресурсов из-за частой смены направления движения.

Заключение

Результаты тестирования различных алгоритмов в фиксированной среде (карте) показали, что наилучшими качествами обладает алгоритм Вороного, обеспечивающий безопасность движения БПЛА и оптимальный по затратам времени и энергоресурсов маршрут. Также неплохими качествами планирования обладает алгоритм A*.

*Исследование выполнено при частичной финансовой поддержке РФФИ (проект № 17-29-07003-офи_м «Разработка методов и моделей динамического планирования поведения и иерархического интеллектуального управления движением беспилотных летательных аппаратов в условиях неопределенной среды при ограничениях на вычислительные ресурсы»).

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

1.    Яковлев К.С. Исследование методов и разработка алгоритмов автоматического планирования траектории на плоскости. – Дис. к.ф.-м.н., 2010, Москва. – 184 с.

2. Liang Yang, Juntong Qi, Jizhong Xiao, Xia Yong “A Literature Reviewof UAV 3D Path Planning” // Proceeding of the 11th World Congress on Intelligent Control and Automation (29 June –4 July 2014), 2014. 6 p. DOI: 10.1109/WCICA.2014.7053093.

3.     Лю В. Методы планирования пути в среде с препятствиями (обзор). – Математика и математическое моделирование, №1, 2018, с.15-58.

4.   Семенова Л.Л. Современные методы навигации беспилотных летательных аппаратов. – Наука и образование сегодня, №4, 2018, с.6-8.

5.    Казаков К.А. Семенов В.А. Обзор современных методов планирования движения. – Труды Института системного программирования РАН, Т.28, вып.4, 2016, с.241-294.

6.   Richter C., Bry A., Roy N. Polynomial Trajectory Planning for Quadrotor Flight // Proceedings of the International   Symposium  of  Robotics            Research,            2013.            8 p. URL: https://pdfs.semanticscholar.org/8c76/f1add88df14c59f75818952beaa1ec69f62a.pdf (дата обращения: 14.02.2020).

7.    Пыхтин П.С., Камаев В.А., Крыжановский А.И., Никляев И.Ю., Пыхтин П.С. Планирование траектории движения мобильного робота с использованием градиента функции исследования областей пространства конфигураций // Кибернетика и программирование, №1, 2014, с.48-60. DOI: 10.7256/2306-4196.2014.1.9828.

8.   Doshi A.A., Singh S.P.N., Postula A.J. An Online Motion Planning and Control Strategy for UAVs in Wind using Reduced Order Forward Models. 7 p. URL: http://www.araa.asn.au/acra/acra2013/papers/pap181s1-file1.pdf (дата обращения: 14.02.2020).

9.      Лавренов P.O., Афанасьев И.М., Магид Е.А. Планирование маршрута для беспилотного наземного робота с учетом множества критериев оптимизации, 2016. – Материалы семинара «Беспилотные транспортные средства с элементами искусственного интеллекта», 2016. URL:https://dspace.kpfu.ru/xmlui/bitstream/handle/net/131530/AI_UV_book_2016_10_20.pdf (дата обращения: 14.02.2020).

10.       LAValle S.M. Planning algorithms // Cambridge university press, 2006. 842 p.   URL: http://planning.cs.uiuc.edu/booka4.pdf (дата обращения: 14.02.2020).

11.    Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning // The International Journal of Robotics Research, 2011, 30(7): 846-894.

12.    Harabor D., Grastien A. Improving Jump Point Search // Proceedings of ICAPS 2014. 9 p. URL: https://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-icaps14.pdf (дата обращения: 14.02.2020).

13.    Nash A., Daniel K., Koenig S., Felner A. Theta*: Any-Angle Path Planning on Grids // Journal of Artificial Intelligence Research, 2010, 39: 533-579.

14.    Alex Nash, Sven Koenig, Craig Tovey. Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D // Conference: Proceedings of the Third Annual Symposium on Combinatorial Search, SOCS 2010, Stone Mountain, Atlanta, Georgia, USA, July 8-10, 2010. URL: https://aaai.org/ocs/index.php/SOCS/SOCS10/paper/viewFile/2083/2524 (дата обращения: 14.02.2020).

15.   Jur van den Berg, Dave Ferguson, James Kuffner “Anytime Path Planning and Replanning in Dynamic Environments” // Conference Paper, Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pp.2366-2371, May, 2006.URL: https://www.csd.uoc.gr/~hy475/papers2006/berg_jur_van_den_2006_1.pdf     (дата     обращения: 14.02.2020).

16.    Panov S., Koceski S. Harmony search based algorithm for mobile robot global path planning // International Journal of Advanced Robotic Systems, 2014, 11:144, DOI: 10.5772/58875.