Occupancy grid mapping

Occupancy grid mapping is een Engelstalige term die verwijst naar een verzameling van algoritmen binnen het domein van de probabilistische robotica. Zij kunnen gebruikt worden door een mobiele robot om consistente omgevingskaarten te genereren op basis van mogelijk onzekere en door ruis beïnvloede sensordata, op voorwaarde dat de pose van de robot perfect gekend is. Een kaart (map) wordt hierbij gezien als een veld van willekeurige variabelen die in een raster worden geordend. Elke variabele is binair en geeft weer of de overeenkomstige locatie al dan niet bezet (occupied) is. De occupancy grid mapping-algoritmen zorgen voor een goede a-posteriori-schatting betreffende de waarschijnlijkheid van de waarden van deze variabelen.

In de praktijk worden dergelijke algoritmen voornamelijk gebruikt voor de creatie van duidelijke kaarten voor navigatie, nadat er eerdere SLAM-technieken werden gebruikt.^[1]

Geschiedenis[bewerken | brontekst bewerken]

In 1984 werd door Thorpe en Matthies een systeem ontworpen dat een routeplanner bevatte die de vloerruimte definieerde als een raster, opgebouwd uit een verzameling even grote cellen. Elke cel kreeg een bepaalde waarde mee, die de geschiktheid van de locatie om deel uit te maken van een bepaald pad weergaf. Het programma hield hierbij rekening met onzekerheden betreffende de locatie en zelfs het bestaan van obstakels en muren, en kan zo als een voorloper van occupancy grid mapping worden beschouwd.^[2] In zijn huidige vorm werd occupancy grid mapping voor het eerst gedefinieerd in 1988 door Hans Moravec en Alberto Elfes (CMU). In de loop der jaren verbeterden de algoritmen steeds meer en meer en vandaag de dag is occupancy grid mapping de dominante werkwijze in probabilistische robotica om omgevingen te modelleren.^[3]

Algoritmen[bewerken | brontekst bewerken]

Basiswerking[bewerken | brontekst bewerken]

Het uiteindelijke doel van een occupancy grid mapping-algoritme bestaat erin om a-posteriori-kennis te verzamelen betreffende omgevingskaarten, op basis van de volgende data:

$P(m|z_{1:t},x_{1:t})$

Hierbij is m de kaart, z_1:t de verzameling van alle sensormetingen tot op een bepaald tijdstip t en x_1:t de opeenvolging van poses die de robot heeft doorlopen en samen het tot tijdstip t afgelegde pad bepalen. Odometrische data speelt geen enkele rol, daar het pad reeds perfect gekend is en de informatie betreffende de poses als zijnde correct wordt beschouwd. De kaarten waarmee er wordt gewerkt bestaan uit fijne rasters waarbij elke cel overeenkomt met één specifieke locatie. Meestal zijn deze tweedimensionaal, maar (weliswaar rekenkundig intensieve) uitbreidingen naar een driedimensionaal systeem zijn mogelijk.

Opsplitsing in deelproblemen[bewerken | brontekst bewerken]

Het groot aantal individuele cellen waarmee er bij deze kaarten gewerkt wordt, kan erg problematisch zijn. Een kaart bestaande uit 2000 cellen kan 2²⁰⁰⁰ mogelijke vormen aannemen. Het zou enorm veel rekenkracht vragen om voor elke mogelijke kaart a-posteriori-kansen te berekenen. Omwille van deze reden wordt het probleem om een goede schatting te maken over de vorm van de kaart opgesplitst in een aantal deelproblemen:

$P(m_{i}|z_{1:t},x_{1:t})$

waarbij m_i één rastercel voorstelt. Elk deelprobleem is binair met een bepaalde vaste toestand, waardoor er gemakkelijk een binaire Bayesiaanse filter op kan worden toegepast. De waarden van de a-posteriori-kansen van gehele kaarten worden benaderd aan de hand van het product van de deelproblemen:

$P(m|z_{1:t},x_{1:t})=\prod _{i}P(m_{i}|z_{1:t},x_{1:t})$

Hoewel deze manier van werken zeer handig is, is zij niet geheel zonder problemen. Onderlinge verbanden tussen de probabiliteiten van de verschillende cellen kunnen in dit model niet worden weergegeven. Hierdoor kunnen er zich in een aantal specifieke situaties gemakkelijk conflicten voordoen tussen twee opeenvolgende sensormetingen.

Sinds kort bestaan er algoritmen die niet in verschillende deelproblemen opgesplitst dienen te worden en rekenkundig toch niet al te intensief zijn.^[4]

Logit[bewerken | brontekst bewerken]

Om te vermijden dat computergerelateerde afrondingsfouten desastreuze gevolgen hebben bij de vermenigvuldiging van kansen die dicht bij 0 en 1 liggen, wordt er vaak gewerkt met de logitfunctie, die dankzij haar logaritmisch karakter optellingen mogelijk maakt. De omrekening gebeurt als volgt:

$l_{t,i}=log{\frac {P(m_{i}|z_{1:t},x_{1:t})}{1-P(m_{i}|z_{1:t},x_{1:t})}}$

We kunnen uit l_t,i gemakkelijk onze kans terug berekenen, indien gewenst:

$P(m_{i}|z_{1:t},x_{1:t})=1-{\frac {1}{1+exp\{l_{t,i}\}}}$

Invers measurementmodel[bewerken | brontekst bewerken]

Occupancy grid algoritmen werken op basis van een aantal deelkansberekeningen van de vorm

$P(m_{i}|z,x)$

Dit wordt een invers measurementmodel genoemd. We spreken van een invers model daar er gebruikgemaakt wordt van gevolgen (metingen) om probabilistische uitspraken te doen over de oorzaken (de omgeving weergegeven als een kaart). Door gebruik te maken van Bayesiaanse technieken kan men dit invers measurementmodel opbouwen op basis van een standaard (forward) measurementmodel. Het invers measurementmodel voor de gehele map is:

$P(m|x,z)={\frac {P(z|x,m)*P(m|x)}{P(z|x)}}=n*P(z|x,m)*P(m)$

Men gaat er hierbij van uit dat P(m|x) = P(m), aangezien de huidige pose van de robot geen invloed heeft op de vormgeving van de kaart. Past men deze redenering toe op de verschillende deelproblemen, wordt het inverse model voor de i-de cel in het raster weergegeven door:

$P(m_{i}|z,x)=n*\sum _{m:m(i)=m_{i}}m_{i}P(z|x,m)*P(m)$

Een dergelijke sommatie over alle mogelijke mappen m waarvoor de celwaarde van cel i gelijk is aan m_i is gezien de totale omvang ervan quasi onmogelijk. Men zal dan ook proberen om een functie te zoeken die de uitkomst van deze som benadert. Er worden hiervoor een aantal waarden gesampeld uit het forward measurement model, waarna er op deze samples een intelligent supervised learning algorithm wordt toegepast (logistische regressie, neurale netwerken,…).

Meerdere sensortypes[bewerken | brontekst bewerken]

In de vorige paragrafen werd er steeds verondersteld dat de sensordata z slechts verzameld werd door één type sensor. Vele robotsystemen werken echter met meerdere types, van sensoren op basis van stereo vision tot laser-range finders. Er zijn verschillende manieren om hiermee om te gaan:

Men kent de data van een specifiek type sensor een verhoudingsgewijze belangrijkheid toe en combineert de data van alle sensoren, rekening houdend met deze verhoudingen. Een nadeel van deze werkwijze is echter dat deze gemakkelijk tot conflicten kan leiden, bijvoorbeeld wanneer een specifiek type obstakel (glazen raam) enkel door bepaalde sensoren gezien kan worden.
Men stelt aparte kaarten op voor elk type sensor en combineert de kaarten aan de hand van de wet van De Morgan:

$P(m_{i})=1-\prod _{k}(1-P(m_{i}^{k}))$

met m^k zijnde de kaart die werd opgesteld op basis van sensortype k.

Men stelt aparte kaarten op voor elk type sensor en neemt het maximum van alle kaarten, wat tot de meest pessimistische schatting leidt. Zodra één kaart aangeeft dat een bepaalde cell occupied is, zal de uiteindelijke kaart dit ook aangeven.

$P(m_{i})=max_{k}P(m_{i}^{k})$

met m^k zijnde de kaart die werd opgesteld op basis van sensortype k.

Bronnen, noten en/of referenties

↑ Thrun, S., Burgard, W. and Fox, D. (2006), Probabilistic Robotics. MIT Press, Cambridge, Mass. ISBN 978-0-262-20162-9.
↑ Moravec, Hans (1988). Sensor Fusion in Certainty Grids for Mobile Robots. AI Magazine 9 (2).
↑ Adam Milstein (2008). Occupancy Grid Maps for Localization and Mapping, Motion Planning, Xing-Jian Jing (Ed.), ISBN 978-953-7619-01-5, InTech, Available from: http://www.intechopen.com/books/motion_planning/occupancy_grid_maps_for_localization_and_mapping
↑ Thrun, S.,, Learning Occupancy Grids With Forward Sensor Models. Carnegie Mellon University, Pittsburgh.

[1] Thrun, S., Burgard, W. and Fox, D. (2006), Probabilistic Robotics. MIT Press, Cambridge, Mass. ISBN 978-0-262-20162-9.

[2] Moravec, Hans (1988). Sensor Fusion in Certainty Grids for Mobile Robots. AI Magazine 9 (2).

[3] Adam Milstein (2008). Occupancy Grid Maps for Localization and Mapping, Motion Planning, Xing-Jian Jing (Ed.), ISBN 978-953-7619-01-5, InTech, Available from: http://www.intechopen.com/books/motion_planning/occupancy_grid_maps_for_localization_and_mapping

[4] Thrun, S.,, Learning Occupancy Grids With Forward Sensor Models. Carnegie Mellon University, Pittsburgh.

[1]

[2]

[3]

[4]