Lidar per robot: dalla scansione alla mappa

Introduzione

Un sensore di distanza ti dice quanto è lontano un singolo oggetto, lungo una sola direzione. Una mappa ti dice la forma di una stanza. Tutto ciò che rende interessante la navigazione sta nel divario tra le due, ed è di questo che si occupa questa pagina.

Entrambi gli estremi sono già trattati: da un lato la misura di un singolo punto, dall’altro SLAM e A* su una griglia di occupazione. Ma entrambi danno per scontato che la griglia esista già. Niente spiega da dove provenga, e la risposta — proiettare una scansione nelle celle con il lancio di raggi — è insieme semplice e piena di trappole.

Un lidar 2D è un sensore ToF su un piatto rotante

È l’informazione più utile da conoscere, perché significa che hai già capito come funziona la metà relativa alla misura.

Dentro un lidar 2D hobbistico c’è un modulo ottico di misura del tempo di volo, esattamente come quello di una scheda di sviluppo della serie VL53, montato di lato e fatto ruotare. Un encoder angolare indica dove stava guardando a ogni misura. L’alimentazione e i dati attraversano il confine rotante tramite un anello rotante o un accoppiamento ottico/induttivo.

Quindi una «scansione» non è una fotografia. È un elenco di coppie (angle, range) raccolte una alla volta nell’arco di una rivoluzione. Ogni limitazione seguente discende da questa frase.

Questo spiega anche perché i sensori ultrasonori non vengono fatti ruotare per trasformarli in lidar. Un fascio ultrasonoro è largo decine di gradi, quindi ruotarlo non offre quasi nulla: spremeresti sulla stanza un fascio già largo. È un fascio ottico stretto a rendere significativa la risoluzione angolare. Far ruotare un singolo sensore ToF con un servomotore, come nel tutorial sulla scansione ultrasonora, equivale davvero a un lidar lento e a bassa risoluzione.

Il budget di campionamento è fisso, quindi risoluzione e attualità sono in conflitto

Questa è la parte che surprises le persone ed è importante comprenderla prima di acquistare qualsiasi cosa.

Il modulo di misura ha un solo dato sulla frequenza di campionamento: quanti campioni al secondo può acquisire. Su un RPLIDAR A1 sono circa 8000 campioni al secondo, e il valore non cambia se modifichi la velocità di rotazione. La velocità di rotazione la scegli tu, in genere da 1 a 10 Hz.

I punti per rivoluzione sono quindi semplicemente il budget diviso per la velocità di rotazione:

points per revolution = samples per second ÷ spin rate
angular step          = 360° ÷ points per revolution

Non puoi avere contemporaneamente scansioni aggiornate e un’elevata risoluzione angolare. Ruotare a 10 Hz dimezza la latenza e quasi dimezza la risoluzione angolare. Questo singolo compromesso influenza il comportamento del robot più di quanto faccia il valore di portata in primo piano, ed è la prima impostazione da regolare deliberatamente invece di lasciare il valore predefinito dal driver.

Robot in movimento veloce in un corridoio aperto: ruota in fretta, perché ti servono dati aggiornati e i muri sono grandi. Robot lento che mappa una stanza affollata: ruota lentamente, perché ti serve il dettaglio e puoi permetterti la latenza.

I fasci divergono, quindi gli ostacoli distanti cadono tra essi

Il passo angolare è un angolo, non una distanza. Due fasci adiacenti si separano mentre si propagano:

gap between beams ≈ range × angular step (in radians)

A 0.45° corrisponde un intervallo di 7.9 mm a un metro e di 31 mm a quattro metri. Niente campiona lo spazio intermedio.

Considera una gamba di sedia di 20 mm. Ruotando a 10 Hz, l’intervallo tra i fasci supera 20 mm a circa 2.5 m: oltre quella distanza la gamba può trovarsi interamente fra due fasci e non restituire nulla. A 5.5 Hz puoi arrivare a circa 4.6 m prima che accada la stessa cosa.

Questo spiega un comportamento che altrimenti sembra un sensore guasto: gli ostacoli sottili compaiono quando il robot si avvicina e saltano nella mappa a uno o due metri di distanza. Il lidar non stava fallendo. La gamba non era mai stata campionata.

