LiDAR voor robots: van scan naar bezettingsraster

Inleiding

Een afstandssensor vertelt je hoe ver één ding weg is, langs één lijn. Een kaart vertelt je de vorm van een kamer. Alles interessante in de navigatie zit in het gat tussen die twee, en dat gat is waar deze pagina over gaat.

De twee uiteinden worden hier al behandeld: enkelvoudige afstandsmeting aan de ene kant, en SLAM plus A* op een bezettingsraster aan de andere. Maar die gaan ervan uit dat het raster al bestaat. Niets zegt waar het vandaan komt, en het antwoord—een scan met ray casting in cellen gieten—is zowel eenvoudig als vol valkuilen.

Een 2D-lidar is een looptijdsensor op een draaitafel

Dit is het nuttigste om te weten, want het betekent dat je de meetkant al begrijpt.

In een hobby-2D-lidar zit één optische looptijdmeetsmodule, precies het soort dat op een VL53-breakout zit, opzij gericht en ronddraaiend. Een hoekencoder meldt waar hij bij elke meting naar keek. Voeding en data crossen de draaiende grens via een slipring of een optische/inductieve koppeling.

Een “scan” is dus geen foto. Het is een lijst van (angle, range)-paren, één voor één verzameld over één omwenteling. Elke beperking hieronder volgt uit die zin.

Dat verklaart ook waarom ultrasone sensoren niet in lidars worden gedraaid. Een ultrasone bundel is tientallen graden breed, dus hem ronddraaien levert je bijna niets op—je zou een al brede bundel over de ruimte uitsmeren. Een smalle optische bundel is wat hoekresolutie überhaupt betekenisvol maakt. Eén looptijdsensor op een servo zwaaien, zoals in de tutorial over scannen met een servo, is echt een langzame lidar met lage resolutie.

Het samplingbudget ligt vast, dus resolutie en versheid zijn een handgreep

Dit is het stuk dat mensen verrast, en het is de moeite waard het te begrijpen voordat je iets koopt.

De meetsmodule heeft één doorvoergetal: hoeveel metingen per seconde hij aankan. Bij een RPLIDAR A1 is dat ongeveer 8000 samples per seconde, en het verandert niet als je de draaisnelheid aanpast. De draaisnelheid kies je zelf, meestal 1–10 Hz.

De punten die je per omwenteling krijgt zijn dus simpelweg het budget gedeeld door de draaisnelheid:

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

Verse scans en een fijne hoekresolutie kan je niet tegelijk hebben. Draai je op 10 Hz, dan halveer je de latency en bijna ook de hoekresolutie. Die ene afweging bepaalt meer aan het gedrag van een robot dan het opgegeven bereik in de specificaties, en het is het eerste dat je bewust moet instellen in plaats van op de standaardwaarde van de driver te laten staan.

Snel rijdende robot in een open gang: draai snel, je hebt de versheid nodig en de muren zijn groot. Langzame robot die een drukke kamer in kaart brengt: draai langzaam, je hebt het detail nodig en kunt de latency veroorloven.

Bundels lopen uiteen, dus verre obstakels vallen ertussen

Een hoekstap is een hoek, geen afstand. Twee naburige bundels gaan steeds verder uiteen:

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

Bij 0,45° is dat 7,9 mm spleet op één meter, en 31 mm op vier meter. Niets bemonstert de ruimte daartussen.

Neem een stoelpoot van 20 mm. Draai je op 10 Hz, dan wordt de bundelspleet 20 mm op ongeveer 2,5 m—daar voorbij kan de poot volledig tussen twee bundels vallen en niets teruggeven. Bij 5,5 Hz haal je ongeveer 4,6 m voordat hetzelfde gebeurt.

Dat verklaart een gedrag dat er anders uitziet als een kapotte sensor: dunne obstakels verschijnen terwijl de robot nadert en springen op een meter of twee uit de kaart. De LiDAR faalde niet. De poot is nooit bemonsterd.

