Конечный автомат: теория и реализация
Конечный автомат — это некоторая абстрактная модель, содержащая конечное число состояний чего-либо. Используется для представления и управления потоком выполнения каких-либо команд. Конечный автомат идеально подходит для реализации искусственного интеллекта в играх, получая аккуратное решение без написания громоздкого и сложного кода. В данной статье мы рассмотрим теорию, а также узнаем, как использовать простой и основанный на стеке конечный автомат.
Мы уже публиковали серию статей по написанию искусственного интеллекта при помощи конечного автомата. Если вы еще не читали эту серию, то можете сделать это сейчас:
- Написание ИИ для хоккея. Часть 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».
Следите за новыми постами по любимым темам
Подпишитесь на интересующие вас теги, чтобы следить за новыми постами и быть в курсе событий.
Теория автоматов, конечные автоматы
Структура, конструкция, принцип действия различных автоматов в значительной мере определяются его функциональным назначением. Различают технологические, транспортные, вычислительные, военные и другие автоматы. В различных отраслях промышленности широко внедряются целые автоматические комплексы, предназначенные для выполнения сложных технологических процессов. Разрабатываются и строятся автоматы, реализующие разнообразные логические функции (Логические машины).
Теория автоматов — раздел кибернетики, возникший под влиянием запросов техники цифровых вычислительных и управляющих машин. Дискретные автоматы, изучаемые в теории автоматов, являются абстрактными моделями реальных систем (как технических, так и биологических), которые перерабатывают дискретную (цифровую) информацию дискретными временными тактами.
В основе теории автоматов лежат точные математические понятия, формализующие интуитивные представления о функционировании (поведении) автомата и о его структуре (внутреннем устройстве).
При этом под преобразованием информации всегда понимается операция, преобразующая последовательности входные, составленные из букв входного алфавита, в последовательности выходные, составленные из букв выходного алфавита.
Широко применяется аппарат математической логики, алгебры, теории вероятностей, комбинаторики и теории графов.
Проблематика теории автоматов в некоторой своей части (структурная теория автоматов) выросла из теории релейно-контактных схем, которая начала складываться в конце 1930-х гг. с привлечением методов алгебры логики.
В структурной теории автоматов исследуются различного рода схемы, предназначаемые для описания того, как сложный автомат создается из более простых компонент (элементов), надлежащим образом соединенных в единую систему.
Другое направление, называемое абстрактной теории автоматов, изучает поведение автоматов (т. е. характер осуществляемого ими преобразования информации) при отвлечении от специфики их внутреннего устройства и возникло в 1950-х гг.
В рамках абстрактной теории автоматов содержание понятий «автомат» и «машина» исчерпывается, по существу, стандартным описанием того преобразования информации, которое осуществляется автоматом. Такое преобразование может быть детерминированным, но может иметь и вероятностную природу.
Наиболее изученными являются детерминированные машины (автоматы), к которым относятся конечные автоматы — главный объект изучения в теории автоматов.
Конечный автомат характеризуется конечностью объема памяти (числа внутренних состояний) и задается посредством функции перехода. При некоторой целесообразной идеализации все современные математические машины и даже мозг, с точки зрения их функционирования, можно рассматривать как конечные автоматы.
Термины «последовательностная машина», «автомат Мили», «автомат Мура» употребляются в литературе (причем не одинаково всеми авторами) как синонимы термина «конечный автомат» либо для подчеркивания тех или иных особенностей в функциях перехода конечного автомата.
К автоматам с неограниченной памятью относится машина Тьюринга, способная осуществлять (потенциально) любое эффективное преобразование информации. Понятие «машина Тьюринга» возникло раньше понятия «конечный автомат» и изучается преимущественно в теории алгоритмов.
Абстрактная теория автоматов тесно связана с известными алгебраическими теориями, например с теорией полугрупп. С прикладной точки зрения представляют интерес результаты, которые характеризуют преобразование информации в автомате в терминах его объема памяти.
Так, например, обстоит дело в задачах с экспериментами над автоматами (работы Э. Ф. Мура и др.), в которых по результатам экспериментов получаются те или иные сведения о функциях перехода автомата или об его объеме памяти.
Другая задача заключается в оценке периодов выходных последовательностей, исходя из имеющихся сведений об объеме памяти автомата и о периодах входных последовательностей.
Большое значение имеют разработка приемов минимизации памяти конечных автоматов и исследование их поведения в случайных средах.
В абстрактной теории автоматов проблема синтеза заключается в следующем. В терминах некоторого четко формализованного языка записываются условия, предъявляемые к поведению проектируемого автомата (к событию, представимому в автомате). При этом требуется выработать методы, которые по любому записанному условию:
1) выясняют, существует ли такой конечный автомат, что осуществляемое им преобразование информации удовлетворяет этому условию;
2) если да, то строят функции перехода такого конечного автомата или же оценивают его объем памяти.
Решение проблемы синтеза в такой постановке предполагает предварительное создание удобного языка для записи условий работы автомата с удобными алгоритмами перехода от записи к переходным функциям.
В структурной теория автоматов проблема синтеза заключается в построении из элементов заданного типа схемы, которая реализует конечный автомат, заданный своими функциями перехода. При этом обычно выдвигают некоторый критерий оптимальности (например, минимальность числа элементов) и стремятся получить оптимальную схему.
Как выяснилось впоследствии, значит, часть методов и понятий, выработанных ранее применительно к релейно-контактным схемам, применима и для схем других типов.
В связи с развитием электронной техники наибольшее распространение нашли схемы из функциональных элементов (логические сети). Частным случаем логических сетей являются абстрактные нервные сети, элементы которых называются нейронами.
Разработано много методов синтеза в зависимости от типа схем и от преобразования информации, для реализации которого они предназначены (Синтез релейных устройств).
Конечный автомат — математическая модель управляющей системы с фиксированным (не способным к увеличению в процессе работы) размером памяти.
Понятие конечный автомат является математической абстракцией, характеризующей общие черты множества управляющих систем (например, многотактного релейного устройства). У всех таких систем имеются общие признаки, которые естественно принять в качестве определения конченого автомата.
Всякий конченый автомат имеет вход, подвергающийся внешним воздействиям, и внутренние элементы. Как для входа, так и для внутренних элементов существует фиксированное число дискретных состояний, которые они способны принимать.
Изменение состояний входа и внутренних элементов происходит в дискретные моменты времени, интервалы между которыми называются тактами. Внутреннее состояние (состояние внутренних элементов) в конце такта полностью определено внутренним состоянием и состоянием входа в начале такта.
К указанной характеристике могут быть сведены все другие определения конченого автомата, в частности определения, предполагающие у конченого автомата наличие выхода, зависящего от внутреннего состояния автомата в данный момент.
С точки зрения такой характеристики, для описания конченого автомата не имеет никакого значения природа его входов и внутренних состояний. Можно вместо входов и состояний рассматривать просто их номера в произвольно выбранной нумерации.
Конечный автомат будет задан, если будет указана зависимость номера его внутреннего состояния от номера предыдущего внутреннего состояния и номера предыдущего состояния входа. Такое задание может иметь вид конечной таблицы.
Другой распространенный способ задания конченого автомата — построение т. н. диаграммы переходов. Состояния входа часто называются просто входами, а внутреннего состояния — просто состояниями.
Конечный автомат может быть моделью как технических устройств, так и некоторых биологических систем. Автоматы первого типа являются, например, релейные устройства и различные электронные вычислительные машины, в т. ч. программируемые логические контроллеры.
В случае релейного устройства роль состояний входа играют комбинации состояний воспринимающих элементов релейного устройства (каждая комбинация таких состояний представляет собой «сложное состояние», характеризуемое указанием для всех воспринимающих элементов тех дискретных состояний, которые они имеют в данный момент). Аналогично, комбинации состояний промежуточных элементов релейного устройства играют роль внутренних состояний.
Программируемый логический контроллер (ПЛК) представляет собой пример устройства релейного действия, которое может быть названо автономным конечным автоматом.
Действительно, после того как в ПЛК введена программа и контроллер начал вычисление, она не подвергается внешним воздействиям, причем каждое ее последующее состояние полностью определено ее предыдущим состоянием. Можно считать, что вход в каждом такте имеет одно и то же состояние.
Обратно, всякий конечный автомат, имеющий единственное возможное состояние входа, естественно называть автономным, поскольку в этом случае внешняя среда не несет информации, управляющей его поведением.
Телеграмм канал для тех, кто каждый день хочет узнавать новое и интересное: Школа для электрика
Если Вам понравилась эта статья, поделитесь ссылкой на неё в социальных сетях. Это сильно поможет развитию нашего сайта!
Не пропустите обновления, подпишитесь на наши соцсети:
Что относится к конечному автомату
Материал из книги Салмре И. Программирование мобильных устройств на платформе .Net Compact Framework. М.: Вильямс. 2006. Кооперайт на английском языке Pearson Education, Inc., 2005.
Аналогичные идеи в части применения автоматов в программировании развиваются мною с 1991 года. (http://is.ifmo.ru/works/switch_prr/) А. Ш. В книге (возможно, только в переводе), почему-то, отсутствует список литературы.
Эта книга становится своего рода библией в быстро развивающемся мире мобильных вычислений. Ее автор работал в компании Microsoft в Редмонде на протяжении 12 лет. Сейчас он работает в Европейском Инновационном Центре компании Microsoft в городе Аахене, Германия, где занимается исследованиями в области разработки программных моделей для современных мобильных устройств.
В этой книге глава 5 (из 17) называется «Наш друг конечный автомат». Учитывая, что автор не является специалистом по конечным автоматам, наличие указанной главы в начале книги свидетельствует о значительной роли автоматов в проектировании мобильных устройств.
Введение
Несмотря на стремительную поступь технологий, надежные методы прикладного программирования и искусство программирования развиваются крайне медленно.
Путь, позволяющий преодолеть трудности, свойственные разработке программного обеспечения, пролегает через использование подходящих методологий.
В эпоху пакетной обработки безраздельно царствовали алгоритмы. Этот период можно назвать эрой «блок-схем».
При построении серверных приложений, отвечающих на запросы, большую роль играет «отсутствие состояния» нет нужды сохранять состояния между двумя последовательными запросами.
При построении удачного интерактивного приложения управляемого событиями, многое зависит от того, продумана ли модель управления состояниями.
Конечный автомат весьма удобная концепция, которую целесообразно использовать для структурирования приложений.
Продуманное применение конечных автоматов облегчает организацию и сопровождение, как логики пользовательского интерфейса, так и логики приложения. Благодаря этому код будет более гибким и надежным, причем это относится к разработке не только мобильных, но и любых других приложений.
Поскольку мобильные приложения должны использовать пространство экрана и системные ресурсы эффективно, конечные автоматы оказываются особенно полезными при разработке ПО для таких приложений.
Ниже излагается, каким образом применение автоматов может способствовать написанию эффективного и надежного года.
«Состояние» вашего приложения может быть определено как совокупность значений всех его переменных. Эти значения представляют уникальное состояние, которое изменяется каким-либо внешним событием. В любой момент времени приложение находится в каком-то определенном состоянии.
Конечный автомат, как отмечалось выше, является средством формальной структуризации приложения. Вместо того чтобы использовать все переменные приложения в качестве расширенного определения его состояния, конечный автомат создает единственную переменную, в которой хранится информация о состоянии приложения. Такой переменной обычно является элемент перечисления некоторого множества действительных состояний, определяемого глобально или на уровне класса.
Мощь подхода, использующего конечные автоматы, обусловлена тем, что он позволяет в явном виде определить действительные состояния для некоторого аспекта вашего приложения и задать соответствующие варианты поведения при переходах приложения из одного состояния в другое.
В приложении может использоваться несколько конечных автоматов, для каждого из которых определяется собственный набор вариантов поведения приложения, подлежащих структуризации.
Приложение, для которого конечные автоматы не определены, в действительности является приложением с множеством конечных автоматов. При этом каждая переменная, определенная на уровне приложения, по сути дела сама является конечным автоматом, и любой код может получить доступ к состоянию и изменить его.
Конечные автоматы используются для формирования набора взаимосвязанных переменных или вариантов поведения и их логической организации, что облегчает обработку состояний.
Конечные автоматы суть организованное поведение. Конечный автомат это просто формальное описание того, как работает приложение. Он позволяет ясно представить различные состояния, в которых может находиться приложение.
Для определения текущего варианта изменения состояния удобно использовать блок операторов switch/case. Каждый оператор case соответствует одному из вариантов изменения состояния и должен содержать вызов функции, выполняющей всю необходимую для этого работу.
Подобного рода централизация и инкапсуляция управления состояниями является одним из наиболее мощных аспектов использования конечных автоматов. Все важные изменения состояний приложения определяются и обрабатываются централизованно в одном месте программы.
1. Явно и неявно определенные конечные автоматы
Для написания кода существуют два подхода. (В моих работах высказывается аналогичное мнение (http://is.ifmo.ru/works/mirk/) А.Ш.)
Подход 1. Зависящее от специфики конкретной ситуации, децентрализованное, неявное управление состояниями (неудачный подход).
Различные аспекты состояния приложения изменяются в разных местах приложения. Переменные, используемые для хранения ключевой информации о состоянии, изменяются непосредственно в тех строках кода, где это оказывается необходимым, а загрузка данных и освобождение памяти от них распределяются по всему приложению в зависимости от конкретной ситуации. Развитие событий напоминает «перетягивание каната» между различными частями приложения, поскольку каждая из функций делает все необходимое для выполнения возложенных на нее задач, не обращая никакого внимания на остальную часть приложения.
Подход 2. Плановое, централизованное, явное управление состояниями (удачный подход).
Явное управление состояниями прямая противоположность предыдущему подходу. В этом случае любые переходы между состояниями реализуются в рамках одной главной функции. Например, в коде обработчика событий, ответственном за изменение некоторого аспекта состояния приложения, это обеспечивается вызовом единственной функции, которая вызывается в соответствии с логикой приложения. При этом используется инкапсуляция. Вместо того чтобы непосредственно изменять состояние интерфейса, коды обработки событий каждого из элементов пользовательского интерфейса вызывают главную функцию управления состояниями, которая и выполняет необходимую работу.
Этот процесс легко масштабируется при расширении или изменении приложения. Необходимые изменения любых аспектов функционирования приложения обеспечиваются за счет использования единственной главной функции. По мере возникновения потребности в дополнительных элементах управления или состояниях приложения, они могут быть без труда включаться в программную модель централизованным образом.
Использование конечных автоматов облегчает эффективную организацию кода, что, в свою очередь, способствует созданию качественных приложений.
Отдаете ли вы себе в этом отчет или нет, но значительная доля кода нашего приложения всегда будет связана с управлением его состояниями. Как бы то ни было, вам придется иметь дело с задачами подобного рода, и только вам решать, выбрать ли явный подход к управлению состояниями приложения или же остановиться на модели неявного управления.
Явное управление состояниями имеет ряд существенных преимуществ, не самым последним из которых является то, что такой подход заставляет вас более тщательно продумывать функционирование вашего приложения.
При проектировании пользовательских интерфейсов мобильных приложений применение конечных автоматов, позволяющих централизованным образом экспериментировать с логикой размещения и масштабирования элементов управления, оказывается особенно полезным.
2. Сколько конечных автоматов должно быть в приложении?
Конечные автоматы должны быть центральной составляющей проекта мобильного приложения. Часто бывает удобно применять несколько конечных автоматов в одном приложении.
Конечный автомат, который управляет кэшированными данными, извлеченными из базы данных, может использоваться наряду с конечным автоматом, управляющим такими графическими объектами, как перья и кисти, кэшируемыми для их использования в обычных задачах рисования. Третий конечный автомат может управлять выполнением задач фоновыми потоками.
И хотя перечисленные автоматы можно было бы объединить в один «главный автомат», такой автомат представлял бы просто формальное объединение всех возможных случаев изменения состояния приложения и не дал бы ничего нового, поскольку состояния, которыми управляют отдельные конечные автоматы, слабо или вообще не коррелируют друг с другом.
Возможна крайность другого рода, когда вместо создания одного конечного автомата, выполняющего всю работу, предпочитают иметь десятки небольших конечных автоматов, каждый из которых управляет отдельной переменной приложения.
Роль ключа в нахождении правильного решения играет корреляция. Если можно выделить набор переменных, объектов или ресурсов, которые тем или иным образом коррелируют между собой, то управление этим набором удобно и целесообразно осуществлять при помощи одного конечного автомата.
3. Области применения конечных автоматов при программировании мобильных устройств
3.1. Конечные автоматы и пользовательские интерфейсы
Пользовательские интерфейсы одна из наиболее очевидных областей, где конечные автоматы могут находить широкое применение. Поведение элементов управления, совместно использующих одну и ту же форму, часто является коррелированным. Некоторые элементы управления отображаются и скрываются в одно и то же время, некоторые элементы перемещаются при отображении других элементов и т.д. (Посмотрите, как предлагается создавать скины для видеоплейера (http://is.ifmo.ru/projects/crystal/) А.Ш.)
С каждой из форм, которую вы конструируете, должен связываться конечный автомат, управляющий визуальным поведением формы. Если в самой форме содержится несколько страниц, например, диалоговые окна с вкладками, то, вероятно, имеет смысл предусмотреть для каждой из подстраниц собственный конечный автомат.
Если логика отображения, сокрытия и перемещения элементов управления будет растворена в логике приложения, то результирующая схема управления окажется весьма запутанной.
Существует настоятельная необходимость в главном арбитре, который бы управлял бы распределением пространства экрана, и конечный автомат великолепно подходит для этих целей.
Расположение всего кода, ответственного за параметры видимости, размеров и размещения, в одном месте позволяет значительно сократить сроки завершения этой части итеративного проектирования, и сделать ее более понятной по сравнению с вариантом, в котором упомянутый код располагается вразброс в различных местах кода, реализующего логику приложения.
Если код пользовательского интерфейса тесно переплетен с логикой приложения, то выполнить это будет очень трудно внесение изменений в пользовательский интерфейс потребует кропотливого изучения всей логики приложения. Поэтому отыскать ошибки в коде интерфейса, насыщенного различного рода взаимосвязями, и устранить их, не нарушая работоспособности приложения, очень трудно, поскольку они разбросаны по всему приложению, а не сконцентрированы в одном месте и надежно инкапсулированы.
Поэтому логику приложения необходимо отделять от пользовательского интерфейса.
Конечный автомат подходит для управления всеми нуждами пользовательского интерфейса мобильного приложения. При этом необходимо следить за эффективным использованием экранного пространства в процессе того, как пользователь переводит приложение из одного состояния в другое. При наличии конечного автомата, который показывает, скрывает и перемещает элементы управления по экрану в соответствии с необходимостью, эту задачу можно решить весьма эффективно.
Абстрагирование всех режимов работы пользовательского интерфейса в одном автомате обеспечивает максимальную гибкость процесса внесения изменений в модель экранного дисплея, избавляя от необходимости просматривать и изменять множество кода, распределенного между различными функциями и обработчиками событий пользовательского интерфейса.
3.2. Конечные автоматы и управление памятью
Как и в случае пользовательских интерфейсов, существует два способа управления данными явный и неявный.
Для мобильных устройств крайне желательно использовать подход, предполагающий явное управление использованием памяти.
Если приходиться иметь дело с несколькими различными типами данных или системных ресурсов, то конечный автомат целесообразно построить для каждого из них.
3.3. Конечные автоматы и фоновые задачи
В мобильных приложениях часто встречаются участки кода, которые либо долго выполняются, либо требуют сетевого доступа. Операции подобного рода рекомендуется выполнять в асинхронном по отношению к потоку выполнения пользовательского интерфейса режиме. При реализации любой асинхронной операции конечный автомат, с помощью которого указанный поток может связываться с фоновым потоком и получать информацию о ходе его выполнения, играет важную роль, так как модель управления потоком на основе конечного автомата позволяет выполнить все требования.
Проектирование фоновых задач в виде классов, использующих конечные автоматы, упрощают получение соответствующих данных от потока пользовательского интерфейса.
Конечные автоматы значительно расширяют возможности управления выполнением фоновых задач. Их использование делает возможным предоставление фоновыми потоками информации о состоянии выполнения, а также обращение других потоков с запросами к фоновому потоку на выполнение определенных действий, например, с запросом на прекращение выполнения фоновой работы.
Приложения лучше всего проектировать на основе однопоточной модели, привлекая фоновую обработку лишь тогда, когда она необходима.
3.4. Конечные автоматы и игры
Конечные автоматы весьма удобно применять в играх (посмотрите игру «Космонавт» (http://is.ifmo.ru/projects/cosmo/) А.Ш.), в которых персонажи, перемещающиеся в области игры, могут действовать в различных режимах (например, персонаж бежит вперед или назад, взбирается по лестнице, падает и т.д.).
Использование автоматов с четко определенными правилами для каждого персонажа, задающими варианты его поведения в различных состояниях и допустимые переходы из одного состояния в другое, позволяет создавать сложные варианты поведения как персонажей, управляемых компьютером, так и персонажей, управляемых пользователем.
Выводы
Идея применения конечных автоматов является чрезвычайно полезной концепцией, плодотворность которой прошла проверку временем (но знает ли об этом народ А.Ш.). Использование конечных автоматов позволяет разработчикам создавать хорошо организованные приложения с гибкими возможностями. Их применение позволяет создавать ясный, понятный и надежно функционирующий код.
Старайтесь избегать неявного управления состояниями приложения и не жалейте времени на разработку явно сформированной модели состояний.
Использование конечных автоматов стало уже обычной практикой (хотелось бы так думать, но я очень сомневаюсь А.Ш.) при проектировании приложений для настольных компьютеров, серверов и мобильных устройств.
Преимущества, обеспечиваемые применением конечных автоматов, заметнее всего проявляются в случае приложений для мобильных устройств, требующих экономного расходывания экранного пространства, памяти, вычислительной мощности и других ресурсов.
Проектирование конечных автоматов по методу Ohe Текст научной статьи по специальности «Компьютерные и информационные науки»
Аннотация научной статьи по компьютерным и информационным наукам, автор научной работы — Строгонов Андрей
В ряде случаев автоматная модель устройства позволяет получить быструю и эффективную реализацию последовательностного устройства. Обычно рассматривают два типа автоматов — автомат Мили (Mealy) и Мура (Moore).
i Надоели баннеры? Вы всегда можете отключить рекламу.
Похожие темы научных работ по компьютерным и информационным наукам , автор научной работы — Строгонов Андрей
Проектирование цифровых автоматов с использованием системы Matlab / Simulink
Синтез моделей управляющих автоматов для socфильтров с конвейерной архитектурой
Использование различных типов памяти при проектировании учебного микропроцессорного ядра для реализации в базисе ПЛИС
Методы и программные продукты для повышения производительности проектов на базе ПЛИС Xilinx
Краткий курс HDL. Часть 5. Написание кода, независимого от аппаратной платформы
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.
Текст научной работы на тему «Проектирование конечных автоматов по методу Ohe»
Проектирование конечных автоматов
В ряде случаев автоматная модель устройства позволяет получить быструю и эффективную реализацию последовательностного устройства. Обычно рассматривают два типа автоматов — автомат Мили (Mealy) и Мура (Moore) [1, 2].
Андрей СТРОГОНОВ, д. т. н.
Конечные автоматы широко используются в различных цифровых прикладных системах и устройствах, особенно в контроллерах. Выход автомата Мура является функцией только текущего состояния, выход автомата Мили — функция как текущего состояния, так и начального внешнего воздействия.
Обычно конечный автомат состоит из трех основных частей:
• Регистр текущего состояния. Этот регистр представляет собой набор тактируемых D-триггеров, синхронизируемых одним синхросигналом. Этот набор используется для хранения кода текущего состояния автомата. Для автомата с n состояниями требуется Log2(n) триггеров.
• Логика переходов. Конечный автомат может находиться в каждый конкретный момент времени только в одном состоянии. Каждый тактовый импульс вызывает переход автомата из одного состояния в другое. Правила перехода определяются комбинационной схемой, называемой логикой переходов. Следующее состояние определяется как функция текущего состояния и входного воздействия.
• Логика формирования выхода. Выход цифрового автомата обычно определяется как функция текущего состояния и исходной установки (в случае автомата Мили). Формирование выходного сигнала автомата определяется с помощью логики формирования выхода.
В качестве примера рассмотрим проектирование простейшего синхронного автомата, который формирует два неперекрываю-щихся импульса Outl и Out2 в ответ на появление сигнала Run на входе автомата (рис. 1а). Полностью синхронный конечный автомат использует регистры для фиксации всех выходных сигналов управления и состояний, а также для асинхронных входных сигналов. Следует заметить, что синхронные конечные автоматы по быстродействию уступают асинхронным.
Метка, расположенная в каждом круге выше линии, — это имя состояния, а метки ниже линий — это выходные сигналы, которые выдаются, когда данное состояние активно. «Дуги», которые возвращаются в то же самое состояние, — это переходы, которые работают по умолчанию. Эти дуги будут иметь истинные значения только в случае, когда не будет истинных значений других условий переходов. Каждое условие перехода из состояния в состояние имеет соответствующее логическое условие, которое должно выполняться, чтобы конечный автомат мог перейти в следующее состояние.
Автомат принимает четыре состояния: Idle, Delay, Next, Done (рис. 1а). Воспользуемся методом двоичного кодирования состояний, который обеспечивает высокую степень кодирования последовательности состояний. Для кодирования состояний потребуется два триггера. Запишем булевы логические уравнения:
50 := (Idle, Run)+Delay,
Символ = обозначает комбинационную схему, ответственную за переход по состояниям, а символ := обозначает триггерный выход, необходимый для хранения кода текущего состояния автомата и выходных сигналов. Схема, построенная по булевым уравнениям в САПР ПЛИС Quartus II компании Altera, показана на рис. 2. На рис. 3 показаны временные диаграммы работы автомата. Уравнение для выходного сигнала Outl представляет собой функцию как состояния, так и входного сигнала Run. Конечный автомат с таким видом стробирования выходов называется автоматом Мили. Уравнение для выходного сигнала Out2 записывается как функция только состояния автомата, что соответствует структуре автомата Мура. Для автоматов Мили удобно представлять диаграммы в другом виде (рис. 1б).
Метод one hot encoding (ОНЕ — кодирование с одним активным, или горячим, состоянием; иначе — унитарное кодирование) получил такое название потому, что в каждый конкретный момент времени активным (hot) может быть только один триггер состояния. Применение метода ОНЕ для ПЛИС по архитектуре ППВМ (программируемые пользователем вентильные матрицы, зарубежная аббревиатура — FPGA) было предложено компанией High-Gate Design [3].
Построение конечного автомата с использованием метода ОНЕ осуществляется по следующей методике — вначале для отображения каждого состояния автомата выделяется
индивидуальный триггер, а затем организуется схема, позволяющая в каждый конкретный момент времени только одному состоянию быть активным [3, 4].
Рассмотрим конечный автомат Мура, предусматривающий семь различных состояний [3, 4]. Построим граф-автомат проектируемого устройства (рис. 4). Автомат переходит из состояния в состояние по переднему фронту синхроимпульса, который отмечен «крестиком». Иерархическая блок-схема автомата, состоящая из 7 блоков S1-S7 и логики формирования выхода, в САПР ПЛИС Quartus II компании Altera показана на рис. 5.
В примере имеется семь состояний (Stage1-7), каждый блок ответственен за формирование своего состояния, например блок S1 отвечает за формирование состояния 1. Все логические входы помечаются как переменные от А до Е. Выходы конечного автомата носят названия Multi, Contig и Single. В данном примере состояние 1, в котором должен находиться конечный автомат при включении питания, имеет структуру триггера с двумя инверторами (схема S1, рис. 6).
Для того чтобы конечный автомат при включении питания всегда принимал известное начальное состояние, выход триггера состояния 1 инвертируется, а чтобы обеспе-
чить логическую непротиворечивость, входной информационный сигнал этого триггера также инвертируется. Таким образом, состояние 1 в начальный момент времени принимает значение логической единицы. Для всех других состояний 2-7 используется Г>-триггер с асинхронным сбросом, тактируемый фронтом синхросигнала.
Автомат спроектирован так, что активный низкий уровень сигнала И8ТО (глобальный
сброс состояний всего автомата, кроме состояния 1) в начальный момент сбрасывает состояния 2-7 (82-87) в ноль, а состояние 1 будет находиться в единице. Далее сигнал И8ТС должен всегда оставаться логической 1. В случае, если конечный автомат все же окажется в недопустимом состоянии, например, в состоянии 3, то с приходом следующего переднего фронта синхроимпульса будет установлено состояние 4. Состояние 4 сбросит состояние 3. Состояние 4 может сбросить и состояние 2. Состояние 5 сбрасывает состояние 4, состояние 6 сбрасывает состояние 5, состояние 7 сбрасывает состояние 6, а состояние 1 сбросит состояние 7. Таким образом, для правильной работы конечного автомата достаточно его один раз сбросить с помощью сигнала И8ТО, а далее автомат, шагая по состояниям, способен сам их сбрасывать.
После того как установлены начальные состояния, необходимо построить логику перехода в следующее состояние. Для определения индивидуального состояния воспользуемся алгоритмом, предложенным в работе [3]. Вначале подсчитывается число условий переходов, ведущих к данному состоянию, и добавляется еще один переход, если условие по умолчанию должно оставлять конечный автомат в том же самом состоянии. Далее строится логический вентиль ИЛИ с числом входов, равным числу условий переходов, определенных ранее.
Далее, для каждого входа вентиля ИЛИ строится логический вентиль И, входами которого служат предыдущие состояния и его логика условия. Если по умолчанию конечный автомат должен оставаться в том же самом состоянии, строится логический вентиль И, входами которого служат данное состояние и обратная величина всех возможных условий переходов, исходящих из данного состояния.
Чтобы определить число условий переходов для состояния 1, рассмотрим граф-автомат. Из рис. 6 видно, что состояние 1 имеет один переход от состояния 7, когда переменная Е истинна. Другой переход — это условие
Рис. 5. Иерархическая блок-схема автомата с кодированием по методу OHE в САПР ПЛИС Quaгtus II
Рис. 6. Cхема для ^стояния 1
по умолчанию, ведущее в состояние 1. Таким образом, состояние 1 имеет два условия переходов. После этого можно построить двухвходовой логический вентиль 2ИЛИ с одним входом для условия перехода от состояния 7, а другим — для перехода по умолчанию, чтобы оставаться в состоянии 1 (рис. 6).
Следующий шаг — это построение логики переходов для данного вентиля 2ИЛИ. Каждый вход вентиля 2ИЛИ есть логическая функция И предыдущего состояния и логики переходов состояния 1. Например, состояние 7 поступает на вход состояния 1, когда
Е имеет истинное значение. Это обеспечивается при помощи логического вентиля 2И (рис. 6). Второй вход вентиля ИЛИ — переход по умолчанию, когда конечный автомат должен оставаться в состоянии 1. Если текущее состояние есть состояние 1 и нет условий переходов, выходящих из состояния 1, которые истинны, то конечный автомат должен оставаться в состоянии 1. Состояние 1 на диаграмме состояний имеет два исходящих условия переходов (рис. 6).
Первый переход является действительным, когда истинно условие (АВС), и ведет в со-
стояние 2. Второй переход, ведущий в состояние 4, является действительным при истинном значении условия (АВС). Логика по умолчанию — это функция И для состояния 1 обратной величины всех условий переходов, исходящих из состояния 1. Эта логическая функция реализуется с использованием вентиля 2И с инвертором на одном из входов и логических элементов, формирующих сигнал для инвертирующего входа вентиля 2И (рис. 6). Комбинационная логика обеспечивает декодирование с учетом входных сигналов и сигнала обратной связи.
Состояние 4 не является начальным состоянием, поэтому для его представления используется D-триггер без инверторов, с входом асинхронного сброса RSTG. Триггер может быть сброшен и выходом состояния 5 (сигнал RSTState5). Имеется три входящих условия перехода и условие по умолчанию, чтобы конечный автомат мог оставаться в состоянии 4. Поэтому на входе триггера используется вентиль 4ИЛИ (схема S4, рис. 7).
Первое условие перехода исходит из состояния 3. В соответствии с изложенными выше правилами необходимо построить функцию И для состояния 3 и логику условия, которая имеет вид A+D (рис. 7).
Следующее условие перехода исходит из состояния 2, оно требует логической функции И для состояния 2 и переменной D. Последнее условие перехода для состояния 4 — от состояния 1. Выход состояния 1 должен пройти через схему 2И с логикой его условия перехода — логическим произведением ABC (рис. 7).
Далее нужно построить логику, обеспечивающую сохранение состояния 4, когда ни одно из условий переходов, исходящих из состояния 4, не имеет истинного значения. Переход, исходящий из состояния 4, является действительным, когда логическое произведение ABC истинно. Следовательно, необходимо пропустить состояние 4 через вентиль И с обратной величиной произведения ABC . Это необходимо для поддерживания триггера в высоком уровне, пока не произойдет действительный переход в следующее состояние. В логике перехода по умолчанию используется вентиль 2И и выход вентиля 3И с инвертором на входе С.
Состояние 2 имеет только одно условие перехода, которое приходит от состояния 1, когда произведение ABC истинно. Конечный автомат будет немедленно переходить по одному из двух переходов из состояния 2 в зависимости от значения сигнала D. Состояние 3, подобно состояниям 1 и 4, имеет переход по умолчанию, и для управления входом D-триггера используется комбинация сигналов A и D, состояния 2 и состояния 3. Состояние 5 управляет состоянием 6 без всяких условий. Конечный автомат ждет в состоянии 6, пока переменная Е не переключится в низкий уровень, прежде чем перейти в состояние 7. В состоянии 7 конечный автомат ждет переключения переменной Е в истинное значение, после чего переходит в состояние 1.
После описания всей логики переходов по состояниям описывается выходная логика. В примере используются три выходных сигнала — Multi, Contig и Single, — каждый из которых относится к одной из трех основных категорий выходных сигналов:
1. Выходные сигналы, формируемые в одном состоянии. Примером может служить выходной сигнал Single, формируемый только в состоянии 6, то есть выходным сигналом является выход триггера.
2. Выходные сигналы, формируемые во многих смежных состояниях. Например, выходной сигнал Contig, который формируется в состояниях З-7, хотя есть ветвь для состояния 2,
3. Выходные сигналы, формируемые по многим несмежным состояниям. Здесь обычно оптимальное решение — это простое декодирование активных состояний. Например, сигнал Multi, который формируется для состояний 2 и 4.
Для формирования логики выходного сигнала Multi используется декодирование состояний 2 и 4 при помощи вентиля 2ИЛИ. Каждый раз, когда конечный автомат окажется в одном из этих состояний, будет сформирован активный сигнал Multi. Для декодирования выходных сигналов для смежных состояний используется синхронный RS-триггер, RS-триггер устанавливается при входе в смежное состояние и сбрасывается при выходе (рис. 5). Временная диаграмма проектируемого автомата представлена на рис. 8,
Для размещения автомата выберем ПЛИС по архитектуре ППВМ APEX20K
(EP20K30ETC144-1). Архитектура ПЛИС семейства APEX20K сочетает в себе достоинства ППВМ ПЛИС с их таблицами перекодировок (LUT). После компиляции проекта оказалось задействовано 20 логических элементов, 8 триггеров. Моделирование проводилось без учета реальных задержек распространения сигналов в ПЛИС. С учетом реальных задержек период тактового сигнала CLK для стабильной работы автомата должен быть не менее 15 нс. Уменьшить число триггеров на один позволяет декодирование состояний 3-7 при помощи 5-входового вентиля ИЛИ. Каждый раз, когда конечный автомат окажется в одном из этих состояний, будет сформирован сигнал Conting. В этом случае и сокращается число логических элементов. Максимальная тактовая частота в обоих схемных решениях составляет fMAX = 290,02 МГц.
Опишем функционирование данного автомата на языке описания аппаратных средств VHDL. Описание проектируемого конечного автомата с использованием двухпроцессного шаблона и перечисляемого типа данных (Enumerated type) на языке VHDL приведено
Рис. 8. Результаты моделирования работы конечного автомата с принудительным сбросом состояний. Показаны переходы по состояниям 1—7
далее. Перечисляемый тип — это такой тип данных, при котором количество всех возможных состояний конечно. Такой тип наиболее часто используется для обозначений состояний конечных автоматов. Любой перечисляемый тип имеет внутреннюю нумерацию: первый элемент всегда имеет номер 0, второй — 1 и т. д.
Для этой модели триггеры синтезируются только для сигнала state, что позволяет избежать лишних триггеров в схеме. Для обеспечения стабильной и безотказной работы используется сброс автомата в начальное состояние (активный высокий уровень сигнала TRST). Таким образом, всегда обеспечивается инициализация автомата в начальное состояние.
В данном примере стиль кодирования (например, метод двоичного кодирования или кодирование по методу OHE) не определен в коде языка VHDL. Xilinx рекомендует использовать кодирование цифровых автоматов с использованием перечисляемого типа, так как в этом случае САПР предоставляется возможность использовать модуль логического синтеза и в зависимости от архитектуры ПЛИС самостоятельно выбирать метод кодирования [5]. В САПР Quartus II предлагается использовать три метода кодирования: Auto, OHE, Minimal Bits. В САПР Xilinx используется семь методов кодирования: Auto, OHE, Gray, Compact, Johnson, Sequential, User [5].
ENTITY avtOHE IS PORT(
A,B,C,D,E,TRST,TCK : IN STD_LOGIC;
Multi, Contig,Single : OUT STD_LOGIC;
STATE1_7 : OUT STD_LOGIC_VECTOR
ARCHITECTURE a OF avtOHE IS
TYPE state_values IS (Stage1, Stage2, Stage3, Stage4, Stage5, Stage6, Stage7);
signal state,next_state: state_values;
— регистровый блок statereg: process(TCK,TRST) begin
if (TRST = ‘1’) then state
elsif (TCK’event and TCK=’1′) then state
end if; end process statereg;
— комбинаторный блок (логика переходов)
case state is when Stage1=>
IF (A=’1′ and B=’0′ and C=’1′) THEN next_state
ELSIF (A=’1′ and B=’1′ and C=’0′) THEN next_state
IF (D=’0′) THEN next_state
ELSIF (D=’1′) THEN next_state
END IF; when Stage3=>
IF (A=’1′ or D=’1′) THEN next_state
IF (A=’1′ and B=’1′ and C=’0′) THEN next_state
IF (E=’0′) THEN next_state
— логика формирования выхода