Оптимальный решатель близоруких лабиринтов

Я дурачился с демоверсией Google Blocky's Maze и вспомнил старое правило, что если вы хотите решить лабиринт, просто держите левую руку на стене. Это работает для любого односвязного лабиринта и может быть реализовано конечным преобразователем.

Пусть наш робот будет представлен преобразователем со следующими действиями и наблюдаемыми:

Действия: идти вперед ( ), повернуть налево ( ), повернуть направо ( ) $\uparrow$ $\leftarrow$ $\rightarrow$
Наблюдаемые: стена впереди ( $\bot$ ), нет стены впереди ( $\top$ )

Тогда мы можем построить левый решатель лабиринтов как (простите мой ленивый рисунок):

преобразователь для решения лабиринта

Если наблюдение за наблюдаемой заставит нас следовать за соответствующим краем из состояния при выполнении действия, связанного с этим краем. Этот автомат решит все односвязные лабиринты, хотя это может занять некоторое время после тупиков. Мы называем другой автомат лучше, чем если: $B$ $A$

$B$ делает строго больше шагов только на конечном количестве лабиринтов, и
$B$ делает строго меньше шагов (в среднем; для вероятностных вариантов) на бесконечном количестве лабиринтов.

Мои два вопроса:

Есть ли конечный автомат лучше, чем нарисованный выше? Что если мы допустим использование вероятностных преобразователей?
Существует ли конечный автомат для решения лабиринтов, которые не обязательно просто связаны?

automata finite-automata artificial-intelligence Артем Казнатчеев
источник

@jmad и я провели в чате довольно плодотворную дискуссию по этому вопросу. Если вы думаете об этом вопросе (особенно об определениях лучше чем ), тогда я рекомендую проверить стенограмму.

Артем Казнатчеев

Я не понимаю, как этот вопрос относится к ИИ (в частности, к нашим агентам, чтобы они не меняли свое поведение при данных экземпляра), но я не эксперт в этой области.

Рафаэль

@ Рафаэль лабиринт и поиск путей (от обзора BFS, DFS до A * и далее) являются основной учебной программой во вводном курсе ИИ. Как интеллект, я согласен, что это не особенно захватывающе, но если ИИ научил меня чему-либо: большая часть ИИ - это просто проблема поиска.

Артем Казнатчеев

Ответы:

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

введите описание изображения здесь

Когда правый следящий автомат находится в положении и его состояние «сигнализирует», что он только что прошел за закрытым квадратом ( с закодированным фиксированным размером, а не произвольным большим квадратом ), тогда он может безопасно повернуть налево и избежать посещения тупика зона. Как подчеркнуто в моем комментарии ниже, автомат будет применять ярлык к каждому лабиринту, который содержит один (или несколько) «субмазов», как показано на рисунке, поэтому он будет работать лучше на бесконечном количестве лабиринтов. В лабиринтах, которые не содержат субмази, как на рисунке, он будет работать как обычный правый следующий автомат. $A$

Аналогичным образом вы можете кодировать конечное число различных фигур фиксированного размера, чтобы избежать тупиков и ускорить работу вашего автомата. Как следствие, не существует «оптимального» решателя близоруких лабиринтов для односвязных лабиринтов с выходом на границе.

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

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

Вор
источник

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

Артем Казнатчеев

@ArtemKaznatcheev: Я думаю, что трюк работает в лабиринтах с входом в лабиринт и выходом на границе. Кроме того, он работает с (бесконечным числом) лабиринтов, в которых есть субмаз, как на рисунке). Я отредактирую вопрос, чтобы уточнить этот момент.

Вор

Если я правильно понимаю, это можно интерпретировать как конечный прогноз: выводить действие только после того , как будут прочитаны следующие символов. Если так, то да, это всегда должно работать.

k

$k$

Рафаэль

@ Рафаэль: Я бы лучше назвал это конечным объемом памяти: если последние шагов (действий) образуют квадрат (по часовой стрелке), то поворот вправо приведет к внутренней части квадрата (тупик), поэтому повернуть налево безопасно.

4 k - 1

$4k-1$

Vor

Вопрос 1

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

Мы строим семейство лабиринтов . Каждый - это коридор длины который заканчивается поворотом направо. То же самое с и слева, соответственно. Мы можем построить преобразователь и который оптимально решает подмножества и соответственно. Тогда ни один датчик не лучше, чем или . $R=(R_i)_i$ $R_i$ $i$ $L$ $A_R$ $A_L$ $R$ $L$ $A_R$ $A_L$

Теперь наоборот: с учетом мы можем построить что доказывает, что ни один решатель не лучше, чем . Я хочу сказать, что я думаю, что мы можем сделать то же самое для левой решающей задачи лабиринта, но набор лабиринтов был бы более сложным. $A_R$ $R$ $A_R$

Вероятностные преобразователи могут быть исключены, поскольку детерминированный преобразователь будет быстрее на этих бесконечных наборах лабиринтов.

Вопрос 2 (благодаря обсуждению с ОП )

Нет. (Источник: эта новаторская статья Лотара Будаха. Эта теорема более четко изложена в аннотации этой статьи Фрэнка Хоффмана.)

jmad
источник

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

Артем Казнатчеев

т.е. если лучше , чем является и вызвать мою левую руку Решатель , то вы показываете , что х и . То , что я прошу вас , чтобы показать, подумал, что мы имеем ( или ). Это очень разные заявления.

A

$A$

B

$B$

A \leq B

$A \leq B$

L

$L$

\exists R

$\exists R$

R ≰ L

$R \not\leq L$

L ≰ R

$L \not\leq R$

\forall A

$\forall A$

A ≰ L

$A \not\leq L$

L \leq A

$L \leq A$

Артем Казнатчеев

@ArtemKaznatcheev: да, я знаю, что это не отвечает на вопрос, я должен был быть более ясным. Моя точка зрения заключается в том, что я думаю, что мы могли бы применить это к ЛГ, но также и то, что слишком чувствителен к этому виду легко бесконечных множеств. (Я думаю, что только если очень похож на (подмножество) )

\leq

$≤$

A \leq B

$A≤B$

B

$B$

A

$A$

jmad

Альтернативное определение, которое я могу придумать, состоит в том, чтобы попросить плохих примеров быть немного (вместо конечных); полиномиальное или меньшее (может быть, лог?) количество плохих примеров и множество: суперполиномиальное / экспоненциальное количество хороших примеров. Но я на самом деле думал, что это было еще более ограничительным, так как должен превзойти на МНОГИХ примерах.

A

$A$

B

$B$

Артем Казнатчеев

@ArtemKaznatcheev: вы можете сделать что-то, что зависит от размера лабиринта (что-то вроде но это сомнительно и непрактично). Мы можем продолжить в чате .

# {A (M) < B (M) ∣ | M | \leq n} / # {M ∣ | M | \leq n} = o (1)

$\#\{A(M)<B(M) ∣ |M|≤n\}/\#\{M ∣ |M|≤n\} = o(1)$

jmad