Twee gevolgen waar je je ontwerp op af moet stemmen:

• Vertrouw geen enkele scan voor dunne obstakels. Meerdere scans in een raster ophopen, zoals hieronder, is wat tafelpoten daadwerkelijk vindt—elke scan neemt net iets andere hoeken mee.
• Stoel- en tafelpoten zijn de klassieke storing van een huishoudrobot, omdat ze dun zijn, op precies LiDAR-hoogte zitten en de robot er pas laat van te weten.

Een scan is geen momentopname

De punten in één omwenteling zijn niet op hetzelfde moment gemeten. Bij 5,5 Hz duurt de veegbeweging 182 ms, en de robot wacht niet beleefd af.

• Bij 0,5 m/s legt de robot 91 mm af tijdens één omwenteling.
• Bij 1 rad/s is de scan over 10,4° uitgesmeerd.

Behandel je die puntenlijst als één starre momentopname bij één pose, dan vervorm je de wereld. Rechte muren komen er gebogen of dubbel uit, en scanmatching voert correcties uit die in werkelijkheid je eigen beweging zijn.

Daarom voert sensor_msgs/LaserScan naast de afstanden ook scan_time en time_increment mee: zo kan een verwerker bepalen wanneer elke bundel werd gemeten. Daarvoor corrigeren—elk punt transformeren met de pose die de robot op het tijdstempel van die bundel had—heet deskewing of bewegingscompensatie, en goede SLAM-frontends doen het voor je.

Wat dit praktisch betekent: zijn je kaarten schoon terwijl je stilstaat en uitgesmeerd tijdens het rijden, dan verdenk je deskewing en tijdstempels lang vóór je de sensor verdenkt. En rem af tijdens het karteren. Halve snelheid is de helft vervorming, gratis.

Eén horizontale doorsnede is alles wat je krijgt

Een 2D-lidar meet een vlak. Wat erboven of eronder ligt, bestaat niet.

De klassieke drie:

• Overstekken. Een tafelblad op 700 mm is onzichtbaar voor een LiDAR op 150 mm. De robot rijdt er zelfverzekerd onder en blijft vastzitten.
• Lage obstakels. Een deurdrempel, een kabel, een sok. Allemaal onder het vlak.
• Afgronden. Een trap omlaag is lege ruimte in elke richting die de LiDAR kan zien. Het leest als prachtig heldere vloer.

Geen hoeveelheid scanverwerking repareert dat, want de informatie is nooit vastgelegd. Echte robots houden een bumper, klifsensoren en vaak ook een naar beneden of naar voren gerichte ranger naast de LiDAR—niet omdat de LiDAR slecht is, maar omdat een vlak een vlak is. Als je leest dat een stofzuigerrobot “LiDAR heeft en toch bumpers”, dan is dit de reden.

Van scan naar raster: ray casting

Nu de karteringskant. Een bezettingsraster deelt de wereld in vierkante cellen en bewaart voor elke cel hoe sterk je gelooft dat ze bezet is.

Het inzicht dat het laat werken: een afstandsmeting vertelt je iets over elke cel langs de straal, niet alleen over de cel aan het einde. Als een bundel 3 m aflegde voor hij op iets stuitte, dan moet al die overgestoken ruimte leeg geweest zijn—anders was hij eerder gestopt.

Elke bundel levert dus drie oordelen op:

1. Cellen die de straal passeerde → bewijs van vrij. Loop de lijn van sensor naar treffer en duw elke cel richting leeg.
2. De cel waarin de meting belandde → bewijs van bezet. Duw hem richting vol.
3. Cellen voorbij de treffer → niets. De bundel stopte. Je hebt niets geleerd over wat achter die muur zit, dus je moet die cellen met rust laten.

Die lijn aflopen is simpelweg lijnrastering—het algoritme van Bresenham, precies het algoritme waarmee je een lijn op een scherm tekent.

