Occupancy grid mapping is de Engelstalige aanduiding voor bepaalde algoritmen binnen de probabilistische robotica. Zij kunnen door een mobiele robot worden gebruikt om kaarten te maken op basis van mogelijk onzekere en door ruis beïnvloede meetwaarden, op voorwaarde dat de stand van de robot volledig is bepaald. Een kaart wordt hierbij gezien als een veld van willekeurige variabelen die in een raster worden geordend. De variabelen zijn binair, dus alleen maar bits en geven weer of de overeenkomstige locatie al dan niet bezet is. De occupancy grid mapping-algoritmen zorgen voor een goede a posteriori-schatting voor de waarschijnlijkheid van de waarden van deze variabelen.
In de praktijk worden dergelijke algoritmen vooral gebruikt om kaarten mee te maken, nadat er eerder SLAM-technieken werden gebruikt.
Geschiedenis In 1984 werd door Thorpe en Matthies een systeem met een routeplanner ontworpen, die de vloerruimte definieerde als een raster, opgebouwd uit 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. Het kan zo als een voorloper van occupancy grid mapping worden beschouwd. In de huidige vorm is occupancy grid mapping voor het eerst in 1988 gedefinieerd door Hans Moravec en Alberto Elfes van de Carnegie Mellon University. De algoritmen verbeterden in de loop van de jaren steeds meer en tegenwoordig is occupancy grid mapping de toonaangevende werkwijze in probabilistische robotica om omgevingen te modelleren.Adam Milstein (2008). Occupancy Grid Maps for Localization and Mapping, Motion Planning, Xing-Jian Jing (Ed.), , InTech, Available from: http://www.intechopen.com/books/motion_planning/occupancy_grid_maps_for_localization_and_mapping
Algoritmen Basiswerking Het doel van een occupancy grid mapping-algoritme bestaat erin om a posteriori-kennis te verzamelen betreffende omgevingskaarten, op basis van de volgende gegevens:
Hierbij is de kaart, de verzameling van alle sensormetingen tot op een bepaald tijdstip en de opeenvolgende standen die de robot heeft doorlopen en samen het tot tijdstip afgelegde pad bepalen. Hodometrische gegevens spelen geen enkele rol, omdat het pad volledig is bepaald en de informatie betreffende de stand van de robot als correct wordt beschouwd. De kaarten waarmee wordt gewerkt bestaan uit fijne rasters waarbij elke cel overeenkomt met één specifieke locatie. Meestal zijn deze tweedimensionaal, maar uitbreidingen naar een driedimensionale kaart zijn mogelijk. Dat kost rekentijd.
Opsplitsing in deelproblemen Het groot aantal individuele cellen waarmee er bij deze kaarten wordt gewerkt kan een probleem geven. Een kaart die uit 2000 cellen bestaat kan 22000 mogelijke vormen aannemen. Het zou 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:
waarbij éé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 hele kaarten worden benaderd aan de hand van het product van de deelproblemen:
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.
Er bestaan algoritmen waarbij het niet meer nodig is het maken van de kaarten in delen op te splitsen en die rekenkundig toch niet al te intensief zijn.
Logit Om te vermijden dat afrondingsfouten bij de vermenigvuldiging van kansen die dicht bij 0 en 1 liggen doorwerken, wordt er vaak gewerkt met de logitfunctie, waarmee kan worden opgeteld. De omrekening gebeurt als volgt:
We kunnen uit de kans terug berekenen, indien gewenst:
Invers measurementmodel Occupancy grid algoritmen werken op basis van een aantal deelkansberekeningen van de vorm
Dit wordt een invers measurementmodel genoemd. Het wordt een invers model genoemd, omdat er van de metingen wordt gebruikgemaakt om er probabilistische uitspraken over te doen de oorzaken hoe de omgeving in een kaart moet worden weergegeven. Door gebruik te maken van bayesiaanse technieken kan men dit invers measurementmodel opbouwen op basis van een standaard, van een forward measurementmodel. Het invers measurementmodel voor de hele kaart is:
Men gaat er hierbij van uit dat , aangezien de huidige stand van de robot op de vormgeving van de kaart geen invloed heeft. Past men deze redenering toe op de verschillende deelproblemen, wordt het inverse model voor de -de cel in het raster weergegeven door:
Een dergelijke sommatie over alle mogelijke kaarten waarvoor de celwaarde van cel gelijk is aan 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. Bijvoorbeeld met logistische regressie of neurale netwerken.
Meer sensortypes In de vorige paragrafen werd er steeds verondersteld dat de sensordata maar door één type sensor werd verzameld. Veel robotsystemen werken met meer types, van sensoren op basis van stereo vision tot laser-range finders. Er zijn verschillende manieren om hiermee om te gaan: Men kent de gegevens van een specifiek type sensor een verhoudingsgewijze belangrijkheid toe en combineert de gegevens van alle sensoren, rekening houdend met deze verhoudingen. Een nadeel van deze werkwijze is 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:
met de kaart die werd opgesteld op basis van sensortype .
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.
met de kaart die werd opgesteld op basis van sensortype .
Categorie:Algoritme Categorie:Robotica