Содержание к диссертации
Введение
ГЛАВА 1. Анализ современных методов и алгоритмов распределенного исследования территории 15
1.1. Методы организации взаимодействия членов группы 15
1.2. Разбиение территории
1.2.1. Алгоритмы кластеризации территории 20
1.2.2. Алгоритм наложения прямоугольной сетки 25
1.2.3. Структуры данных для представления информации о зонах 28
1.3. Задача о назначениях 34
1.3.1. Алгоритмы решения задачи о назначениях 34
1.3.2. Алгоритм последовательного выбора
1.4. Задача коммивояжёра 43
1.5. Выводы 44
ГЛАВА 2. Разработка математической модели БПЛА с видеодатчиком на борту 46
2.1. Состояния БПЛА и видеодатчика 46
2.1.1. Состояния БПЛА 46
2.1.2. Состояния видеодатчика 48
2.1.3. Состояния БПЛА с видеодатчиком 49
2.2. БПЛА с видеодатчиками на борту 51
2.2.1. БПЛА с одним видеодатчиком 51
2.2.2. Описание кадра 53
2.2.3. БПЛА с несколькими видеодатчиками 55
2.3. Сведение задачи обследования территории к задаче о
назначениях 59
2.3.1. Требования к разбиению территории на зоны 59
2.3.2 Сведение задачи обследования территории к задаче о назначениях 61
2.4. Выводы 63
ГЛАВА 3. Разработка системы предполетного квазиоптимального определения маршрутов группы БПЛА 64
3.1. Алгоритм последовательного выбора 64
3.1.1. Представление территории в виде клеточного автомата 64
3.1.2. Время работы БПЛА 67
3.1.3. Расход энергоресурса 70
3.1.4. Алгоритм последовательного выбора 71
3.2. Сравнение функций приемлемости 75
3.2.1. Максимизация ценности 75
3.2.2. Минимизация расстояния 77
3.2.3. Обобщенная функция приемлемости 80
3.3. Двухэтапная оптимизация 82
3.3.1. Идея метода 82
3.3.2. Сначала ценность потом расстояние 83
3.3.3. Сначала расстояние потом ценность 88
3.3.4. Сравнение методов 92
3.4. Минимизация пересечений траекторий 94
3.4.1. Недопущение пересечения траекторий 94
3.4.2. Недопущение прохождения через реперные точки других БПЛА 96
3.4.3. Модифицированный алгоритм последовательного выбора 99
3.5. Метод идентификации столкновений 105
3.5.1. Определение положения БПЛА в произвольный момент времени 105
3.5.2. Идея метода 112
3.5.3. Реализация метода
3.6. Алгоритм синхронизации 117
3.7. Обобщенный алгоритм предполетного определения маршрутов группы БПЛА 122
3.8. Структура системы предполетнего определения маршрутов 124
3.9. Выводы 127
ГЛАВА 4. Проверка системы предполетного определения маршрутов группы БПЛА 129
4.1. Логическая структура системы моделирования 129
4.2. Функциональная модель системы 131
4.3. Программное моделирование системы 134
4.4. Моделирование алгоритмов 137
4.5. Экспериментальная проверка 141
4.6. Выводы 143
Заключение 144
Список литературы
- Алгоритмы кластеризации территории
- Состояния видеодатчика
- Определение положения БПЛА в произвольный момент времени
- Функциональная модель системы
Введение к работе
Актуальность работы. С развитием информационных технологий человечество всё активнее использует робототехнические системы (РБТС) для выполнения различных задач, часто связанных с риском для жизни и здоровья.
Дальнейшее усовершенствование одиночных РБТС сопряжено с рядом неразрешимых проблем: ограничения, накладываемые массогабаритными характеристиками РБТС, ограниченность систем технического зрения (СТЗ) и др.
По этим причинам перспективным направлением развития робототехники является групповая робототехника, заключающаяся в разработке методов и алгоритмов группового взаимодействия роботов в целях решения общей задачи, а также практическая реализация этих методов и алгоритмов. Проблемой группового применения роботов занимаются в ведущих научных центрах мира. Однако исследования в этой области до сих пор так и не дошли до практического применения.
Проблемы групповой робототехники будем рассматривать на примере задачи сбора информации о территории. Пусть имеется некоторая ограниченная территория S, состояние которой изменяется с течением времени. Также имеется N беспилотных летательных аппаратов (БПЛА), на каждом из которых установлен видеодатчик высокого разрешения. Требуется организовать такое взаимодействие группы, при котором за минимальное время будет сфотографирована вся территория. Так как время обследования меньше, чем время изменения состояния территории, то считаем состояние территории квазистатическим.
Поскольку каждый БПЛА оснащается источником энергоресурса, имеющим ограниченную ёмкость, то наибольшую важность приобретает не только обеспечение минимального времени, затрачиваемого на сбор информации, но и обеспечение минимального расхода энергоресурса. Также необходимо гарантировать отсутствие столкновений между БПЛА группы. При использовании группы БПЛА в разведывательных целях важным является обеспечение минимального времени сбора информации об оперативной обстановке на близлежащей территории. Степень разработанности темы. Проблеме группового управления роботами посвящен ряд крупных научно-исследовательских проектов, выполняемых в США, Японии, Германии, Китае и России. Примерами таких проектов являются: «MARTHA» (Франция), «AMADEUS» (Япония), «DARS» (Япония), «Cognitive Colonies» (США), «Тактические мобильные робототехнические системы» (США), «Kiva Systems» (США). Примерами роботизированных систем, автоматизирующих решение
задачи обследования территории, являются: «MSSMP» (США), «MDARS» (США), «Guardium» (Израиль), «Eyedrive» (Израиль), «Платформа-М» (Россия), БПЛА «Груша» (Россия), «Трал Патруль» (Россия) и др.
В России наиболее заметными работами в области группового взаимодействия роботов являются работы Каляева И.А., Капустяна С.Г., Станкевича Л.А., Юревича Е.И., Шалыто А.А., Городецкого В.И., Павловского В.Е., Швецова А.Н., Лохина В.М., Коршунова Ю.М. и других исследователей. В данных работах предлагаются и развиваются: алгоритм коллективного улучшения плана, алгоритм последовательного выбора целей, многоагентный подход к построению систем управления, системы управления на основе нейронных сетей и когнитивных моделей и др.
Проблемами автоматизации обработки и анализа получаемых изображений в России занимаются Алпатов Б.А., Денисов Д.А., Колмогоров Г.С., Крыловецкий А.А., Костоусов В.Б., Кулешов С.В., Путятин Е.П., Бакут П.А. и другие исследователи.
Целью диссертационной работы является разработка алгоритмов предполетного квазиоптимального определения маршрутов группы беспилотных летательных аппаратов, осуществляющих сбор информации о территории с изменяющейся оперативной обстановкой, не допускающих столкновений между членами группы и обеспечивающих сбор информации об оперативной обстановке на близлежащей территории за минимальное время.
Для достижения поставленной цели решаются следующие задачи.
-
Провести анализ существующих алгоритмов разбиения территории на зоны и методов группового взаимодействия РБТС.
-
Разработать математическую модель БПЛА с видеодатчиком на борту.
-
Модифицировать алгоритм последовательного выбора с целью недопущения прохождения по реперным точкам двух или более различных БПЛА при минимальном расходе энергоресурса и обеспечении минимального времени сбора информации об оперативной обстановке на близлежащей территории.
-
Разработать метод идентификации столкновений БПЛА в воздухе.
-
Разработать алгоритм синхронизации движения БПЛА, не допускающий их столкновений.
Методы исследования. В диссертационной работе использованы методы, основанные на элементах теории множеств, аналитической геометрии, теории алгоритмов, теории вероятностей, а также имитационного моделирования.
Научная новизна работы
-
Разработана математическая модель БПЛА с видеодатчиком высокого разрешения на его борту, позволяющая свести задачу обследования территории к задаче о назначениях.
-
Модифицирован алгоритм последовательного выбора. Модифицированный вариант отличается тем, что он минимизирует прохождение по реперным точкам двух или более различных БПЛА.
-
Предложен метод идентификации столкновений БПЛА в воздухе, основанный на проверке минимального расстояния между БПЛА во время работы.
-
Разработан алгоритм синхронизации движения БПЛА, не допускающий их столкновения. При использовании данного алгоритма вероятность столкновения между двумя БПЛА не превышает 0.05%.
Теоретическая значимость работы заключается в её вкладе в развитие группового взаимодействия РБТС.
Практическая значимость работы состоит в том, что разработанные в ней алгоритмы и методы могут быть использованы при проектировании и построении систем управления группой РБТС, осуществляющих сбор информации об ограниченной территории.
Результаты диссертационной работы использовались в НИР «Удар», выполненной в АО «ВНИИ «Сигнал».
Основные положения, выносимые на защиту.
-
Математическая модель БПЛА с видеодатчиком на борту, позволяющая свести задачу обследования территории к задаче о назначениях.
-
Модифицированный алгоритм последовательного выбора, не допускающий прохождения по реперным точкам двух или более различных БПЛА при минимальном расходе времени на обследование близлежащих участков территории.
-
Метод идентификации столкновений БПЛА в воздухе, позволяющий обнаруживать места столкновений членов группы до того, как они приступят к выполнению поставленной задачи.
-
Алгоритм синхронизации движения БПЛА, не допускающий их столкновений.
Достоверность полученных в диссертационной работе
результатов подтверждается корректным использованием
математического аппарата и результатами имитационного моделирования.
Внедрение результатов работы. Материалы диссертации внедрены в процесс разработки систем группового управления роботами в ПАО «НПО «Андроидная техника» и в АО «ВНИИ «Сигнал». Результаты
исследования внедрены в учебный процесс ФГБОУ ВПО «КГТА им. В.А. Дегтярева».
Апробация работы. Основные положения и результаты диссертационного исследования докладывались и обсуждались на: международной конференции (RAIPAP’2013) «Робототехника и искусственный интеллект. Проблемы и перспективы» (Брест, 2013); международной школе-конференции «Тараповские чтения-2013» «Современные проблемы математики, механики, информатики» (Харьков, 2013); международной научно-технической конференции «Современные технологии в системах управления и вооружения» (Ковров, 2013).
Публикации. Основное содержание работы изложено в 13 работах, в том числе в 7 журналах, входящих в перечень ВАК, получено свидетельство об официальной регистрации программы для ЭВМ.
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, четырех приложений. Работа изложена на 179 страницах машинописного текста, содержит 67 рисунков и 4 таблицы. Библиографический список содержит 78 наименований, из них 14 иностранных источников.
Алгоритмы кластеризации территории
В предыдущем разделе было рассмотрено, как территория разбивается на отдельные зоны. Теперь рассмотрим вопрос, как хранить и обрабатывать информацию о зонах (будем называть её матрицей Mz). Эффективность того или иного способа представления матрицы Mz удобно оценивать, исходя из набора основных операций, которые будут выполняться над матрицей Mz: нахождение зоны, внутри которой расположен агент с заданными координатами (x;y); поиск зон соседних по отношению к заданной зоне; добавление новых зон.
Также немаловажной характеристикой используемого способа представления является его эффективность для территорий различного размера и формы.
Наибольшей популярностью пользуются два возможных представления матрицы Mz: 1) в виде двумерного массива, 2) в виде графа. Для каждого из этих способов оценим вычислительную сложность [36] перечисленных выше операций над матрицей Mz.
Самым простым (в отношении программной реализации) является использование двумерного массива. В этом случае каждая зона описывается парой индексов (i; j). Оценим сложность операций над матрицей Mz, представленной в виде двумерного массива.
Операция нахождения зоны, в которой расположен агент с заданными координатами (x; y), выполняется по формулам: size _ zone где (x0;y0) – координаты центра начальной зоны, от которой ведется отсчет других зон; size_zone – размер зон. По этим формулам операции поиска зоны осуществляется за время O(1). Поиск зон, соседних по отношению к заданной зоне z(i)(j), также выполняется за время O(1) по формулам: z_left = z(i-1)(j), (1.3) z_right = z(i+1)(j), z_top = z(i)(j+1), z_bottom = z(i)(j-1), где z_left – зона, расположенная слева от заданной зоны; z_right – зона, расположенная справа от заданной зоны; z_top – зона, расположенная «над» заданной зоной; z_bottom – зона, расположенная «под» заданной зоной.
Добавление новой зоны является затратной операцией и требует перераспределения памяти. Поскольку сложность этой операции прямо пропорциональна размеру матрицы Mz, то её можно оценить как O(size(Mz)).
Более того, добавить в двумерный массив 1 зону нельзя. Если двумерный массив, описывающий матрицу Mz, имеет размер NM, то мы должны добавлять, либо N, либо M новых зон. Это приводит к неэффективному расходу памяти.
Главным недостатком представления матрицы Mz в виде двумерного массива является его низкая эффективность для территорий невыпуклой геометрической формы. Рисунок 1.11 наглядно демонстрирует данную проблему.
Если исследуемая территория S имеет форму, например, как на рис. 1.11(а), то использование двумерного массива для представления матрицы Mz эффективно. Если же исследуемая территория S имеет форму, как на рис. 1.11(б), то использование двумерного массива неэффективно, так как при его использовании появляется большое количество зон, которые не могут быть достигнуты агентом, но требуют памяти, а потому увеличивают размер матрицы Mz.
Представление матрицы Mz в виде графа лишено такого недостатка. При представлении матрицы Mz в виде графа каждой зоне соответствует вершина графа, а смежные вершины описывают соседние зоны. На рис. 1.12 показан пример представления территории в виде графа.
Для того чтобы оценить сложность операций над матрицей Mz, представленной в виде графа, необходимо определиться с формой представления графа. Имеется два стандартных способа представления графа: в виде массива списков смежных вершин и в виде матрицы смежности [4, 32].
Представление графа в виде матрицы смежности неэффективно из-за высокого расхода памяти. При добавлении новой вершины размер матрицы смежности увеличивается с NN до (7V+1)(7V+1), что при большом значении N весьма существенно. Поэтому будем считать, что граф представляется в виде массива списков смежных вершин.
Количество списков равно числу вершин (в нашем случае, зон). А число элементов в каждом списке не превосходит 4, так как у любой зоны не может быть более 4 «соседних» зон. Оценим сложность [36] каждой операции, выполняемой над матрицей Mz.
Задача нахождения зоны, внутри которой расположен агент, решается с помощью алгоритма A [67]. При этом в худшем случае потребуется перебрать все зоны, поэтому его сложность в грубом приближении можно оценить O(size(Mz)). Однако это крайне грубая оценка.
Важным преимуществом представления в виде графа перед двумерным массивом является возможность добавления всего одной зоны, что позволяет более эффективно использовать память. Однако, если геометрическое расстояние между добавляемой зоной и ближайшими к ней ранее известными зонами велико, то необходимо добавлять несколько зон (вершин). На рис. 1.13 показано несколько случаев добавления новой зоны в матрицу Mz («0» - ближайшая известная зона, «1» - добавляемая зона).
Если агент расположен в точке с координатами (х;у) и ближайшая к нему известная зона имеет координаты центра (хо;уо), то число зон, которые необходимо добавить в граф, вычисляется по формуле: При добавлении новых зон неизбежно увеличивается количество списков смежности. Это приводит к необходимости перераспределения памяти. Если массив списков смежности организован в виде связного (или двусвязного) списка, то добавление в него нового списка смежности потребует времени O(1) без необходимости перемещения уже имеющихся списков смежности. Однако добавление каждой новой зоны требует проведения поиска по всем уже известным ранее зонам, что занимает время O(size(Mz)). Проведение поиска необходимо для предотвращения дублирования зон в матрице Mz. Таким образом, суммарная сложность операции добавления зон в матрицу Mz составляет: k O(size(Mz)), где k – количество добавляемых зон. Данная оценка значительно хуже, чем для двумерного массива. Задача нахождения зон, соседних по отношению к заданной зоне благодаря использованию списков смежности ограниченной длины, выполняется за время O(1).
Состояния видеодатчика
Состояние «Покой» является начальным, в нём БПЛА не выполняет поставленную задачу. При этом первые шесть элементов вектора (2.1) постоянны, а седьмой элемент (запас хода) монотонно увеличивается. Это связано с зарядкой аккумуляторных батарей, установленных на борту БПЛА. Он находится в этом состоянии до тех пор, пока перед ним не будет поставлена задача (в виде множества реперных точек и траектории движения по их обходу) и имеющийся запас хода не будет достаточен для выполнения поставленной задачи.
В состоянии «Движение» БПЛА перемещается к очередной реперной точке или к базовой точке, из которой стартовала вся группа. В этом состоянии изменяются все элементы вектора (2.1). Имеющийся запас хода уменьшается. По достижении реперной точки БПЛА переходит в состояние «Съемка». По достижении базовой точки он переходит в состояние «Покой». Достижение базовой точки означает, что либо БПЛА посетил все заданные реперные точки, либо он получил команду на досрочное завершение работы. Также БПЛА может вернуться на базовую точку при обнаружении дефицита энергоресурса.
В состоянии «Съемка» БПЛА осуществляет съемку с помощью установленного на его борту видеодатчика. Теоретически в этом состоянии должен меняться только уровень энергоресурса. Остальные элементы вектора (2.1) должны оставаться константными. На практике же это не так. Данные элементы могут изменяться вследствие воздействия на БПЛА таких факторов, как ветер, несогласованность серводвигателей, удерживающих БПЛА в фиксированном положении, и др. Уровень энергоресурса уменьшается вследствие работы серводвигателей и видеодатчика. После того как БПЛА сделал снимок, он возобновляет движение к следующей реперной точке или базовой точке. Когда БПЛА посетит все заданные реперные точки, он возвращается на базу.
Рассмотрим случай, когда на борту БПЛА установлен один видеодатчик. Обычно его устанавливают под некоторым фиксированным углом к нормали плоскости БПЛА так, как показано на рисунке 2.3.
Предположим, что видеодатчик направлен по курсу БПЛА. Установим ориентацию координатных осей так, как показано на рисунке 2.4.
Линейные координаты фотоаппарата определяются соотношением (2.3) на основе линейных координат БПЛА.
Угловые координаты видеодатчика также выражаются через угловые координаты БПЛА следующим образом: то выражение (2.5) приводится к выражению (2.4). Одновременно с этим, видеодатчик гиростабилизирован, поэтому выражение (2.4) сохраняет свою истинность. Уравнение плоскости видеодатчика запишется в виде: Раскрыв определитель, получим уравнение прямой, проходящей через центр видеодатчика нормально к его плоскости. В каноническом виде оно запишется:
Приведенный выше расчет можно повторить и для других вариантов расположения и ориентации видеодатчика. При этом мы вновь и вновь будем приходить к выражениям (2.7) и (2.8). На основании этого можно утверждать, что выражения (2.7) и (2.8) справедливы практически для любого одиночного расположения видеодатчика на борту БПЛА.
Каждый сделанный кадр удобно представлять в виде вектора: С = (Хс, Yc, Н, De, Д у, а, %х, %у, t), (2.9) где Хс и Yc - координаты центра кадра в плоскости XOY; Н - высота БПЛА, во время снимка, равная его координате Z ; De - половина диагонали кадра (2.8); /3 - угол, значение тангенса которого равно отношению сторон кадра; у - угол крена видеодатчика во время фотоснимка; а - «ценность» кадра; Хх и ХУ - отношение размера фотографируемого участка (в метрах) к размеру кадра (в пикселях) в направлении сторон кадра; t - время фотоснимка. На рисунке 2.5 представлено схематичное изображение кадра.
Половина диагонали кадра De и угол /? позволяют однозначно определить размеры кадра с помощью соотношений: Нс =2De sin/?, гч г, (2.10) W = 2D cosp, с в / где Нс - высота кадра; Wc - его ширина. «Ценность» кадра - характеристика, используемая при установлении порядка обхода кадров и построении траектории. Отношения Хх и Ху выражаются следующим образом: W Нс Rx , ЛУ Ry , (2.11) где Wc - ширина кадра в метрах; Rx - разрешение кадра вдоль оси X в пикселях; Нс - высота кадра в метрах; Ry - разрешение кадра вдоль оси Y в пикселях.
Для обеспечения качественной обработки собранной информации значения отношений Хх и Ху должны удовлетворять условию: ХХ Х, ХУ Х, (2.12) где х – пороговое значение отношения размера, снимаемого с помощью видеодатчика участка (в метрах) к размеру кадра (в пикселях). Его точное значение зависит от характера последующей обработки собранной информации.
Из выражений (2.10) и (2.8) видно, что размеры участка территории, охватываемой одним кадром, прямо пропорциональны высоте БПЛА. Условие (2.12) накладывает ограничение на высоту БПЛА.
На БПЛА может быть установлено несколько видеодатчиков. Обозначим через SCti - множество точек плоскости XOY, составляющих кадр /-го видеодатчика. Хотя данное множество является функцией времени и набора переменных видеодатчика и БПЛА (например, текущие координаты и углы ориентации БПЛА, изменяющиеся во времени) будем рассматривать одиночные кадры в фиксированном положении БПЛА (и, соответственно, видеодатчиков).
Определение положения БПЛА в произвольный момент времени
Посещение всех реперных точек и изготовление снимков требует расхода энергоресурса. Его точное значение зависит от ряда факторов таких как длина траектории, количество реперных точек, необходимость выполнения маневров (поворотов) и т.д. Путь, который пройдет БПЛА, двигаясь с постоянной скоростью, составит: м г- — Ц = VJ\Xjк —Х{k+1 2 +\Yik—Yik+1 2 -\М +1 [Lr + Ls), (3.11) к=0 где М - количество реперных точек; (Хг0; Уг,0) и ( чм+1; УІ,М+1) – координаты стартовой точки, из которой стартуют и в которую возвращается БПЛА группы. Расход энергоресурса составит: м R = к1 +(к2 +к3) \М + 1+к4М + k5L + k6 S\(pj + к7, (3.12) j=0 где к1 - расход энергоресурса на набор нужной высоты; к2 - расход энергоресурса на трогание и набор скорости; к3 - расход энергоресурса на торможение; к4 - расход энергоресурса на изготовление снимка; к5 - расход энергоресурса на единицу пути при движении с постоянной скоростью; L -пройденный с постоянной скоростью путь (3.11); к6 - расход энергоресурса при повороте на один градус; щ - суммарный поворот в /-й реперной точке; к7 - расход энергоресурса на посадку в стартовой точке. Суммарный поворот щ складывается из двух составляющих: cpt =coi +y/t, (3.13) где сої - угол поворота при ориентировании видеодатчика; щ - угол поворота при ориентировании на следующую реперную точку.
В стартовой точке интерпретация этих углов иная: сої - угол поворота при ориентации на первую реперную точку; щ - угол поворота при возвращении в исходную ориентацию после возвращения в стартовую точку. Затрачиваемое на выполнение задачи количество энергоресурса должно удовлетворять условию: R б, (3.14) где Rg - имеющийся на борту БПЛА запас энергоресурса. Если условие (3.14) не выполнено, то БПЛА не сможет выполнить поставленную перед ним задачу из-за нехватки энергоресурса. В этом случае часть задачи должна быть передана другому БПЛА группы.
При обследовании приграничных территорий большую важность имеет своевременное получение информации о ближайших участках территории. Поскольку обследование всей доверенной территории требует времени, то наибольший интерес представляет оперативная обстановка в зонах, расположенных в непосредственной близости от базы. Эта информация представляет наибольший интерес. На основе такого разделения каждой зоне ставится в соответствие некоторая ценность. Она определяется выражением: (X = 1 J т , (3.5) где Lj - расстояние между стартовой точкой, из которой стартует группа, и центром 7-й зоны. Введем функцию Aj(t), задающую сумму ценностей кадров, сделанных /-м БПЛА к моменту времени t. Она запишется в виде: АМ)= 1 . (3.16) к=\ Для всей группы сумма ценностей составит: N A(t) = JAl(t). (3.17) Поиск экстремума функционала (3.17) при соблюдении условия (3.14) является задачей оптимизации. Решением данной задачи является множество траекторий БПЛА, входящих в состав группы. Для его поиска используется алгоритм последовательного выбора.
Функция приемлемости j-й зоны для i-го БПЛА в момент времени t (1.5) запишется в виде: a \CPi( )v J\ k f1\t,i,j)= / k=1 (3.18) На рисунке 3.2 приводится алгоритм выбора зоны отдельным БПЛА, основанный на использовании функции (3.18). Рис. 3.2. Алгоритм выбора зоны В результате работы данного алгоритма БПЛА может не выбрать ни одной зоны. Это может произойти в том случае, если выбор любой из зон приводит к нарушению условия (3.14). Рис. 3.3. Алгоритм последовательного выбора На рисунке 3.3 приводится алгоритм последовательного выбора, в котором каждый БПЛА группы при выборе зон использует алгоритм, изображенный на рисунке 3.2. В алгоритме, изображенном на рисунке 3.3, каждый БПЛА выбирает новую зону с помощью алгоритма, изображенного на рисунке 3.2. Вспомогательная переменная C в алгоритме последовательного выбора используется для выявления случаев, когда решение не может быть найдено. Это происходит, когда на очередной итерации цикла выбора зон ни один БПЛА группы не выбирает зону при условии, что не все зоны распределены между членами группы. В этом случае решение не может быть найдено с помощью алгоритма последовательного выбора. Для решения задачи нужно либо уменьшить обследуемую территорию, либо увеличить количество БПЛА входящих в состав группы.
Оценим вычислительную сложность алгоритма. При условии хранения результата расчета функции (3.16) к моменту времени t, сложность расчета функции (3.18) составит O(1). Так же при условии хранения в памяти результата расчета затрачиваемого энергоресурса (3.12) для имеющегося набора зон, выбранных БПЛА, сложность проверки условия (3.14) при возможном добавлении новой зоны составит O(1). Тогда вычислительная сложность алгоритма, изображенного на рисунке 3.2, составит O(M), где M – количество зон.
Тело цикла в алгоритме, изображенном на рисунке 3.3, исполняется M раз. На каждой итерации исполняется алгоритм, изображенный на рисунке 3.2 и имеющий сложность O(M). Отсюда сложность всего алгоритма составит O(M2). (3.19) Алгоритм последовательного выбора позволяет за полиномиальное время находить квазиоптимальное решение. Но, как показывает проведенное моделирование, поиск экстремума функции (3.17) приводит к не самому лучшему решению.
Для исследования поведения алгоритма последовательного выбора при условии максимизации функции приемлемости (3.18) было проведено программное моделирование. На рисунке 3.4 представлен пример траекторий, построенных этим алгоритмом.
При моделировании использовались следующие параметры: размер обследуемой территории 30 на 20 реперных точек, реперные точки располагаются равномерно вдоль горизонтальной и вертикальной границ территории, образуя регулярную «сетку», количество БПЛА в группе равно 3. Сама программа моделирования была разработана на языке C++.
Большой красный кружок в левом верхнем углу обозначает стартовую точку, из которой стартуют и в которую должны вернуться все члены группы. Реперные точки обозначены кружками меньшего диаметра. Траектории БПЛА обозначены различным цветом. Траектория движения первого БПЛА – красным, второго – синим, третьего – зеленым цветами. Цвет каждой реперной точки соответствует тому БПЛА, который делает в ней снимок.
Функциональная модель системы
Среди алгоритмов, не имеющих такую проблему, наименьшее время работы группы обеспечивает алгоритм двухэтапной оптимизации, в порядке сначала расстояние потом ценность. Именно этот алгоритм и выбран в качестве основного.
Оценим его вычислительную сложность. Составление массива из 2 (оптимальное значение K для этого алгоритма) ближайших к БПЛА реперных точек имеет сложность O(M), где M – количество реперных точек, распределяемых между членами группы. Выбор из них реперной точки, соответствующей зоне с наибольшей ценностью осуществляется за время O(1). Таким образом, сложность выбора очередной реперной точки для отдельного БПЛА группы составит: O(M) + O(1) = O(M). Поскольку между членами группы распределяется M реперных точек, то вычислительная сложность всего алгоритма составит O(M2). (3.24) Если сравнить эту сложность со сложностью алгоритма последовательного выбора в его исходной формулировке (3.19), то увидим, что она не изменилась. 3.4. Минимизация пересечений траекторий
Все рассмотренные ранее варианты алгоритма последовательного выбора никак не проверяют возможность столкновения между БПЛА во время работы. Поэтому они не обеспечивают надежное взаимодействие между членами группы.
Под надежным взаимодействием будем понимать такое совместное решение общей задачи, при котором исключается вероятность столкновения между участниками взаимодействия. Для гарантирования надежного взаимодействия нужны дополнительные действия. Полностью исключить вероятность столкновения невозможно. Мы можем лишь максимально уменьшить её.
Для минимизации вероятности столкновений между членами группы необходимо строить траектории их движения таким образом, чтобы они не пересекались. При условии непересекающихся траекторий вероятность столкновения будет минимальна.
Будем рассматривать алгоритм двухэтапной оптимизации в порядке сначала расстояние потом ценность при дополнительном ограничении на получаемое решение: траектории не должны пересекаться. На рисунке 3.22 представлены траектории БПЛА, построенные модифицированным алгоритмом.
Из траекторий, изображенных на рисунке 3.22, виден главный недостаток предлагаемого подхода. Построение непересекающихся траекторий с течением времени усложняется. Такие траектории становятся возможными для одного БПЛА. Все остальные неизбежно пересекают траекторию первого. Поэтому агенты теряют возможность работать в группе.
На рисунке 3.22 единственным БПЛА, который может продолжать работу не пересекая траектории других членов группы является БПЛА, выделенный красный цветом. Все остальные неизбежно будут пересекать его траекторию. Из-за этого групповая работа сходит на нет.
На рисунке 3.23 представлен график нарастания ценности с течением времени для алгоритма без ограничений (график зеленого цвета) и с ограничением на недопустимость пересечений траекторий (график красного цвета).
Из рисунка 3.23 видно, что вначале графики практически совпадают, но после некоторого момента времени в случае ограничения на траектории ценность нарастает значительно медленнее. Это объясняется тем, что оставшиеся реперные точки посещает только один БПЛА. В результате группе, при условии ограничения на пересечения траекторий, требуется на 31.4% больше времени, чем при отсутствии такого ограничения.
Нарастание ценности с течением времени для алгоритма без ограничений (график зеленого цвета) и с ограничением на пересечения траекторий (график красного цвета) Ослабим ограничение. Пусть траектории могут пересекаться, но ни один БПЛА в составе группы не должен пересекать реперные точки, принадлежащие другому БПЛА этой же группы. Такое пересечение опасно, так как в реперных точках все БПЛА делают остановки. Поэтому существует ненулевая вероятность того, что во время прохождения БПЛА через чужую реперную точку в ней будет находиться другой БПЛА, которому она принадлежит. В этом случае произойдет столкновение. На рисунке 3.24 такие опасные участки обведены красным прямоугольником.
На рисунке 3.25 представлены траектории БПЛА, построенные с ослабленным ограничением. Из этих траекторий видно, что, во-первых, они не имеют потенциально опасных участков, отмеченных на рисунке 3.24 и, во-вторых, у них нет проблемы, свойственной траекториям, построенным с ограничением на пересечения (рисунок 3.22). Групповая работа БПЛА продолжается всё время.
На рисунке 3.26 представлены графики нарастания ценности с течением времени для алгоритма без ограничений (график зеленого цвета) и с ограничением на недопустимость прохождения через реперные точки другого БПЛА группы (график красного цвета).