Due conseguenze da tenere presenti nella progettazione:

• Non fidarti di una singola scansione per gli ostacoli sottili. Accumula più scansioni in una griglia, come vedrai tra poco: è ciò che rileva davvero le gambe dei tavoli, perché ogni scansione campiona angoli leggermente diversi.
• Le gambe di sedie e tavoli sono il guasto classico dei robot domestici, perché sono sottili, si trovano esattamente all’altezza del lidar e il robot le scopre solo tardi.

Una scansione non è un’istantanea

I punti di una rivoluzione non sono stati misurati nello stesso istante. A 5.5 Hz la scansione dura 182 ms e il robot non aspetta cortesemente.

• Procedendo a 0.5 m/s, il robot percorre 91 mm durante una rivoluzione.
• Ruotando a 1 rad/s, la scansione viene sfumata su 10.4°.

Trattare quell’elenco di punti come un’unica istantanea rigida scattata in una sola posa deforma il mondo. Le pareti dritte risultano curve o doppie e la corrispondenza tra le scansioni combatte correzioni che in realtà sono dovute al tuo stesso movimento.

Ecco perché sensor_msgs/LaserScan trasporta scan_time e time_increment insieme alle distanze: permettono a chi consuma i dati di determinare quando è stato emesso ogni fascio. Correggerlo — trasformando ogni punto con la posa che il robot aveva alla marca temporale di quel fascio — si chiama compensazione del movimento (deskewing), e le buone implementazioni iniziali di SLAM lo eseguono al posto tuo.

In pratica: se le mappe sono pulite quando il robot è fermo e sfumate quando si muove, sospetta prima il deskewing e le marche temporali, non il sensore. E rallenta durante la mappatura. Metà velocità significa metà distorsione, senza alcun costo.

Ottieni soltanto una sezione orizzontale

Un lidar 2D misura un piano. Qualunque cosa si trovi sopra o sotto quel piano non esiste.

I tre casi classici:

• Soffitroni. Un piano di tavolo a 700 mm è invisibile a un lidar a 150 mm. Il robot ci passa sotto con sicurezza e si incastra.
• Ostacoli bassi. Una soglia, un cavo, un calzino. Tutti sotto il piano.
• Dislivelli. Una scala che scende è spazio vuoto in ogni direzione che il lidar può vedere. Appare come un pavimento perfettamente libero.

Nessuna elaborazione della scansione risolve il problema, perché l’informazione non è mai stata acquisita. I robot reali mantengono un paraurti, sensori di bordo e spesso anche un sensore rivolto verso il basso o in avanti oltre al lidar, non perché il lidar sia inadeguato, ma perché un piano resta un piano. Quando leggi che un robot aspiratore «ha il lidar e mantiene comunque i paraurti», ecco perché.

Dalla scansione alla griglia: lancio di raggi

Ora la metà relativa alla mappatura. Una griglia di occupazione divide il mondo in celle quadrate e memorizza, per ciascuna, quanto sei convinto che sia occupata.

L’intuizione che la rende possibile è questa: una lettura di distanza fornisce informazioni su ogni cella lungo il raggio, non solo su quella all’estremità. Se un fascio ha percorso 3 m prima di colpire qualcosa, allora tutto lo spazio attraversato doveva essere libero, altrimenti si sarebbe fermato prima.

Ogni fascio produce quindi tre verdetti:

1. Celle attraversate dal raggio → evidenza di spazio libero. Percorri la linea dal sensore all’impatto e sposta ogni cella verso «vuota».
2. Cella in cui termina la misura → evidenza di occupazione. Spostala verso «piena».
3. Celle oltre l’impatto → nessuna informazione. Il fascio si è fermato. Non hai appreso nulla di ciò che si trova oltre quella parete, quindi devi lasciare quelle celle invariate.

Percorrere la linea è semplicemente rasterizzazione di linee: l’algoritmo di Bresenham, lo stesso che disegna una linea sullo schermo.

