Laberinto Robot Solver, utilizando Inteligencia Artificial con Arduino (4 / 10 paso)

Paso 4: Resolver el laberinto - la regla de la mano izquierda

Como comentamos en la introducción la mayoría de los laberintos, sin embargo complejo su diseño puede aparecer, se formaron esencialmente de una pared continua con muchos nudos y ramas. Si la pared que rodea el objetivo de un laberinto está conectada con el perímetro del laberinto en la entrada, el laberinto puede resolverse siempre por mantener una mano en contacto con la pared, sin embargo muchos desvíos que pueden implicar. Estos laberintos 'simples' se conocen correctamente como "Simplemente conectados."

Busca en Wikipedia, nos enteramos de queel seguidor de la pared es la regla más conocida para atravesar laberintos. Es también conocida como la regla de la mano izquierda o la derecha regla. Si el laberinto es simplemente conexa, es decir, sus paredes están conectadas juntos o límite externo del laberinto, luego manteniendo una mano en contacto con una de las paredes del laberinto el solucionador se garantiza para no perderse y llegar a una salida diferente si lo hubiera; de lo contrario, él o ella volverá a la entrada después de haber atravesado junto a cada corredor que parte de las paredes por lo menos una vez."

En Resumen, la regla de la mano izquierda puede ser descrita como:

1. Coloque su mano izquierda en la pared.
2. Empezar a caminar hacia adelante
3. En cada interseccióny a lo largo del laberinto, mantenga siempre la mano izquierda tocar la pared a su izquierda.
4. Finalmente, llegar al final del laberinto. Usted probablemente no seguirá el camino más corto y más directo, pero llegar allí.

Por lo tanto, la clave aquí es identificar las intersecciones, definir qué curso tomar basado en las reglas anteriores. Específicamente en nuestra clase de laberinto 2D, hay 8 diferentes tipos de intersecciones (véase el cuadro 1):

Mirando el cuadro, podemos realizar que son las acciones posibles en las intersecciones:

1. En una "Cruz"
   • Ir a la izquierda
   • Ir a la derecha
   • Siga recto
2. En forma de "T":
   • Ir a la izquierda
   • Ir a la derecha
3. En el derecho solamente:
   • Ir a la derecha
4. En a sólo la izquierda:
   • Ir a la izquierda
5. En el recto o a la izquierda:
   • Ir a la izquierda
   • Siga recto
6. En recta o derecha:
   • Ir a la derecha
   • Siga recto
7. En un callejón sin salida:
   • Ir atrás ("U turn")
8. En el final del laberinto:
   • Parada

Pero, aplicando la "regla de la mano izquierda", las acciones se reducirá a una opción:

1. En una "Cruz": ir a la izquierda
2. En forma de "T": ir a la izquierda
3. A un derecho solamente: ir a la derecha
4. Sólo una izquierda: ir a la izquierda
5. En el recto o a la izquierda: ir a la izquierda
6. En recta o derecha: ir recto
7. En un callejón sin salida: ir atrás ("U turn")
8. En el final del laberinto: detener

Estamos casi allí. Cuando el robot llega a un callejón sin salida o al final de un laberinto, es fácil de identificar ya que no existen situaciones ambiguas (ya hemos implementado las acciones en el Robot seguidor de línea). El problema es cuando el robot encuentra una "línea" por ejemplo, porque una línea puede ser una "Cruz" (1) o una "T" (2). También cuando llegue a una "izquierda o derecha giro", aquellos pueden ser las opciones para ir directamente o un giro (opciones 3 y 4) (5 o 6). Para descubrir exactamente en qué tipo de intersección es el robot, debe tenerse un paso adicional: el robot debe ejecutar una "pulgada extra" y ver lo que es el siguiente (véase el cuadro 2 como ejemplo).

Por lo tanto, en términos de flujo de que las acciones posibles se puede ahora describir como:

1. En un callejón sin salida: ir atrás ("U turn")
2. En una línea:
   • Ejecutar una pulgada extra
   • Si hay una línea: es un "cruce" == > ir a la izquierda
   • Si no hay ninguna línea: es una "T" == > ir a la izquierda
   • Si hay otra línea: es el final de laberinto == > detener
3. En una vuelta a la derecha:
   • Ejecutar una pulgada extra
   • Si hay una línea: es una recta o derecha == > ir directamente
   • Si no hay ninguna línea: es un derecho == > ir a la derecha
4. En un giro a la izquierda:
   • Ejecutar una pulgada extra
   • Si hay una línea: es un derecho o a la izquierda == > ir izquierda
   • Si no hay ninguna línea: es una izquierda == > ir a la izquierda

Tenga en cuenta que de hecho, en el caso de un "giro a la izquierda", usted puede omitir la prueba, porque tomarás la izquierda de todos modos. Salí de la explicación más genéricos sólo para mayor claridad. El código real me salto esta prueba.

(el cuadro 3, se muestra un laberinto muy sencillo en mi piso del laboratorio, que utilizo para fines de prueba):