В чем заключается метод моделирования конечных автоматов

Конечный автомат: теория и реализация

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

Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:

Написание ИИ для хоккея. Часть 1.
Написание ИИ для хоккея. Часть 2.
Написание ИИ для хоккея. Часть 3.

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

Что такое конечный автомат?

Конечный автомат (или попросту FSM — Finite-state machine) это модель вычислений, основанная на гипотетической машине состояний. В один момент времени только одно состояние может быть активным. Следовательно, для выполнения каких-либо действий машина должна менять свое состояние.

Конечные автоматы обычно используются для организации и представления потока выполнения чего-либо. Это особенно полезно при реализации ИИ в играх. Например, для написания «мозга» врага: каждое состояние представляет собой какое-то действие (напасть, уклониться и т. д.).

На данный момент этот блок не поддерживается, но мы не забыли о нём! Наша команда уже занята его разработкой, он будет доступен в ближайшее время.

Конечный автомат можно представить в виде графа, вершины которого являются состояниями, а ребра — переходы между ними. Каждое ребро имеет метку, информирующую о том, когда должен произойти переход. Например, на изображении выше видно, что автомат сменит состояние «wander» на состояние «attack» при условии, что игрок находится рядом.

Планирование состояний и их переходов

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

Отправной точкой является состояние «find leaf», которое остается активным до тех пор, пока муравей не найдет лист. Когда это произойдет, то состояние сменится на «go home». Это же состояние останется активным, пока наш муравей не доберется до муравейника. После этого состояние вновь меняется на «find leaf».

Если состояние «find leaf» активно, но курсор мыши находится рядом с муравьем, то состояние меняется на «run away». Как только муравей будет в достаточно безопасном расстоянии от курсора мыши, состояние вновь сменится на «find leaf».

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

Реализация простого конечного автомата

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

public class FSM < private var activeState :Function; // указатель на активное состояние автомата public function FSM() < >public function setState(state :Function) :void < activeState = state; >public function update() :void < if (activeState != null) < activeState(); >> >

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

Метод update() класса FSM должен вызываться каждый кадр игры. А он, в свою очередь, будет вызывать функцию того состояния, которое в данный момент является активным.

Метод setState() будет задавать новое активное состояние. Более того, каждая функция, определяющая какое-то состояние автомата, не обязательно должна принадлежать классу FSM — это делает наш класс более универсальным.

Использование конечного автомата

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

Наш муравей представлен классом Ant, в котором есть поле brain. Это как раз экземпляр класса FSM.

public class Ant < public var position :Vector3D; public var velocity :Vector3D; public var brain :FSM; public function Ant(posX :Number, posY :Number) < position = new Vector3D(posX, posY); velocity = new Vector3D( -1, -1); brain = new FSM(); // Начинаем с поиска листка. brain.setState(findLeaf); >/** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void < >/** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void < >/** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void < >public function update():void < // Обновление конечного автомата. Эта функция будет вызывать // функцию активного состояния: findLeaf(), goHome() или runAway(). brain.update(); // Применение скорости для движения муравья. moveBasedOnVelocity(); >(. ) >

Класс Ant также содержит свойства velocity и position. Эти переменные будут использоваться для расчета движения с помощью метода Эйлера. Функция update() вызывается при каждом обновлении кадра игры.

Для понимания кода мы опустим реализацию метода moveBasedOnVelocity(). Если хотите узнать поподробнее на тему движения, прочитайте серию статей Understanding Steering Behaviors.

Ниже приводится реализация каждого из методов, начиная с findLeaf() — состояния, ответственного за поиск листьев.

public function findLeaf() :void < // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) if (distance(Game.mouse, this) >

Состояние goHome() — используется для того, чтобы муравей отправился домой.

public function goHome() :void < // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) >

И, наконец, состояние runAway() — используется при уворачивании от курсора мыши.

public function runAway() :void < // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) < // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.setState(findLeaf); >>

Улучшение FSM: автомат, основанный на стеке

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

Кажется, что изменение тривиальное. Нет, такое изменение создает нам проблему. Представьте, что текущее состояние это «run away». Если курсор мыши отдаляется от муравья, что он должен делать: идти домой или искать лист?

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

А вот и наглядная демонстрация работы конечного автомата, основанного на стеке:

Реализация FSM, основанного на стеке

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

public class StackFSM < private var stack :Array; public function StackFSM() < this.stack = new Array(); >public function update() :void < var currentStateFunction :Function = getCurrentState(); if (currentStateFunction != null) < currentStateFunction(); >> public function popState() :Function < return stack.pop(); >public function pushState(state :Function) :void < if (getCurrentState() != state) < stack.push(state); >> public function getCurrentState() :Function < return stack.length >0 ? stack[stack.length - 1] : null; > >

Обратите внимание, что метод setState() был заменен на pushState() (добавление нового состояния в вершину стека) и popState() (удаление состояния на вершине стека).

Использование FSM, основанного на стеке

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

public class Ant < (. ) public var brain :StackFSM; public function Ant(posX :Number, posY :Number) < (. ) brain = new StackFSM(); // Начинаем с поиска листка brain.pushState(findLeaf); (. ) >/** * Состояние "findLeaf". * Заставляет муравья искать листья. */ public function findLeaf() :void < // Перемещает муравья к листу. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this) if (distance(Game.mouse, this) > /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void < // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) if (distance(Game.mouse, this) > /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void < // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) < // Нет, уже далеко. Пора возвращаться к поискам листочков. brain.popState(); >> (. ) >

Вывод

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

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

Перевод статьи «Finite-State Machines: Theory and Implementation».

4. Моделирование поведения

