Известия РАН. Теория и системы управления, 2019, № 1, стр. 153-165

ЗАДАЧА ОПЕРАТИВНОЙ ДВУМЕРНОЙ МАРШРУТИЗАЦИИ ГРУППОВОГО ПОЛЕТА БЕСПИЛОТНЫХ ЛЕТАТЕЛЬНЫХ АППАРАТОВ

В. И. Гончаренко a*, Г. Н. Лебедев a, Д. А. Михайлин b

a МАИ (национальный исследовательский ун-т), ИПУ РАН
Москва, Россия

b ГНИИЦ РТ МО РФ
Москва, Россия

* E-mail: vladimirgonch@mail.ru

Поступила в редакцию 28.12.2017
После доработки 24.09.2018

Полный текст (PDF)

Аннотация

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

0. Введение. В связи с широким использованием беспилотных летательных аппаратов (БЛА) для наблюдения наземных объектов задачам маршрутизации движения БЛА неизменно уделяется повышенное внимание. При решении таких задач крайне важна оперативность получения данных об объекте наблюдения. Методы решения задач маршрутизации движения БЛА можно представить двумя классами.

К первому классу относятся эвристические алгоритмы одномерной маршрутизации [16], в том числе с применением [710] нейросетевых технологий. Они позволяют выбирать очередной пункт маршрута, используя данные о пунктах в ближайшей к летательному аппарату окрестности (или “окне обнаружения”), при расширении которой попадание в нее первого пункта означает выбор ближайшего пункта. К этому классу относятся “жадный” алгоритм и алгоритм Дейкстры [1]. Максимальной простотой обладает “жадный” алгоритм, выбирающий очередной i-й пункт с использованием критерия I1 его минимальной дальности rij до обслуживающего j-го БЛА:

(0.1)
${{I}_{1}} = \mathop {\min }\limits_{i,j \in Z} \{ {{r}_{{ij}}}\} .$

Критерий (0.1) не учитывает последствий выбора на будущих участках маршрутного полета, что приводит в ряде случаев к завышенной длине пути.

Алгоритм Дейкстры избавлен от этого недостатка и результаты его маршрутизации ближе к оптимальным из-за более совершенного критерия выбора I2:

(0.2
${{I}_{2}} = \mathop {\min }\limits_{i,j \in Z} \{ {{r}_{{ij}}} + k{{l}_{{ib}}}\} ,$ )
где lib – приближенная оценка оставшегося пути, после обслуживания выбранного i-го пункта, k < 1 – коэффициент относительной значимости последствий, меньший единицы из-за неточности прогнозирования затрат в будущем.

Кроме этого, названным выше алгоритмам присущи следующие недостатки:

в случае группового полета БЛА их действия далеки от оптимальных по критерию минимума пройденного пути;

не все заданные пункты могут попасть в маршрут.

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

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

неясно, как распределить общий состав пунктов на заранее неизвестные отдельные списки одномерных маршрутов для каждого БЛА;

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

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

1. Постановка задачи. Ставится задача оперативного планирования маршрутного полета двух однотипных БЛА на заданной высоте с заданной скоростью при распределении общего множества наблюдаемых наземных пунктов между ними помимо самой маршрутизации. Это необходимо в полетных ситуациях, когда оба БЛА сближаются друг с другом, и для разрешения конфликта нужно особое правило назначения каждого пункта одному из маршрутов, т.е. решается задача оперативного построения на борту каждого БЛА непересекающихся маршрутов [17, 18].

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

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

В формализованном виде постановка решаемой задачи описывается следующим образом.

Дано.

1. Множество неподвижных точечных пунктов наблюдения, координаты их расположения и общее число n (см. табл. 1, это число n = 5), что позволяет сформировать исходную матрицу М0 расстояний между ними, началом 0 и концом (n + 1) маршрутов, согласно методу ветвей и границ.

Таблица 1.

Исходная матрица расстояний М0

0 1 2 3 4 5 6
0 Х 5 8 11 9.4 11.5 Х
1 Х Х 3 6 5.8 6.7 11
2 Х 3 Х 3 5 4.3 8
3 Х 6 3 Х 5.8 3 5
4 Х 5.8 5 5.8 Х 3.5 9.4
5 Х 6.7 4.3 3 3.5 X 5.8
6 Х Х Х Х Х Х Х

