¿Cuál es el objetivo?

Un robot autónomo debe resolver un laberinto y completar su recorrido desde la celda de salida hasta la celda de llegada en el menor tiempo posible.

"Dispondrá de 7 minutos para completarlo en el menor tiempo que pueda. Ganará la competición el robot que complete el recorrido en el menor tiempo.

Cada celda tiene un tamaño de 180 por 180 milímetros, y sobre cada uno de los lados de la celda puede existir, o no, una pared que no dejará pasar al robot por ese lateral."

Este extracto viene de las reglas de competición de la OSHWDem y se basa en un laberinto de 16 x 16 celdas. Ten en cuenta que otras competiciones pueden tener laberintos más grandes y otras normas. Por el momento nos centraremos en estas normas, aunque lo suyo es que tu robot, a nivel de programación y mecánica, sea lo suficientemente flexible como para adaptarse.

La posición inicial es en una de las cuatro esquinas del laberinto. El único requisito es que el cuadro de inicio esté rodeado por tres paredes a la izquierda, derecha y atrás del robot. 

En la imagen abajo, la posición C0-R0 es la casilla inicial. El destino está en uno de los cuatro cuadrados en el mismo centro del laberinto (posición C7-R7, C7-R8, C8-R7 y C8-R8). 

Se puede acceder al cuadrado que encierra las cuatro posiciones de destino a través de una sola abertura. Alcanzar cualquiera de los cuatro cuadrados cuenta como laberinto resuelto.

Identificar la orientación y los muros

Para conseguir resolver un laberinto mediante código, necesitamos definir el laberinto como un array de dos dimensiones de 16x16 casillas. Cada posición del array tiene un valor inicial de 0.

Sabemos que mientras el robot está en el laberinto, puede moverse mientras mira hacia cuatro direcciones (orientaciones). Para representar esto en el algoritmo, debe usarse una variable que define la orientación del robot para almacenar uno de los cuatro valores; 0, 1, 2 y 3. 

Cada vez que el robot realiza un giro, la variable de orientación se actualiza.

Ahora hay que representar de alguna manera todas las posibilidades de muros que puede encontrar el robot gracias a sus sensores de distancia que veremos más adelante.

Método pared derecha (o izquierda)

Esta es la forma más sencilla de resolver un laberinto sin demasiadas complicaciones en cuando a la programación. A ver, necesitas programar, si no no estaría leyendo este artículo, pero digamos que es sencillo de hacer.

El funcionamiento es bien sencillo y consiste en hacer que el robot siga siempre la pared derecha. También puedes seguir la pared izquierda según cómo sea el laberinto al que te enfrentas, aunque normalmente esto debería ser configurable con algún botón en el robot.

Abajo puedes ver un ejemplo siguiendo la pared izquierda.

Debes tener en cuenta que aunque sea un algoritmo relativamente sencillo de programar, solo funciona si el laberinto no tiene islas. De lo contrario, tu robot podría entrar en bucle y no salir nunca.

Método Floodfill

Imagina que viertes agua en el destino del laberinto (que son las cuatro celdas centrales rodeadas por 7 paredes). El agua primero fluirá hacia la celda inmediatamente fuera de las celdas de destino. Y luego a las celdas vecinas de fácil acceso. Del mismo modo, el agua fluirá a lo largo de los caminos del laberinto y finalmente alcanzará la posición inicial del ratón.

Definimos otro laberinto de 16*16, llamémoslo matriz Flood. Inspirándonos en el ejemplo del vertido de agua, asignamos cero a las cuatro celdas de destino, 1 a la celda a la que las celdas de destino pueden acceder inmediatamente, y así sucesivamente. Las celdas a las que fluye el agua en último lugar obtendrán el número más alto.

Si colocas el robot en cualquier lugar del laberinto y le pides que viaje a la celda con el valor 1 menor que el valor de la celda en la que se encuentra, se garantiza que el robot eventualmente llegará al destino en la ruta con un número mínimo de celdas.

Pero espera, porque seguramente te has dado cuenta de un detalle importante: 

Tu robot todavía no sabe cómo están organizadas las paredes del laberinto.

Lo que se hace es asumir al principio que no hay paredes, salvo las que contiene la meta del centro. Entonces e array de coordenadas y valores, inicialmente se parecerá a algo así:

El robot debe moverse a una casilla de menor valor hasta llega a cero (meta), pero como dijimos, todavía no sabe cómo están organizadas las paredes. Lo que debe hacer ahora, es intentar llegar a la casilla de menos valor según avanza, pero según va encontrando paredes, ir ajustando la ruta.

Eso lo podemos definir en los siguientes pasos lógicos:

• Encuentra los valores de sus celdas vecinas (de la matriz de inundación)
• Mover a la celda vecina con el menor valor.
• Detecta las paredes a su izquierda, derecha y al frente.
• Actualiza las paredes recién encontradas en el laberinto.
• Realice el relleno de inundación para todo el conjunto
• Regresar al paso 1 y continúe hasta que el robot se mueva a la posición deseada.

Cada vez que el robot encuentre una nueva pared, debe recalcular todo el array de valores con las nuevas paredes encontradas y eso por cada celda del laberinto. De esta forma, irá actualizando los valores hasta encontrar el camino a la meta.

Cuando el robot encuentre finalmente la celda final de meta, tendrás en tu array el camino correcto y completo para llegar desde la meta hasta el centro y viceversa. 

Al llegar a la meta, normalmente se hace que el robot recorra el camino en sentido inverso hasta el inicio del laberinto para poder sacarlo, aunque es opcional, es cómodo.

Algunos robots aprovechan el camino de vuelta para volver a hacer el mismo proceso en orden inverso e intentar encontrar un camino alternativo (puede haber otros caminos!) y guardar un segundo mapa. Luego decidir cuál es el más rápido.

Ahora que el robot sabe cuál es el camino a la meta, solo falta iniciarlo de nuevo para que esta vez, en lugar de buscar un camino, recorra el camino encontrado lo más rápido posible. Pero eso (y todo lo anterior) no es posible si tu robot no tiene los componentes fundamentales de control que consisten en sensores de distancia, motores y un buen ajuste de control para que sea eficiente en su camino.

Todo eso lo veremos en las siguientes páginas.

Una buena recomendación, antes de empezar a programar como un loco al mismo tiempo que montas tu robot, es usar el simulador MMS (link abajo). Es un sistema muy interesante, ya que, mediante una simulación, puede sprobar tu código antes de que lo metas en tu robot. Con eso te vas a ahorrar un montón de trabajo y podrás afinar tu algoritmo de forma cómoda.

Referencias

Esta página está inspirada en este artículo donde se explica el funcionamiento del robot Picola. Te dejo unos enlaces interesantes para que puedas indagar más.

• Código fuente Picola

También hay un excelente simulador de micromouse donde puede practicar y probar tu código en un robot virtual y ver cómo se defiende. Lo podrás cruzar con tu código de Arduino y afinar tu algoritmo.

• Simulador MMS
• MMS Arduino