При создании программной системы недостаточно ответить на вопросы что делает система? ( глава 2) и из чего она состоит? (глава 3) — требуется ответить на вопрос как работает система?. Ответ на этот вопрос дает модель поведения. Поведение реальной программы целиком и полностью определяется ее кодом — как программа составлена, так она и выполняется (с точностью до сбоев) — «от себя» компьютер ничего не придумывает. Но программа — это просто запись алгоритма. Таким образом, мы приходим к следующему определению.

Модель поведения (behavior model) ‒ это описание алгоритма работы системы.

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

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

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

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

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

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

4.1.1. Конечные автоматы

Конечным автоматом (Мили) называется совокупность пяти объектов:

конечного множества $A=\$, называемого входным алфавитом; элементы множества $A$ называются входными символами, сигналами, событиями, стимулами или воздействиями;
конечного множества $Q=\$, называемого алфавитом состояний; элементы множества $Q$ называются состояниями;
конечного множества $B=\$, называемого выходным алфавитом; элементы множества $B$ называются выходными символами, реакциями или воздействиями;
тотальной (всюду определенной) функции $\delta : A \times Q \to Q$, называемой функцией переходов;
тотальной функции $\lambda : A \times Q \to B$, называемой функцией выходов.

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

Автоматное преобразование. Пусть задан автомат $S$, некоторое состояние $q$ из алфавита $Q$ этого автомата и входное слово $\alpha$ в алфавите $A$. По этой информации однозначно определяется выходное слово $\beta$ в алфавите $B$. А именно, по состоянию $q$ и первому символу слова $\alpha$ с помощью функции выходов $\lambda$ определяется первый символ слова $\beta$ и с помощью функции переходов $\delta$ определяется следующее состояние автомата. Затем по новому состоянию и второму символу входного слова $\alpha$ определяется второй символ выходного слова $\beta$ и следующее состояние. И так далее. Поскольку функции $\lambda$ и $\delta$ тотальны, автомат $S$ и состояние $q$ определяют некоторый алгоритм преобразования слов в алфавите $A$ в слова в алфавите $B$.

Преобразование слов в алфавите $A$ в слова алфавите $B$ с помощью автомата $S$ называется автоматным преобразованием и обычно обозначается той же буквой $S$, что и автомат.

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

автоматное преобразование сохраняет длину, то есть результат преобразования состоит из такого же числа символов, что и аргумент, $\mid\alpha\mid = \mid S(\alpha)\mid$;
автоматное преобразование обладает свойством префикса ∇ , $S(\alpha + \beta) = S(\alpha) + S(\beta)$, где $+$ — операция конкатенации (сцепления строк).

∇ Другими словами, автоматное преобразование является гомоморфизмом, «уважающим» конкатенацию.

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

Реактивные системы. Конечный автомат можно интерпретировать и другим образом, а именно, можно считать, что элементы множества $A$ — это стимулы (события), а элементы множества $B$ — это реакции (обработчики событий). В таком случае, если задан автомат $S$ и некоторое состояние $q$ этого автомата, то описано автоматное поведение, то есть последовательность (возможно, бесконечная) пар «стимул — реакция».

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

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

В настоящее время общепринятым является тезис Чёрча–Тьюринга — фундаментальное утверждение, высказанное Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов. В самой общей форме оно гласит, что любая интуитивно вычислимая функция может быть вычислена некоторой машиной Тьюринга, и таким образом, понятие машины Тьюринга равнообъемно понятию алгоритма.

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

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

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

Во-первых, сразу выделяют одно состояние, которое считается начальным (обычно ему дают номер 0 или 1 ).

Автомат с выделенным начальным состоянием называется инициальным.

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

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

Автомат называется автоматом Мура, если функция выходов зависит только от состояния. В этом случае данная функция обычно обозначается $\mu : Q \to B$ и называется функцией пометок.

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

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

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

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

Первая модификация является стандартным приемом в синтаксическом анализе. Автомату вообще не назначается функция выходов, только функция переходов. При этом среди состояний выделяется подмножество допускающих состояний (остальные состояния, соответственно, считаются недопускающими). Если на вход такому автомату подать последовательность входных символов (анализируемое слово), то в конце работы автомат окажется в каком-то состоянии (допускающем или недопускающем). В первом случае говорят, что автомат допустил входное слово, а во втором — отверг. Такой автомат называется распознавателем, поскольку он распознает среди всех слов множество допустимых, т.е. распознает некоторый язык. Ответ на вопрос, каков класс языков, распознаваемых конечными автоматами, явился одним из первых фундаментальных результатов теории автоматов ∇ , и этот ответ довольно любопытен: автоматами можно распознать те и только те языки, которые описываются регулярными выражениями.

∇ Распространен предрассудок, что конечные автоматы применяются только для синтаксического анализа. Это не так. Действительно, первые результаты и первые применения теории автоматов были получены именно в синтаксическом анализе. Но потом появились другие результаты и другие области применения.

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

Автомат, имеющий одно состояние, называется комбинационным.

Ясно, что в комбинационном автомате функция переходов тривиальна, и фактически комбинационный автомат$nbsp;— это просто функция, которая сопоставляет входному символу выходной.

∇ Напомним, что исходя из определения, данного в начале этого параграфа, конечный автомат имеет конечное число состояний.

Рис. Сеть интерпретатора конечного автомата

Впрочем, верно и обратное утверждение: для любой сети можно построить эквивалентный конечный автомат.

∇ Эти модификации относятся к классу экстравагантных и редко реализуются на практике, возможно, потому, что к ним еще не привыкли.

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

Если отношение перехода $\delta$ является многозначным, $\delta : A \times Q \to 2^Q$, то автомат называется недетерминированным.