2. Принято, что отдельные списки пунктов, обслуживаемых каждым БЛА, отсутствуют.

3. При решении задачи формируется два разомкнутых маршрута горизонтального полета двух БЛА, имеющие заданные общие начальную и конечную точки А и В (рис. 1, точки 0 и 6).

Рис. 1.

Расположение пунктов наблюдения с указанием найденных в конце расчета маршрутов M1 и M2

4. Каждый пункт должен быть обслужен только одним БЛА один раз.

5. Скорости и высоты полета двух БЛА постоянны, одинаковы и заданы.

6. Формируемые при координированном планировании маршруты полета двух БЛА не должны пересекаться.

7. Конечным результатом планирования является получение двумерного маршрута. Под двумерной маршрутизацией понимается выполнение двух операций – операции выбора первоочередного пункта, подлежащего включению в план с помощью одного критерия, и новой операции назначения для этого пункта наиболее “близкого” БЛА с использованием другого особого критерия, учитывающего прогнозируемое движение соседнего БЛА.

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

2. Модификация метода ветвей и границ для решения задачи двумерной маршрутизации. Этот метод применим в сложных полетных ситуациях возможного сближения маршрутов полета, когда их пересечений необходимо избежать [17, 18]. Он состоит в следующем.

1. Расчет проводится на каждом шаге при условии, что при этом для каждого маршрута M1 и M2 формируется своя матрица расстояний М1 и М2, которые совпадают друг с другом в самом начале расчета, и они анализируются поочередно, как показано на рис. 2.

Рис. 2.

Иллюстрация процедуры сокращения размерности матриц расстояния

2. В очередной анализируемой матрице классическим методом выбирается элемент (i, j) минимальной длины.

3. Выполняется новая операция, а именно оценивается близость выбранного элемента к так называемым треугольным моделям аппроксимации двух маршрутов [5, 17], показанных пунктиром на рис. 3. Мерой этой близости являются расстояния m1 и m2 от анализируемого элемента (i, j) до вершин этих треугольных моделей.

Рис. 3.

Треугольные модели аппроксимации двух маршрутов

4. В случае принадлежности элемента (i, j) одному из маршрутов в соответствующей матрице M1 исключаются элементы строки i, столбец j и элемент (i, j), как показано на рис. 2, а в другой матрице M2 – элементы двух строк i и j и двух столбцов i и j, и расчеты повторяются.

5. При этом параметры вершин формируемых треугольных моделей постепенно уточняются, а именно они оцениваются как средние значения координат пунктов, попавших в маршрут, и эти данные попадают в новые столбцы (n + 2) и (n + 3) каждой из двух матриц, как показано на рис. 4.

Рис. 4.

Иллюстрация процедуры постепенного уточнения треугольных моделей аппроксимации маршрутов

Поясним это на примере, приведенном на рис. 4. В самом начале расчета до анализа выбираемых пунктов треугольные модели обоих маршрутов – вырожденные, так как их вершины есть начальный пункт 0, конечный пункт 6 и точки 7 и 8 в середине отрезка (0, 6), и все они лежат на одной прямой. Поэтому координаты точек 7 и 8 равны друг другу:

${{x}_{7}}(0) = 8;\quad {{z}_{7}}(0) = 0;\quad {{x}_{8}}(0) = 8;\quad {{z}_{8}}(0) = 0.$

Далее на первом шаге в результате анализа исходной матрицы М0 находится элемент минимальной длины (1, 2), который присоединяется к любому из маршрутов, например к первому M1. Тогда исходная матрица М0, теряя строку 1 и столбец 2, образует матрицу М1, а теряя две строки и два столбца 1, 2 – образует матрицу М2. Кроме того, корректируется координата вершины первой модели аппроксимации после присоединения элемента (1, 2), имеющего координаты х1 = 6.5 и z1 = 0, в результате чего точка 7 не совпадает, как прежде, с точкой 8, и имеем следующие координаты:

${{x}_{7}}(1) = 0.5(8 + 6.5) = 7.25;\quad {{z}_{7}}(1) = 0;\quad {{x}_{8}}(1) = 8;\quad {{z}_{8}}(1) = 0.$

На втором шаге анализируется полученная до этого матрица М2, в результате чего элементом минимальной длины становится дуга (4, 5), имеющая координаты х2 = 9.5 и z2 = 4. Этот элемент расположен ближе к точке 8 треугольной модели второго маршрута. Поэтому, как и на первом шаге, появляются новые матрицы М1 и М2 и корректируются координаты вершины второй модели аппроксимации (см. на рис. 4 матрицы М1 и М2 на втором шаге):

${{x}_{7}}(2) = 7.25;\quad {{z}_{7}}(2) = 0;\quad {{x}_{8}}(2) = 0.5(8 + 9.75) = 8.75;\quad {{z}_{8}}(2) = 0.5 \cdot 4 = 2.$

На третьем шаге расчеты повторяются, и в результате анализа новой матрицы М1 получаем элемент минимальной длины (2, 3), который присоединяется к маршруту M1, поскольку пункт 2 в него уже включен. Учитывая координаты элемента, равные х3 = 9.5 и z3 = 0, повторно корректируем координаты первой модели:

${{x}_{7}}(3) = \quad(8 + 6.5 + 9.5){\text{/}}3 = 8;\quad {{z}_{7}}(3) = 0;\quad {{x}_{8}}(3) = 8.75;\quad {{z}_{8}}(3) = 2.$

На рис. 4 видно, что по мере продолжения расчетов вершины 7 и 8 треугольных моделей аппроксимации постепенно расходятся.

После третьего шага в результате сокращения размерности матриц М1 и М2 они приобретают вид, показанный на рис. 4. Согласно принятому порядку чередования теперь нужно анализировать матрицу М2, в которой элементы минимальной длины (0, 4) и (5, 6) равноценны и относятся к маршруту M2. Выбрав элемент (0,4), имеющий координаты x4 = 4.7 и z4 = 2.4, получим результат расчета на четвертом шаге и в итоге – два очевидных координированных маршрута (рис. 4):

${{M}_{1}}{\text{: }}0--1--2--3--6;\quad {{M}_{2}}{\text{: }}0--4--5--6.$

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

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

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

На рис. 5 показана найденная с помощью одномерной маршрутизации траектория облета 10 пунктов, расположенных слева и справа от линии 0–11, в силу чего БЛА движется галсами при неоправданно большой длине пути.

Рис. 5.

Траектория полета при одномерной маршрутизации

На рис. 6 приведен результат двумерной маршрутизации, полученный модифицированным матричным методом, при этом общая длина пути и время выполнения полетного задания сократилось примерно в 2 раза. Однако данный метод не пригоден для оперативного планирования на каждом шаге координированного полета двух БЛА на их борту из-за значительной трудоемкости вычислений.

Рис. 6.

Траектории полета при двумерной маршрутизации

3. Логическая схема комплексирования эвристического и матричного алгоритмов двумерной маршрутизации. Все множество возможных полетных ситуаций движения группы БЛА по своим маршрутам можно разбить на три случая, если максимальный радиус R круга или “окна обнаружения” ограничить заданным постоянным значением [5]. В первом случае окна обнаружения любой пары БЛА не пересекаются, а это возможно, если расстояние riζ между этими БЛА больше 2R:

(3.1)
${{r}_{i}}_{\zeta } > {\text{2}}R,$
где i – номер пункта, в котором оказался БЛА1, ζ – номер пункта, в котором оказался БЛА2. Тогда выбор очередных пунктов маршрутов полета этих пар предлагается осуществлять с помощью дважды выполненной одномерной маршрутизации по правилу (0.2).

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

(3.2)
${{r}_{i}}_{\zeta } < R.$

Третьему случаю соответствует условие

(3.3)
$R < {{r}_{i}}_{\zeta } < {\text{2}}R$
и ситуация, приведена на рис. 7 для двух БЛА.

Рис. 7.

Расположение в третьем случае ближайших пунктов 1, 2 и 3, попавших в пересекающиеся окна обнаружения двух БЛА

