Pianificazione dei percorsi e mappatura: dal flood fill a SLAM
Puoi pianificare un percorso su una griglia nota, ripianificare quando compaiono nuovi ostacoli e spiegare come un robot costruisce la mappa su cui sta pianificando.
La navigazione reattiva permette a un robot di muoversi in una stanza senza sapere mai dove si trova. Finisce presto: un robot puramente reattivo non può ricevere l’istruzione vai in cucina e si metterà volentieri a girare per sempre in una stanza a ferro di cavallo. La pianificazione è la risposta e richiede qualcosa che il controllo reattivo non ha mai: una mappa.
Questo percorso inizia quando la mappa è già pronta. In un labirinto, flood fill propaga le distanze dall’obiettivo e il robot scende semplicemente la pendenza, ripianificando nell’istante in cui scopre un muro che aveva assunto aperto. Poi il mondo diventa più complicato: A* pianifica su una griglia di occupazione in cui le celle hanno costi, gli ostacoli devono essere inflati e l’euristica decide se il pianificatore è veloce o soltanto corretto.
L’ultimo nodo è quello onesto. Ogni pianificatore precedente presuppone che tu abbia una mappa, mentre un robot reale deve costruirla mentre si muove su ruote che gli mentono. SLAM è ciò che accade quando mappatura e localizzazione rifiutano di essere separate, e la chiusura del loop è ciò che impedisce alla mappa di curvarsi mentre l’odometria deriva. Un IMU si guadagna il suo posto qui per lo stesso motivo: misura la rotazione direttamente, cosa che le ruote che slittano semplicemente non possono fare.
Prima di iniziare
Devi sentirti a tuo agio con array bidimensionali e ragionamento algoritmico di base — code e l’idea di visitare le celle in un certo ordine. Vale la pena completare prima il percorso di controllo dei motori, perché ogni pianificatore qui presuppone che il robot possa eseguire un movimento comandato e riportare in modo approssimativo quanto sia andato lontano.
Cosa saprai fare
- Riempire una griglia con le distanze da un obiettivo e seguire il gradiente fino a esso.
- Eseguire A* con un’euristica che sai non sovrastimare e spiegare perché questa proprietà rende più breve il risultato.
- Trasformare letture di distanza in una griglia di occupazione tramite ray casting, aggiornando separatamente le celle libere e quelle occupate.
- Spiegare perché l’odometria da sola non può produrre una mappa utilizzabile durante un lungo percorso e che cosa aggiunge SLAM.
Dove le persone si bloccano
Un’euristica che sovrastima. A* garantisce il percorso più breve solo quando l’euristica non dichiara mai una distanza superiore al costo residuo reale. Usare la distanza euclidea su una griglia a 4 connessioni, o aumentare un’euristica per accelerare la ricerca, restituisce silenziosamente percorsi che non sono i più brevi.
Pianificare per un robot puntiforme. Il percorso viene calcolato attraverso la griglia, ma il robot ha una larghezza. Una rotta che sfiora un angolo è geometricamente valida ma fisicamente una collisione. Gonfia gli ostacoli del raggio del robot prima di pianificare e il problema scompare.
Trattare lo sconosciuto come libero. Una cella che nessuno ha osservato non è vuota: è non misurata. Pianifica attraverso di essa come se fosse spazio libero e il robot entrerà con sicurezza in qualunque cosa non sia mai stata vista. Lo sconosciuto è un terzo stato e deve restare tale.
Movimenti diagonali con costo uno. Su una griglia a 8 connessioni un passo diagonale copre √2 celle, non una. Addebitargli un costo di uno produce percorsi che preferiscono le scale e distanze semplicemente sbagliate.
Supporre che il robot sia dove dice l’odometria. Ogni pianificatore qui opera su una posa. L’odometria delle ruote deriva senza limite, quindi un piano perfetto viene eseguito da una posizione sempre più fittizia. Questo divario è l’intera motivazione dell’ultimo nodo di questo percorso.
Di cosa hai bisogno
| Cosa | Perché questo percorso ne ha bisogno | Note |
|---|---|---|
| Familiarità con array 2D e code | Ogni algoritmo qui è un ciclo su una griglia | Nessuna matematica avanzata; una coda e un ciclo annidato sono tutto il necessario |
| Un robot che esegue i movimenti comandati | Un piano vale nulla se il robot non riesce a percorrerlo | Il percorso di controllo dei motori ti porta qui |
| Un giroscopio o IMU | Le ruote non possono misurare una rotazione attraversata con uno slittamento | MPU-6050; i nodi di mappatura dipendono dall’orientamento |
| Un sensore di distanza, idealmente con scansione | Le celle diventano note solo quando vengono misurate | Basta un sonar ruotato da un servomotore per costruire una griglia rudimentale |
| Un posto dove visualizzare una griglia | Fare il debug di un pianificatore guardando un robot è quasi impossibile | Stampa caratteri ASCII sulla porta seriale, oppure usa i laboratori di questo percorso |
I due laboratori funzionano interamente nel browser, quindi puoi completare i nodi flood fill e copertura senza alcun hardware.
Perché il percorso segue quest’ordine
Il labirinto viene prima perché la mappa è già pronta. In un labirinto di micromouse il mondo è una griglia per costruzione: le celle hanno una dimensione nota, i muri sono sui bordi delle celle e la posizione del robot è sempre un indice di cella. Questo elimina tutto il problema della percezione e lascia solo la pianificazione, che è ciò che sei venuto a imparare. Flood fill in una griglia nota è l’introduzione più pulita possibile all’idea di «calcolare un campo di distanza, poi scendere la pendenza».
A* viene secondo perché elimina una alla volta le comodità del labirinto. Ora le celle hanno costi e non soltanto muri. La griglia è più grande, quindi espandere tutta la griglia è uno spreco e un’euristica diventa utile. Il robot ha una larghezza, quindi gli ostacoli vanno inflati. E le celle possono essere sconosciute, un’idea davvero nuova che il labirinto non richiedeva mai.
Le griglie di occupazione vengono terze perché sono il punto in cui la mappa smette di essere fornita. Il ray casting trasforma una lettura di distanza in prove su molte celle contemporaneamente: tutto ciò che si trova lungo il raggio è più probabilmente libero e il punto finale è più probabilmente occupato; aggiornare separatamente questi due elementi è tutta la tecnica.
L’IMU si trova qui deliberatamente. Arriva esattamente nel nodo in cui l’errore di orientamento inizia a scriversi nella mappa, perché un giroscopio misura la rotazione direttamente e le ruote che slittano semplicemente non possono farlo.
SLAM viene per ultimo perché è l’ammissione che i nodi precedenti stavano assumendo qualcosa di falso. Ogni pianificatore precedente opera su una posa e ogni posa precedente proveniva da un’odometria che deriva senza limite. SLAM è ciò che accade quando smetti di fingere che mappatura e localizzazione possano essere risolte separatamente.
La copertura chiude il percorso perché è il problema che in modo più ovvio richiede una mappa e in modo più ovvio non può essere risolto in modo reattivo. «Sono passato da tutte le parti?» è una domanda a cui solo la memoria può rispondere.
Punti di verifica: come sapere che una fase è stata compresa
| Fase | La verifica | Cosa significa superarla |
|---|---|---|
| Flood fill | Stampa il campo di distanza per un piccolo labirinto | L’obiettivo è 0, i valori aumentano verso l’esterno e i muri creano le deviazioni previste |
| Ripianificazione | Rivela un muro che il robot aveva assunto aperto | Il campo si aggiorna e la prossima mossa del robot cambia, senza riesplorare |
| Correttezza di A* | Eseguilo su una griglia di cui conosci la risposta a mano | Ha sempre la stessa lunghezza del percorso più breve calcolato a mano |
| Ammissibilità | Aumenta deliberatamente l’euristica di 2× | La ricerca diventa più veloce e il percorso più lungo: hai visto il compromesso |
| Costo diagonale | Pianifica attraverso spazio aperto su una griglia a 8 connessioni | Il percorso è una diagonale dritta, non una scala; i diagonali costano √2 |
| Inflazione degli ostacoli | Pianifica oltre un angolo con l’inflazione disattivata, poi attivata | Disattivata, il percorso sfiora l’angolo; attivata, lo evita del raggio del robot |
| Griglia di occupazione | Fai scansionare un sensore su una porta e disegna la griglia | Lo spazio libero appare lungo i raggi, le celle occupate alle estremità, quelle sconosciute dietro i muri |
| Gestione dello sconosciuto | Chiedi al pianificatore di attraversare spazio non mappato | Rifiuta, oppure lo fa deliberatamente: entrambe vanno bene, indovinare no |
| Deriva | Percorri un anello chiuso e confronta l’inizio e la fine della mappa | La mappa non si chiude: quel divario è esattamente ciò che la chiusura del loop esiste per correggere |
| Copertura | Esegui una spazzata pianificata e una camminata casuale per la stessa durata | La spazzata pianificata copre molto di più e puoi indicare entrambe le percentuali |
Dove si ferma questo percorso
Questo percorso pianifica in un mondo statico, bidimensionale e di dimensione nota. Ognuna di quelle parole è una limitazione che vale la pena nominare.
Statico. Nulla qui gestisce una persona che attraversa il piano. Gli ostacoli dinamici richiedono un pianificatore locale che opera sotto quello globale, con ripianificazioni molto più rapide di quanto A* possa fare sull’intera griglia.
Bidimensionale. Una griglia di celle libere e occupate è una pianta del pavimento. Non può rappresentare un tavolo sotto cui si può passare ma attraverso cui no, ed è per questo che i robot professionali usano rappresentazioni 3D o costmap a livelli.
Basato su griglia. I pianificatori a campionamento come RRT e RRT* gestiscono spazi ad alta dimensionalità, per esempio lo spazio delle giunti di un braccio robotico, in cui una griglia è inutile. Scambiano la garanzia del percorso più breve con la possibilità di funzionare.
Il percorso non copre neppure i filtri particellari o la localizzazione di Monte Carlo, che sono il modo in cui un robot si ritrova in una mappa che gli è stata fornita anziché in una che sta costruendo. È il problema più semplice e molto più comune, e vale la pena sapere che esiste prima di ricorrere a SLAM completo.
Percorso di apprendimento
Il percorso
Segui i nodi in ordine: ognuno sblocca il successivo una volta completato. I tuoi progressi vengono salvati su questo dispositivo.
0 / 9 completati
Domande comuni
Domande frequenti
Qual è la differenza tra flood fill e A* nella pianificazione dei percorsi robotici?
Flood fill calcola la distanza dall'obiettivo a ogni cella della griglia, così il robot può poi scendere da qualsiasi punto in cui si trovi. A* cerca da un unico punto di partenza verso un unico obiettivo ed espande solo le celle che un'euristica suggerisce promettenti. Flood fill è la scelta giusta in un labirinto di micromouse, perché il robot scopre continuamente nuovi muri e deve ripianificare da una nuova posizione ogni poche celle: avere già calcolata la distanza di ogni cella rende l'operazione gratuita. A* è la scelta giusta su una griglia grande in cui pianifichi una volta da un punto noto e espandere tutta la mappa sarebbe uno spreco.
Perché il mio percorso A* taglia gli angoli degli ostacoli?
Perché hai pianificato per un punto mentre il robot ha una larghezza. Il percorso è geometricamente valido attraverso la griglia ma fisicamente una collisione, perché il pianificatore non sapeva mai che il robot occupa più di una cella. La soluzione standard è inflare ogni ostacolo del raggio del robot prima di pianificare, cioè far crescere verso l'esterno le celle occupate, così ogni percorso trovato dal pianificatore è automaticamente libero per il robot reale. È molto più semplice e affidabile che controllare la distanza libera durante la ricerca.
Cosa rende ammissibile un'euristica A* e perché è importante?
Un'euristica ammissibile non sovrastima mai il costo residuo reale fino all'obiettivo. Questa singola proprietà garantisce che A* restituisca il percorso più breve: una sovrastima anche solo in un punto può far scegliere alla ricerca una rotta che avrebbe dovuto rifiutare. I modi comuni di violarla sono usare la distanza euclidea su una griglia a 4 connessioni, dove il costo reale è quello di Manhattan ed è sempre almeno tanto grande, e aumentare deliberatamente l'euristica per accelerare la ricerca. Il secondo è una tecnica reale, ma rinuncia alla garanzia del percorso più breve e devi esserne consapevole.
Ho bisogno di SLAM per un robot hobbistico?
Solo quando il robot deve sapere dove si trova durante un lungo percorso in uno spazio di cui non gli hai fornito una mappa. Se puoi fornire una mappa, la sola localizzazione è molto più semplice. Se lo spazio è abbastanza piccolo da rendere tollerabile la deriva dell'odometria — un labirinto, una singola stanza, pochi minuti di guida — non ti serve neppure. SLAM si guadagna la sua complessità quando falliscono contemporaneamente entrambe le condizioni, ed è una soglia reale, non un distintivo: moltissimi robot davvero capaci non ne hanno bisogno.
Perché la mia mappa a griglia di occupazione si curva mentre il robot si muove?
Perché la deriva dell'odometria viene scritta nella mappa. Ogni scansione viene posizionata nella posa che il robot credeva di avere, quindi una stima dell'orientamento che è ruotata lentamente inserisce nella mappa un corridoio rettilineo come una curva. Nella mappatura non c'è nulla di sbagliato: sta registrando fedelmente una posa fittizia. È esattamente ciò che la chiusura del loop corregge: riconoscere che il robot è tornato in un punto già visitato e correggere l'intera traiettoria perché le due osservazioni concordino.
Perché le celle sconosciute non dovrebbero essere trattate come spazio libero?
Perché una cella che nessuno ha osservato non è vuota: è non misurata, e la differenza decide se il robot entra in cose che non ha mai visto. Se tratti lo sconosciuto come libero, il pianificatore è felice di far passare il percorso attraverso una regione che nessun sensore ha mai coperto, che di solito è proprio dove si trovano i mobili, perché spazio occluso e spazio occupato sono fortemente correlati. Tieni lo sconosciuto come terzo stato distinto accanto a libero e occupato e decidi deliberatamente se un determinato pianificatore può attraversarlo.