Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение и постановка задачи

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

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

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

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

Исходными данными поставленной задачи являются:

· характеристики БЛА;

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

· количество БЛА;

· начальное положение и характеристики движения наземных объектов;

· скорость бокового ветра;

· начальный и конечный пункты движения каждого БЛА.

Постановка задачи

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

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

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

· диапазон изменения скорости и высоты полета БЛА;

· зависимость минимального радиуса разворота от скорости полета и скорости ветра.

Также оговаривается тот факт, что на борту БЛА присутствует аппаратура фото- или видеонаблюдения наземных объектов. Исходя из того, что современные объективы фотокамер позволяют провести фотосъемку в хорошем качестве с высоты до нескольких сот метров, выберем углы обзора камеры, учитывая, что камера должна полностью охватывать зоны недосягаемости БЛА (рисунок 1). Зоны недосягаемости - это те зоны, в которые БЛА не может попасть из своего текущего положения в силу того, что его разворот производится по окружности, радиус которой определяется его характеристиками.

аппарат программа беспилотный летающий

Рисунок 1. Выбор углов обзора камеры

Примем высоту полета БЛА равной 200 метров. Радиус разворота БЛА в отсутствие ветра равен 60 метрам. Исходя из этого, рассчитаем углы обзора камеры по продольной и поперечной осям самолета:

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

1. Специальная часть

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

Обзор существующих методов поиска оптимального маршрута при одиночном полете БЛА

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

Полный перебор

Полный перебор всех возможных вариантов является самым простым решением задачи. Этот метод решает задачу поиска оптимального маршрута «в лоб». Основой метода полного перебора является составление и расчет всех возможных последовательностей облета объектов. Данный метод всегда дает оптимальное решение задачи, однако требует для выполнения большого количества времени и вычислительных ресурсов БЦВМ. При этом с ростом числа объектов время решения задачи растет экспоненциально, так как количество возможных вариантов равно n!, где n - число объектов (рисунок 1.1.1).



Рисунок 1.1.1 Зависимость времени выполнения алгоритма от числа объектов

Сильные стороны:

· простота реализации;

· найденное решение всегда оптимально.

Слабые стороны:

· Колоссальное время решения задачи.

· Необходимость использования больших объемов памяти.

Генетические алгоритмы

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

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

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

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

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

Рисунок 1.1.2 Операция скрещивания

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

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

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

Рисунок 1.1.3 Мутация

После проведения всех этих операций заканчивается одно поколение генетического алгоритма и производится проверка на условие останова. Условием останова может быть, например, количество выполненных поколений или очень маленькая изменчивость наилучшего решения в нескольких популяциях. Если условие останова не соблюдено, то все операции генетического алгоритма повторяются заново с текущей популяцией. В противном случае наилучшее решение из текущей популяции принимается в качестве оптимального [1]. Схема работы генетического алгоритма представлена на рисунке 1.1.4.

Рисунок 1.1.4 Схема работы генетического алгоритма

Сильные стороны работы ГА:

· практически полная независимость от характеристик пространства поиска;

· малая зависимость от характера критерия оптимальности;

· найденное решение практически всегда является оптимальным.

Слабые стороны:

· сложность реализации;

· большая зависимость от выбора варианта кодирования хромосомы.

Метод восхождения

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

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

Рисунок 1.1.5 Случай нахождения максимума для унимодальной функции



Рисунок 1.1.6 Случай нахождения максимума для функции с локальными максимумами

Сильные стороны:

· простота реализации;

· надежность работы для унимодальных функций.

Слабые стороны:

· остановка в локальных минимумах, невозможность работы в случае, если пространство поиска имеет несколько минимумов;

· неопределенное время поиска.

Динамическое программирование

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

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

1) Разбиение задачи на подзадачи меньшего размера.

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

3) Использование полученного решения подзадач для конструирования решения глобальной задачи.

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

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

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

Рисунок 1.1.7 Представление задачи в виде графа

Кружками обозначены вершины, линиями - пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.