Недетерминированный ∇ автомат на каждом такте своей работы находится в одном или одновременно в нескольких состояниях. На первый взгляд такая конструкция кажется неустойчивой и даже невозможной, но это впечатление обманчиво. Теорема детерминизации утверждает, что для любого недетерминированного конечного автомата существует эквивалентный ему детерминированный. Идея конструктивного доказательства этой теоремы проясняет ситуацию. Пусть дан недетерминированный автомат с множеством состояний $Q$ . Рассмотрим детерминированный автомат с множеством состояний $2^Q$, т.е. новое множество состояний — это множество всех подмножеств исходного. Остается только заменить многозначные переходы из одного подмножества старых состояний в другое подмножество однозначными переходами из одного нового состояния в другое. Отсюда видно, что недетерминированное описание поведения может быть экспоненциально короче детерминированного описания того же самого поведения.

∇ Недетермированность часто путают со случайностью или неопределенностью, и пугаются этого слова. Напрасно. В данном контексте в недетерминированном поведении нет ничего случайного или неопределенного.

4.1.2. Применение автоматов

Количество рассмотренных (и детально исследованных!) вариаций на тему конечных автоматов весьма велико — их обзор не является предметом данной книги. Нас интересует, почему теория конечных автоматов была использована авторами UML в качестве средства моделирования поведения. По нашему мнению, основных причин три:

теоретическая;
историческая;
практическая.

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

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

Этот список можно продолжать неограниченно: первое слово в теореме Райса — «все». Значит ли это, что вообще все неразрешимо и про алгоритмы ничего нельзя узнать? Разумеется, нет. Если дана конкретная запись алгоритма, то путем ее индивидуального изучения, скорее всего, можно установить наличие или отсутствие нужных свойств. Речь идет о том, что невозможен единый метод, пригодный для всех случаев.

Обратите внимание, что теорема Райса справедлива в случае использования любой, но универсальной модели вычислимости (способа записи алгоритмов). Если же используется не универсальная модель вычислимости, то теорема Райса не имеет места. Другими словами, существуют подклассы алгоритмов, для которых некоторые важные свойства оказываются алгоритмически разрешимыми. Конечные автоматы являются одним из важнейших таких подклассов. С одной стороны, данный формализм оказывается достаточно богатым, чтобы выразить многие практически нужные алгоритмы (примеры см. ниже), с другой стороны, целый ряд свойств автоматов можно проверить автоматически, причем найдены весьма эффективные алгоритмы. В частности, проблемы эквивалентности и остановки для автоматов эффективно разрешимы. В случае использования универсального языка программирования мы не можем автоматически убедиться в правильности программы: нам остается только упорно тестировать ее в смутной надежде повысить свою уверенность в надежности программы. В случае же использования конечных автоматов многое можно сделать автоматически, надежно и математически строго — поэтому теория конечных автоматов столь интересна для разработки программных систем.

Историческая причина популярности конечных автоматов состоит в том, что данная техника развивается уже достаточно давно и теоретические результаты были с успехом использованы при решении многих практических задач. В частности, системы проектирования, спецификации и программирования, основанные на конечных автоматах и их модификациях, активно развиваются и применяются уже едва ли не полвека. Особенно часто конечные автоматы применяются в конкретных предметных областях, где можно обойтись без использования универсальных моделей вычислимости. В результате очень многие пользователи, инженеры и программисты хорошо знакомы с конечными автоматами и применяют их без затруднений. Мы не готовы дать исчерпывающий обзор предметных областей, где применяются конечные автоматы, и ограничимся одним достаточно показательным примером. В области телекоммуникаций уже более 15 лет активно применяется промышленный стандарт — язык спецификации и описания алгоритмов SDL (Specification and Description Language).

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

Первый способ — табличный. Автомат записывается в форме таблицы, столбцы которой помечены символами входного алфавита, строки помечены символами алфавита состояний, а в ячейках таблицы записаны соответствующие значения функций $\delta$ и $\lambda$. Рассмотрим пример, речь в котором пойдет об автомате, который вычисляет натуральное число, следующее по порядку за данным, по представлению данного числа в позиционной двоичной системе счисления. Входной и выходной алфавиты состоят из символов 0 , 1 и s (пробел). Для упрощения примера будем считать, что двоичные цифры записи числа поступают на вход автомата в обратном порядке — справа налево, то есть первым поступает младший разряд. Автомат имеет три состояния, которые для ясности мы назовем «начальное», «перенос» и «копирование». Пусть на вход конечного автомата, заданного таблицей, расположенной ниже, поступает число 1101 , а результат, который мы должны получить – 1110 , т.е. натуральное число, следующее за исходным.

Ниже приведена таблица соответствующего конечного автомата.

Табл. Таблица конечного автомата

0	1	s
начальное	копирование, 1	перенос, 0	начальное, s
перенос	копирование, 1	перенос, 0	начальное, 1
копирование	копирование, 0	копирование, 1	начальное, s

На вход автомата символы поступают в обратном порядке, т.е. сначала 1 , затем 0 , 1 и 0 . Изначально автомат находится в состоянии «начальное» и при поступлении первого входного символа 1 переходит в состояние «перенос», передавая на выход 0 (первая строка, третий столбец). Далее на вход поступает 0 и автомат из состояния «перенос» переходит в состояние «копирование» (вторая строка, второй столбец). Обработку двух последних входных символов оставим в качестве упражнения для читателя.

Второй способ — графический. Автомат изображается в виде диаграммы ориентированного графа, узлы которого соответствуют состояниям и помечены символами алфавита состояний, а дуги называются переходами и помечены символами входного и выходного алфавита следующим образом. Допустим, $\delta(a_i, q_j)=q_u$, $\lambda(a_i, q_j)=b_v$. Тогда проводится дуга из узла $q_j$ в узел $q_u$ и помечается символами $a_i, b_v$. Такой граф называется диаграммой состояний-переходов. На следующем рисунке приведена диаграмма графа состояний-переходов для примера, заданного предыдущей таблицей.

Рис. Диаграмма состояний-переходов

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

