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

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

Авторизуйтесь

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

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

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

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

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

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

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

Описание состояний автомата

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

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

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

Описание состояний интеллекта муравья

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

Cube Dev , Удалённо , От 8000 $

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

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

Описание состояний интеллекта муравья. Обратите внимание на отсутствие перехода между «run away» и «go home»

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

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

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

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

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

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

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

Описание состояний интеллекта муравья, сосредоточенное на коде

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

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

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

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

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

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

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

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

Обновленное описание состояний интеллекта муравья

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

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

Конечный автомат, основанный на стеке

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

Переходы в FSM, основанном на стеке

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

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

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

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

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

Вывод

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

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

Источник

Теория вычислений. Введение в конечные автоматы

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

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

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

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

• По горизонтали вверху находятся возможные входные символы.
• По вертикали слева находятся текущие возможные состояния.

Здесь видно, что из состояния 0 в состояние 1 можно попасть только, если у нас будет входной символ ‘a’, из состояния 1 в состояние 2, если символ ‘b’.

Текущее состояние — множество состояний в котором автомат может находиться в данный момент времени.

Стартовое состояние — состояние откуда КА начинает свою работу.

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

Детерминированные конечные автоматы (deterministic finite automaton)

Простейший КА, в котором может быть одно состояние в текущий момент времени, обладает детерминированностью.

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

Недетерминированные конечные автоматы (nondeterministic finite automaton)

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

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

Недетерминированность — ноль и более переходов для одного символа в каких-либо состояниях.

Множества состояний — в один момент времени НКА может находится в нескольких состояниях.

Заключительное состояние обозначается двойным кругом.

В стартовом состоянии у нас текущим состоянием является <1>, при входном символе ‘b’ у нас появляется возможность, пойти в состояние 1 и в состояние 2, то есть после входного символа ‘b’ текущим состоянием является множество <1, 2>.

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

Здесь видно два свободных перехода из стартового состояния, то есть без чтения входного символа мы сразу находимся в множестве состоянии <2, 4>.

Для преобразования НКА в ДКА используется алгоритм Томпсона.
При преобразовании НКА в ДКА может получиться не совсем минимальный ДКА и для его минимизации можно применить алгоритм Бржозовского.

Конечные автоматы с магазинной памятью (pushdown automaton)

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

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

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

Добавление символов в стек — при любом переходе решает какие символы добавить в стек.

• Детерминированные — к нему применяются те же правила как к ДКА к тому же завершает работу только в заключительном состоянии.
• Недетерминированные — к нему применяются те же правила как к НКА к тому же он может завершать работу в заключительном состоянии или когда стек станет пуст.

Шаблон: входной_символ; удаляемый_символ/добавляемый символ. На дно стека добавляется символ $ для, того, что понять когда он закончился.

Этот КАМП подсчитывает вложенность скобок, за счет добавления и удаления символов из стека.

ДАМП не равен НАМП, поэтому невозможно одно преобразовать в другое, следовательно НАМП обладает преимуществом перед ДАМП.

Машина Тьюринга (Turing machine)

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

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

Шаблон: считаный_символ_с_головки/записаный_символ; сторона_смещения_головки. края ленты обозначаются ‘_’.

Эта МТ выполняет инкремент двоичного числа, головка стоит слева, там где начинается лента.

1. Если находится в состоянии 1 и прочитан нуль, записать еди­ницу, сдвинуть вправо и перейти в состояние 2.
2. Если находится в состоянии 1 и прочитана единица, записать нуль, сдвинуть влево и перейти в состояние 1.
3. Еcли находится в состоянии 1 и прочитан пустой квадратик, записать единицу, сдвинуть вправо и перейти в состояние 2.
4. Если находится в состоянии 2 и прочитан нуль, записать нуль, сдвинуть вправо и остаться в состояние 2.
5. Если находится в состоянии 2 и прочитана единица, записать единицу, сдвинуть вправо и остаться в состояние 2.
6. Если находится в состоянии 2 и прочитать пустой квадратик, записать пустой квадратик, сдвинуть влево и перейти в состоя­ние 3.

ДМТ эквивалентен НМТ, так, что они тоже не различаются.

Универсальная машина Тьюринга (universal Turing machine)

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

1. Память порождаемой машины не может быть больше, чем у самой УМТ.
2. Нужно уметь правильно разделять пространство ленты между порождаемой машиной и УМТ, ведь их данные находятся на одной ленте.

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

Источник