Simultaneous localization and mapping

Simultaneous localization and mapping (SLAM), ook bekend als concurrent mapping and localization (CML) is een techniek waarbij een robot of een ander autonoom voertuig een kaart van een onbekende omgeving opstelt (mapping) en zich vervolgens tegelijkertijd in dezelfde kaart probeert terug te vinden (localization).

Een kaart gegenereerd door de robot Hector op de 2010 German Open

Gedetailleerde uitleg

Een robot gebruikt een kaart hoofdzakelijk voor navigatie. Om een robot van punt A naar punt B te laten bewegen, waarbij men enkel de coördinaten van deze punten kent, is meestal een kaart van de omgeving nodig. SLAM is hierdoor een van de grootste problemen in de wereld van robotica. Het is een kip-en-eiprobleem, omdat men een kaart nodig heeft om zich ergens in te kunnen terugvinden, maar een juiste locatie van de robot is nodig om een juiste kaart op te kunnen bouwen.

Om dit probleem op te lossen moeten er twee fundamentele vragen gesteld worden: Hoe ziet de wereld eruit?. Om dit te beantwoorden moet men een set van informatie verzamelen die afkomstig is uit verschillende sensoren, deze koppelen en zo een representatie op te stellen van de omgeving. Dit kan moeilijker zijn dan het lijkt omdat men altijd te maken krijgt met ruis en eventuele fouten die de sensors opvangen.

De tweede fundamentele vraag is: Waar ben ik? Om hierachter te komen moet men kennis hebben van de omgeving om de huidige locatie juist te kunnen inschatten. Plaatsbepaling is ook weer moeilijk aangezien de juiste positie van de robot altijd afwijkt van waar hij denkt dat hij is, wat de opstelling van de kaart weer in vraag brengt.

SLAM wordt dus gezien als een probleem waarbij men een kaart construeert, zichzelf in deze kaart plaatst, en continu de kaart verbetert en eigen locatie beter bepaalt. Vaak wordt er gebruikgemaakt van landmerken, dus oriëntatiepunten in de omgeving waardoor de robot zijn locatie beter kan bepalen.

Animatie van het scannen

Sensing

Om de omgeving in kaart te kunnen brengen worden er verschillende sensoren op de robot aangebracht. Deze sensoren geven data door naar de robot die vervolgens een kaart opstelt. Er zijn twee types van sensoren: 1D, dus er is 1 straal die iets scant, of 2D, die een gebied scant. De meest gebruikte zijn 2D sensoren, zoals laser rangefinders of een LIDAR laser scanner. De figuur hiernaast toont een theoretisch voorbeeld van hoe een omgeving wordt 'gescand'. Er wordt telkens een meting gedaan en de waarde (afstand) die men terugkrijgt van de meting wordt op een kaart getekend. Door op deze manier in ruimtes rond te scannen kunnen we een kaart opstellen. Natuurlijk is dit een theoretische benadering. In de realiteit krijgt men altijd te maken met ruis, foute metingen of storingen.

Mapping

Mapping is de volgende stap in SLAM. Mapping is niets anders dan een kaart opstellen met de beschikbare data. Er zijn verschillende soorten kaarten, maar bij SLAM wordt meestal met geografische kaarten gewerkt, dat wil zeggen meestal een plattegrond van de omgeving. Bij 3D gebaseerde kaarten krijgen we te maken met diepte wat voor een perspectiefzicht zorgt.

Locating

Positionering is misschien wel het moeilijkste onderdeel van SLAM. Om de juiste positie te verkrijgen, moet men ten eerste over een referentiepunt beschikken. We kunnen uitgaan van het feit dat de x-, y- en z-coördinaten van de robot allemaal op nul staan, waardoor dit de startpositie wordt. Natuurlijk krijgt met zo een benadering, alles wat zich onder de robot bevindt een negatieve waarde, wat later aangepast moet worden voor de juiste data representatie. Het andere probleem is de echte positie van de robot. We kunnen berekenen hoe ver we zijn bewogen aan de hand van de snelheid waarmee we ons bewegen, en de hoek waarin we ons draaien. Theoretisch gezien zouden we dan altijd exact op hetzelfde punt zijn wat onze echte positie is. In praktijk is dit echter een groot probleem. We krijgen altijd te maken met bijvoorbeeld het glijden van de wielen, waardoor we stel maar 50 graden naar rechts draaien in plaats van de bedoelde 35 graden. Deze afwijking is moeilijk te voorspellen, en wordt groter en groter als we deze niet corrigeren. Het gevolg is dat we dan altijd een andere kaart zullen projecteren, en niet de eerste kaart en positie verbeteren.

Data-associatie

Stel de volgende situatie: Men komt in een kamer en ziet een stoel. Deze stoel wordt voor ons dan een oriëntatiepunt. We verlaten de kamer en na een tijd komen we terug. We zien weer een stoel en kunnen zeggen dat het dezelfde stoel is die we vroeger hadden gezien. Zo hebben we de oude stoel met de nieuwe 'geassocieerd'. Stel nu dat er twee exact dezelfde stoelen zijn in deze kamer. Wanneer we weggaan en terugkomen, weten we niet meer welke stoel degene is die we de eerste keer hadden gezien. De beste gok is om te zeggen dan de linkse stoel de eerste stoel die we aan de linkerkant hadden gezien en de rechtse stoel de eerste die we aan de rechtse kant gezien hebben. In praktijk kunnen er dus volgende problemen voorkomen:

• Je kunt een oriëntatiepunt niet gezien hebben;
• Je kunt een oriëntatiepunt merken maar nooit meer terugvinden;
• Je kunt verkeerd een oriëntatiepunt associëren met een eerder gezien oriëntatiepunt;

De twee stoelen in het voorbeeld zijn slechte oriëntatiepunten. Een goed oriëntatiepunt moet makkelijk herkenbaar zijn, dus bepaalde karakteristieken bezitten waardoor we deze gemakkelijk kunnen herkennen .

Problemen

De twee fundamentele vragen, Hoe ziet de wereld eruit? en Waar ben ik? lijken simpel maar het is niet vanzelfsprekend om deze te beantwoorden. Ten eerste, zoals al gezegd, moet er rekening gehouden met ruis of slechte(verkeerde) metingen. Ten tweede, de assumptie van waar de robot zich bevindt is altijd verschillend dan in de realiteit, wat een ‘vervormde’ kaart met zich meebrengt. Men moet over een juiste positionering beschikken om de juiste kaart te kunnen bouwen. Om de afwijkingen en fouten te verkleinen gebruikt men statistische technieken zoals Kalman filters, of scan matching. Vanuit de statistiek zijn er twee hoofdproblemen: online SLAM problem, en de Full SLAM problem. Waarom ze 'problemen' worden genoemd? Omdat er telkens een bepaalde actie moet worden ondernomen om tot een oplossing te komen. Er zijn verschillende soorten SLAM die deze 'problemen' oplossen, en naar een accurate kaartvoorstelling en positionering leiden. Het volgende probleem is de inschatting. SLAM houdt een continu en een discreet component. Dit wil zeggen, er is een continu probleem met inschatting van de objecten in de kaart, en de positie van de robot. Dit wordt continu gedaan. Deze objecten kunnen eventueel oriëntatiepunten zijn. Het discrete probleem heeft te maken met correspondentie: Wanneer SLAM een object herkent, moet men een verband kunnen leggen met andere, vroeger ontdekte objecten in de kaart, met de vraag: is het net gevonden object een nieuwe of heb ik deze al gezien?

Online SLAM problem

Bij de online SLAM problem zoekt men naar de positie op de kaart op 1 bepaald tijdstip. Stel de volgende formule:

Online SLAM

$p{\big (}x_{t},m|z_{1:t},u_{1:t})$

Hierbij is p de waarschijnlijkheid, $x_{t}$ de positie op tijdstip $t$, $m$ is de kaart van de omgeving, $z_{1:t}$ zijn de metingen van de sensoren, en ten slotte $u_{1:t}$ zijn de 'controls' dus hoe de robot bewogen heeft. De online SLAM kenmerkt zich met het feit dat we enkel de waarschijnlijkheid berekenen voor maar 1 tijdstip $t$, en in vele algoritmes telkens wanneer we het volgende tijdstip nemen, verwijderen we als het ware de gegevens van vorige tijdstippen. De figuur hiernaast toont dit principe. De nieuwe positie $x_{t+1}$ ontstaat door een beweging $u_{t+1}$, hieruit leidt een meting naar de omgeving $z_{t+1}$ die vervolgens naar een nieuwe kaartvoorstelling leidt.

Full SLAM problem

De Full SLAM problem zoekt naar het hele pad op de kaart die de robot heeft uitgevoerd, in plaats van enkel voor positie $x_{t}$. De formule voor Full SLAM verschilt niet veel van Online SLAM:

Full SLAM

$p{\big (}x_{1:t},m|z_{1:t},u_{1:t})$

Zoals men ziet hebben we te maken met een beweging van tijdstip 1 tot tijdstip $t$ (dus nu). De figuur hiernaast toont hoe men een kaart kan verkrijgen met behulp van Full SLAM. Zoals aangegeven, wordt er nu rekening gehouden met de vorige posities van de robot, dus worden ze niet 'verwijderd' als bij Online SLAM.

Soorten SLAM

Aangezien er verschillende stappen in SLAM zijn, is het mogelijk om elke stap op een andere manier, met een ander algoritme te oplossen. Hieronder een overzicht:

• EKF SLAM
  • SEIF (Sparse Extended Information Filter)
  • UKF (Unscended Kalman Filter)
• Particle Filter SLAM
  • FastSLAM
  • DP-SLAM
• Expectation-Maximization-Filter SLAM
• Graph gebaseerde technieken
  • GraphSLAM, TORO, HOG-Man, TreeMap

Externe links

• SLAM For Dummies (A Tutorial Approach to Simultaneous Localization and Mapping)
• Andrew Davison research page at Imperial College London about SLAM using vision
• Autonomous and Perceptive Systems research page at University of Groningen about visual SLAM
• openslam.org A collection of open source code and explanations of SLAM.
• Matlab Toolbox of Kalman Filtering applied to Simultaneous Localization and Mapping Vehicle moving in 1D, 2D and 3D
• SLAM Example using Processing.js of Feature-Based Navigation.

Bronnen, noten en/of referenties

• Durrant-Whyte, H., Bayley, T. (2006) Simultaneous Localization and Mapping(SLAM): Part I The Essential Algorithms http://www.acfr.usyd.edu.au/homepages/academic/tbailey/papers/slamtute1.pdf.

---