В процессе применения в программировании автоматная техника обогатилась рядом приемов, которые не совсем укладываются в исходную математическую модель, но очень удобны на практике. Например, помимо функций переходов и выходов, можно включить в описание автомата еще одну составляющую — процедуру реакции. Смысл добавления состоит в следующем: при выполнении перехода из одного состояния в другое вызывается соответствующая процедура реакции, которая выполняет еще какие-то действия (имеет побочный эффект, см. параграф 3.2.4), помимо вывода выходного символа и смены состояния. Если процедура реакции ничем не ограничена, например, может читать и писать в потенциально бесконечную память, то конечный автомат превращается, фактически, в универсальную модель вычислимости подобную машине Тьюринга. При этом, разумеется, утрачиваются теоретически привлекательные свойства разрешимости, однако программировать с помощью процедур реакции очень удобно. Разработаны и различные промежуточные варианты: например, если побочный эффект процедур реакции ограничен работой со стеком, то получается так называемый магазинный автомат. Магазинные автоматы позволяют запрограммировать существенно более широкий класс алгоритмов и в то же время сохраняют некоторые из важнейших теоретических преимуществ.

Наконец, важным практическим обстоятельством является тот факт, что автоматы очень легко программируются средствами обычных языков программирования. Например, пусть нужно запрограммировать работу автомата с состояниями 1, 2, …, k , где 1 — начальное состояние и k — заключительное состояние, а входные стимулы: A, B, … Z можно получить с помощью функции get() . В таком случае можно использовать код следующей структуры:

state := 1 while state ≠ k stimulus := get() switch state case 1 switch stimulus case A // какие-то действия state := s // новое состояние case B . . . end switch stimulus . . . end switch state end while

Мы закончим этот параграф небольшим примером из информационной системы отдела кадров.

ИЗМЕНЕНИЯ В ТЕХНИЧЕСКОМ ЗАДАНИИ После приема на работу соискатель становится штатным сотрудником. Штатный сотрудник может быть переведен с одной должности на другую. Штатный сотрудник может быть уволен.

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

Табл. Жизненный цикл сотрудника

Принять hire()	Перевести move()	Уволить fire()
Кандидат Applicant	Принять(), В штате	Ошибка(), Кандидат	Ошибка(), Кандидат
В штате Employed	Ошибка(), В штате	Перевести(), В штате	Уволить(), Уволен
Уволен Unemployed	Принять(), В штате	Ошибка(), Уволен	Ошибка(), Уволен

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

Рис. Жизненный цикл сотрудника в ИС ОК

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

4.1.3. Сети Петри

Предыдущие два параграфа могут создать впечатление, что конечные автоматы — единственный теоретический механизм, который используется для моделирования поведения. Это не совсем так. Конечные автоматы и их многочисленные модификации действительно используются чаще всего, но есть и другие формализмы, которые также применяются на практике, в том числе и в UML.

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

Известно множество различных модификаций сетей Петри, предложенных для решения конкретных задач. Мы рассмотрим самый простой вариант. В этом варианте сеть Петри определяется как ориентированный двудольный граф, имеющий вершины двух видов, которые называются позиции и переходы. На диаграмме позиции обычно изображаются в виде небольших кружков, а переходы в виде горизонтальных черточек. Для сети Петри определяется понятие маркировки, которая сопоставляет каждой позиции неотрицательное целое число. На диаграмме маркировка обозначается с помощью маленьких черных кружков, которые помещаются внутрь позиций. Разные авторы называют эти кружки по-разному: точки, маркеры, отметки, ярлыки, фишки и т. п. У каждого перехода в сети Петри есть некоторое количество (может быть ноль) входных позиций (из которых дуги ведут в переход) и некоторое количество (может быть ноль) выходных позиций (в которые дуги ведут из перехода). Переход в сети Петри называется разрешенным, если все его входные позиции не пусты (т. е. их маркировка строго больше нуля). Любой разрешенный переход может сработать. В результате срабатывания перехода маркировка всех входных позиций уменьшается на 1 , а маркировка всех выходных позиций увеличивается на 1 . На диаграмме количество маркеров во входных позициях уменьшается, а в выходных — увеличивается. В результате срабатывания перехода маркировка сети Петри изменяется: некоторые переходы могут стать разрешенными или, наоборот, перестать быть таковыми.

Сеть Петри является удобным формализмом для описания поведения, в особенности асинхронного, параллельного и недетерминированного. Рассмотрим, например, простую вычислительную систему (процессор), последовательно обрабатывающую задания, которые поступают во входную очередь. Когда процессор свободен и во входной очереди имеется задание, оно обрабатывается процессором, а затем выводится в выходную очередь. На следующем рисунке приведена сеть Петри, моделирующая эту систему. Если в условиях начальной маркировки, показанной слева, сработают переходы $t_1, t_2, t_1, t_1$, то сеть будет иметь маркировку, показанную на рисунке справа. Обратите внимания, что срабатывание переходов $t_1, t_1, t_2, t_1$ или $t_1, t_1, t_1, t_2$ даст тот же самый результат, а срабатывание переходов $t_2, t_1, t_1, t_1$ невозможно, потому что переход $t_2$ не разрешен в начальной маркировке.

Рис. Сеть Петри

По сравнению с конечными автоматами сети Петри обладают рядом особенностей, которые объясняют их широкое применение для моделирования параллелизма. Прежде всего, сети Петри асинхронны — в них отсутствует понятие времени. Время срабатывания и относительный порядок срабатывания разрешенных переходов никак не указываются. Тем не менее, сама структура сети позволяет в некоторых случаях отвечать на важнейший вопрос: какими свойствами будет обладать маркировка, получаемая в результате произвольной последовательности срабатываний переходов. Например, нетрудно доказать, что позиция $p_2$ никогда не будет иметь маркировку больше 1 (что, очевидно, имеет явный практический смысл — процессор может обрабатывать только одно задание). Далее, в сетях Петри очень наглядно и четко моделируется параллелизм (переходы, входные позиции которых не пересекаются, параллельны), конфликты (переходы, входные позиции которых пересекаются, конфликтуют), тупики (переходы, которые не разрешены в данной маркировке и всех достижимых из нее) и т. д. Наконец, теория сетей Петри за последние десятилетия была разработана достаточно глубоко и детально, чтобы давать ответы на многие трудные вопросы практического параллельного программирования.