Рисунок 1.1.8 Введение меток для каждой вершины

Первый шаг. Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Рисунок 1.1.9

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.



Рисунок 1.1.10

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг. Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 - вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Рисунок 1.1.11

Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22<, устанавливаем метку вершины 4 равной 22.

Рисунок 1.1.12

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Рисунок 1.1.13

Третий шаг. Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:



Рисунок 1.1.14

Дальнейшие шаги. Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Рисунок 1.1.15а

Рисунок 1.1.15б

Завершение выполнения алгоритма. Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.

Сильные стороны:

· простота реализации;

· быстрота работы;

· известное заранее время поиска.

Слабые стороны:

· свойство «отсутствия последствий», то есть невозможность работы в случае подвижных объектов.

Жадный алгоритм

Существует несколько вариантов работы жадного алгоритма, но, в целом, их принцип сводится к тому, что находится оптимальное решение для каждой локальной задачи, но решение глобальной задачи может в общем случае не являться оптимальным. Для задачи поиска оптимального маршрута это вырождается в то, что следующим всегда выбирается объект, «ближайший» к текущему положению БЛА. Но в данном случае маршрут, который получается в результате, не всегда является оптимальным (Рисунок 1.1.16). [2]

Рисунок 1.1.16 Сравнение оптимального пути (черные стрелки) и пути, полученного с помощью жадного алгоритма (красные стрелки)

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

Сильные стороны:

· простота реализации;

· быстрота работы;

· известное заранее время поиска.

Слабые стороны:

· неоптимальное решение глобальной задачи.

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

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

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

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

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

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

Обзор существующих методов оптимизации групповых действий

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

Мультиагентные системы

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

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

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

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

Функция, которая отображает набор пар наблюдение - действие до текущего момента времени в оптимальное действие в текущий момент времени называется стратегией агента

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

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

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

· в детерминистическом мире модель перехода отображает единственным образом пару состояние-действие в новое состояние;

· в стохастическом мире модель перехода отображает пару состояние-действие в распределение вероятности состояний.

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

Сам процесс принятия решения состоит в следующем. Каждый агент в течение одного цикла переговоров совершает 4 действия:

· отправляет или получает предложение,

· обдумывает полученное предложение,

· отправляет ответ (согласие или несогласие),

· принимает решение.

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

b_i(T_j) = V_Tjw_r - S_t,

где V_Tjw_r - «цена» объекта,

S_t - относительное время преследования объекта

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

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

· если объект выбран только одним БЛА, то данное предложение одобряется;

· если объект выбран несколькими БЛА, то согласие посылается только тому БЛА, для которого максимален выигрыш;

· один БЛА может отправить только одно согласие для каждой цели;

· если все соседи данного БЛА (то есть те БЛА, от которых он находится в непосредственной близости) согласны с его целью, он получает право на принятие решения о целесообразности следования до его текущей цели;

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

Выделим сильные и слабы стороны данного подхода

Сильные стороны:

· постоянное взаимодействие между агентами;

· коллективное принятие решения всеми агентами.

Слабые стороны:

· в случае необходимости использования большой истории действий возрастает ресурсоемкость данного подхода;

· агент зачастую действует по аналогии с жадным алгоритмом, а значит его решение в общем случае нельзя считать оптимальным;

· необходимость использования стохастических прогнозов в случае использования информации об оценках будущей реакции окружения да действия агентов.

Задача многих коммивояжеров

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

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

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

Данный метод описан в работе [4]. В данной работе предлагается сначала провести кластеризацию всех объектов по методу k-средних. Этот метод заключается в том, что все объекты разбиваются на количество кластеров k, равное количеству БЛА следующим образом:

· случайным образом на поле решения задачи выбрасывается k точек, которые являются центрами кластеров (центроидами);

· каждый объект заносится в кластер того центроида, к которому он находится ближе всего;

· после того, как все объекты занесены в кластеры, позиции центроидов пересчитываются таким образом, чтобы суммарное расстояние до всех объектов оказалось минимальным;