Een meting op maximaal bereik vraagt om eigen afhandeling. Veel drivers melden het maximum, of oneindig, als er niets terugkwam. Dat betekent niet “er staat een muur op 12 m”, maar “er is niets gevonden”. Markeer de straal vrij en markeer geen bezette cel aan het eind.

Log-odds: waarom je optelt in plaats van vermenigvuldigt

Je zou per cel een kans kunnen opslaan en Bayes-updates vermenigvuldigen. In de praktijk bewaart iedereen log-odds:

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

Twee redenen. Veel kleine kansen vermenigvuldigen lopen onder de vloer; logaritmen optellen niet. En het maakt de update een enkele optelling, goedkoop genoeg om voor elke cel van elke bundel van elke scan te doen.

Neem voor p = 0.5 (geen idee) de waarde l = 0, kies één waarde voor een treffer en één voor een miss—neem p_occ = 0.7 (l = +0.847) en p_free = 0.4 (l = −0.405)—dan is de update:

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

Een cel die op l = 0 begint na drie treffers:

Bewijs stapelt op en tegenspraak trekt het terug. Dat is het hele algoritme.

Klem de totalen. Dit is belangrijker dan het lijkt. Twintig opeenvolgende treffers zonder klem zetten een cel op l = 16.9, oftewel p = 0.999999. Nu verzet iemand de stoel. Die zekerheid ongedaan maken kost 42 waarnemingen van vrij. De stoel laat een blijvende spook achter en je planner blijft om niets heen sturen.

l klemmen op iets als ±3,5 lost het op: sterk geloof blijft sterk, maar een handvol tegensprekende scans kan het omgooien. Als je kaarten zich ophopen met geesten van weggehaalde objecten, is dit vrijwel altijd de reden.

Onbekend is een derde toestand, geen synoniem voor vrij

Dit is de fout die zelfverzekerde, gevaarlijke plannen oplevert.

Een vers geïnitialiseerd raster is volledig onbekend. Behandelt je planner onbekend als begaanbaar, dan routeert hij dwars door de delen van de wereld die je nooit hebt bekeken—en juist omdat ze ononderzocht zijn, wonen daar de verrassingen. Behandelt hij onbekend als geblokkeerd, dan weigert de robot te bewegen, want alles is onbekend.

Beide zijn fout; houd de drie toestanden gescheiden en beslis bewust:

• Bezet — plan er niet doorheen.
• Vrij — plan er doorheen.
• Onbekend — plan er alleen doorheen tegen een kostenprijs, of alleen bij bewuste verkenning.

Frontierverkenning, de manier waarop een robot bepaalt waar hij als volgende kijkt, is volledig gebouwd op de grens tussen vrij en onbekend. Klap die twee samen en je gooit het weg.

De keuze van de celgrootte

Het gebruikelijke antwoord is 5 cm voor robots binnen, en er is een reden om niet fijner te gaan alleen omdat het kan.

Een cel die kleiner is dan je bundelspreiding op normale afstand verzint nauwkeurigheid die je niet hebt—op 4 m zitten de bundels 31 mm uit elkaar, dus 1 cm-cellen laten permanente gaten tussen stralen zien die nooit opvullen. Cellen die veel groter zijn dan de marge rond je robot maken deuren juist onpasseerbaar, omdat één bezette cel de opening kan opslokken.

Praktische regel: neem de celgrootte iets kleiner dan de smalste doorgang die je moet rijden, en niet kleiner dan je bundelspreiding waar je werkelijk werkt. Blaas dan obstakels op met de robotstraal op planniveau in plaats van de cellen te verkleinen om te compenseren.

Als het misgaat

Die laatste rij is de eerlijke kanttekening bij de hele pagina. LiDAR verslaat sonar op resolutie, tempo en bereik, en verliest daarna compleet op een glazen deur, waarop geluid reflecteert en licht niet. Het is het duidelijkste argument om niet één sensor te kiezen en het probleem voor opgelost te verklaren.