Основной механизм сетей Петри дает повод упомянуть одну важную теоретическую идею, которая хотя и не образует отдельного формализма, но иногда бывает очень полезна для моделирования поведения как в UML, так и в других случаях. Заметим, что переход в сети Петри может сработать, если все его входные позиции не пусты — в них что-то есть. Никто снаружи «не подталкивает» переход к срабатыванию — переход «сам» определяет, что есть условия для его срабатывания.

Сопоставим это с механизмом процедур (функций, действий и т.п.) в языках программирования. В каких случаях срабатывает процедура? Первый, самый привычный случай — процедуру вызвали, т.е. явно передали ей управление извне ∇ . Второй случай — процедура является процедурой реакции на события. Эти два случая исчерпывают возможности обычных процедурных языков программирования. Но возможен еще и третий случай: процедура срабатывает, потому что определены все ее аргументы. Такое срабатывание не является характерным для распространенных языков программирования, но вызывает наибольшие человеческие симпатии у авторов. Действительно, первый случай — работа выполняется «из-под палки», второй — работа выполняется потому, что что-то случилось, третий — работа выполняется потому, что ее можно выполнить.

∇ Еще нужно не забыть передать аргументы!

4.1.4. Средства моделирования поведения

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

Мы разделили все средства моделирования поведения в UML на четыре группы

описание поведения с явным выделением состояний;
описание поведения с явным выделением потоков данных и управления;
описание поведения как последовательности сообщений во времени;
описание параллельного поведения.

Заметим, что полного взаимно-однозначного соответствия между выделенными группами и каноническими диаграммами UML не наблюдается. Действительно, если первые две группы средств однозначно отображаются диаграммами автомата и диаграммами деятельности, то для описания последовательности сообщений применяется несколько различных типов диаграмм, а описание параллельного поведения «размазано» по всем типам канонических диаграмм. Рассмотрим эти четыре группы средств в целом, «с высоты птичьего полета», не углубляясь пока в детали нотации и семантики.

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

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

Жизненный цикл (lifecycle) — последовательность изменений состояния объекта.

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

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

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

Поток управления ‒ это последовательность выполнения операторов (команд) в программе.

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

Во-первых, на поток управления оказывают влияние различные управляющие конструкции: операторы перехода, условные операторы, операторы цикла и т.д.

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

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

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

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

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

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

Именно диаграммы взаимодействия претерпели наибольшее расширение и усовершенствование в UML 2 по сравнению с UML 1.

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

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

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

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

Использование автоматов для эмулирования жизни

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

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

Рисунок 1 — П оведение змейки

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

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

Рисунок 2 — У сложнение действий в поведении змейки

Казалось бы, ничего существенно не поменялось. Однако перед программистом, который решил сымитировать жизнь змеи, встала огромная проблема. Теперь из состояния «убежать от врага» змея может попасть сразу в 2 состояния: «поиск добычи» или «отправиться домой». Как было сказано ранее, змее надо отправиться домой, если она уже была в пути домой; в противном случае ей надо продолжать охотиться. Для решения таких задач были придуманы конечные автоматы, основанные на стеке.

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

Рисунок 3 — Пример стека состояний змеи

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

Рисунок 4 — Пример усложненного графа состояний змеи

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

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

Сети Петри

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

Приведем простой пример, для того чтобы понять устройство сетей. Представим, что человек возвращается домой с работы и не хочет терять время на приготовление еды. Лучшим способом будет заказать еду в каком-либо магазине. Также представим, что человек захочет заехать в магазин по пути домой. Садясь в машину, человек может позвонить в службу доставки еды, а затем в навигаторе указать номер ближайшего магазина. В таком случае решение задачи “заказать еду” и “съездить в магазин” может быть записано в виде автомата:

Рисунок 5 — Пример простого автомата выбора человека

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

Рисунок 6 — Сеть Петри действий человека

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

Применение NLP для автоматического построения сетей Петри

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

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

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

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

Генерация конечных автоматов для управления моделью беспилотного самолета Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Александров Антон Вячеславович, Казаков Сергей Владимирович, Сергушичев Алексей Александрович, Царев Федор Николаевич, Шалыто Анатолий Абрамович

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

GENERATION OF FINITE STATE MACHINES FOR UNMANNED AIRPLANE CONTROLLING

A genetic programming method for induction of finite state machines with continuous and discrete output actions is suggested in the article. Instead of the known approach using modeling as a controlling automaton quality estimation and demanding much time we use method of automata behavior comparison with human controlling behavior. Special feature of this approach is the opportunity to use controlling objects not only with discrete but with continuous parameters. This approach is illustrated by the example of finite state machine creation for unmanned airplane controlling in the loop mode.

Текст научной работы на тему «Генерация конечных автоматов для управления моделью беспилотного самолета»

ТЕХНОЛОГИИ АВТОМАТНОГО ПРОГРАММИРОВАНИЯ И ИСКУССТВЕННОГО

ГЕНЕРАЦИЯ КОНЕЧНЫХ АВТОМАТОВ ДЛЯ УПРАВЛЕНИЯ МОДЕЛЬЮ

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

Ключевые слова: конечные автоматы, генетическое программирование, беспилотный самолет.

В последнее время для программирования систем со сложным поведением все шире применяется автоматное программирование, в рамках которого поведение программ описывается с помощью конечных детерминированных автоматов (в дальнейшем — автоматов) [1].

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

