Планирование полета группы беспилотных летательных аппаратов

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

• · Возможность оперативно получать информацию из труднодоступных и высоко опасных для человека мест.
• · Сниженные расходы на инфраструктуру и обслуживание по сравнению с пилотируемыми аппаратами, применяемыми для тех же целей.

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

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

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

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

Тогда задачу распределения множества БЛА по множеству целей запишем следующим образом. Пусть определен ненаправленный граф G = (V, E), где множество вершин V = {0, 1, …, n} - это множество целей, а E — множество ребер. Вершина с индексом 0 является «базой» с которой стартуют все БЛА представленные множеством Q = {0, 1, … m}. Каждое ребро [i, j] имеет не отрицательный вес cij = cji, причем для метрики весов C (i, j) выполняется неравенство треугольника. Тогда необходимо определить множество маршрутов БЛА с минимальным общим весом таких чтобы: каждый маршрут начинался и заканчивался на «базе», каждая цель посещалась лишь единожды.

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

Генетический алгоритм предполагает формализацию задачи таким образом, что бы ее решение было закодировано в виде вектора (хромосомы). Решение нашей задачи можно записать в вектор размерности n, где n — число целей и каждый элемент вектора может принимать значения от 1 до m, где m — число БЛА. Таким образом, каждой цели ставиться в соответствие лишь один БЛА, а же одному БЛА можно поставить в соответствие несколько целей. Очевидно, что такая запись решения учитывает лишь соответствие набора целей и БЛА, и не учитывает порядок, в котором БЛА их будет облетать. Если использовать в качестве функции приспособленности, какой либо алгоритм решающий задачу коммивояжера, то гамильтоновы циклы, полученные для каждого БЛА этим алгоритмом, будут решением нашей «Транспортной задачи».

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

Рис. 1. Преобразование остовного дерева в маршрут коммивояжера: а) остовное дерево; б) двойной обход дерева; в) маршрут, полученный алгоритмом MST

беспилотный летательный коммивояжер квазиоптимальный Учитывая то, что для нашей метрики весов C (i, j) выполняется неравенство треугольника лучше всего использовать алгоритм MST (Minimum Spanning Tree — минимальное остовное дерево). Основная идея этого алгоритма в том, что на графе определяется минимальное остовное дерево (рис. 1, а), затем строиться маршрут двойного обхода минимального остовного дерева (рис. 1, б), который преобразуется в гамильтонов цикл (рис. 1, в).

Остовное дерево находим алгоритмом Крускала, затем составив маршрут двойного обхода, выбираем произвольно вершину, например вершина 1 (рис. 1, в), из нее идем по двойному маршруту и добавляем в новый маршрут, первый следующий не посещенный город на маршруте двойного обхода. Функция приспособленности, определенная таким образом, будет давать решение не превосходит двух оптимальных.

Для скрещивания хромосом в генетическом алгоритме популяция делится на две части «хорошую» и «плохую», из «хорошей» части с лучшим значением функции приспособленности выбираются по закону равной плотности вероятности две хромосомы, точка кроссовера так же определяется по закону равной плотности вероятности. У полученных двух потомков функции приспособленности сравниваются, потомок с лучшим значением добавляться в популяцию. Количество добавленных хромосом равно количеству хромосом в «плохой» части. После добавления всех хромосом популяция упорядочивается согласно функции приспособленности и отбрасывается столько хромосом с худшим значением приспособленности, сколько их было в «плохой» части. Таким образом, восстанавливается исходный размер популяции. Граница раздела популяции на «хорошую» и «плохую» — настраиваемый параметр.

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

Условием останова алгоритма — процент одинаковых хромосом выше заданного порогового значения.

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

Таблица 1. Результаты тестов.

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

Среднее превышение оптимальных результатов в 28,5% обусловлено тем, что алгоритм минимального остовного дерева (MST) дает квазиоптимальное решение задачи коммивояжера с ошибкой меньшей чем 100%. Для получения более точных результатов использование метода ветвей и границ нецелесообразно из-за его вычислительная сложности. Целесообразно использовать модификацию алгоритма MST, а именно алгоритм Кристофидеса для которого результат заведомо отличается от оптимального не более чем на 50%.