Una lettura alla distanza massima richiede una gestione separata. Molti driver riportano il massimo, oppure l’infinito, quando non è tornato nulla. Questo non significa «c’è una parete a 12 m», significa «non è stato trovato nulla». Marca il raggio come libero e non marcare nessuna cella finale come occupata.

Log-odds: perché sommi invece di moltiplicare

Potresti memorizzare una probabilità per cella e moltiplicare insieme gli aggiornamenti di Bayes. In pratica tutti memorizzano invece i log-odds:

l = ln( p / (1 - p) )          p = 1 / (1 + e^(-l) )

Le ragioni sono due. La moltiplicazione di molte probabilità piccole va in underflow; la somma di logaritmi no. Inoltre rende l’aggiornamento una sola addizione, abbastanza economica da eseguire per ogni cella di ogni fascio di ogni scansione.

Con p = 0.5 (nessuna idea) corrispondente a l = 0, scegli un valore per un impatto e uno per un mancato rilevamento — per esempio p_occ = 0.7 (l = +0.847) e p_free = 0.4 (l = −0.405) — e l’aggiornamento è:

l_cell += l_occ     # this beam hit this cell
l_cell -= 0.405     # this beam passed through this cell

Una cella che parte da l = 0 dopo tre impatti:

Le evidenze si accumulano e il disaccordo le riporta indietro. Questo è l’intero algoritmo.

Limita i totali. È più importante di quanto sembri. Venti impatti consecutivi senza limitazione portano una cella a l = 16.9, cioè p = 0.999999. Se poi qualcuno sposta la sedia, annullare quella certezza richiede 42 osservazioni di spazio libero. La sedia lascia un’ombra permanente e il pianificatore continua a evitare la nulla.

Limitare l a valori come ±3.5 risolve il problema: una convinzione forte resta forte, ma poche scansioni contraddittorie possono ribaltarla. Se le tue mappe accumulano immagini fantasma di oggetti rimossi, quasi sempre è questa la causa.

Sconosciuto è un terzo stato, non un sinonimo di libero

Questo è l’errore che produce pianificazioni sicure ma pericolose.

Una griglia appena inizializzata è interamente sconosciuta. Se il pianificatore considera sconosciuta una cella come percorribile, la attraverserà tranquillamente anche nelle zone mai osservate che, proprio perché inesplorate, sono quelle in cui si nascondono le sorprese. Se invece la considera bloccata, il robot si rifiuterà di muoversi all’avvio, perché tutto è sconosciuto.

Entrambe le scelte sono sbagliate; mantieni distinti i tre stati e decidere in modo consapevole:

• Occupata — non pianificare attraverso di essa.
• Libera — pianifica attraverso di essa.
• Sconosciuta — pianifica attraverso di essa soltanto a un costo, oppure soltanto durante un’esplorazione deliberata.

L’esplorazione di frontiera, il meccanismo con cui un robot sceglie dove guardare dopo, si basa interamente sul confine fra libero e sconosciuto. Se unisci i due stati, hai buttato via questa capacità.

Scelta della dimensione delle celle

La risposta abituale è 5 cm per i robot interni, e conviene non scendere più in dettaglio solo perché è possibile.

Una cella più piccola dell’intervallo tra fasci alla distanza tipica inventa una precisione che non hai: a 4 m i fasci distano 31 mm, quindi celle da 1 cm lasciano buchi permanenti fra raggi che non si riempiono mai. D’altra parte, celle molto più grandi del margine di ingombro del robot fanno sembrare impossibili le porte, perché una singola cella occupata può inghiottire lo spazio libero.

Regola pratica: usa celle appena più piccole del passaggio più stretto attra cui devi passare, ma non più piccole dell’intervallo tra fasci nel luogo in cui operi. Poi inflaziona gli ostacoli del raggio del robot durante la pianificazione, invece di ridurre le celle per compensare.

Quando qualcosa va storto

L’ultima riga è la precisazione onesta per tutta la pagina. Il lidar batte il sonar in risoluzione, frequenza e portata, poi di fronte a una porta di vetro perde completamente il bersaglio: il suono si riflette sul vetro, la luce lo attraversa. È l’argomento più chiaro per non scegliere un solo sensore e considerare risolto il problema.