Для многих задач управляющие автоматы удается строить эвристически, но существуют задачи, для которых такое построение невозможно или затруднительно. К этому классу относятся, например, задача «Умный муравей» [2-4], задача «Умный муравей-3» [5] и задача об управлении моделью беспилотного летательного аппарата [6].

Существует несколько подходов к решению последней задачи. Один из них состоит в выделении «идеальной» траектории из нескольких полетов, выполненных человеком, и последующем следовании ей. Такой подход описан в работе [7].

Другой подход — использование автоматов для управления беспилотным летательным аппаратом и построение таких автоматов с помощью генетических алгоритмов, описанных в работах [8-12].

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

Цель настоящей работы — разработка лишенного указанного недостатка метода, основанного на генетическом программировании, для построения автоматов, управляющих объектами со сложным поведением. Для этого предлагается строить автоматы управления таким объектами отдельно для каждого из их режимов работы с помощью генетического программирования, используя обучающие примеры, создаваемые для каждого режима. Задавая большое число обучающих примеров, можно, как и в работе [7], избавиться от неточностей, допускаемых человеком при управлении. Такой подход является развитием идей, предложенных в работе [14], в которой рассматривались только объекты, управляемые дискретными выходными воздействиями.

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

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

А.В. Александров, С.В. Казаков, А.А. Сергушичев, Ф.Н. Царев, А.А. Шалыто

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

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

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

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

Подход, предлагаемый в настоящей работе, ориентирован на объекты управления как с дискретными, так и с непрерывными органами управления. Если все органы дискретны, то следует использовать методику, изложенную в работе [14].

Непрерывное воздействие изменяет параметр органа управления на некоторую вещественную величину, а дискретное — устанавливает соответствующий орган управления в конкретное значение. Заметим, что последовательное выполнение действий с одним органом управления эквивалентно сумме воздействий на него в случае непрерывного воздействия и последнему воздействию — в случае дискретного.

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

В свою очередь, примером дискретного исполнительного органа является стартер. Дискретное воздействие на него — включение или выключение. Тогда последовательность включений и выключений стартера эквивалентна последнему, совершенному над ним действию.

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

Каждый элемент Т.т[(] последовательности входных параметров состоит из Р чисел — значений этих параметров в момент времени /.

Элемент Т.ат[] включает в себя два набора: Т.атЩ.й и Т.ат[].с. Последовательность Т.атЩ.й состоит из Б дискретных, а Т.атЩ.с — из С непрерывных параметров. Таким образом, Т.атЩ состоит из Б + С чисел.

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

Предлагаемый алгоритм генетического программирования

Существуют различные модели алгоритмов генетического программирования, например, классический и островной [15].

Классический алгоритм генетического программирования состоит из следующих шагов: 1. Создание начальной популяции. 2. Вычисление значений функции приспособленности. 3. Отбор особей для скрещивания. 4. Скрещивание. 5. Мутация.

Поколение, полученное после шага 5, становится текущим, и шаги 2-5 повторяются, пока не будет достигнуто условие останова.

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

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

Ниже приведено описание этого алгоритма в порядке, удобном для понимания.

Особь в предлагаемом алгоритме генетического программирования

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

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

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

На рис.1 изображен возможный «скелет» автомата.

Рис. 1. «Скелет» автомата

Для данного скелета хо-х4 — заданные предикаты, а значения выходных воздействий (кортежей) 21, . 28 определяются в дальнейшем с помощью алгоритма их расстановки.

Выбранная функция приспособленности отражает близость поведения автомата к эталонному и имеет вид

Для вычисления ее значения на вход автомата подается каждая из N последовательностей T[i].in -входной набор i-го теста и определяется последовательность значений управляющих параметров T[i].out, которую генерирует автомат.

Здесь под Dist(out, ans) понимается «расстояние» между выходной и эталонной последовательностями управляющих параметров, которое вычисляется по формуле

■ ■ [out[t].d[k] ф ans [t].d[k]] + ■ (out[t].c[k] — ans [t].c[k])2

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

Алгоритм расстановки воздействий — дополнительный шаг в алгоритме генетического

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

■ Dist (T [i].out,T [i].ans)2

i=l Dist(T [i].ans,0)2

Суммы по каждому параметру можно минимизировать независимо друг от друга. Значит, необходимо минимизировать сумму T [i].len

i=1 Dist (T [i].ans,0)2

для каждого k от 1 до D и сумму

i=1 Dist (T [i].ans,0)2

для m от 1 до C. Далее считаем индексы k и m зафиксированными.

Расстановка дискретных воздействий. Выделим из суммы (2) слагаемые, соответствующие каждому переходу:

i=1 j =1teTimei,j Dist(T[i].ans,0)2 j=l i=l teTimeг,j Dist(T[i].ans,0)2

Здесь Timei,j — множество таких моментов времени t, при которых номер последнего выполненного перехода автомата, запущенного на тесте i, равен j, а n — число переходов в автомате.

Таким образом, для каждого j от 1 до n необходимо минимизировать выражение

i=1 teTimei , Dist(T[i].ans,0)2

Зафиксируем j. Как и в случае, когда обучающий пример состоит из одного теста, T[i].out[t].d[k] при t e Timei j равно значению k-го дискретного параметра на переходе j. Обозначим его через u.

Сгруппируем слагаемые с одинаковым значением T[i].ans[t].d[k]. При этом получим:

h=1 i=1 teTimeV, j,h Dist(T[i]ans,0)2 h=1 i=1 Dist(T[i]ans,0)2 teTimeV,j1

ф vh ]■ ]TimeVi j h|

= ZZ„. i::h\21 Timer, J = ■ h=1 ‘ ‘

G N Г , 1 N [u ф vh] ■ ■

h=1 i=1 Dist (T [i] .ans,0) i=1 Dist (T [i].ans,0)

