Формулировка задачи

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

работе [86]идеи алгоритмов семейства BUGбыли расширены для случая сенсоров, срабатывающих при достижением агента некоторого расстояния до препятствия.

В работе [84]рассмотрена дискретная версия этой задачи (рисунок 5.1.1), которая больше подходит для экспериментов с построением автоматных программ. В этой задаче поле представляет собой бесконечную клетчатую сетку. Каждая клетка поля либо свободна, либо содержит препятствие. Каждая связанная (по ребру или вершине) группа препятствий имеет конечный размер. Одна из свободных клеток назначается целью. Агент занимает целую клетку. Местоположение агента определяется декартовыми координатами и направлением (вверх, вниз, вправо, влево). Назовём соседней клетку, которая граничит по ребру с текущей. В алгоритмах BUG-lи BUG-2 память объёмом O(l)используется для того, чтобы сохранить состояние (координаты и направление) агента в некоторый момент времени. Логика агента закодирована в автомате согласно парадигме автоматного программирования.

Рисунок 5.1.1. Диаграмма компонентов

5.1.1. Входные данные

Входные данные, доступные агенту, следующие:

• Xt, Yt- координаты цели;

• X_a, Y_a, D_a- координаты и направление агента;

• X_s, Y_s, D_s- координаты и направление сохранённой позиции;

• X_r, Y_r- координаты смежной клетки спереди (функции от X_a, Y_a, D_a, даны для простоты);

• O- наличие препятствия в смежной клетке спереди от агента.

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

5.1.2. Выходные воздействия

Основываясь на входных данных, агент может сделать одно из следующих действий:

• «move forward»: сделать шаг вперёд на соседнюю клетку;

• «rotate positive»: повернуть на 90 градусов по часовой стрелке;

• «rotate negative»: повернуть на 90 градусов против часовой стрелки;

• «report reached»: завершить работу и вернуть ответ о том, что цель достигнута;

• «report unreachable»: завершить работу и вернуть ответ о том, что цель недостижима;

• «save position»: сохранить текущие координаты и направление в память;

• «do nothing»: ничего не делать.

5.1.3. Возможные условия завершения

Результат работы агента может быть один из следующих:

1. Агент сделал шаг внутрь препятствия. В этом случае считается, что агент завершился аварийно.

2. Агент зацикливается.

3. Агент всё время движется в сторону от препятствия.

4. Агент выполняет действие «report reached» и не находится в целевой клетке.

5. Агент выполняет действие «report reached» и находится в целевой клетке.

6. Агент выполняет действие «report unreachable», и цель достижима.

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

8. Агент выполняет действие «report unreachable», цель недостижима, и агент посетил все вышеуказанные клетки.

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

В работе [84] было сказано, что 800 автоматов были построены при помощи генетического программирования и частичной коэволюции с тестами. Все эти автоматы имеют четыре либо пять состояний. Каждый из них прошёл более 10⁴ тестов, в которых были случайно сгенерированные поля размера 20 ? 20. При этом были и достижимые, и недостижимые цели, поля были и с границей, состоящей из препятствий, и без такой границы.

Все автоматы корректно завершили работу на всех построенных тестах, однако, это не означает, что они корректны. В работе [84] формальное доказательство их корректности отсутствует.

5.2.