1.3.2.Задача «Умный муравей»

Приведем описание задачи «Умный муравей» на основе работ [, ]. Используется двумерный тор размером 32 на 32 клетки (1.3.2). На некоторых клетках поля расположены яблоки – черные клетки на 1.3.2. Яблоки расположены вдоль некоторой ломаной линии, но не на всех ее клетках. Клетки ломаной, на которых яблок нет – серые. Белые клетки – не принадлежат ломаной и не содержат яблок. Всего на поле 89 яблок.

В клетке с пометкой «Start» находится муравей. Он занимает клетку поля и смотрит в одном из четырех направлений (север, запад, юг, восток). В начале игры муравей смотрит на восток. Он умеет определять, находится ли яблоко непосредственно перед ним. За ход муравей совершает одно из четырех действий:

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

• поворачивается вправо;

• поворачивается влево;

• стоит на месте.

Съеденные муравьем яблоки не восполняются. Муравей жив на всем протяжении игры – еда не является необходимым ресурсом для его существования. Никаких других персонажей, кроме муравья, на поле нет. Ломаная строго задана. Муравей может ходить по любым клеткам поля. Игра длится 200 ходов, на каждом из которых муравей совершает одно из четырех описанных выше действий. В конце игры подсчитывается количество яблок, съеденных муравьем. Это значение – результат игры. Цель игры – создать муравья, который за 200 ходов съест как можно больше яблок. Муравьи, съевшие одинаковое количество яблок, заканчивают игру с одинаковым результатом вне зависимости от числа ходов, затраченных каждым из них на процесс еды. Однако эта задача может иметь различные модификации, например, такую, в которой при одинаковом количестве съеденных яблок, лучшим считается муравей, съевший яблоки за меньшее число ходов. Ниже будет показано, что поведение муравья может быть задано конечным автоматом. При этом может быть поставлена задача о построении автомата с минимальным числом состояний для муравья, съедающего все яблоки, или автомата для муравья, съедающего максимальное количество яблок при заданном числе состояний. Конечный автомат, изображенный на 1.3.2, содержит всего пять состояний.

Этот автомат описывает поведение муравья, который не решает задачу – за 200 ходов съедает только 81 яблоко, а за 314 ходов — все 89 яблок. Муравей действует по принципу «Вижу яблоко – иду вперед. Не вижу – поворачиваю направо. Сделал круг, но яблок нет – иду вперед». Приведем автомат (1.3.2), который построен в работе [] с помощью генетических алгоритмов и решает поставленную задачу. 

На этом рисунке используются следующие обозначения: N – непосредственно перед муравьем нет еды, F – непосредственно перед муравьем есть еда; M – идти вперед, L – повернуть налево, R – повернуть направо, NO – стоять на месте. Можно заметить, что действие NO никогда не выполняется. Данный автомат изображен некорректно – из одиннадцатого состояния изображен переход, помеченный входным воздействием 0, с «непонятным» действием S. Однако если это действие заменить на N, то автомат корректно решает задачу.  Автомат из работы [], приведенный на , содержит 11 состояний. По утверждению авторов, он съедает все яблоки за 193 хода. 

Для генерации конечных автоматов, задающего муравья, в работах [, ] были применены генетические алгоритмы. В работе [] приспособленность особи (fitness) определяется как количество яблок, съеденное за 200 ходов. Кодирование автомата, задающего поведение муравья, в особь генетического алгоритма (битовую строку) в этой работе осуществлялось следующим образом: входному воздействию F сопоставлялась единица, а N – ноль. Каждое из четырех действий муравья кодировалось двоичными числами: 00 – NO, 01 – L, 10 – R, 11 – M. Покажем, как выполняется кодирование автомата в целом. На 1.3.2 приведен пример графа переходов автомата, описывающего поведение некоторого муравья.

 Кодирование этого графа переходов приведено в табл. 1.3.2.

Преобразуем эту таблицу в битовую строку. Для этого сначала требуется запомнить число состояний автомата (в данном случае четыре). В начале строки задан двоичный номер начального состояния автомата (в данном примере – 00). Далее записаны пары (Новое состояние, Действие). Содержимое полей (Состояние, Вход) не записываются, так как они повторяются для каждого автомата с фиксированным числом состояний. Для рассматриваемого примера искомая строка имеет вид: 00 0101 0011 0110 1011 1100 1011 0001 1110 Здесь курсивом выделены биты, соответствующие новому состоянию, а обычным шрифтом — биты, соответствующие выполняемому на переходе действию. Жирным шрифтом выделены биты, кодирующие начальное состояние. Отметим, что автором настоящей диссертации в бакалаврской работе [] был предложен генетический алгоритм, с помощью которого был построен автомат, содержащий семь состояний и решающий задачу об «Умном муравье». Диаграмма переходов этого автомата приведена на 1.3.2. В работе [] с помощью перебора показано, что автоматы с меньшим, чем семь числом состояний задачу «Умный муравей» решить не могут.

Отметим, что в книге [] создатель генетического программирования J. R. Koza предлагает другой подход к представлению автомата, нежели кодирование с помощью битовой строки, – поведение муравья задается в виде дерева разбора, которое далее может быть преобразовано в автомат. Апробация этого метода проводилась на другом игровом поле – Santa Fe Trail.  ^