· шаги 2 и 3 повторяются до тех пор, пока центроиды не перестанут передвигаться.

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

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

К полученной последовательности применяется алгоритм имитации отжига (алгоритм поиска минимума некоторой функции), целевой функцией которого является время облета объектов в заданной последовательности.

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

Сильные стороны:

· применение множества способов препятствования попаданию в локальные минимумы.

Слабые стороны:

· исключение взаимодействия между БЛА;

· применяется сразу несколько методов поиска и оптимизации, что существенно увеличивает время расчета;

· метод применим только для неподвижных объектов.

1.2 Разработка модели одиночных действий БЛА

Решается задача поиска оптимального маршрута облета движущихся объектов одним БЛА с учетом ветра. Разобьем её на несколько подзадач.

1. Поиск оптимального маршрута облета неподвижных объектов одним БЛА без учета ветра;

2. Учет подвижности объекта;

3. Учет ветра;

Для решения задачи 1 запишем алгоритм перелета БЛА в точку с определенными координатами. Исходными данными для него являются:

1. Начальные координаты БЛА;

2. Начальный угол курса БЛА;

3. Координаты объекта;

4. Минимальный радиус разворота БЛА;

5. Координаты точки.

Проиллюстрируем это на рисунке 1.2.1.

Рисунок 1.2.1 Начальные данные для задачи, где xЛА, yЛА - начальные координаты БЛА, xО, yО - начальные координаты объекта, R - минимальный радиус разворота БЛА, стрелкой указано начальное направление полета БЛА.

Для построения оптимальной траектории полета до точки разобьем полет на 2 этапа:

1. Полет по дуге радиусом R;

2. Полет по прямой до объекта.

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

Найдем точку касания. Для этого обратимся к рисунку 1.2.2.

Рисунок 1.2.2 Нахождение точки касания

Найдем угол :

Теперь, зная этот угол, легко найти координаты точки касания:

После того, как мы определили точки касания, выберем из них ту, при полете через которую мы будем двигаться в сторону объекта. Для этого введем несколько дополнительных углов (рисунок 1.2.3).

Рисунок 1.2.3 Выбор точки касания

Здесь - углы между векторами скорости БЛА и осью Х в точках касания.

- углы между прямыми, соединяющими точки касания с объектом, и осью X.

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

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



Рисунок 1.2.4 Нахождения угла

Теперь длину траектории можно определить как

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

Задачу учета подвижности объекта будем решать следующим образом. Мы предполагаем, что в течение того времени, за которое БЛА сблизится с объектом, последний будет двигаться прямолинейно с постоянной скоростью. Таким образом, мы можем найти точку, по прибытии в которую БЛА «встретится» с объектом. Иллюстрация этого процесса приведена на рисунке 1.2.5.



Рисунок 1.2.5 Поиск точки упреждения

Для нахождения точки упреждения мы можем записать следующие функции:

1. Функция, определяющая время движения объекта до одной из точек, расположенных на прямой, по которой движется объект;

2. Функция, определяющая время движения БЛА до вышеуказанной точки.

Таким образом, мы получаем две функции, точка пересечения которых является решением поставленной задачи (рисунок 1.2.6).

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

Теперь мы легко можем рассчитать координаты точки встречи БЛА и объекта и время перелета в эту точку.

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

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

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

Рисунок 1.2.7 Пример дерева для трех объектов

На этом рисунке в кружках показаны номера объектов, которые на данном шаге должен пролететь БЛА.

Также следует отметить, что в случае, если при пролете ЛА над очередным объектом, в области в области обзора бортовой фотокамеры оказываются другие объекты, то они сразу же обрабатываются, а время перелета до этих объектов считается равным нулю.

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

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

1.3 Разработка нейронной сети - аналога модуля «Поиск оптимального маршрута для одного БЛА»

