Поведение конечных автоматов в лабиринтах

Работа посвящена исследованию задач о поведении конечных автоматов в лабиринтах. Для любого $n$ строится лабиринт, который можно обойти с помощью $2n$ камней но нельзя обойти с помощью $n$ камней.
Спектр задач обхода обширен и затрагивает ключевые аспекты теоретической Computer Science. Конечно, решение таких задач не означает автоматическое решение сложных проблем теории сложности, тем не менее рассмотрение данных вопросов может положительно сказаться на понимании сути теоретической Computer Science. Есть надежда, что поведение автоматов в лабиринтах является хорошей моделью для нетривиальных теоретико-информационных задач, и отработка методов и подходов к исследованию поведения роботов даст более серьезные результаты с будущем.
Задачи связанные c автоматным анализом геометрических сред имеют довольно богатую историю изучения. Первой работой, давшей начало подобного рода задачам, стоит признать работу Шеннона [24]. В ней рассматривается модель мыши в виде автомата, которая должна найти определенную цель в лабиринте. Другая ранняя работа, так или иначе затрагивающая нашу проблематику, это работа Фишера [9] о вычислительных системах с внешней памятью в виде дискретной плоскости.
Серьёзным толчком к исследование поведения автоматов в лабиринтах послужила работы Деппа [7, 8], в которых предложена следующая модель: имеется некоторая конфигурация клеток из $\mathbb{Z}^2$ (шахматный лабиринт), в которой конечные автоматы, обозревая некоторую окрестность клетки, в которой они находятся, могут перемещаться в соседнюю клетку в одном из четырёх направлений.
Основной вопрос, который ставится в подобной модели, существует ли автомат обходящий все подобные лабиринты.
В [20] Мюллер построил для заданного автомата плоскую ловушку (лабиринт который обходится не полностью) в виде $3$-графа. Будах [5] построил шахматную ловушку для любого заданного конечного автомата. Отметим, что решение Будаха было довольно сложным (первые варианты содержали 175 страниц). Более наглядные решения данного вопроса представлены здесь [29, 31, 33, 34]. Антельман [2] оценил сложность подобной ловушки по числу клеток, а в [1] Антельман, Будах и Роллик сделали конечную ловушку для любой конечной системы автоматов.
В постановке с шахматным лабиринтом и одним автоматом есть ещё ряд результатов, связанных с проблемами обходимости лабиринтов с различными числом дыр, с расслоениями лабиринтов по количеству состояний автомата и другими вопросами. Обзор подобных проблем можно найти например здесь [35].
Невозможность обхода всех плоских шахматных лабиринтов одним автоматом выдвинула вопрос об изучении возможных усилений модели автомата, которая решит задачу обхода. Основным способом усиления может являться рассмотрение коллектива автоматов, вместо одного автомата, взаимодействующих между собой. Частным и широко используемым случаем является рассмотрение системы из одного полноценного автомата и некоторого количества автоматов камней, которые не имеют внутреннего состояние и могут передвигаться только совместно с главным автоматом. Взаимодействие между автоматами является ключевой особенностью данного усиления, оно позволяется иметь коллективу (или одному автомату с камнями) внешнюю память, тем самым существенно разнообразит его поведение. Если от взаимодействия автоматов избавиться, то полученная независимая система будет немногим лучше одного автомата.
Далее обсудим известные результаты связанные с коллективом автоматов.