ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2014, № 2, с. 111-121
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
УДК 004.4242
ГЕНЕРАЦИЯ УПРАВЛЯЮЩИХ АВТОМАТОВ ПО ОБУЧАЮЩИМ ПРИМЕРАМ НА ОСНОВЕ МУРАВЬИНОГО АЛГОРИТМА © 2014 г. И. П. Бужинский, В. И. Ульянцев, Д. С. Чивилихин, А. А. Шалыто
Санкт-Петербург, Санкт-Петербургский национальный исследовательский ун-т информационных
технологий, механики и оптики Поступила в редакцию 18.06.13 г., после доработки 25.10.13 г.
Предлагается метод генерации управляющих автоматов по обучающим примерам, в котором в качестве алгоритма поисковой оптимизации используется муравьиный алгоритм. Эффективность метода оценивается на примере генерации автоматов управления моделью беспилотного самолета. При этом показано, что предлагаемый метод обеспечивает производительность и качество выше, чем у метода, основанного на генетических алгоритмах.
DOI: 10.7868/S0002338814020048
Введение. Автоматное программирование — парадигма, в рамках которой программы проектируются в виде систем автоматизированных объектов управления [1]. Автоматизированный объект управления состоит из объекта управления и системы управления, которая может содержать один или несколько управляющих конечных автоматов (далее — автоматов). Одна из областей, для которой целесообразно применение автоматного программирования, — управление объектами со сложным поведением, т.е. объектами, которые могут демонстрировать различное поведение при одинаковых входных воздействиях. Примерами применения автоматного программирования при решении задач данного класса могут служить работы [2—4]. В [3, 4] автоматы строятся автоматически, поскольку ручное их построение является затруднительным. Существуют задачи, для которых ручное построение автоматов и вовсе невозможно.
Для автоматизации процесса построения автоматов необходимо ввести критерий качества. Один из способов это сделать — задать функцию приспособленности (ФП), сопоставляющую каждому конечному автомату вещественное число. Нахождение автомата с заданным значением ФП можно осуществлять на основе алгоритмов поисковой оптимизации (например, эволюционных алгоритмов [5—9]). Альтернативный подход к заданию критерия качества состоит в описании набора ограничений, которым должен удовлетворять автомат. Этот подход использован в [10, 11], где задача генерации конечного автомата сводится к задаче о выполнимости булевой формулы (SAT) [12].
В [133] для построения автомата с дискретными выходными воздействиями, управляющего моделью беспилотного самолета, был использован такой алгоритм поисковой оптимизации, как генетический алгоритм. При этом ФП автомата вычислялась на основе моделирования в авиаси-муляторе, и поэтому полный цикл генерации автомата занимал несколько недель на двух двухъ-ядерных персональных компьютерах. В [14] также был применен генетический алгоритм, но ФП автомата вычислялась не на основе моделирования, а на основе обучающих примеров, что позволило сократить время генерации автомата на персональном компьютере до нескольких часов. Отличительная особенность публикации [14] — использование наряду с дискретными непрерывных выходных воздействий.
В настоящей работе предлагается метод генерации автоматов, являющийся усовершенствованием метода, предложенного в [14]. При этом в качестве алгоритма поисковой оптимизации используется модификация муравьиного алгоритма [15, 16], предложенная в [17], что позволяет сократить время генерации автоматов на компьютере с четырьмя ядрами до четверти часа.
1. Постановка задачи. Управляющим конечным автоматом Мили называется шестерка (S, E, A, 8, X, s0), где S — конечное множество состояний, E — множество входных событий, A — множество выходных воздействий, 8: S х E^ S — функция переходов, X: Sх E^ A — функция выходов, s0 — начальное состояние.
е1/-0.8
е^-0.15 62/0.1
Рис. 1. Пример управляющего автомата
Рис. 2. Авиасимулятор В^ШОеаг (снимок экрана)
Пример автомата приведен на рис. 1. Круги на диаграмме соответствуют состояниям автомата, а цифры внутри кругов — их номерам. Начальное состояние 1 отмечено входящей в него слева стрелкой. На каждой из остальных стрелок, обозначающих переходы, слева от косой черты находится входное событие, по которому совершается переход, справа — выходное воздействие (в данном случае — вещественное число), вырабатываемое при совершении перехода. Крайняя правая стрелка соответствует двум переходам сразу.
Сформулируем решаемую задачу. Задан набор обучающих примеров, на основе которых необходимо сгенерировать автомат, имеющий дискретные и непрерывные выходные воздействия, который управляет объектом со сложным поведением. Обучающие примеры записываются человеком и являются примерами желаемого поведения объекта управления.
В настоящей работе, как и в [14], в качестве объекта управления рассматривается модель беспилотного самолета, а желаемое ее поведение — выполнение некоторой фигуры пилотажа. Для моделирования используется авиасимулятор, необходимые требования к которому состоят в возможности записи во время полета параметров самолета (скорости, угла крена и т.п.) и положений органов управления самолетом, характеризуемых числами. В качестве такого симулятора выбран ВЩШОеаг [18] (рис. 2).
1.1. Управление объектом. Опишем, как происходит взаимодействие автомата и объекта управления. Кортежем входных воздействий автомата назовем упорядоченный набор из р вещественных чисел, описывающих состояние объекта управления, подаваемый на вход автомата. Применительно к задаче управления моделью беспилотного самолета кортеж входных воздействий состоит из параметров полета — высоты, скорости, углов курса, тангажа, крена и т.д.
Объект управления обладает органами управления, положение которых может изменять автомат. Положения органов управления будем задавать числами. Органы управления, множество положений которых конечно, являются дискретными. Примером дискретного органа управления является стартер, который может быть включен или выключен. Обозначим множество значений /-го, I = 1, й дискретного органа управления как V. Положение других органов управления можно задать числами из некоторого отрезка вещественной оси — это непрерывные органы управления. Например, положение руля направления, варьирующееся от крайнего левого до крайнего правого, может быть задано числами из отрезка [—1, 1]. Обозначим нижнюю и верхнюю границы
отрезка возможных значений к-го, к = 1, с непрерывного органа управления как тк и Мк соответственно.
Выходные воздействия
Параметры полета
Входные воздействия
Рис. 3. Процесс взаимодействия автомата и объекта управления
Кортежем выходных воздействий автомата назовем пару из двух упорядоченных наборов чисел: й целых и с вещественных, где й — число дискретных органов управления, с — число непрерывных органов управления. Кортеж выходных воздействий является "снимком" положений всех органов управления в некоторый момент времени. Множество выходных воздействий автомата будем считать образованным всеми возможными кортежами выходных воздействий: А = V х ...х Уй х ИъМ1] х ... х [тс,Мс].
Предикатом будем называть булеву переменную, зависящую от состояния объекта управления или среды, в которой объект находится. Примерами предикатов являются утверждения "вертикальная скорость положительна" или "угол тангажа больше 5°". Будем считать, что всю информацию, необходимую для вычисления предикатов, можно извлечь из кортежей входных воздействий. Фиксируем набор из т предикатов Рь ..., Рт. Выбор предикатов для каждого набора обучающих примеров осуществляется вручную.
Реализуем автомат как синхронный — все такты его работы происходят через равные промежутки времени (интервал между тактами равен 0.1 с). В качестве входных событий для автомата будем использовать утверждения "Р истинно" и "Р ложно" для каждого предиката Р. Для каждого события в каждом состоянии автомата будем хранить переход, для которого заданы конечное состояние и кортеж выходных воздействий (более точно — кортеж изменений выходных воздействий).
Такт состоит из т переходов: 1-й по очередности переход происходит по событию, соответствующему значению предиката Р. Пусть на некотором такте выполнились переходы, которым сопоставлены кортежи выходных воздействий с непрерывными составляющими, представленными с-мерными векторами Zl, zm, тогда непрерывная часть кортежа выходных воздействий всего такта Z формируется по правилу
где z — непрерывная часть кортежа выходных воздействий на предыдущем такте. Далее нам будет удобно считать непрерывные воздействия на переходах не ограниченными отрезками [т1, М1],..., [тс, Мс ], при этом элементы ^ при выходе за границы этих отрезков приравниваются соответствующим границам. Дискретные выходные воздействия такта устанавливаются равными дискретным воздействиям, соответствующим последнему выполнившемуся переходу.
Схема взаимодействия автомата и самолета приведена на рис. 3. Подаваемые на вход автомата кортежи входных воздействий зависят от текущего состояния самолета (параметров полета).
1.2. Обучающие примеры. Теперь формализуем понятие обучающего примера. Обозначим число моментов времени, записанное в /-м обучающем примере, как Ь1 (/ = 1, N, где N — число обучающих примеров). Далее это число будем называть длиной /-го обучающего примера. Каждый обучающий пример состоит из двух частей. Первая из них — последовательность кортежей входных воздействий I, состоящая из чисел I, ,, где / = 1, Ц — момент времени, у = 1, р — номер входного воздействия в кортеже. Вторая часть — последовательность кортежей выходных воздействий О, состоящая из чисел Д , 1 и С, , к, где / и / определяют обучающий пример и момент
времени, I = 1, й — номер дискретного органа управления, а к = 1, с — номер непрерывного органа
т
(1.1)
I=1
Таблица 1. Образец обучающего примера (р = 4, ё = 1, с = 3, Ь-, = 235)
Значения Описание г = 1 ( = 10 t = 20 г = 235
I, г, 1 Угол тангажа, град 3.078 3.544 4.112 2.412
1, 2 Угол крена, град -0.076 0.351 3.413 1.759
I, г, з Угол курса, град 198.03 198.11 198.41 205.64
1, г, 4 Скорость, узлы 251.42 252.29 253.20 289.40
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.