Costruisci un Micromouse per labirinto con flood fill

Cosa stai costruendo

Un robot che viene messo in un labirinto mai visto, trova il centro e poi torna indietro percorrendo il percorso più breve di cui può dimostrare l’esistenza.

Quella seconda metà è ciò che distingue un micromouse da ogni altro robot di questo sito. Un robot seguilinea reagisce. Un robot per l’evitamento degli ostacoli reagisce. Un micromouse ricorda: costruisce una mappa mentre si muove e poi pianifica tra celle che non ha visitato. È il più piccolo problema completo di robotica: rilevamento, movimento, mappatura e pianificazione, tutti contemporaneamente.

La strategia a due corse

I mouse da competizione fanno diverse corse e vengono valutati sulla più veloce. Questo produce una strategia che vale la pena copiare anche quando nessuno sta cronometrando:

Prima corsa — esplora. Guidare con attenzione, registrare quali celle hanno quali pareti e raggiungere il centro. La velocità è irrilevante: la mappa è il prodotto.

Seconda corsa — sfrutta. Applica flood fill alla mappa completata, calcola il percorso più breve e percorrilo senza fermarti a rilevare ciò che già sai.

La divisione conta perché le due corse vogliono cose opposte. L’esplorazione vuole movimento lento e cauto e sensori costanti. La corsa veloce vuole impegno. Provare a fare entrambe le cose insieme produce un robot che è scarso in entrambe.

Perché l’algoritmo non è la parte difficile

Flood fill è davvero semplice: assegna alla cella dell’obiettivo la distanza 0, assegna a ogni vicina un valore superiore di 1 rispetto al vicino più basso raggiungibile e poi scendi sempre verso un numero minore. Sono poche decine di righe e su una griglia è dimostrabilmente il percorso più breve.

La parte difficile è che l’algoritmo presuppone che il robot sappia in quale cella si trova.

Conta male una cella, oppure gira di 88° invece di 90° qualche volta, e il pianificatore sta risolvendo il labirinto per un robot che si trova altrove. Il sintomo è frustrante: l’algoritmo è perfetto, il cablaggio è corretto e il robot entra con sicurezza in un muro.

L’ordine di costruzione qui sotto dedica quindi gran parte dell’impegno al movimento e aggiunge il pianificatore per ultimo. Puoi dimostrare il pianificatore separatamente nel simulatore del risolutore di labirinto, dove la posizione è esatta per costruzione: è precisamente il motivo per cui simularlo prima vale il tempo investito.

Lista dei componenti

Totale: circa $70–95, più il labirinto.

Tre sensori di distanza, non uno. Un solo sensore frontale costringe il robot a girare per guardare, il che costa tempo e—molto peggio— introduce un errore di orientamento a ogni osservazione. Tre sensori fissi permettono al robot di leggere tutte e tre le pareti di una cella in un istante, senza muoversi. Questa è la differenza tra un mouse che mappa in modo affidabile e uno che accumula errore ogni volta che controlla una parete.

Ricorda che tutti e tre i sensori VL53L0X si accendono sull’indirizzo 0x29, quindi servono tre GPIO su XSHUT per attivarli uno alla volta e riassegnare gli indirizzi— e per rifarlo a ogni avvio, perché la modifica è volatile.

Fai attenzione alla RAM. Un campo delle distanze flood fill 16×16 memorizzato come uint8_t occupa 256 byte, più una mappa dei muri e una coda. Nei 2 KB di un Uno lo spazio c’è, ma solo se lo gestisci con attenzione— il che è già un buon esercizio e il motivo per cui molte persone passano a ESP32 qui.

Ordine di costruzione

1 — Ottieni tre letture di distanza pulite. Fronte, sinistra, destra, usando i sensori a tempo di volo VL53L0X. Condividono un bus I²C e si avviano allo stesso indirizzo, quindi attivali uno alla volta tenendo gli altri in reset e riassegnando gli indirizzi all’avvio. Conferma che ognuno legga una parete a una distanza nota prima di montare qualsiasi cosa.

