Construya un Micromouse: robot para laberintos con Flood Fill

Qué va a construir

Un robot al que se suelta en un laberinto que nunca ha visto, encuentra el centro y luego vuelve por la ruta más corta que puede demostrar que existe.

Esa segunda mitad es lo que distingue a un micromouse de cualquier otro robot de este sitio. Un seguidor de línea reacciona. Un esquivador de obstáculos reacciona. Un micromouse recuerda: construye un mapa mientras se mueve y luego planifica sobre celdas que no ha visitado. Es el problema de robótica completo más pequeño que hay: percepción, movimiento, mapeo y planificación, y todo tiene que funcionar a la vez.

La estrategia de dos pasadas

Los ratones de competición hacen varias pasadas y se puntúa la más rápida. Eso produce una estrategia que merece la pena copiar aunque nadie te esté cronometrando:

Pasada uno: explorar. Conduce con cuidado, registra qué celdas tienen qué paredes y llega al centro. La velocidad es irrelevante; el producto es el mapa.

Pasada dos: explotar. Haz un flood fill del mapa terminado, calcula la ruta más corta y recórrela sin parar a sensorear nada que ya sepas.

La división importa porque las dos pasadas quieren cosas opuestas. Explorar quiere movimiento lento y cauto y percepción constante. La pasada de velocidad quiere compromiso. Intentar hacer las dos a la vez produce un robot que se da mal en cada una.

Por qué el algoritmo no es la parte difícil

El flood fill es realmente simple: dale a la celda meta la distancia 0, dale a cada vecina 1 más que la menor vecina que puede alcanzar, y luego avanza siempre a un número menor. Son unas decenas de líneas y es demostrablemente el camino más corto en una rejilla.

La parte difícil es que da por supuesto que el robot sabe en qué celda está.

Cuentes mal una celda, o gires 88° en vez de 90° unas cuantas veces, y el planificador estará resolviendo el laberinto para un robot que está en otro sitio. El síntoma es desconcertante: el algoritmo es perfecto, el cableado está bien, y el robot se mete con confianza en una pared.

Así que el orden de construcción de abajo dedica la mayor parte de su esfuerzo al movimiento y añade el planificador al final. Puedes demostrar el planificador por separado en el simulador de resolución de laberintos, donde la posición es exacta por construcción —y precisamente por eso vale la pena simularlo primero.

Lista de materiales

Total: unos $70–95, más el laberinto.

Tres sensores de distancia, no uno. Un único sensor frontal obliga al robot a girar para mirar, y eso cuesta tiempo y —mucho peor— introduce error de rumbo en cada observación. Tres sensores fijos permiten leer las tres paredes de una celda en un instante, sin moverse. Esta es la diferencia entre un ratón que mapea de forma fiable y uno que acumula error cada vez que comprueba una pared.

Recuerda que los tres sensores VL53L0X arrancan en la dirección 0x29, así que necesitas tres GPIO en XSHUT para levantarlos de uno en uno y reasignar direcciones —y hay que repetirlo en cada arranque, porque el cambio es volátil.

Vigila la RAM. Un campo de distancias de flood fill para 16×16 guardado como uint8_t son 256 bytes, más el mapa de paredes, más una cola. En los 2 KB de un Uno eso cabe, pero solo si eres deliberado al respecto —lo cual ya es un buen ejercicio, y una razón por la que mucha gente se pasa al ESP32 aquí.

Orden de construcción

1 — Consigue tres lecturas de distancia limpias. Frente, izquierda y derecha, con sensores de tiempo de vuelo VL53L0X. Comparten un bus I²C y arrancan en la misma dirección, así que levántalos de uno en uno manteniendo los otros en reset y reasignando direcciones al arrancar. Confirma que cada uno lee una pared a una distancia conocida antes de montar nada.

2 — Consigue que conduzca recto y gire a escuadra. Este es el proyecto real. Sigue seguimiento de pared y giros precisos: un lazo PID sobre los sensores laterales para mantenerse centrado, giros con giróscopo integrado en vez de contar encoders, y re-escuadrar contra una pared frontal siempre que haya una disponible. No avances hasta que el robot pueda hacer diez giros y siga mirando en la dirección correcta.

3 — Cuenta celdas de forma fiable. Los encoders predicen dónde debería estar una frontera; el flanco de bajada de una pared lateral confirma dónde está de verdad. Cuando discrepen, cree a la pared: es una referencia física, no una estimación acumulada.

4 — Registra las paredes en un mapa. Dos bits por celda para cuatro paredes, y un laberinto 16 × 16 cabe en unos cientos de bytes. Registra lo que ves según lo ves.

5 — Añade el flood fill. Ahora el planificador tiene datos honestos. Recalcula las distancias cada vez que una pared recién descubierta invalide el plan actual: esa replanificación es la razón completa de usar flood fill en vez de una búsqueda de una sola pasada.

Notas de hardware que importan

Pequeño gana a rápido. El robot tiene que girar dentro de una celda. Un chasis ceñido con las ruedas cerca del centro de rotación pivota limpio; uno largo roza las paredes en cada giro, y ningún ajuste arregla la geometría.

El backlash es error de rumbo. Cada giro sobre el sitio invierte los motores, y un reductor flojo pierde los primeros pocos grados: unos 0.9° de rumbo en una rueda de 42 mm por 4° de juego. Los motores N20 con reductor metálico existen justo por eso.

Monta los sensores laterales algo adelantados y angulados. Apuntarlos de frente significa que solo ven una pared cuando están exactamente a su lado, así que el robot se entera de la pared tarde. Un pequeño ángulo hacia delante le da al lazo de control un adelanto.

Dale a los sensores una alimentación estable. Un VL53L0X devuelve números plausibles pero equivocados en un raíl que se hunde en vez de fallar de forma evidente —el peor tipo de fallo, porque el mapa se llena de paredes que no están.

Qué significa hacerlo bien

Dos de esas filas merecen énfasis.

La detección de paredes no tiene crédito parcial. Una pared registrada mal corrompe el mapa, el flood fill calcula entonces una ruta segura a través de una pared, y la pasada de velocidad se mete de frente en ella. No hay degradación suave, y por eso la pasada de exploración va lenta.

Las filas de deriva son el proyecto real. El algoritmo no es la parte difícil: el flood fill son unas cuarenta líneas y puedes probarlo entero en el simulador sin hardware alguno. La parte difícil es que tras diez celdas el robot ya no está donde cree que está, y un ratón que deriva 20 mm cada diez celdas estará tocando una pared al llegar al lado opuesto del laberinto. Todo lo que hace que un micromouse real funcione —corrección por seguimiento de pared, giros con giróscopo fusionado, calibración de encoders— existe para luchar contra ese único número.

Cuando va mal

Casi todas las entradas de esa tabla son fallos de movimiento o percepción y no del algoritmo. Esa distribución es lo más útil que conviene saber antes de empezar, porque te dice en qué gastar tus fines de semana.

Si quieres las ideas de mapeo y planificación sin el hardware, el simulador de resolución de laberintos ejecuta la misma estrategia de dos fases en el navegador, y la ruta de planificación de caminos y mapeo la lleva hacia A* y SLAM. Para un primer robot de laberinto mucho más barato, el solucionador de laberintos sobre línea usa cinta en vez de paredes y no necesita ningún sensor de distancia.