Для замены модуля «Поиск оптимального маршрута для одного БЛА» будем использовать нейронную сеть с прямыми связями (feedforward network) с одним скрытым слоем, на вход которой будут подаваться следующие значения:

· относительные координаты по оси X для каждого объекта (Дx);

· относительные координаты по оси Y для каждого объекта (Дy);

· относительный угол курса для каждого объекта (Дш);

· скорость каждого объекта (V_i);

· скорость БЛА (V);

· минимальный радиус разворота БЛА (R_min).

Количество нейронов будет выбираться экспериментальным путем. Количество выходных нейронов будет соответствовать количеству объектов, на которое данная нейронная сеть рассчитана. Выходные значения нейронной сети будут формироваться таким образом, что, тот выход, который соответствует следующему в маршруте объекту (то есть тому объекту, к которому сейчас необходимо двигаться БЛА), будет переходить в активное состояние (значение этого выхода станет равным «1»), а все остальные выходы останутся в пассивном состоянии (их значение будет установлено в «0»). Данная нейронная сеть изображена на рисунке 1.3.1.

Рисунок 1.3.1 Нейронная сеть для замены модуля поиска оптимального маршрута

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

1.4 Разработка модели групповых действий БЛА

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

Рисунок 1.4.1 Разбиение области задач на части. К1, К2 - конечные пункты маршрута первого и второго БЛА соответственно

После этого проанализируем, какие из объектов пересекут линию раздела областей за заданный промежуток времени t_К и разделим все объекты на три группы:

1) объекты, принадлежащие области ответственности первого БЛА;

2) объекты, принадлежащие области ответственности второго БЛА;

3) Спорные объекты, которые за время t_К пересекли линию раздела областей ответственности, отведенных каждому БЛА.

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

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

Рисунок 1.4.2 Пример распределения спорных объектов

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

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

На рисунке 1.4.3 изображена общая схема работы алгоритмов поиска оптимального маршрута.

Рисунок 1.4.3 Общая схема работы системы

1.5 Разработка программы, моделирование системы и анализ результатов

На основании алгоритмов, разработанных в пунктах 1.2 - 1.3, была реализована программа, предназначенная для поиска оптимального распределения объектов между двумя БЛА. Данная программа была реализована и выполнена на языке MATLAB в среде разработки MatLab 2008a.

Для реализации алгоритмов была выбрана среда матlab по следующим причинам:

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

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

Среди недостатков использования данной среды можно выделить лишь один - высокая стоимость коммерческой лицензии. [6]

Листинги исходных кодов приведены в приложении 1.

Моделирование работы модуля «Поиск оптимального маршрута одного БЛА»

Промоделируем работу данного модуля для случая поиска оптимального маршрута облета пяти объектов и проанализируем результаты. Исходные данные и результаты проиллюстрированы на рисунке 1.5.1 и в таблице 1.5.1. Следует также отметить, что координаты по осям X и Y отсчитываются от некоторой начальной точки с координатами (0,0).

Рисунок 1.5.1 Результат выполнения модуля «Поиск оптимального маршрута для одного БЛА»

Таблица 1.5.1. Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
БЛА	-50	50	40	90
Первый объект	689	374	15	72
Второй объект	83	114	15	238
Третий объект	152	412	15	103
Четвертый объект	996	39	15	69
Пятый объект	106	480	15	271
Конечная точка движения	1050	50	-	-

Анализируя работу данного модуля, можно сказать, что он выполняется корректно и маршрут, который был сформирован, является оптимальным. Для доказательства построим график зависимости времени облета всех объектов от номера вершины дерева, с помощью которого осуществляется перебор вариантов облета (рисунок 1.5.2). Изображение дерева слишком велико, поэтому оно не приводится для данного примера.

Рисунок 1.5.2 График зависимости времени облета от номера вершины дерева

Таким образом, номер вершины дерева облета, соответствующей минимальному времени облета всех объектов - 114. Данной ветви соответствует маршрут 2, 5, 3, 1, 4, что соответствует иллюстрации на рисунке 1.5.1.