2 — Fagli percorrere dritto e girare in quadrato. Questo è il vero progetto. Segui inseguimento delle pareti e svolte precise: un ciclo PID sui sensori laterali per restare centrato, svolte integrate con il giroscopio invece dei conteggi degli encoder e riallineamento in quadrato contro una parete frontale ogni volta che è disponibile. Non andare avanti finché il robot non riesce a fare dieci svolte e a essere ancora rivolto nella direzione giusta.

3 — Conta le celle in modo affidabile. Gli encoder prevedono dove dovrebbe essere un confine; il fronte di discesa di una parete laterale conferma dove si trova davvero. Quando sono in disaccordo, credi alla parete: è un punto di riferimento fisico, non una stima accumulata.

4 — Registra i muri in una mappa. Due bit per cella per quattro muri, e un labirinto 16 × 16 entra in poche centinaia di byte. Registra ciò che vedi quando lo vedi.

5 — Aggiungi flood fill. Ora il pianificatore ha dati onesti. Ricalcola le distanze ogni volta che un muro appena scoperto invalida il piano corrente: questa riorganizzazione è l’intero motivo per cui si usa flood fill invece di una ricerca eseguita una sola volta.

Note hardware importanti

Piccolo batte veloce. Il robot deve ruotare dentro una cella. Un telaio compatto con le ruote vicino al centro di rotazione pivota in modo pulito; uno lungo urta i muri a ogni svolta e nessuna quantità di regolazione corregge la geometria.

Il gioco del riduttore è errore di orientamento. Ogni svolta su se stesso inverte i motori e un riduttore allentato perde i primi gradi, circa 0.9° di orientamento con una ruota da 42 mm per 4° di gioco. Esistono motori N20 con riduttore metallico per questo motivo.

Monta i sensori laterali leggermente in avanti e inclinati. Puntarli dritti verso l’esterno significa vederli una parete solo quando è perfettamente accanto, così il robot impara a conoscerla in ritardo. Un piccolo angolo in avanti dà al ciclo di controllo un’anticipazione.

Dai ai sensori un’alimentazione stabile. Un VL53L0X restituisce numeri sbagliati dall’aspetto plausibile su una linea che si affossa invece di fallire in modo ovvio: è il tipo peggiore di guasto, perché la mappa si riempie di muri che non ci sono.

Che aspetto ha un buon risultato

Due di queste righe meritano attenzione.

Il rilevamento delle pareti non ha crediti parziali. Un muro registrato male corrompe la mappa, poi flood fill calcola un percorso convincente ma sbagliato attraverso un muro e la corsa veloce ci va dritta contro. Non esiste un degrado graduale, ed è per questo che la corsa di esplorazione procede lentamente.

Le righe sulla deriva sono il vero progetto. L’algoritmo non è la parte difficile— flood fill richiede circa quaranta righe e puoi provarlo interamente nel simulatore senza hardware. La parte difficile è che dopo dieci celle il robot non è più dove crede di essere, e un mouse che deriva 20 mm ogni dieci celle toccherà un muro dal lato opposto del labirinto. Tutto ciò che fa funzionare un vero micromouse— correzione durante l’inseguimento della parete, svolte fuse con il giroscopio, calibrazione degli encoder— esiste per combattere proprio quel numero.

Quando va storto

Quasi ogni voce di quella tabella è un guasto di movimento o sensore piuttosto che dell’algoritmo. Questa distribuzione è la cosa più utile da sapere prima di iniziare, perché dice dove investire i tuoi fine settimana.

Se vuoi le idee di mappatura e pianificazione senza hardware, il simulatore del risolutore di labirinto esegue nel browser la stessa strategia a due fasi e il percorso di apprendimento di pianificazione del percorso e mappatura la porta avanti verso A* e SLAM. Per un primo robot da labirinto molto più economico, il risolutore di labirinto di linee usa il nastro invece dei muri e non ha bisogno di nessun sensore di distanza.