Здесь vh — к-ое значение k-го дискретного параметра, G — число возможных значений этого параметра, TmeVij,h — множество тех моментов времени / из Ттеу, при которых Т[0].атЩ.с1[Щ равно vh.

Выбрав уи в качестве значения дискретного параметра на /’-ом переходе, получим следующее значение суммы:

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

.апш,0) / _1 Dist(T [/].апш,0)

Для минимизации суммы (4) необходимо выбрать то значение уи, при котором N 1 I-1- I

Т/те¥/ у максимально. Таким образом, на у-ом переходе в качестве значения к-го

дискретного параметра следует выбрать уи, где И _ argmaxI——\Т/теУ/ Л .

Расстановка непрерывных воздействий. Ввиду того, что величина изменения т-го непрерывного параметра в момент времени t (Т[/].ои^].с[т]) равна сумме изменений этого параметра на всех выполненных переходах к этому моменту, из формулы (3) получим:

Здесь, как и раньше, ц — неизвестная величина изменения т-го непрерывного параметра на у-ом переходе, а а/ у ^] — число выполненийу-го перехода к моменту времени t автомата, запущенного на тесте /.

Производная 8 по иИ имеет вид

I 2а, рЩ !аг- у[t]Uj■ — Т[/].аns[t].c[m]

Приравняв все 8’и к нулю, для каждого непрерывного параметра т получим систему из п уравне-

!а / 2^ ]а/, у ^ ] иу «I

п ( N 1 Т[/].1еп Л N 1 Т[,].1еп

I I-2 !а /,п №,, у [t] и у «I-2 IТЩ.атЩ.с[т]а ,,п [t].

/_1 БШ(Т [/].апш,0) V /_1 Бгш^Т [/].апш,0)

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

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

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

Операторы алгоритма генетического программирования

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

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

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

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

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

— изменение начального состояния;

— добавление, удаление или изменение случайного перехода в «скелете» автомата.

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

Оператор скрещивания. В скрещивании принимают участие две особи. Результатом применения оператора также являются две особи. Обозначим «родительские» особи как Р1 и Р2, а «дочерние» — С1 и С2. Тогда для стартовых состояний С1./^’ и С2./8 справедливо одно из следующих утверждений:

— C1.is = Р1и С2./8 = Р2./&;

— С1= Р2./8 и С2./8 = Р1./&\

Далее для каждой ячейки таблицы переходов ^И][]] с равной вероятностью выбирается один из следующих вариантов:

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

