Solución óptima de laberintos miopes

10

Estaba jugando con la demostración de Google Blocky's Maze , y recordé la vieja regla de que si quieres resolver un laberinto, solo mantén la mano izquierda en la pared. Esto funciona para cualquier laberinto conectado de forma simple y puede implementarse mediante un transductor finito.

Deje que nuestro robot sea representado por un transductor con las siguientes acciones y observables:

  • Acciones: avance ( ), gire a la izquierda ( ), gire a la derecha ( )
  • Observables: muro adelante ( ), sin muro adelante ( )

Luego podemos construir el solucionador de laberintos izquierdo como (perdón por mi dibujo perezoso):

transductor para resolver el laberinto

Donde ver un observable nos hará seguir el borde apropiado fuera del estado mientras ejecutamos la acción asociada con ese borde. Este autómata resolverá todos los laberintos conectados de forma simple, aunque puede llevar su tiempo siguiendo callejones sin salida. Llamamos a otro autómata mejor que A si:B A

  1. da estrictamente más pasos solo en un número finito de laberintos, yB

  2. toma estrictamente menos pasos (en promedio; para variantes probabilísticas) en un número infinito de laberintos.B

Mis dos preguntas:

  1. ¿Existe un autómata finito mejor que el que se muestra arriba? ¿Qué pasa si permitimos transductores probabilísticos?

  2. ¿Existe un autómata finito para resolver laberintos que no están necesariamente simplemente conectados?

Artem Kaznatcheev
fuente
@jmad y yo tuvimos una discusión muy fructífera en el chat sobre esta pregunta. Si está pensando en la pregunta (especialmente las definiciones de mejor que ), le recomiendo revisar la transcripción.
Artem Kaznatcheev
No veo cómo esta pregunta se relaciona con la IA (en particular, con nuestros agentes para no cambiar su comportamiento con los datos de la instancia), pero no soy un experto en ese campo.
Raphael
3
@Raphael para resolver laberintos y encontrar caminos (desde la revisión de BFS, DFS, hasta A * y en adelante) son un currículo básico en un curso de introducción a la IA. Estoy de acuerdo, como inteligencia, esto no es particularmente emocionante, pero si la IA me ha enseñado algo: la mayoría de la IA es solo un problema de búsqueda.
Artem Kaznatcheev

Respuestas:

6

Si entendí bien la pregunta, creo que puede aplicar un truco de aceleración para obtener autómatas más rápidos en un número infinito de laberintos (siempre que la salida se coloque en uno de los bordes): simplemente puede usar los estados internos para almacenar un número finito de pasos y reconocer callejones sin salida como el de la figura:

ingrese la descripción de la imagen aquí

Cuando un autómata de seguimiento a la derecha está en la posición y su estado "indica" que acaba de seguir un cuadrado cerrado ( con un tamaño fijo codificado, no un cuadrado grande arbitrario ), puede girar con seguridad a la izquierda y evitar visitar el callejón sin salida zona. Como se subraya en mi comentario a continuación, el autómata aplicará el acceso directo en cada laberinto que contenga uno (o más) "submazes" como el de la figura, por lo que funcionará mejor en infinitos laberintos. En los laberintos que no contienen un submaze como el de la figura, funcionará como un autómata de seguimiento a la derecha estándar.A

De manera similar, puede codificar un número finito de diferentes formas de tamaño fijo para evitar callejones sin salida y acelerar su autómata. Como consecuencia, no existe un solucionador de laberintos miopes "óptimo" para laberintos conectados simplemente con la salida colocada en el borde.

El truco funciona si la entrada se coloca dentro del laberinto y la salida también en el borde; pero si la salida se coloca dentro del laberinto, entonces no funciona porque se deben visitar todas las ubicaciones y, en este caso, su solucionador miope es óptimo.

Obviamente, no puede aplicar el mismo truco para resolver laberintos conectados no simplemente (pero debería funcionar si hay un límite superior fijo en el tamaño de cada componente no conectado).

Vor
fuente
Este es un truco genial para el caso de entrada-salida en el límite (que es una subclase de laberintos conectados simplemente). Muestra que en este caso restringido, el orden que definí no tiene elementos mínimos. Sin embargo, no creo que se pueda generalizar a todos los laberintos conectados simplemente (que es el conjunto que sigue a la izquierda).
Artem Kaznatcheev
@ArtemKaznatcheev: Creo que el truco funciona en laberintos con entrada dentro del laberinto y salida también en el límite. Además, funciona en laberintos (infinitos) en los que hay un submaze como el de la figura). Editaré la pregunta para aclarar este punto.
Vor
Si entiendo correctamente, esto se puede interpretar como una búsqueda anticipada finita: generar una acción solo después de que se hayan leído los siguientes símbolos. Si es así, sí, eso siempre debería funcionar. k
Raphael
@Raphael: mejor lo llamaré una cantidad finita de memoria: si los últimos pasos (acciones) forman un cuadrado (en el sentido de las agujas del reloj), girar a la derecha conduciría a la parte interna del cuadrado (un callejón sin salida), entonces es seguro girar a la izquierda. 4k1
Vor
5

Pregunta 1

Creo que su definición de mejor es demasiado estricta en el sentido de que lo finito es demasiado restrictivo (pero no tengo una mejor definición).

Construimos una familia de laberintos . Cada R i es un corredor de longitud i que termina con un giro a la derecha. Lo mismo con L y izquierda, respectivamente. Podemos construir un transductor A R y A L que resuelva de manera óptima los subconjuntos R y L , respectivamente. Entonces no transductor es mejor que A R o A L .R=(Ri)iRiiLARALRLARAL

ARRAR

Los transductores probabilísticos probablemente pueden descartarse ya que un transductor determinista será más rápido en estos conjuntos infinitos de laberintos.

Pregunta 2 (gracias a la discusión con OP )

No. (fuente: este documento innovador de Lothar Budach. El teorema se establece más claramente en el resumen de este artículo de Frank Hoffmann).

jmad
fuente
sí, tendríamos que definir algunas clases de equivalencia en laberintos bajo transformaciones estándar (como rotaciones y reflexiones) para hacer que la pared izquierda y derecha sigan el equivalente. Lamentablemente, su sección de pregunta 1 no responde a mi primera pregunta . Usted muestra que hay solucionadores incomparables (en el orden parcial 'mejor que') (como el izquierdo y el derecho si no hacemos suposiciones de simetría), pero no prueba que no haya uno que sea mejor que la mano izquierda
Artem Kaznatcheev
ABABLRRLA A L L ALRAALLA
ABBA
AB
#{A(M)<B(M)|M|n}/#{M|M|n}=o(1)