Время работы данного модуля составляет 57,3648 секунды. Как и ожидалось, время работы данного модуля не позволяет включить его в состав программного обеспечения БЦВМ, поэтому замена его на нейронную сеть оказалась оправданной.

Моделирование работы модуля «Поиск оптимального маршрута нескольких БЛА»

Теперь, после того, как мы убедились, что алгоритм выбора оптимального маршрута для одного БЛА работает корректно, проверим работу всей системы в целом (на примере двух БЛА), а затем проанализируем работу каждого из модулей, чтобы выяснить возможность применения данной системы в составе комплекса бортового программного обеспечения. Исходные данные для эксперимента приведены в таблице 1.5.2.

Таблица 1.5.2 Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
Первый БЛА	-225	-57	40	90
Второй БЛА	-225	317	40	90
Первый объект	105	42	10	133
Второй объект	573	15	14	172
Третий объект	737	19	14	246
Четвертый объект	984	257	13	94
Пятый объект	177	119	10	281
Шестой объект	939	90	11	29
Седьмой объект	467	194	10	213
Конечный пункт маршрута первого БЛА	1502	-57	-	-
Конечный пункт маршрута второго БЛА	1502	-317	-	-

Скорость ветра зададим равной 3 м/с

Ниже приведены результаты одной итерации работы системы.

Модуль анализа движения объектов

Результатом работы модуля явилось следующее распределение объектов:

· Первый БЛА: 5-й и 6-й объекты;

· Второй БЛА: 4-й и 7-й объекты;

· Спорные объекты: 1-й, 2-й и 3-й объекты.

Время работы модуля составило 0,005 секунды.

Модуль генерации вариантов распределения объектов

Для выбранной итерации было назначено следующее распределение объектов:

· Первый БЛА: 1-й, 5-й, 3-й и 6-й объекты;

· Второй БЛА: 2-й, 4-й и 7-й объекты.

Время работы модуля составило 0,0131 секунды.

Модуль нахождения оптимального маршрута для одного БЛА

Для выбранной итерации были составлены следующие оптимальные маршруты:

· Первый БЛА: 1-й и 5-й - 3-й - 6-й объекты;

· Второй БЛА: 7-й - 2-й - 4-й объекты.

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

Время работы модуля составило 31,7279 секунды.

Модуль определения минимального радиуса разворота.

Для текущих значений скорости БЛА и скорости ветра был рассчитан минимальный радиус разворота R_min = 70 м.

Время работы модуля составило 0.000004 секунды.

Модуль запоминания оптимального маршрута

Маршрут, просмотренный на текущей итерации, сохранен для дальнейшей обработки.

Время работы модуля составило 0,0008 секунды.

Результаты работы системы

В результате работы системы было выбрано оптимальное распределение объектов и составлены оптимальные маршруты их облета двумя БЛА. На рисунке 1.5.3 изображены выбранные маршруты, а также показаны начальные пункты движения БЛА (они изображены в виде самолетов), конечные пункты движения первого и второго БЛА - К₁ и К₂ соответственно, начальные положения и направление движения объектов (они изображены в виде черных окружностей), а также точки «обслуживания» объектов (они изображены синими точками). Красные непрерывные линии показывают траектории движения БЛА по оптимальным маршрутам. Время работы всей системы составило 172.4834 секунды.

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

Рисунок 1.5.3 Результат выполнения модуля «Поиск оптимального маршрута для нескольких БЛА»



Рисунок 1.5.4 Дерево перебора всех вариантов облета для первого БЛА (соответствие значений, указанных на вершине номерам объектов: «1» - 5-й объект, «2» - 6-й объект, «3» - 1-й объект, «4» - 3-й объект)

Моделирование работы системы с использованием нейронной сети и анализ результатов

Смоделируем работу созданной нейронной сети в среде Matlab с использованием встроенной утилиты nntool, предназначенной для работы с нейронными сетями.

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

· скорости движения БЛА и объектов постоянны и заданы заранее;