Взаимодействие сгенерированного автомата с моделью беспилотного самолета. Существуют симуляторы, моделирующие полет самолета. Авторами был выбран свободный кроссплатформенный симулятор FlightGear (http://www.flightgear.org), который применительно к настоящей работе позволяет осуществлять как ручное, так и автоматное управление моделью самолета. На рис. 2 представлен снимок экрана симулятора FlightGear в момент начала разгона.

Рис. 2. Снимок экрана симулятора РНдМОвэг в момент начала разгона

Симулятор позволяет осуществлять сохранение параметров полета (скорость, направление полета и т.д.) и параметров самолета (положение руля, элеронов, состояние стартера и т.п.). Параметры полета являются входными параметрами для системы управления, а параметры самолета — управляющими, так как за счет их изменений выполняется управление самолетом. Значения управляющих параметров формируются автоматом (рис. 3).

Новые значения управляющих параметров

значении управляющих параметров

Рис. 3. Управление самолетом с помощью автомата

Задача генерации автомата, выполняющего «мертвую петлю». Эта задача может быть сформулирована следующим образом: требуется построить автомат, под управлением которого модель самолета делает мертвую петлю, а затем ровно пролетает несколько секунд.

Использование предлагаемого метода. Кратко рассмотрим основные шаги применения предлагаемого метода на рассматриваемом примере:

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

— сформирован необходимый и достаточный набор утверждений о состоянии самолета;

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

— каждый набор состоял из 10 тестов;

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

— опрос параметров производился 10 раз в секунду;

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

Перечислим параметры алгоритма и их значения:

— размер поколения — 100 особей;

— число состояний автомата — от двух до пяти;

— вероятность мутации — 0,5;

— метод отбора — турнирный;

— размер элиты — две особи;

— величина такта — 0,1 с.

Вычисления производились на одном ядре компьютера с процессором Intel Core 2 Duo T7250 с тактовой частотой 2 ГГц под управлением операционной системы Microsoft Windows XP. Язык программирования — Java.

В среднем время работы алгоритма составляло около 10 часов для одного набора параметров и одного набора тестов. При этом было вычислено около двух тысяч поколений. Таким образом, создание и обработка одного поколения в среднем занимала около 20 с или 0,2 с на один автомат, что значительно меньше, чем в работе [13], где это занимало около 5 минут. Выбранные утверждения:

— x0 — двигатель включен;

— x1 — ускорение изменения направления движения самолета больше нуля;

— x2 — скорость изменения направления движения самолета больше нуля;

— x3 — величина отклонения от начального направления меньше одного градуса;

— x4 — величина отклонения от начального направления больше нуля (отклонение влево);

— x5 — ускорение изменения крена (угла наклона) больше нуля;

— x6 — скорость изменения крена больше нуля;

— x7 — крен самолета маленький (меньше одного градуса);

— x8 — крен больше нуля (самолет завалился на правый бок);

— x9 — ускорение изменения вертикальной скорости самолета больше нуля;

— xj0 — скорость изменения вертикальной скорости больше нуля;

— xji — вертикальная скорость маленькая (меньше 0,1 метра в секунду);

— x12 — вертикальная скорость больше нуля (самолет поднимается).

Управляющими органами являются магнето, стартер, дроссель, элероны, руль высоты и руль направления. Первые два органа являются дискретными, а остальные — непрерывными. При этом, напри-

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

В результате запусков алгоритма генетического программирования было установлено:

— автоматы с тремя-четырьмя состояниями «ведут себя» достаточно хорошо;

— с увеличением числа состояний автомата его структура становится все менее логичной, а поведение ухудшается.

Записанные тесты. Приведем ссылки на некоторые видеозаписи полетов под управлением человека:

— успешное выполнение «мертвой петли» (этот полет вошел в обучающий набор) -http://www.youtube.com/watch?v=G5Kcx0ohpNo;

— неудачное выполнение — http://www.youtube.com/watch?v=OGVTch-a97A.

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

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

В процессе наблюдения за ходом выполнения «мертвой петли» под управлением лучшего автомата было установлено, что в зависимости от параметров среды и самолета при запуске автомата возможны три варианта выполнения «петли»:

1. В большинстве случаев модель самолета, как и при управлении вручную, выполняет одну «мертвую петлю» и летит дальше;

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

3. Модель может вообще не выполнить «мертвую петлю», так как автомат не справляется с управлением, что, правда, бывает крайне редко.

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

Пример полета самолета под управлением лучшего из полученных автоматов

Ниже приведены ссылки на видеозаписи трех вариантов реализации «мертвой петли» под управлением лучшего автомата:

1. Выполнение «мертвой петли», близкое к «идеальному» (http://www.youtube.com/watch?v=TzrLoJjjVTA);

2. Выполнение «мертвой петли» с заваливанием на левый борт с последующим выравниванием (http://www.youtube.com/watch?v=C6WV7x2bqE8);

3. Последовательное выполнение двух «мертвых петель» (http://www.youtube.com/watch?v=yFiG4yz67Ks).

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

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

Исследование выполнено по Федеральной целевой программе «Научные и научно-педагогические кадры инновационной России на 2009-2013 годы» в рамках государственного контракта П1188 от 27 августа 2009 года.

1. Поликарпова Н.И., Шалыто А.А. Автоматное программирование. — СПб: Питер, 2010. — 176 с.

2. Angeline P., Pollack J. Evolutionary Module Acquisition // Proceedings of the Second Annual Conference on Evolutionary Programming. Cambridge: MIT Press, 1993. — Р. 154-163.

3. Jefferson D., Collins R., Cooper C., Dyer M., Flowers M., Korf R., Taylor C., Wang A. The Genesys System: Evolution as a Theme in Artificial Life // Proceedings of Second Conference on Artificial Life. — MA: Addison-Wesley, 1992. — P. 549-578.

4. Царев Ф.Н., Шалыто А.А. Применение генетического программирования для генерации автомата в задаче об «Умном муравье» / Сборник трудов IV-ой Международной научно-практической конференции. — М.: Физматлит, 2007. — Т. 2. — С. 590-597.

5. Бедный Ю.Д., Шалыто А.А. Применение генетических алгоритмов для построения автоматов в задаче «Умный муравей». — СПбГУ ИТМО, 2007 [Электронный ресурс]. — Режим доступа: http://is.ifmo.ru/works/ant, свободный. Яз. рус. (дата обращения 09.02.2011).

6. Паращенко Д.А., Царев Ф.Н., Шалыто А.А. Технология моделирования одного класса мультиагент-ных систем на основе автоматного программирования на примере игры «Соревнование летающих тарелок». Проектная документация. — СПбГУ ИТМО, 2006. [Электронный ресурс]. — Режим доступа: http://is.ifmo.ru/unimod-projects/plates/, свободный. Яз. рус. (дата обращения 09.02.2011).

7. Coates A., Abbeel P., Ng A.Y. Learning for Control from Multiple Demonstrations // Proceedings of the 25th International Conference on Machine Learning. — Helsinki, 2008. — P. 144-151.

8. Гладков Л. А., Курейчик В.В., Курейчик В.М. Генетические алгоритмы. — М.: Физматлит, 2006.

9. Рассел С., Норвиг П. Искусственный интеллект: современный подход. — М.: Вильямс, 2006.

10. Koza J.R. Genetic programming: On the Programming of Computers by Means of Natural Selection. -Cambridge: MIT Press, 1992.

11. Курейчик В.М. Генетические алгоритмы. Состояние. Проблемы. Перспективы // Известия РАН. Теория и системы управления. — 1999. — № 1. — С. 144-160.

12. Курейчик В.М., Родзин С.И. Эволюционные алгоритмы: генетическое программирование // Известия РАН. Теория и системы управления. — 2002. — № 1. — С. 127-137.

13. Поликарпова Н.И., Точилин В.Н., Шалыто А.А. Метод сокращенных таблиц для генерации автоматов с большим числом входных переменных на основе генетического программирования // Известия РАН. Теория и системы управления. — 2010. — № 2. — С. 100-117.

14. Царев Ф.Н. Метод построения управляющих конечных автоматов на основе тестовых примеров с помощью генетического программирования // Информационно-управляющие системы. — 2010. -№ 5. — С. 31-36.

15. Яминов Б. Генетические алгоритмы. — СПбГУ ИТМО, 2005. [Электронный ресурс]. — Режим доступа: http://rain.ifmo.ru/cat/view.php/theory/unsorted/genetic-2005, свободный. Яз. рус. (дата обращения 09.02.2011).

Александров Антон Вячеславович Казаков Сергей Владимирович Сергушичев Алексей Александрович Царев Федор Николаевич Шалыто Анатолий Абрамович

Санкт-Петербургский государственный университет информационных технологий, механики и оптики, студент, alantbox@gmail.com Санкт-Петербургский государственный университет информационных технологий, механики и оптики, студент, kazakov_sergey_v@mail.ru Санкт-Петербургский государственный университет информационных технологий, механики и оптики, студент, alsergbox@gmail.com Санкт-Петербургский государственный университет информационных технологий, механики и оптики, аспирант, fedor.tsarev@gmail.com Санкт-Петербургский государственный университет информационных технологий, механики и оптики, доктор технических наук, профессор, зав. кафедрой, shalyto@mail.ifmo.ru