XVII Международная студенческая научная конференция Студенческий научный форум - 2025

Введение

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

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

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

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

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

• поиск врага;

• атака;

• бегство.

Мы можем создать правила для перехода между этими состояниями:

• если охранник видит противника, он атакует;

• если охранник атакует, но больше не видит противника, он возвращается к патрулированию;

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

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

• ожидание (между поиском врага);

• поиск (когда замеченный ранее враг прячется);

• бегство за помощью (когда враг замечен, но слишком силён, чтобы справиться с ним в одиночку).

Варианты выбора, доступные в каждом состоянии, обычно ограничены — например, охранник, скорее всего, не будет искать потерянного из виду врага, если его здоровье слишком низкое. В какой-то момент длинный список «если <x и y но не z> тогда <p>» становится слишком громоздким, и формализованный подход к реализации состояний и переходов между ними может помочь. Для этого мы рассматриваем все состояния и под каждым состоянием перечисляем все переходы к другим состояниям с соответствующими условиями. Также нам нужно указать исходное состояние, чтобы знать, с чего начать, прежде чем применять другие условия.

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

Рис. 1. Диаграмма конечного автомата

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

1. «Постоянное действие» в каждом цикле или кадре:

- состояние «Поиск врага» непрерывно движется по заданному маршруту;

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

2. «Действия при переходе»:

- При смене на состояние «Поиск союзников», агент определяет направление и запоминает его для дальнейшего использования;

- В процессе возвращения в состояние «Атака» после успешного поиска, происходит действие "сообщить другу об опасности".

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

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

Для решения этого:

- Вводится система периодической проверки (например, 5 раз в секунду) видимости;

- При обнаружении цели генерируется событие «Враг видим»;

- Автомат реагирует на эти события с задержкой, но более эффективно по ресурсам.

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

К сожалению, качественный ИИ требует создания большого конечного автомата с которым крайне неудобно работать. Например, нам нужно расширить состояние «Атака», разделив его на несколько состояний «Рукопашная атака» и «Атака издалека», то состояния требующие переход в состояние «Атака» придется перенаправить входящие переходы. Вероятно, вы также заметили, что в нашем примере есть много дублируемых переходов. К состояниям «Ожидание» и «Поиск врага» ведут идентичные переходы, поэтому хорошо было бы избежать повторения данной работы, особенно если мы захотим добавить ещё больше похожих состояний. Для решения этой проблемы мы создадим ещё одну группу «Небоевые состояния», которая объединит в себе состояния «Ожидание» и «Поиск врага», имеющую только один общий набор переходов в боевые состояния. Данную группу можно представить в виде состояния, тогда состояния «Ожидание» и «Поиск врага» можно рассматривать как «подсостояния» состояния «Небоевые», что позволит нам более эффективно описывать всю систему. Пример использования отдельной таблицы переходов для нового небоевого подсостояния:

Основные состояния:

Небоевое состояние:

И в виде диаграммы:

Рис.2. Диаграмма иерархического конечного автомата

Фактически, это та же схема, но теперь она содержит состояние «Небоевое», который заменяет "Поиск врага" и "Ожидание". Это состояние представляет собой конечный автомат с двумя подсостояниями - поиск врага и ожидание. Если каждое состояние может иметь свой собственный конечный автомат подсостояний (и эти подсостояния также могут иметь свои собственные конечные автоматы), то мы получаем иерархический конечный автомат. Путем объединения состояния «Небоевое» мы уменьшаем количество повторяющихся переходов и можем делать то же самое для любых новых состояний, которые имеют общие переходы. Например, если в будущем мы добавим состояние "Атака" с подсостояниями "Рукопашная атака" и "Атака снарядами", они могут быть подсостояниями, между которыми осуществляется переход в зависимости от расстояния до противника и наличия боеприпасов, а общие выходные переходы основаны на уровнях здоровья и других факторах. Таким образом, используя минимум повторяющихся переходов, мы можем описать сложные поведенческие шаблоны.

Заключение

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

Список литературы

1. Обзор техник реализации игрового ИИ[Электронный ресурс] – Режим доступа: https://habr.com/ru/articles/420219/ (дата обращения 11.11.2024)

2. Теория автоматов [Электронный ресурс] – Режим доступа: https://bigenc.ru/c/teoriia-avtomatov-1658d7 (дата обращения 11.11.2024)

3. Что такое конечный автомат и как его создать [Электронный ресурс] – Режим доступа: https://gitverse.ru/blog/articles/data/288-chto-takoe-konechnyj-avtomat-i-kak-ego-sozdat (дата обращения 11.11.2024)