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

В последнее время все чаще применяется автоматное программирование [21], в рамках которого поведение программ описывается с помощью конечных детерминированных автоматов.

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

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

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

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

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

Каждая команда состоит из N летательных аппаратов.

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

Для каждого аппарата задана начальная скорость и начальное направление движения.

Каждый летательный аппарат имеет определенный запас топлива, расходуемого в процессе движения. По команде «Старт» все аппараты начинают движение с целью максимально удалиться от линии старта. В процессе полета они могут изменять скорость движения за счет изменения расхода топлива.

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

Жизненный цикл беспилотного летательного аппарата в рассматриваемой задаче может быть описан графом перехода автомата с тремя состояниями: «Полет». «Нормальное завершение гонки», «Аварийное завершение гонки».

Таблица 2 Используемые обозначения.

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

Динамика беспилотного летательного аппарата Беспилотный летательный аппарат представляет собой дискообразное «летающее крыло» радиусом один метр. На вид сверху описываемого летательного аппарата.

Беспилотный летательный аппарат имеет реактивный двигатель (горизонтальный прямоугольник на рис. 3), топливный бак (вертикальный прямоугольник), аэродинамические рули и бортовой компьютер, который регулирует расход топлива и положение аэродинамических рулей. Летательный аппарат может передвигаться со скоростями от 1 м, с. Его максимальная скорость зависит от запаса топлива и сопротивления воздуха.

Беспилотный летательный аппарат движется в соответствии со вторым законом Ньютона. Его движение определяется двумя силами: сопротивлением воздуха F и тягой двигателя T. Если тяга не равна сопротивлению воздуха, то летательный аппарат движется с ускорением, которое может быть положительным (если тяга больше сопротивления воздуха) или отрицательным (если сопротивление воздуха больше тяги).

Ускорение определяется по формуле:

где m — масса беспилотного летательного аппарата. При этом считается, что изменение его массы за счет выгорания горючего пренебрежимо мало.

Сопротивление воздуха определяется по формуле (2):

F=c1+c2v2

где v — скорость беспилотного летательного аппарата, а коэффициенты c1 и c2 определяются его аэродинамическими характеристиками и одинаковы для всех аппаратов обеих команд.

Тяга двигателя определяется по формуле:

T=c4q ,.

где q — расход топлива в сантиметрах кубических в секунду. Расход топлива находится под контролем бортового компьютера летательного аппарата, что позволяет изменять расход от 0 до 1. Константа c4 определяется характеристиками двигателя беспилотного летательного аппарата и одинакова для всех аппаратов обеих команд.

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

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

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

Если центр второго летательного аппарата находится в областях, отмеченных на 0 знаком «+», сопротивление воздуха его движению падает на 50%. Если же центр второго летательного аппарата находится в области, помеченной знаком «-», сопротивление воздуха возрастает на 50%.

Аэродинамические воздействия от нескольких летательных аппаратов складываются, так что в зоне «++» на рис. 5 сопротивление воздуха отсутствует, а в зонах «0» воздействия компенсируют друг друга.

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

Под относительной скоростью столкновения понимается величина проекции векторной разности скоростей летательных аппаратов на прямую, проходящую через центры аппаратов в момент столкновения (рис. 6). На рисунке вектор vrel соответствует относительной скорости.

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

Каждые t миллисекунд обновляются параметры. Во-первых, с соревнования снимаются летательные аппараты, движущиеся со скоростью, меньшей 1 м/с.

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

В-третьих, производится расчет новых скоростей летательных аппаратов по формуле:

где vtemp — вектор скорости летательного аппарата после учета ускорения, vold — вектор старой скорости летательного аппарата, a — вектор ускорения. После этого происходит поворот вектора скорости на угол равный углу поворота аэродинамических рулей (рис. 7). В результате поворота получается вектор новой скорости беспилотного летательного аппарата vnew.

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

В-пятых, происходит равномерное прямолинейное движение летательных аппаратов. Если при этом происходит соударение аппаратов, то их скорости и координаты изменяются в соответствии с законами сохранения импульса и энергии. При этом летательные аппараты, относительная скорость которых превосходила 1 м/с, выбывают из гонки.

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

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

Структура системы управления беспилотным летательным аппаратом Каждый беспилотный летательный аппарат управляется системой, состоящей из нейронной сети и конечного автомата. Таким образом, используется мультиагентный подход [23] — каждый летательный аппарат представляет собой агента, взаимодействующего с внешней средой и другими агентами.

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

• · создание начального поколения;
• · мутация;
• · скрещивание (кроссовер);
• · отбор особей для формирования следующего поколения;
• · вычисление функции приспособленности (фитнес-функции).

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

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

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

Создание начального поколения Начальное поколение заполняется случайно сгенерированными системами управления. При этом в каждой системе управления случайным образом генерируются конечный автомат и нейронная сеть — веса связей в ней инициализируются случайными числами от -1 до 1.

