Un proyecto muy interesante en robótica educativa es la realización de un robot resuelve laberintos. Dependiendo del nivel y experiencia del grupo se le puede programar con algoritmos de diferente dificultad. El resultado es siempre espectacular para quien está empezando a programar puesto que es capaz de dotar al robot de una inteligencia que le hace ser capaz de escapar de un laberinto.
La construcción de un robot resuelve laberintos es muy similar independientemente de la plataforma que uséis y lo vais a poder realizar tanto con Arduino, Lego Mindstorms o cualquier kit de robótica educativa tipo mBot de Makeblock. Realmente lo importante es elegir el algoritmo que vamos a programar en el robot y posteriormente estudiar la forma en la que debemos utilizar los sensores que tengamos disponibles para poder llevar a cabo el algoritmo elegido.
Si nunca habéis trabajado con un robot resuelve laberintos lo normal sería empezar por el algoritmo más sencillo de resolver a nivel de robótica y programación y en proyectos posteriores ir subiendo la complejidad.
Estos son algunos de los algoritmos para diseñar un robot resuelve laberintos:
- Seguidor de paredes. Se trata de un algoritmo para resolver laberintos simples. Consiste en seguir paralelo a una pared y si se llega a una intersección girar siempre hacia el mismo lado, izquierda o derecha, pero siempre hacia el mismo. Lógicamente puede no encontrarse el camino más corto. Este método no funcionará cuando el objetivo del laberinto está en el centro y hay un circuito cerrado rodeándolo, ya que es muy probable que vuelva al punto de origen sin llegar al centro.
- Algoritmo de garantía. Es una versión modificada del seguidor de paredes pero que es capaz de saltar entre islas resolviendo laberintos que el seguidor de paredes no puede resolver. Garantiza la resolución desde cualquier comienzo desde el perímetro hasta el objetivo en el centro, pero no es capaz de hacerlo al revés. No necesita marcar o recordar los lugares por los que ha pasado, pero si contar los giros que hace a derecha o izquierda, de manera que pueda saber que se encuentra en una isla y pueda saltar a otra zona en la dirección elegida como preferente.
- Cadena. Trata al laberinto como muchos pequeños laberintos encadenados y los resuelve en secuencia. En base utiliza el algoritmo de garantía y por lo tanto el seguidor de paredes. Aunque puede no encontrar el camino más corto si que trata de acortarlo ya que compara caminos alternativos y analiza si ya se ha pasado por un punto o no.
- Vuelta atrás recursiva. Se trata de que el robot resuelve laberintos debe mapear en memoria las zonas por las que va pasando. Puede explorar en las cuatro direcciones con la condición de que si ya ha pasado por un camino evita pasar de nuevo. Siempre encuentra la solución aunque no sea la más corta.
- Algoritmo de Trémaux. Planteado por el ingeniero francés Charles Trémaux para resolver por personas en el interior de un laberinto. Es muy similar al método de la vuelta atrás recursiva y hay que seguir las siguientes normas: no seguir el mismo camino dos veces, tomar cualquier camino si se llega a una intersección nueva, si un camino nuevo lleva a una intersección conocida o a un callejón sin salida volver al inicio del camino y por último, si un camino viejo lleva a una intersección vieja seguir un camino nuevo, y si no lo hay seguir cualquiera. Siempre resuelve el laberinto y si se deja al robot en el interior de un laberinto siempre encuentra la salida.
Hay más algoritmos para programar un robot resuelve laberintos, pero os recomiendo empezar con estos, sobretodo si no tenéis mucha experiencia en el tema.
La competición más conocida utilizando un robot resuelve laberintos es la Micromouse Competition, en funcionamiento desde finales de los 70 aunque se tiene constancia de algunos eventos desde la década de los 50. Dejo al pie de página un vídeo que refleja el altísimo nivel de esta competición, donde los robots en una primera exploración mapean el laberinto para posteriormente resolver el laberinto de la manera más rápida con resultados increíbles de menos de 5 segundos.
No dejéis de visitar el reto de robótica con mBot como robot resuelve laberintos También hay alguna práctica con robots en laberintos en la plataforma de cursos de robótica educativa de Juegos Robótica, donde puedes aprender a programar desde cero con diversos kits de robótica educativa.
Si os interesa profundizar más en este tema o en algún algoritmo concreto no tenéis más que decirlo.
Dani S.
Esperanto la solucion al resuelve laberinto…
Hola Begoña!
La solución estará colgada entre mañana y el viernes, espero que os guste.
Dani
Ya lo tienes Begoña: https://juegosrobotica.es/retos/reto-mbot-robot-laberinto/
Que algoritmo haces para que memorice el camino más corto, y cuando lo pones de nuevo en la pista solo vaya por ese camino?
Si se quisiera memorizar para encontrar el camino más corto habría que memorizar los giros y el tiempo transcurrido entre giros para hacer un mapa “virtual”, y luego analizar y encontrar el camino más corto para que luego al volver a poner al robot vaya directo por el camino más corto. Mapear el laberinto no es difícil, pero que el robot analice el laberinto mapeado requiere de una programación bastante compleja. La Micromouse Competition requiere de ese tipo de programación. La manera de resolver ese tipo de robots resuelve laberintos no se puede explicar en un comentario ni siquiera en varias entradas, pero puede que lo aborde en un futuro en Juegos Robótica.
me gustaría que me guíes con el tema de programar el mapeo del recorrido como memorizar los giros y el tiempo
Hola Daniel!
Es difícil responder a tu pregunta sin llegar a profundizar, pero tienes que pensar que el laberinto es una cuadrícula de dos dimensiones (columna_x_fila). A través de variables y arrays debes controlar en qué casilla se encuentra el robot. Si parte de la D8 y avanza a la D7, si realiza un giro a la izquierda y luego avanza pasará a estar en la C7. Los giros los vas a tener controlados cuando se produzcan, y los avances deberías controlar tiempos de avance. Si lo haces con un mBot al no tener encoder no tienes otra manera, pero puedes intentar calibrarlo igual que muestro en el reto 26 convirtiendo mBot en BeeBot.
Saber en qué casilla se encuentra el robot en cada momento es fundamental, y contabilizar el número de veces que pasa el robot por ella o al menos si ya ha pasado o no.
Por ejemplo en un laberinto que normalmente no podrías resolver con un seguidor de paredes por estar la solución en el centro con forma de isla, si controlas las casillas por las que ya has pasado y las tratas como paredes podrás solucionar el laberinto.
Mapear el laberinto es un salto importante después de un seguidor de paredes, ánimo!
Dani
cuales serian tus recordaciones finales respecto a este robot
¿A qué te refieres con recordaciones?
cuales serian tus recordaciones finales respecto a este robot
Buenas noches, yo soy nuevo en esto de la programación con arduino, resulta que este año comencé a trabajar en otro lugar donde me dijeron que debo participar en proyectos de rebotica.
En el proyecto en el que debo participar trata de programar una plata Arduino Orion de Makeblock, para que un carro robot salga de un laberinto.
Me gustaría saber si alguien podría ayudarme un poco con la programación o indicarme de donde puedo bajar mas información, intente hacerlo siguiendo la programación de Mbot pero hay unos bloques que no soy compatibles para la placa Arduino Orion.
De antemano muchas gracias.
Hola Mario,
Si llegas a entender el funcionamiento del algoritmo y el desarrollo del programa no debes tener problema en encontrar los bloques específicos para la placa Orion. Básicamente te van a afectar los bloques relacionados con el movimiento de motores.
El reto con mBot estaba limitado en sensores, pero si puedes no dudes en añadir más sensores de ultrasonidos para obtener más información del laberinto.
Saludos,
Dani S.
Quisiera me ayudarán a programar un Arduino nano con el sensor ultrasónico en mblock, para hacer un seguidor de pared. Gracias
Hola Eduardo,
El concepto es el mismo independientemente de la placa que uses. Si ya tienes solucionada la configuración del robot con Arduino Nano debes utilizar el mismo algoritmo, tan sólo debes adaptar las órdenes de avance y giro a las salidas concretas que manejen los motores.
Saludos
Beaitiful!!!