Первоначальный анализ показывает, что r1 < r2, не учитывая пока местоположение остальных пунктов. Пусть в третьем случае выполняются условие, когда r1 < r2, но m1 > m2, как представлено на рис. 8.

Рис. 8.

Сравнение двух операций оценки близости очередного пункта к самим БЛА и к вершинам треугольных моделей аппроксимации маршрутов

Из рис. 8 видно, что при использовании правила m2 < m1, маршруты M1 и M2 разнесены друг от друга на безопасное расстояние.

Сформулированное правило выбора маршрута с помощью неравенства m2 < m1 отличается от правила “жадного” алгоритма r1 < r2 тем, что позволяет избежать пересечения маршрутов.

Исходя из достоинств сформулированного правила, можно скомплексировать критерий I3 в виде следующей суммы аналогично критерию (0.2), используемому в алгоритме Дейкстры:

(3.4)
${{I}_{3}} = \mathop {\min }\limits_{i,j \in Z} \{ {{r}_{{ij}}} + k{{m}_{i}}\} ,$
где mi – расстояние от анализируемого пункта i до вершины прогнозируемой треугольной модели аппроксимации траектории, найденной при учете всех пунктов, попавших в окно наблюдения БЛАj (в отличие от проанализированных пунктов по матричному методу маршрутизации).

В результате комплексирования эвристического алгоритма по критерию (3.4) и матричного алгоритма можно перечислить следующие правила оперативного планирования в различных полетных ситуациях.

1. Зоны а, б, в – пустые. В этой ситуации операция маршрутизации отсутствует и оба БЛА движутся в заданную конечную точку B маршрута, расширяя при этом радиус окна обнаружения.

2. Зона в – пустая, а также одна из зон а или б – пустая, для которой планирование отсутствует. Для занятой зоны осуществляется одномерная маршрутизация с помощью эвристического алгоритма. Другой БЛА движется в ближайший пункт, не попавший в его окно обнаружения.

3. Зона в содержит хотя бы один или более общие пункты. Тогда независимо от содержания зоны а или б осуществляется двумерная маршрутизация матричным алгоритмом.

Логика различения ситуаций а, б и в определяется группой неравенств:

(3.5)
$\begin{gathered} \left\{ \begin{gathered} {{r}_{{j1}}} < R \hfill \\ {{r}_{{j2}}} < R \hfill \\ \end{gathered} \right.\begin{array}{*{20}{c}} {} \end{array}j = 1,\;...,\;n - {\text{д в у м е р н а я }}\;{\text{м а р ш р у т и з а ц и я }}({\text{о б л а с т ь в }}){\text{;}} \hfill \\ \left\{ \begin{gathered} {{r}_{{j1}}} < R \hfill \\ {{r}_{{j2}}} > R \hfill \\ \end{gathered} \right.\begin{array}{*{20}{c}} {} \end{array}j = 1,\;...,\;n - {\text{о д н о м е р н а я }}\;{\text{м а р ш р у т и з а ц и я }}({\text{о б л а с т ь а }}){\text{;}} \hfill \\ \left\{ \begin{gathered} {{r}_{{j1}}} > R \hfill \\ {{r}_{{j2}}} < R \hfill \\ \end{gathered} \right.\begin{array}{*{20}{c}} {} \end{array}j = 1,\;...,\;n - {\text{о д н о м е р н а я }}\;{\text{м а р ш р у т и з а ц и я }}({\text{о б л а с т ь б }}){\text{.}} \hfill \\ \end{gathered} $

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

Рис. 9.

Блок-схема алгоритма комплексирования операций оперативной маршрутизации для двух БЛА

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

4. Пример планирования облета вокруг Москвы двух БЛА при экологическом мониторинге 30 городов Московской области. В качестве примера было сформировано полетное задание облета двумя БЛА 30 пунктов Московской области при их экологическом мониторинге и максимальном радиусе окна обнаружения R = 50 км (рис. 10).

Рис. 10.

План облета двумя БЛА 30 городов вокруг Москвы при экологическом мониторинге

Поясним действия предложенного подхода для двух отдельных случаев – при использовании только матричного алгоритма и в случае его комплексирования с эвристическим алгоритмом. В первом случае ввиду недопустимо высокой размерности исходной матрицы расстояний 30 × 30 элементов и необходимости превращения замкнутых маршрутов в разомкнутые предлагается следующий прием. Определив наиболее удаленные от начального пункта 1 находящиеся с другой стороны Москвы пункты 16 и 17, зададимся искусственной конечной точкой 31 планируемых четырех разомкнутых маршрутов, расположенной посредине между пунктами 16 и 17, чтобы потом состыковать эти маршруты в два замкнутых. Таким образом, южнее показанной на рис. 10 линии 1–31 необходимо учитывать при двумерной маршрутизации на юге Москвы пункты 2–8 и 12–6 (всего 12), а при двумерной маршрутизации на севере – пункты 9, 10, 17–30 (всего 16), что уже упрощает решение.

Кроме того, разобьем процесс планирования на ряд шагов при использовании на каждом шаге матрицы расстояний между пунктами, попавшими в окна обнаружения двух БЛА радиусом R = 50 км (см. рис. 7). Будем также считать, что в состав всех пунктов на каждом шаге дополнительно включен конечный пункт 31, не попавший в эти окна, а конечным результатом двумерного планирования на одном шаге станут два пункта внутри окна наблюдения, которые будут начальными для следующего шага маршрутизации.

Например, при маршрутизации полета на юге Москвы на первом шаге начало двух маршрутов общее – пункты (1, 1), учитываемые последующие пункты – 2, 3, 11, 31, в результате планирования маршруту M1 соответствует ряд 1–2–3–31, маршруту M2 – ряд 1–11–31. В итоге для следующего шага формируется новая пара начальных пунктов (3, 11), несовпадающих друг с другом.

Затем на юге Москвы следующими парами являются (3, 12), (3, 14), (3, 15), (4, 15), (8, 15), (8, 16) – всего восемь пар с максимальным числом пунктов не более трех, попавших в окна обнаружения на каждом шаге. При планировании полета на севере Москвы образуются пары (1, 1), (27, 28), (10, 22), (9, 18) – всего четыре пары с максимальным числом попавших в области притяжения пунктов не более шести. Сопоставляя размерности матрицы 30 × 30 и матриц, в среднем порядка 5 × 5 можно убедиться, что используемый прием снижает трудоемкость вычислений в 20–30 раз.

Вместе с тем при рассмотрении данного примера удалось установить четыре особенности матричного алгоритма, подтверждающие его эффективность. Первая особенность состоит в том, что на начальных шагах маршрутизации исходный пункт 1 является общим для всех маршрутов, а значит, согласно рис. 7, зоны а и б – пустые, и поэтому все обслуживаемые в зоне в пункты – общие, вследствие чего координация группового полета неизбежна. И все равно в этих случаях формируются два маршрута при полете на юге и два при полете на севере Москвы.

В частности, при полете на юге Москвы две исходные матрицы на первом шаге планирования одинаковы, содержат пункты 2, 3, 11, попавшие в окна обнаружения, и имеют вид, представленный в табл. 2.

Таблица 2.

Исходные матрицы М1 и М2 на первом шаге планирования полета на юге Москвы М1 = М2

1 2 3 11 31
1 Х 48 54 20 190
2 Х Х 17 29 145
3 Х 17 Х 36 132
11 Х 29 36 Х 170
31 Х Х Х Х Х

Формируя нули в каждом столбце и в каждой строке, можно убедиться, что среди них элементом минимальной длины является дуга (1–11), которую можно присоединить к любому из двух маршрутов (их треугольные модели аппроксимации в точке старта одинаковы), например маршруту M1, самому южному из всех, согласно рис. 10. Поэтому, вычеркивая из матрицы М1 строку 1 и столбец 4, а из матрицы М2 – столбцы 1, 4 и строки 1, 4, получим для следующей операции две разные матрицы (см. табл. 3).

Таблица 3.

Матрицы М1 и М2 на втором шаге планирования полета на юге Москвы

Матрица М1 Матрица М2
1 2 3 31 2 3 31
2 Х Х 17 145 2 Х 17 145
3 Х 17 Х 132 3 17 Х 132
11 Х 29 36 170 31 Х Х Х
31 Х Х Х Х

Теперь, анализируя матрицу М2, обнаруживаем в ней элемент минимальной длины (2, 3), что позволяет присоединить его к маршруту M2 и тем самым получить итог в виде двух маршрутов вместо одного:

${{M}_{1}}{\text{: }}1{\text{--}}11{\text{--}}31;\quad {{M}_{2}}{\text{: }}1{\text{--}}2{\text{--}}3{\text{--}}31.$

Как видно на рис. 10, концы этих маршрутов (3–11) образуют пару начальных вершин для следующего шага планирования, а расстояние между ними весьма велико и равно 44. Кроме того, хотя процессы расчета координат вершин треугольных моделей не приводятся ввиду их тривиальности, расстояния между этими вершинами также увеличиваются.

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

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

Третья особенность была обнаружена при планировании координированного полета на юге Москвы, когда в окно обнаружения БЛА1 в ряде случаев не попадает ни один пункт, т.е. зона а – пустая и, значит, матрица М1 отсутствует. Это относится к парам (3, 12), (4, 15), (8, 15). В этом случае для БЛА, не имеющего в области притяжения ни одного пункта, следующим попавшим для обслуживания пунктом является ближайший пункт вне окна обнаружения. Оказывается, что при одиночном анализе единственной матрицы удается приблизиться к ситуации, когда в зоне в появляется общий пункт и матрицы, как и маршруты, раздваиваются.

Четвертая особенность состоит в том, что во всех случаях удалось избежать “перемычек”, особенно при групповом полете на севере Москвы, где, наоборот, много пунктов и нет пустых зон а, б, в ни на одном шаге. В частности, рассматривая самую сложную пару (10–22), включающую наблюдение пунктов 9, 18, 19, 20, 21, можно убедиться, что элемент (19–10), играющий роль перемычки между двумя маршрутами согласно, рис. 10, не попадает ни в один из планируемых маршрутов. Поэтому после присоединения элементов (21–20), (20–19) и (18–31) к маршруту M2 и элементов (10–9) и (9–31) к маршруту M1 получаем окончательный ответ:

${{M}_{1}}{\text{: }}10{\text{--}}9{\text{--}}31;\quad {{M}_{2}}{\text{: }}22{\text{--}}21{\text{--}}20{\text{--}}19{\text{--}}18{\text{--}}17.$

Теперь остается состыковать все четыре разомкнутых маршрута, избавившись от искусственной точки 31. Соединим по критерию ближайших расстояний пункт 16 с пунктом 1, а пункт 8 с пунктом 9, чтобы получить два замкнутых непересекающихся маршрута M1 и M2. Кроме того, для повышения безопасности группового полета наметим вылет одного БЛА на юг, а другого – на север Москвы, чтобы они приблизились друг к другу всего один раз.

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

Рассмотрим теперь решение данного примера для второго случая комплексирования матричного и эвристического методов – с помощью модифицированного алгоритма. Оказывается, что среди 12 перечисленных пар пустая зона в допускает автономное одномерное планирование в пяти случаях для полетов на юге от Москвы, а именно в пяти парах – (3, 12), (3, 14), (3, 15), (4, 15), (8, 15). Поэтому при использовании модифицированного алгоритма Дейкстры с помощью критерия (3.5) удается еще сократить общие вычислительные затраты: в 1.7 раза по сравнению с первым случаем и в 40–50 раз по сравнению с полноразмерным матричным решением задачи.

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

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

Наряду с выбором нужного элемента маршрута введена новая операция выбора того маршрута, который должен этот элемент присоединить на основе оценки близости через расстояние от анализируемого элемента до центра притяжения треугольной модели аппроксимации траекторий полета каждого БЛА. Результатом применения матричного метода являются разведение центров притяжения маршрутов в разные стороны, а затем – оценка положения выбираемого элемента матриц относительно аппроксимируемых треугольных траекторий, что позволяет избежать их лишних пересечений. Рассмотренные примеры показывают, что предложенный подход позволяет получить выигрыш в 1.5–2 раза по времени выполнения полетного задания по сравнению с одномерной маршрутизацией.

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

  1. Левитин А.В. Алгоритмы. Введение в разработку и анализ. М.: Вильямс, 2006. 576 с.

  2. Андреев М.А., Миллер А.Б., Миллер Б.М., Степанян К.В. Планирование траектории беспилотного летательного аппарата в сложных условиях при наличии угроз // Изв. РАН. ТиСУ. 2012. № 2. С. 166–176.

  3. Vian J., Moore J. Trajectory Optimization with Risk Minimization for Military Aircraft // AIAA J. Guidance. 1989. V. 12. № 3. P. 311–317.

  4. Zadeh S.M., Powers D., Sammut K. Optimal Route Planning with Prioritized Task Scheduling for AUV Missions Article, University, Adelaide, SA5042, Australia, 2016. P. 1–8.

  5. Lebedev G., Goncharenko V., Mikhaylin D., Rumakina A. Aircraft group coordinated flight route optimization using branch-and-bound procedure in resolving the problem of environmental monitoring // ITM Web of Conferences. V. 10 Seminar on Systems Analysis. Moscow, Russia, February 14–15, 2017. Published online: Les Ulis, France, 2017.

  6. Лебедев Г.Н., Румакина А.В. Система логического управления обхода препятствий беспилотным летательным аппаратом при маршрутном полете // Тр. МАИ: электронный журнал. 05.10.2015. Вып. № 83. URL: http://mai.ru//upload/iblock/8c0/lebedev-rumakina_rus.pdf.

  7. Лебедев Г.Н., Мирзоян Л.А. Нейросетевое планирование действий по облету наземных объектов группой летательных аппаратов // Авиакосмическое приборостроение. 2005. № 12. С. 41–47.

  8. Лебедев Г.Н., Мирзоян Л.А., Ефимов А.В. Нейросетевое планирование групповых действий ЛА при наблюдении заданной группы подвижных объектов // Мехатроника, автоматизация, управление. 2009. № 11. С. 60–65.

  9. Лебедев Г.Н., Румакина А.В. Нейросетевое планирование маршрута разновысотного полета беспилотного летательного аппарата // Авиакосмическое приборостроение. 2014. № 5. С. 3–8.

  10. Лебедев Г.Н., Гончаренко В.И., Румакина А.В. Нейросетевая двумерная маршрутизация полета летательных аппаратов с помощью модифицированного метода ветвей и границ // Нейрокомпьютеры: разработка, применение. 2017. № 7. С. 49–57.

  11. Беллман Р. Динамическое программирование. М.: Изд-во иностр. лит., 1961. 400 с.

  12. Мельников А.В., Гайдай В.А., Рогозин Е.А. Построение оптимальной траектории полета беспилотного летательного аппарата при выполнении задач поиска // Вестн. Воронежск. ин-та МВД России. 2017. № 1. С. 52–62.

  13. Лебедев Г.Н., Зо Мин Тайк. Синтез оптимального управления боковым движением воздушных или речных судов при пересечении их маршрутов под произвольным углом // Мехатроника, автоматизация, управление. 2014. № 5. С. 61–68.

  14. Гончаренко В.И., Горченко Л.Д. Организация маневрирования аэробаллистических летательных аппаратов в условиях противодействия // Изв. РАН. ТиСУ. 2017. № 3. С. 170–183.

  15. Кузин Л.Т. Основы кибернетики: в 2-х т. М.: Энергия, 1973. 576 с.

  16. Гришанин Ю.С., Лебедев Г.Н., Липатов А.В., Степаньянц Г.А. Теория оптимальных систем. М.: МАИ, 1999. 317 с.

  17. Лебедев Г.Н, Гончаренко В.И., Румакина А.В. Модификация метода ветвей и границ для двумерной маршрутизации координированного полета группы летательных аппаратов // Мехатроника, автоматизация, управление. 2016. Т. 17. № 11. С. 783–791.

  18. Гончаренко В.И., Лебедев Г.Н., Михайлин Д.А., Хахулин Г.Ф. Информационная система непрерывного контроля безопасности полета группы воздушных судов при их сближении // Изв. вузов. Авиационная техника. 2018. № 2. С. 117–123.

Дополнительные материалы отсутствуют.