Padplanning en kartering: van flood fill tot SLAM
Je kunt een route plannen door een bekend raster, opnieuw plannen als er nieuwe obstakels verschijnen, en uitleggen hoe een robot de kaart bouwt waarop hij een route plant.
Reactieve navigatie krijgt een robot door een kamer zonder dat hij ooit weet waar hij is. Dat houdt snel op: aan een puur reactieve robot kun je geen ga naar de keuken zeggen, en hij loopt vol vertrouwen eindeloos rond in een kamer die de vorm van een hoefijzer heeft. Planning is het antwoord, en dat vraagt om iets wat reactieve regeling nooit heeft — een kaart.
Dit leertraject begint waar de kaart gratis is. In een doolhof laat flood fill de afstanden vanaf het doel naar buiten stromen en loopt de robot simpelweg bergafwaarts, en hij plant opnieuw op het moment dat hij een muur ontdekt die hij als open had aangenomen. Daarna wordt de wereld rommeliger: A* plant over een occupancy grid waar cellen kosten hebben, obstakels moeten worden opgeblazen en de heuristiek bepaalt of je planner snel is of alleen maar correct.
De laatste knop is de eerlijke. Elke planner hierboven veronderstelt dat je een kaart hebt, en een echte robot moet er zelf een bouwen terwijl hij rijdt op wielen die tegen hem liegen. SLAM is wat er gebeurt wanneer kartering en lokalisatie niet gescheiden kunnen zijn, en lusafsluiting is wat voorkomt dat de kaart doorbuigt naarmate de odometrie afdrijft. Een IMU verdient zijn plek hier om dezelfde reden: hij meet rotatie rechtstreeks, en dat kunnen wielen die slippen simpelweg niet.
Voordat je begint
Je moet je thuis voelen in tweedimensionale arrays en elementair algoritmisch denken — wachtrijen, en het idee van cellen in een bepaalde volgorde bezoeken. Het leertraject motorregeling is de moeite waard om eerst te doen, want elke planner hier gaat ervan uit dat de robot een opgedragen beweging kan uitvoeren en ruwweg kan melden hoe ver hij is gekomen.
Wat je aan het eind kunt
- Een raster vullen met afstanden vanaf een doel en de gradiënt naar beneden volgen.
- A* draaien met een heuristiek die je kunt aantonen nooit te overschatten, en uitleggen waarom die eigenschap het resultaat het kortst maakt.
- Afstandsmetingen via ray casting omzetten in een occupancy grid, waarbij vrije en bezette cellen apart worden bijgewerkt.
- Uitleggen waarom odometrie alleen over een lange rit geen bruikbare kaart kan opleveren, en wat SLAM toevoegt.
Waar mensen vastlopen
Een heuristiek die overschat. A* garandeert alleen het kortste pad wanneer de heuristiek nooit een afstand claimt die groter is dan de werkelijke resterende kosten. Euclidische afstand op een 4-verbonden raster gebruiken, of een heuristiek opschalen om de zoektocht sneller te maken, geeft in stilte paden die niet het kortst zijn.
Plannen voor een puntrobot. Het pad wordt door het raster berekend, maar de robot heeft breedte. Een route die een hoek raakt is meetkundig geldig en fysiek een botsing. Blaas obstakels vóór het plannen op met de straal van de robot en het probleem verdwijnt.
Onbekend als vrij behandelen. Een cel die niets heeft waargenomen is niet leeg — ze is ongemeten. Plan er doorheen als vrije ruimte en de robot rijdt zelfverzekerd in alles wat nooit gezien is. Onbekend is een derde toestand, en die moet een derde toestand blijven.
Diagonale stappen die één kosten. Op een 8-verbonden raster beslaat een diagonale stap √2 cellen, niet één. Die voor één berekenen levert paden op die de voorkeur geven aan trappen en afstanden die simpelweg fout zijn.
Aannemen dat de robot staat waar de odometrie zegt. Elke planner hier werkt op een pose. Wielodometrie drijft onbegrensd af, dus een perfect plan wordt uitgevoerd vanaf een positie die steeds fictiever wordt. Dat gat is de hele motivatie voor de laatste knop van dit leertraject.
Wat je nodig hebt
| Wat | Waarom dit leertraject het nodig heeft | Opmerkingen |
|---|---|---|
| Gemak met 2D-arrays en wachtrijen | Elk algoritme hier is een lus over een raster | Geen gevorderde wiskunde; een wachtrij en een geneste lus zijn de hele gereedschapskist |
| Een robot die opgedragen bewegingen uitvoert | Een plan is waardeloos als de robot het niet kan rijden | Het leertraject motorregeling brengt je tot hier |
| Een gyrosensor of IMU | Wielen kunnen geen rotatie meten die ze voorbijgeslipt hebben | Een MPU-6050; de karteringsknopen hangen af van de koers |
| Een afstandssensor, bij voorkeur een scanner | Cellen worden alleen bekend doordat ze gemeten worden | Een sonar die door een servo heen en weer zwaait volstaat voor een grove kaart |
| Een plek om een raster te visualiseren | Een planner debuggen door naar een robot te kijken is vrijwel onmogelijk | Druk ASCII af op de seriële poort, of gebruik de labs uit dit leertraject |
De twee labs draaien volledig in de browser, dus je kunt de knopen over flood fill en dekking afronden zonder enige hardware.
Waarom dit leertraject in deze volgorde loopt
Het doolhof komt eerst omdat de kaart gratis is. In een micromuizendoolhof is de wereld per constructie een raster — cellen hebben een bekende afmeting, muren liggen op celgrenzen en de positie van de robot is altijd een celindex. Dat haalt in één klap elk waarnemingsprobleem weg en laat alleen de planning over, en dat is het waar je hier bent om te leren. Flood fill in een bekend raster is de zuiverst mogelijke introductie in “bereken een afstandsveld en loop dan bergafwaarts”.
A* komt als tweede omdat het de gemakken van het doolhof één voor één wegneemt. Cellen hebben nu kosten in plaats van alleen muren. Het raster is groter, dus het hele uitbreiden is verspilling en wordt een heuristiek de moeite waard. De robot heeft breedte, dus obstakels moeten worden opgeblazen. En cellen kunnen onbekend zijn, en dat is een werkelijk nieuw idee dat het doolhof nooit nodig had.
Occupancy grids komen als derde omdat de kaart daar niet meer aan je wordt gegeven. Ray casting maakt van één afstandsmeting in één keer bewijs over veel cellen — alles langs de straal is waarschijnlijker vrij, het eindpunt is waarschijnlijker bezet — en die twee apart bijwerken is de hele techniek.
De IMU staat hier bewust. Hij komt aan op precies de knop waar de koersfout zichzelf in de kaart gaat schrijven, omdat een gyrosensor rotatie rechtstreeks meet en wielen die slippen dat simpelweg niet kunnen.
SLAM komt als laatste omdat het de erkenning is dat de vorige knopen iets onwaars ondernamen. Elke planner hierboven werkt op een pose, en elke pose hierboven kwam uit odometrie die onbegrensd afdrijft. SLAM is wat er gebeurt wanneer je ophoudt te doen alsof kartering en lokalisatie apart opgelost kunnen worden.
Dekking sluit het leertraject af, omdat het het probleem is dat het duidelijkst een kaart nodig heeft en het duidelijkst niet reactief kan worden opgelost. “Ben ik overal geweest?” is een vraag die alleen geheugen kan beantwoorden.
Controlepunten: hoe je weet dat een etappe is geland
| Etappe | De controle | Hoe een succes eruitziet |
|---|---|---|
| Flood fill | Druk het afstandsveld van een klein doolhof af | Het doel is 0, de waarden nemen naar buiten toe en de muren veroorzaken de omwegen die je verwacht |
| Herplanning | Toon een muur die de robot als open had aangenomen | Het veld werkt bij en de volgende zet van de robot verandert — zonder opnieuw te verkennen |
| Juistheid van A* | Draai hem op een raster waarvan je het antwoord met de hand kent | Elke keer dezelfde lengte als het met de hand berekende kortste pad |
| Toelaatbaarheid | Schaal je heuristiek bewust op met 2× | De zoektocht wordt sneller en het pad wordt langer — nu heb je de afweging gezien |
| Diagonale kosten | Plan over open ruimte op een 8-verbonden raster | Het pad is een rechte diagonaal, geen trap; diagonalen kosten √2 |
| Obstakelopblazing | Plan voorbij een hoek met opblazing uit, daarna aan | Uit: het pad raakt de hoek; aan: het houdt de hoek vrij op een straal van de robot |
| Occupancy grid | Zwaai een sensor over een deuropening en render het raster | Vrije ruimte verschijnt langs de stralen, bezette cellen aan de uiteinden, onbekend achter muren |
| Omgaan met onbekend | Vraag je planner om door onbekend gebied te plannen | Hij weigert, of hij kiest er bewust voor — allebei prima, gokken niet |
| Drift | Rijd een gesloten lus en vergelijk het begin en het einde van de kaart | De kaart sluit niet — dat gat is precies wat lusafsluiting moet herstellen |
| Dekking | Draai een geplande dekking en een willekeurige wandeling even lang | De geplande dekking dekt veel meer af, en je kunt beide percentages noemen |
Waar dit leertraject ophoudt
Dit leertraject plant in een statische, tweedimensionale wereld met bekende afmetingen. Elk van die woorden is een beperking die je moet benoemen.
Statisch. Niets hier verwerkt een persoon die over de geplande route loopt. Dynamische obstakels hebben een lokale planner nodig die onder de globale draait, en die veel sneller herplannen kan dan A* over een heel raster.
Tweedimensionaal. Een raster van vrije en bezette cellen is een plattegrond. Het kan een tafel niet weergeven waar je onderdoor maar niet doorheen kunt rijden, en daarom gebruiken serieuze robots 3D-weergaven of gelaagde costmaps.
Rastergebaseerd. Bemonsteringsplanners zoals RRT en RRT* verwerken hoogdimensionale ruimten — bijvoorbeeld de gewrichtsruimte van een robotarm — waar een raster hopeloos is. Ze ruilen de garantie op het kortste pad in voor de mogelijkheid om überhaupt te werken.
Het leertraject behandelt ook niet deeltjesfilters of Monte-Carlo-lokalisatie, waarmee een robot zichzelf vindt in een kaart die hem is gegeven in plaats van een die hij bouwt. Dat is het eenvoudigere en een stuk veelvoorkomender probleem, en het is de moeite waard dat het bestaat te weten voordat je naar volledige SLAM grijpt.
Leerroute
De route
Volg de knooppunten op volgorde – elk ontgrendelt het volgende zodra je het hebt afgerond. Je voortgang wordt op dit apparaat opgeslagen.
0 / 9 klaar
Veelgestelde vragen
Veelgestelde vragen
Wat is het verschil tussen flood fill en A* bij padplanning voor robots?
Flood fill berekent de afstand van het doel naar elke cel in het raster, zodat de robot daarna vanaf elke plek bergafwaarts kan lopen. A* zoekt vanaf één start naar één doel en breidt alleen de cellen uit die een heuristiek als veelbelovend aanmerkt. Flood fill is de juiste keuze in een micromuizendoolhof, omdat de robot voortdurend nieuwe muren ontdekt en om de paar cellen vanaf een nieuwe positie opnieuw moet plannen — dat elke cel zijn afstand al berekend heeft maakt dat gratis. A* is de juiste keuze op een groot raster waar je één keer vanaf een bekend startpunt plant en het hele raster uitbreiden zinloos zou zijn.
Waarom schraapt mijn A*-pad de hoeken van obstakels?
Omdat je voor een punt hebt gepland en de robot breedte heeft. Het pad is meetkundig geldig door het raster en fysiek een botsing, omdat de planner nooit wist dat de robot meer dan één cel inneemt. De standaardoplossing is elk obstakel vóór het plannen opblazen met de straal van de robot — de bezette cellen naar buiten laten groeien — zodat elk pad dat de planner vindt automatisch vrij is voor de echte robot. Dat is veel eenvoudiger en betrouwbaarder dan tijdens het zoeken proberen de vrije ruimte te controleren.
Wat maakt een A*-heuristiek toelaatbaar, en waarom is dat belangrijk?
Een toelaatbare heuristiek overschat nooit de werkelijke resterende kosten naar het doel. Die ene eigenschap is wat garandeert dat A* het kortste pad teruggeeft — overschat ergens en de zoektocht kan zich vastleggen op een route die hij had moeten verwerpen. De gebruikelijke manieren om dat te breken zijn euclidische afstand gebruiken op een 4-verbonden raster, waar de werkelijke kosten Manhattan zijn en altijd minstens zo groot, en bewust de heuristiek opschalen om de zoektocht sneller te maken. De tweede is een echte techniek, maar ze ruilt de garantie op het kortste pad in, en je moet weten dat je die inruilt.
Heb ik SLAM nodig voor een hobbyrobot?
Alleen wanneer de robot moet weten waar hij is tijdens een lange rit door een ruimte waarvoor hij geen kaart heeft gekregen. Kun je zelf een kaart aanleveren, dan is alleen lokalisatie een stuk eenvoudiger. Is de ruimte klein genoeg dat de odometriedrift hanteerbaar blijft — een doolhof, één kamer, een paar minuten rijden — dan heb je het ook niet nodig. SLAM verdient zijn complexiteit wanneer beide voorwaarden tegelijk vervallen, en dat is een echte drempel en geen badge: er zijn genoeg werkelijk capabele robots die het nooit nodig hebben.
Waarom buigt mijn occupancy-gridkaart door terwijl de robot rijdt?
Omdat de odometriedrift in de kaart wordt weggeschreven. Elke scan wordt geplaatst op de pose die de robot meende te hebben, dus een koersschatting die langzaam is gedraaid zet een rechte gang als een kromme lijn in de kaart. Er is niets mis met de kartering — hij legt getrouw een pose vast die fictie is. Dit is precies wat lusafsluiting herstelt: herkennen dat de robot terug is op een plek waar hij al was, en het hele traject corrigeren zodat de twee waarnemingen overeenkomen.
Waarom mogen onbekende cellen niet als vrije ruimte worden behandeld?
Omdat een cel die niets heeft waargenomen ongemeten is, niet leeg, en dat verschil bepaalt of de robot in dingen rijdt die hij nooit heeft gezien. Behandel onbekend als vrij en de planner leidt je zonder problemen door een gebied dat geen enkele sensor ooit heeft afgedekt — en dat is meestal precies waar de meubels staan, omdat afgeschermde ruimte en bezette ruimte sterk samenhangen. Houd onbekend als een aparte derde toestand naast vrij en bezet, en beslis bewust of een gegeven planner er doorheen mag plannen.