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

• Автор: Ефимов, Алексей Витальевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2012
• Место защиты: Москва
• Количество страниц: 118 с. : ил.

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

1.2 Актуальность работы.

1.3 Цель работы.

1.4 Основные положения, выносимые на защиту и их научная новизна, достоверность и практическая ценность.

1.5 Апробация.

1.6 Структу ра диссертационной работы.

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

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

2.2 Предложенный подход к решению задачи с помощью динамического программирования

2.3 Вычисление ординат минимального риска в различных полетных ситуациях.
2.4 Приближенный аналитический синтез функции Веллмана в задаче маршругизации полета
2.5 Аппроксимация функции Беллмана и пример работы полученного алгоритма маршрутизации.
2.6 Моделирование облета группы неподвижных объектов
2.7 Выводы по главе 2.
Глава 3. Применение динамического прраммирования для маршрутизации облета мобильных объектов в контролируемом регионе
3.1 Постановка задачи
3.2 Предложенный подход к решению задачи с помощью динамического программирования.
3.3 Вычисление ординат минимального риска в различных полетных ситуациях
3.4 Приближенный аналитический синтез функции Веллмана в задаче маршрутизации полета.
3.5 Аппроксимация функции Веллмана и пример работы полученного алгоритма маршрутизации
3.6 Моделирование алгоритмов расчета функции штрафа для мобильных объектов.
3.7 Выводы по главе 3
Глава 4. Применение фильтра Калмана для оценки параметров бокового ветра
4.1 Оценка вектора состояния беспилотного летательного аппарата
4.2 Построение фильтра.
4.3 Результаты моделирования.
4.4 Выводы по главе 4
Глава 5. Разработка программы для расчета маршрута облета объектов.
5.1 Архитектура программы
5.2 Поиск оптимального маршрута полета Л А с использованием полного перебора.
5.3 Бортовой алгоритм без учета динамики БЛА.
5.4 Реализация модуля расчета маршрута с помощью предложенного метода.
5.5 Проверка работы программы расчета маршрута БЛА.
5.6 Выводы по главе 5
Заключение.
Список использованной литературы


Основой метода полного перебора является составление и расчет всех возможных последовательностей облета объектов. Данный метод всегда даег оптимальное с (точки зрения выбранного критерия качества) решение задачи, однако требует для выполнения большого количества времени и вычислительных ресурсов БЦВМ. При этом с ростом числа объектов время решения задачи растет экспоненциально, так как количество возможных вариантов равно п! Рисунок 1. Колоссальное время решения задачи. Необходимость использования больших объемов памяти. Существует несколько вариантов работы жадного алгоритма [9], но, в целом, их принцип сводится к тому, что находится оптимальное решение для каждой локальной задачи, но решение глобальной задачи может в общем случае не являться оптимальным. Для задачи поиска оптимального маршрута это вырождается в то, что следующим всегда выбирается объект, «ближайший» к текущему положению БЛА. Но в данном случае маршрут, который получается в результате, не всегда является оптимальным (Рисунок 1. Рисунок 1. Как видно из рисунка 1. Н в конечную точку К, полученный с помощью жадного алгоритма, отличается от оптимального. Генетические алгоритмы [6-8] - метод оптимизации, который основан на принципах, наблюдаемых в природе. Они сочетают в себе такие качества, как высокая скорость работы, малая вероятность остановки в локальных минимумах пространства поиска. Работа генетических алгоритмов основана на принципах естественного отбора и использует множество понятий и определений, заимствованных из генетики. Это такие понятия, как хромосома, ген, приспособленность, мутация, отбор, скрещивание и другие. В начале работы алгоритма генерируется начальная популяция - набор особей, характеризуемых хромосомами. Каждая хромосома представляет собой строку. В этой строке закодирована информация о маршруте полета БЛА. Например, если у нас имеются 4 объекта, которые необходимо облететь, мы можем закодировать хромосому в виде двоичной строки таким образом, что каждые 2 бита будут представлять собой номер объекта в двоичном коде. Ог выбора кодировки хромосомы зачастую зависит эффективность применения генетического алгоритма. Например, в нашем случае, в результате работы алгоритма мы будем получать множество восьмибитных строк, большинство из которых не будут годиться для решения задачи, так как некоторые объекты будут учтены несколько раз, а некоторые могут быть вообще не учтены. Соответственно такой вариант кодирования можно считать не очень удачным. После создания начальной популяции (обычно она создается случайным образом) следует отобрать некоторое число особей в качестве родителей для будущих поколений. Существует несколько алгоритмов выбора, однако самым популярным является правило рулетки. Рассмотрим его несколько подробнее. Для каждой из особей в существующей популяции производится вычисление функции приспособленности (функция, которая является критерием оптимальности того или иного маршрута). После этого колесо рулетки разделяется на сектора, каждый из которых соответствует определенной особи, а его размер пропорционален значению функции приспособленности этой особи. Далее, «запуская» рулетку необходимое число раз, мы отбираем особи в популяцию родителей (если сгенерированное случайное число попадает в сектор, соответствующий определенной особи, то она попадает в популяцию родителей). При этом одна и та же особь может быть выбрана в популяцию родителей несколько раз, таким образом, вероятность наиболее приспособленной особи участвовать в образовании потомства выше, чем у менее приспособленного). После того, как популяция родителей создана, мы случайным образом отбираем двоих (или более, в зависимоеги от конкретной реализации алгоритма) и с некоторой вероятностью производим операцию скрещивания. Эта операция заключается в том, что хромосомы двух родителей разделяются на несколько частей (в дальнейшем будем рассматривать случай, когда хромосома разделяется на две части) в точках, называемых точками скрещивания, и обмениваются этими частями. Таким образом, мы получаем две особи следующего поколения (рисунок 1.