Операции мутации Мутация особи. При мутации особи с равной вероятностью мутирует либо одна система управления летательным аппаратом, либо вторая.

Мутация системы управления беспилотным летательным аппаратом. При мутации системы управления беспилотным летательным аппаратом мутирует либо нейронная сеть, либо конечный автомат.

Мутация нейронной сети. При мутации нейронной сети мутирует случайно и равновероятно выбирается один элемент сети и мутирует.

Мутация элемента сети. При мутации элемента сети случайно выбирается один из весов связей, и к нему прибавляется случайное число из отрезка [-0.05; 0.05].

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

Изменение начального состояния. Начальное состояние изменяется на случайно выбранное состояние автомата.

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

Операции скрещивания.

Оператор скрещивания получает на вход две особи (P1, P2) и выдает две особи (S1,S2). Пусть X — некоторая особь. Пусть X. s1 и X. s2 — системы управления беспилотными летательными аппаратами, входящие в эту особь. Пусть s — некоторая система управления аппаратом. Обозначим как s. ns входящую в нее нейронную сеть, а как s. a — входящий в нее автомат.

Скрещивание особей. При скрещивании особей происходит скрещивание систем управления летательными аппаратами: P1. s1 и P2. s1, P1. s2 и P2. s2. Обозначим системы, получившиеся в результате первого скрещивания, s11 и s12, а в результате второго — s21 и s22. Тогда для особей-потомков будет справедливо: S1. s1=s11, S1. s2=s21, S2. s1=s21, S2. s2=s22.

Скрещивание систем управления беспилотными летательными аппаратами. При скрещивании систем управления беспилотными летательными аппаратом s1 и аппаратом s2 происходит скрещивание автоматов s1. a и s2. a и скрещивание нейронных сетей s1. ns и s2.ns. Получившиеся в результате скрещиваний автоматы обозначим a1 и a2, а нейронные сети ns1 и ns2. В результате скрещивания системы управления летательными аппаратами получаются системы управления s3 и s4: s3 содержит a1 и ns1, s4 — a2 и ns2.

Скрещивание автоматов. Обозначим автоматы, поступающие на вход оператора скрещивания автоматов, A1 и A2. Начальное состояние некоторого автомата, А обозначим A. is, а переход из состояния I по значению входной переменной j как A (i, j). Обозначим автоматы, получающиеся в результате скрещивания A3 и A4. Для их начальных состояний справедливо:

• · либо A3. is = A1. is и A4. is = A2. is;
• · либо A3. is = A2. is и A4. is = A1.is.

Скрещивание производится отдельно для каждого состояния i и для каждого значения j входной переменной. В каждом случае возможно два равновероятных варианта:

• · A3(i, j) = A1(i, j) и A4(i, j) = A2(i, j);
• · A3(i, j) = A2(i, j) и A4(i, j) = A1(i, j).

Проиллюстрируем скрещивание автоматов на примере случая одной входной переменной. Обозначим переход из состояния номер i в автомате A1 по значению входной переменной «1» как A1(i, 1), а по значению «0» как A1(i, 0). Аналогичный смысл придадим обозначениям A2(i, 0) и A2(i, 1). Тогда для переходов из состояния с номером i в автоматах-потомках A3 и A4 будет справедливо одно из четырех соотношений:

• · либо A3(i, 0) = A1(i, 0), A4(i, 1) = A2(i, 1) и A4(i, 0) = A2(i, 0), A4(i, 1) = A1(i, 1);
• · либо A3(i, 0) = A2(i, 0), A4(i, 1) = A1(i, 1) и A4(i, 0) = A1(i, 0), A4(i, 1) = A2(i, 1);
• · либо A3(i, 0) = A1(i, 0), A4(i, 1) = A1(i, 1) и A4(i, 0) = A2(i, 0), A4(i, 1) = A2(i, 1);
• · либо A3(i, 0) = A2(i, 0), A4(i, 1) = A2(i, 1) и A4(i, 0) = A1(i, 0), A4(i, 1) = A1(i, 1).

Скрещивание нейронных сетей. Обозначим нейронные сети, поступающие на вход оператора скрещивания нейронных сетей, NS1 И NS2, а получающиеся в результате его применения — NS3 и NS4. Опишем их устройство. Обозначим NS (i) нейрон с номером i сети NS.

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

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

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

с1 = 0.625;

с2 = 0.025;

с4 = 3.125;

Дt = 0.3;

L = 7.

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

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

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

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

Функция переходов и действий автомата, входящего в систему управления первым беспилотным летательным аппаратом, приведена в таблице 2. Строки этой таблицы соответствуют состояниям автомата (пронумерованы числами от 0 до 5), столбцы — возможным комбинациям значений трех входных переменных. Серым цветом отмечена строка с начальными состояниями.

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