· объекты движутся в том же направлении, что и БЛА;

· количество объектов равно трем.

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

В ходе разработки и моделирования работы данной нейронной сети количество нейронов в скрытом слое было выбрано равным 35. Таким образом, данная нейронная сеть имеет структуру 14-35-3.

Моделирование данной нейронной сети производилось на ПЭВМ со следующими характеристиками:

· Тактовая частота процессора: 2 ГГц;

· Количество ядер процессора: 1;

· Объем памяти: 1,5 Гб.

Процесс генерации данной обучающей выборки занял 8 часов.

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

Исходные данные для эксперимента представлены в таблице 1.5.3.1

Таблица 1.5.3 Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
БЛА	-50	0	40	90
Первый объект	122	127	10	90
Второй объект	79	149	10	90
Третий объект	146	141	10	90
Конечный пункт маршрута БЛА	300	0	-	-

Скорость ветра примем равной нулю.

В результате работы исходный алгоритм выдал следующую последовательность облета объектов: 2-й, 1-й, и затем 3-й.

Нейронная сеть имела на выходах следующие значения:

· Первый выход: 0,0000

· Второй выход: 0,9994

· Третий выход: 0,0021

На втором шаге работы алгоритма нейронная сеть имела на выходах следующие значения:

· Первый выход: 0.9161

· Второй выход: 0.1097

· Третий выход: 0.1006

На последнем шаге работы алгоритма остался только один объект.

Таким образом, нейронная сеть предложила первым пунктом маршрута сделать второй объект (так как был активен второй выход). Вторым пунктом маршрута был предложен первый объект.

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

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

Таблица 1.5.4 Исходные данные для эксперимента

	X, м	Y, м	V, м/с	Курс, град.
Первый БЛА	-50	75	40	90
Второй БЛА	-50	125	40	90
Первый объект	60	80	10	90
Второй объект	100	100	10	90
Третий объект	140	70	10	90
Четвертый объект	80	140	10	90
Пятый объект	130	130	10	90
Конечный пункт маршрута первого БЛА	300	75	-	-
Конечный пункт маршрута второго БЛА	300	125	-	-

Минимальный радиус разворота БЛА в этом эксперименте был принят равным 20 м.

В результате работы система, использующая алгоритм полного перебора, выдала следующую последовательность облета объектов для двух БЛА:

Первый БЛА: 1-й, 2-й и затем 3-й объект;

Второй БЛА: 4-й и затем 5-й объект.

Система, использующая нейронную сеть, выдала следующую последовательность облета объектов:

Первый БЛА: 1-й, 2-й и затем 3-й объект;

Второй БЛА: 4-й и затем 5-й объект.

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

· Первый выход: 0,9998

· Второй выход: 0,0000

· Третий выход: 0,0000

На второй итерации значения изменились на следующие:

· Первый выход: 0,0267

· Второй выход: 0,7650

· Третий выход: 0,0000

Соответственно, последним в маршруте остался объект номер три.

Нейронная сеть второго БЛА на первой итерации имела следующие значения на выходах:

· Первый выход: 0,9878

· Второй выход: 0,6347

· Третий выход: 0,0021

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

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

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

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

Время, необходимое для одного цикла работы нейронной сети составляет 0.007731 секунды. Время процедуры, необходимой для расчета изменения координат объектов после того, как БЛА достигнет объекта, предлагаемого нейронной сетью составляет 0,000612 секунды. Таким образом, для просчета, например, оптимального маршрута для 10 БЛА потребуется 0,0834 секунды. Теперь рассчитаем, сколько такая задача заняла бы времени при применении исходного алгоритма. Для пяти объектов время расчета алгоритма составляет 51 секунду. Так как количество комбинаций, которое просчитывается в этом случае равно 5! = 120, на одну операцию расходуется 0,4250 секунды. Для десяти объектов это время составит 0.4250 ? 10! = 1542240 секунд, что равно примерно 428 часам или 18 суткам.

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

2. Экономическая часть

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