Выявление коллизий и определение границ безопасного сближения траекторий группы беспилотных летательных аппаратов на основе условной оптимизации

Язык труда и переводы:
УДК:
623.746:519.857
Дата публикации:
21 сентября 2021, 15:08
Категория:
В7. Динамика движения и управление полетом космических и летательных аппаратов
Авторы
Титков Иван Павлович
МГТУ им. Н.Э. Баумана
Аннотация:
Рассмотрена задача выявления коллизий и определения границ безопасного сближения прямолинейных (отрезков) и кусочно-линейных (ломаных) траекторий группы беспилотных летательных аппаратов. Для выявления коллизий для пары прямолинейных траекторий определено и проверено расстояние между отрезками. Для определения границ безопасного сближения поставлена задача условной оптимизации и решается аналитически с применением метода множителей Лагранжа об определении точки, принадлежащей первому отрезку и располагающейся на заданном расстоянии от второго отрезка. Предложено аналитическое решение для параллельных траекторий. Для кусочно-линейных траекторий выполнена декомпозиция до прямолинейных траекторий с последующим агрегированием определенных границ безопасного сближения. Приводятся примеры применения предлагаемых способов определения границ безопасного сближения. Исследована производительность реализации предложенных методов и оценивается длительность вычислений.
Ключевые слова:
группа БПЛА, траекторная безопасность, угроза столкновений, предупреждение столкновений, условная оптимизация, метод множителей Лагранжа
Основной текст труда

Введение

При решении задач управления группой беспилотных летательных аппаратов (БПЛА) возникает необходимость в обеспечении траекторной безопасности. Одним из способов обеспечения траекторной безопасности является предупреждение столкновений [1, 2]. Для этого необходимо выявлять коллизии на опорных траекториях БПЛА (недопустимое сближение траекторий или столкновение, зона возможного столкновения воздушных судов [3]) и определить границы безопасного сближения траекторий (расстояния безопасного расхождения воздушных судов [3]). Эти данные возможно использовать для принятия решений о продолжении движения вдоль опорной траектории [4] или планирования маневров уклонения [5, 6].

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

Выявление коллизий и определение границ безопасного сближения прямолинейных траекторий

Для выявления коллизий для пары прямолинейных траекторий (отрезков) необходимо определить и проверить расстояние между отрезками. Задача определения расстояния между отрезками является известной и решенной. Если найденное расстояние менее заданного безопасного расстояния (выявлена коллизия), то целесообразно определить границы безопасного сближения прямолинейных траекторий.

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

Пара прямых задана с помощью векторно-параметрических уравнений:

{\begin{array}{*{20}{c}}{{p_{1}}\left({t_{1}}\right)=\left\{{\begin{array}{l}x_{1}^{}\left({t_{1}}\right)=x_{1}^{S}+{m_{1}}{t_{1}},\\y_{1}^{}\left({t_{1}}\right)=y_{1}^{S}+{n_{1}}{t_{1}},\\z_{1}^{}\left({t_{1}}\right)=z_{1}^{S}+{p_{1}}{t_{1}},\end{array}}\right.}&{{p_{2}}\left({t_{2}}\right)=\left\{{\begin{array}{l}x_{2}^{}\left({t_{2}}\right)=x_{2}^{S}+{m_{2}}{t_{2}},\\y_{2}^{}\left({t_{2}}\right)=y_{2}^{S}+{n_{2}}{t_{2}},\\z_{2}^{}\left({t_{2}}\right)=z_{2}^{S}+{p_{2}}{t_{2}},\end{array}}\right.}\end{array}}

где p_{i}^{S}=\left({x_{i}^{S},y_{i}^{S},z_{1}^{S}}\right) — точка начала i -й прямой; p_{i}^{F}=\left({x_{i}^{F},y_{i}^{F},z_{i}^{F}}\right) — точка конца i -й прямой; m_{i}^{}=x_{i}^{F}-x_{i}^{S} , n_{i}^{}=y_{i}^{F}-y_{i}^{S} , p_{i}^{}=z_{i}^{F}-z_{i}^{S} — компоненты направляющего вектора {s_{i}}=\left({{m_{i}},{n_{i}},{p_{i}}}\right) i -й прямой; {t_{i}}\in \left({-\infty ,+\infty }\right) — параметр i -й прямой.

Необходимо найти точку p_{1}^{d}\subset {p_{1}}\left({t_{1}}\right) , принадлежащую первому отрезку и удаленную от второго отрезка на заданное расстояние r_{d}^{} : \left|{p_{1}^{d},{p_{2}}\left({t_{2}}\right)}\right|=r_{d}^{} .

Функция расстояния между точкой первого отрезка и вторым отрезком:

r\left({t_{1}}\right)={\frac {\left|{\left({{\bar {p}}_{2}^{S}-{\bar {p}}_{2}^{F}}\right)\times \left({{{\bar {p}}_{1}}\left({t_{1}}\right)-{\bar {p}}_{2}^{F}}\right)}\right|}{\left|{\left({{\bar {p}}_{2}^{S}-{\bar {p}}_{2}^{F}}\right)}\right|}}. Для нахождения точек на первом отрезке, удаленных от второго отрезка на заданное расстояние r_{d} , необходимо решить параметрическое уравнение {r^{2}}\left({t_{1}}\right)-r_{d}^{2}=0 . Решение уравнения может быть представлено в виде задачи нахождения наименьшего значения функции f\left({t_{1}}\right) : f\left({t_{1}}\right)={r^{2}}\left({t_{1}}\right)-r_{d}^{2} .

Соответствующая точка на прямой: {\begin{array}{*{20}{c}}{t_{1}^{d}=\mathop {\arg } \limits _{t_{1}}\mathop {\min } \limits _{D}f\left({t_{1}}\right),}&{p_{1}^{d}={p_{1}}\left({t_{1}^{d}}\right)}\end{array}} . Точка принадлежит отрезку при условии t_{1}^{d}\in \left[{0,1}\right] .

Для получения аналитического решения используется метод множителей Лагранжа с ограничением типа равенство: \left\{{\begin{array}{l}{t_{1}}\to \min ,\\f\left({t_{1}}\right)=0.\end{array}}\right. Функция Лагранжа имеет вид L\left({{t_{1}},{\lambda _{0}},{\lambda _{1}}}\right)={\lambda _{0}}{t_{1}}+{\lambda _{1}}f\left({t_{1}}\right) , где {\lambda _{0}} и {\lambda _{1}} — множители Лагранжа, одновременно не равные нулю.

Необходимо решить систему уравнений: \left\{{\begin{array}{l}{\frac {\partial L\left({{t_{1}},{\lambda _{0}},{\lambda _{1}}}\right)}{\partial {t_{1}}}}=0,\\f\left({t_{1}}\right)=0.\end{array}}\right. Символьная запись аналитического решения может быть получена, например, с использованием пакета символьных вычислений программного комплекса MATLAB и не приводится из соображений объема. Уравнение f\left({t_{1}}\right)=0 квадратное, поэтому решение содержит пару корней t_{1}^{1} , t_{1}^{2} . На рис 1. показан пример определения точки на первом отрезке, удаленной от второго отрезка на заданное расстояние.

Рис. 1. Пример определения точки на первом отрезке, удаленной от второго отрезка на заданное расстояние (прямые скрещиваются, вид сверху)

В случае параллельных или близких к параллельным траекториям возникает проблема деления на ноль в знаменателе аналитического решения. Для устранения этой проблемы возможно использовать следующий алгоритм. На первом шаге необходимо определить ближайшую точку второго отрезка к началу первого отрезка — начало или конец второго отрезка. На втором шаге необходимо определить пару точек на первом отрезке, удаленных от ранее найденной точки на втором отрезке на заданное расстояние. Эта пара точек может быть найдена аналитически в результате решения задачи о пересечении первого отрезка и сферы с центром в начале или конце второго отрезка заданного безопасного радиуса. Для этого достаточно решить уравнение {\left({{x_{1}}\left({t_{1}}\right)-{x_{0}}}\right)^{2}}+{\left({{y_{1}}\left({t_{1}}\right)-{y_{0}}}\right)^{2}}+{\left({{z_{1}}\left({t_{1}}\right)-{z_{0}}}\right)^{2}}=r_{d}^{2} , где {x_{0}}=x_{2}^{S} , {y_{0}}=y_{2}^{S} , {z_{0}}=z_{2}^{S} или {x_{0}}=x_{2}^{F} , {y_{0}}=y_{2}^{F} , {z_{0}}=z_{2}^{F} для начала или конца второго отрезка соответственно. Указанное уравнение квадратное, поэтому его решение содержит пару корней t_{1}^{1} , t_{1}^{2} . Решением задачи является {t_{1}}=\min \left({t_{1}^{1},t_{1}^{2}}\right) .

На рис. 2 представлен пример определения точки на первом отрезке, удаленной от второго отрезка на заданное расстояние, для случая параллельных прямых (вид сверху).

Рис. 2. Пример определения точки на первом отрезке, удаленной от второго отрезка на заданное расстояние, для случая параллельных прямых

На рис. 3 представлен пример выявления коллизий и определения границ безопасного сближения для прямолинейных траекторий.

Рис. 3. Пример выявления коллизий и определения границ безопасного сближения для прямолинейных траекторий

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

Выявление коллизий и определение границ безопасного сближения для кусочно-линейных траекторий

Выявление коллизий для кусочно-линейных (ломаных) траекторий может быть сведено к попарному выявлению коллизий между всеми отрезками всех ломаных. В случае выявления целесообразно определить границы безопасного сближения для пары отрезков, которые войдут в состав границ ломаных. Решение задачи для пары отрезков получено выше. На рис. 4 представлен пример определения границ безопасного сближения для трех кусочно-линейных (ломаных) траекторий.

Рис. 4. Пример определения границ безопасного сближения трех кусочно-линейных (ломаных) траекторий (вид сверху)

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

Вычислительный эксперимент

Вычислительный эксперимент предназначен для определения и сравнения быстродействия вычислений предложенного способа выявления коллизий и определения границ безопасного сближения траекторий. Вычислительный эксперимент проведен на персональном компьютере с процессором Intel Core i7 4790k и 32 Гб оперативной памяти под управлением операционной системы Windows 7. Указанные алгоритмы реализованы с использованием языка программирования C++, использованы функции класса FMath игрового движка Unreal Engine (UE) 4 (сборка Development Editor).

Во время проведения вычислительного эксперимента измеряется количество вычислений задач за 1 с, решение которых лежит в основе выявления коллизий и определения границ безопасного сближения траекторий; точки и безопасное расстояние выбираются случайным образом при каждом решении задачи в ограниченном диапазоне значений. Задачи и результаты измерений представлены в таблице.

Результаты измерений количества решений задач в секунду

Задача

Решения в секунду, млн

Определение расстояния между двумя точками (UE FVector::Dist)

4,8 

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

2,4 

Определение ближайших точек пары отрезков (UE FMath::SegmentDistToSegmentSafe)

2,1 

Определение расстояния между точкой и отрезком (UE FMath::PointDistToSegment)

2,2

Определение точки пересечения отрезка и сферы (по предложенному аналитическому решению уравнения)

2,4 

Выявление пересечения отрезка и сферы (UE FMath::LineSphereIntersection)

3,1 

Выявление коллизий для N прямолинейных траекторий требует N\cdot \left({N-1}\right) определений ближайших точек на паре отрезков и N\cdot \left({N-1}\right) определений расстояния между найденными ближайшими точками, общая длительность составит T=N\cdot \left({N-1}\right)\cdot \left({{t_{1}}+{t_{3}}}\right) , где {t_{1}} , {t_{3}} — длительности одного решения задачи 1 и 3 соответственно.

Количество и длительность вычислений для определения границ безопасного сближения N прямолинейных траекторий зависит от количества параллельных траекторий. Для оценки возможно использовать наибольшую из длительностей N\cdot \left({N-1}\right)\cdot {t_{2}} для не параллельных траекторий или N\cdot \left({N-1}\right)\cdot \left({{t_{3}}+{t_{5}}}\right) для параллельных траекторий, где {t_{2}} , t_{3} , t_{5} — длительность одного решения задачи 2, 3 и 5 соответственно.

Количество и длительность вычислений для N_{L} кусочно-линейных (ломаных) траекторий зависит от количества кусочно-линейных участков (звеньев) каждой траектории. Для грубой оценки сверху возможно использовать полученные выше зависимости при N=\max \left({{\bf {N}}_{L}}\right) , {{\bf {N}}_{L}}=\left({{N_{L_{1}}},...,{N_{L_{N}}}}\right) , где {N_{L_{i}}} — количество кусочно-линейных участков (звеньев) i -й траектории.

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

Заключение

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

Литература
  1. Постановление Правительства РФ от 11 марта 2010 г. № 138 «Об утверждении Федеральных правил использования воздушного пространства Российской Федерации». URL: https://ivo.garant.ru/#/document/197839 (дата обращения 21.09.2012).
  2. International Civil Aviation Authority. Manual on Remotely Piloted Aircraft Systems (RPAS). International Civil Aviation Organization, 2015. 166 p. URL: https://skybrary.aero/sites/default/files/bookshelf/4053.pdf (дата обращения 23.06.2021).
  3. ГОСТ 25491–82. Системы предупреждения столкновения воздушных судов. Термины и определения. М.: Издательство стандартов, 1983. 7 с.
  4. Titkov I.P., Karpunin A.A. Collision-Aware Formation Assignment of Quadrotors // Procedia Computer Science. Proceedings of the 14th International Symposium «Intelligent Systems – 2021», INTELS 2020. Moscow, December 14–16, 2020, Lomonosov Moscow State University, Federal Research Center “Computer Science and Control” of RAS, RUDN University, St. Petersburg Electrotechnical University “LETI”, and Bauman Moscow State Technical University. Procedia Computer Science (Elsevier). 2021. Vol. 186. Pр. 727–735. DOI:10.1016/j.procs.2021.04.195
  5. Воронов Е.М., Карпунин А.А. Обеспечение траекторной безопасности в задаче облета динамической круговой зоны // Наука и образование: научное издание МГТУ им. Н.Э. Баумана. 2011. № 12. URL: http://technomag.edu.ru/doc/280873.html (дата обращения 23.06.2021).
  6. Воронов Е.М., Карпунин А.А. Обеспечение траекторной безопасности в задаче облета статичной круговой зоны // Вестник Российского университета дружбы народов. Инженерные исследования. 2012. № 1. С. 58–70. URL: http://journals.rudn.ru/engineering-researches/article/view/5168/4622 (дата обращения 23.06.2021).
Ваш браузер устарел и не обеспечивает полноценную и безопасную работу с сайтом.
Установите актуальную версию вашего браузера или одну из современных альтернатив.