Drohne Relief-Darstellung

Im Rahmen des einwöchigen Autonome Systeme Labors wurde die nachfolgende Dokumentation in Zusammenarbeit mit meinem Kommilitonen Thorsten Z. angefertigt.

Inhalt

• Gruppenmitglieder
• Zusammenfassung / Abstract
• Keywords
• Arbeitsplan
• Einführung
• Aufgabenanalyse
• Relevante Komponenten des RoboView-Frameworks
• Mathematisches Modell für die Erfassungseigenschaften des Ultraschall-Sensors
• Idee
• Modell
• Bezeichnungen
• Ablauf
• Algorithmus in Pseudocode
• Modellierung der Datenstruktur - GridMap
• Idee
• Interface
• Implementierung der GridMap
• HashMap
• Hashing-Verfahren
• Mapping von gemessenen Punkt-Daten auf Zellen in der GridMap
• Wahrscheinlichkeitswert für eine Zelle setzen
• Ausdehnung der GridMap
• GridMap leeren
• Ausblick
• Abtastrate
• Grafische Implementierung
• Coverage Maps
• Referenzen
• Ressourcen

Gruppenmitglieder

• Thorsten Z.
• Maximilian S.

Zusammenfassung / Abstract

Die Arbeit beschreibt ein Modell für die Erfassungseigenschaften eines Ultraschall-Sensors. Ein Ultraschall-Sensor hat eine kegelförmige Abtastung. Wenn ein Objekt durch den Sensor erkannt wurde, bekommt man einen Distanzwert zurück gegeben, Informationen über die Lage des Objektes innerhalb des Kegels fehlen jedoch. Durch die mathematische Analyse des Abtastkegels, konnte ein Modell für den Sensor erstellt werden. In einem eigens dafür entwickelten Algorithmus wird der Ultraschall-Kegel mit Hilfe ausgesendeter Vektoren stückweise abgetastet und Wahrscheinlichkeitswerte über die abgetasteten Regionen berechnet. Dadurch wird eine Statistik über die Wahrscheinlichkeit des Ortes eines Objektes innerhalb des Kegels ermittelt. Weiter wird eine spezielle Datenstruktur, eine so genannte GridMap, vorgestellt, in die diese Wahrscheinlichkeitswerte abgelegt werden. Zuletzt wird die GridMap ausgelesen und die interpretierten Wahrscheinlichkeitswerte als Relief in OpenGL dargestellt.

Keywords

Ultraschall, Sensor, GridMap, OpenGL, Topologie, Raumtopologie

Arbeitsplan

Montag 25.02.2013

• Aufgabenanalyse (Milestone 0)
• Teilaufgaben festlegen und Arbeitsplan erstellen.
• Bereits existierende Ansätze ermitteln.
• Theoretische Einarbeitung in das Thema (Grid Maps).
• Ziel: Allgemeines Verständnis was wie zu tun ist und Projektspezifikation.

Dienstag 26.02.2013

• In Eclipse-Projektstruktur/-Projektfunktionen einarbeiten (Milestone 1)
• Bestimmung der für das Ziel relevant Projektkomponenten.
• Bestimmen an welcher Stelle Komponenten erweitert werden müssen.
• Bestimmen wie auf Sensordaten zugegriffen werden kann.
• Ziel: Allgemeines Verständnis der bereits vorhandenen Projekstruktur/-komponenten und Dokumentation der relevanten Komponenten.
• Entwicklung des Modelles für Erfassungseigenschaften des Ultraschall-Sensors (Milestone 2)
• Analyse der Sensordaten.
• Kegelproblematik lösen
• Bestimmen welche mathematischen Lösungswege möglich/sinnvoll sind.
• Modell mathematisch formulieren und Algorithmus erarbeiten

Mittwoch 27.02.2013

• Entwicklung des Modelles für Erfassungseigenschaften des Ultraschall-Sensors (Milestone 2)
• Implementierung des Modells mit einer Software-Architektur
• Implementierung der GridMap (Milestone 3)
• Interface
• Implementierung der kegelförmigen Ultraschallerfassung. (Milestone 4)
• Ziel: Fertiges Modell, welches in der Lage ist, per Ultraschallsensor eine Karte zu erstellen.

Donnerstag 28.02.2013

• Implementierung des Modells mit einer Software-Architektur
• Implementierung der kegelförmigen Ultraschallerfassung. (Milestone 4)
• Ziel: Fertiges Modell, welches in der Lage ist, per Ultraschallsensor eine Karte zu erstellen.

Freitag 29.02.2013

• Implementierung des Modells mit einer Software-Architektur
• Implementierung der kegelförmigen Ultraschallerfassung. (Milestone 4)
• Ziel: Fertiges Modell, welches in der Lage ist, per Ultraschallsensor eine Karte zu erstellen
• Dokumentation

Einführung

Ultraschall-Sensoren senden Schallwellen, die in ihrer Ausbreitung die Form eines Kegels bilden. Die gemessene Distanz enthält keine Informationen, wo innerhalb des Kegels ein Objekt lokalisiert ist. Für gewisse Anwendungen ist die Information über die Lage eines gefundenen Objektes jedoch gewünscht, zum Beispiel beim Kartografieren eines Geländes. Ein anderer Punkt betrifft die Kosten der Sensoren. Es könnte anstelle eines Ultraschall-Sensors auch ein Laser oder ein bildgebender Sensor eingesetzt werden, der die Lokalisierung deutlich vereinfacht. Durch den Einsatz eines günstigen Ultraschall-Sensors und die Entwicklung eines sinnvollen mathematischen Modells, wählt man die preisgünstigere Variante. Beide Aspekte sind beim vorliegenden Projekt der Flugdrohne von Bedeutung.

Aufgabenanalyse

Im Zuge der Aufgabenanalyse sowie der Einarbeitung in die Entwicklungsumgebung und die gesamte Projektstruktur, soll die Aufgabe komplett verstanden und mögliche Lösungsansätze bereits skizziert werden. Innerhalb der Projektstruktur sollen die potenziell zu bearbeitenden Stellen herausgefunden werden. (siehe Milestone 0 und 1). Es soll analysiert werden, welche Informationen der Ultraschallsensor liefert und eine Strategie entwickelt werden, um das Problem der kegelförmigen Abtastung des Sensors zu lösen. Die Idee ist hierbei, über ein Zeitintervall hinweg die Wahrscheinlichkeiten für die Belegungen (Occupation) der Zellen zu ermitteln. Die Erfassungseigenschaften sollen in einem mathematischen Modell beschrieben und ein Algortithmus daraus abgeleitet werden. (Milestone 2) Die erfassten Wahrscheinlichkeitsdaten sollen in einer Gridmap persistiert werden, die als Grundlage der grafischen Ausgabe dient (siehe Milestone 3). Dieses Ultraschall-Modell soll innerhalb des RoboView-Projektes implementiert werden (siehe Milestone 4). Die Karten muss in OpenGL aufgebaut und mit den Sensordaten befüllt werden (siehe Milestone 5). Das gesamte Projekt wird zunächst auf Basis der zur Verfügung gestellten Software-Emulation entworfen und ausgeführt. Eine mögliche spätere Hardware-Emulation ist möglich aber nicht nötig.

Relevante Komponenten des RoboView-Frameworks

Mathematisches Modell für die Erfassungseigenschaften des Ultraschall-Sensors

Um die kegelförmigen Erfassungseigenschaften des Ultraschall-Sensors korrekt abzubilden, ist ein mathematisches Modell nötig. Dadurch wird garantiert, dass der Algorithmus zur Erfassung von Objekten im Raum, funktioniert. Im Folgenden sollen die Überlegungen zum Modell, die korrekte mathematische Formulierung und eine Skizze zum entworfenen Algorithmus widergegeben werden.

Idee

Eine Drohne fliegt mit einer definierten Höhe über dem Boden. Der Ultraschall-Sensor sendet sein Signal in eine bestimmte Richtung, üblicherweise nach unten. Durch die vom Sensor zurück gegebene Distanz ist die Höhe des aktuell zu analysierenden Sensorkegels bekannt. Jeder Ultraschall-Sensor besitzt außerdem eine so genannte Beam-Width, die den Winkel zwischen der Kegel-Halbierenden und dem äußeren Rand (dem Mantel) des Kegels, beschreibt. Die Idee um herauszufinden, wo innerhalb des Kegels ein Objekt mit hoher Wahrscheinlichkeit zu finden ist, wird der gesamte Kegel stufenweise von der Spitze bis zur Bodenfläche abgetastet. Alle Vektoren die nicht in einer bestimmten Region nah der Grundfläche oder genau darauf liegen, korrespondieren mit Zellen die definitiv leer sind, in denen also keine Objekt gefunden werden können. Das liegt daran, dass die Distanz zum gefundenen Objekt länger ist, als er ausgesendete Vektor. Das ermöglicht es nicht nur besetzte Zellen in eine Datenstruktur einzutragen, sondern auch solche die definitiv unbesetzt sind. Solche Vektoren, die genau in der Region um die Grundfläche oder darauf liegen, liegen in einem Bereich der potentiell von einem Objekt besetzt wird. Um festzustellen, ob tatsächlich ein Objekt in einer Region liegt, müssen viele Messungen des Sensors ausgewertet werden und für alle Messungen eine Wahrscheinlichkeit berechnet werden, ob eine Region von einem Objekt besetzt ist. Diese Messungen werden in einer GridMap gespeichert (siehe nächster Abschnitt).

Modell

Grafik 0

Bezeichnungen

Ablauf

Um alle Zellen die in dem Kegel liegen, welcher von dem Sensor erfasst wird, zu bestimmen, wird zuersteinmal bestimmt welche Zellreihen überhaupt in dem Kegel liegen. Dazu wird zuerst die erste Zellreihe unterhalb des Sensors bestimmt, welche sich durch y-(y%r) errechnet. Dies erklärt sich dadurch, dass der Sensor ja theorethisch zwischen zwei Zellreihen liegen kann. Durch die Subtraktion von y%r wird also der Rest, welcher über der ersten Zellreihe unterhalb des Sensor steht, entfernt. Alle nachfolgenden Zellreihen sind nun immer ein vielfaches von r von der ersten Zellreihe entfernt, also y-(y%r)-r für die zweite Zellreihe unterhalb des Sensors, y-(y%r)-2r für die dritte Zellreihe unterhalb des Sensors, usw. Die letzte Zellreihe errechnet sich durch (y-y_t)-((y-y_t)%r). Dies erklärt sich dadurch, dass die letzte Zellreihe sich unterhalb oder auf der höhe befindet, welche mit d und y_t ein rechtwinkliges Dreieck bildet. y_t ist hierbei das Teilstück von y (siehe Grafik 1). Da nun alle Zellreihen bekannt sind kann dazu übergegangen werden die Zellen zu berechnen. Zellen können anhand von Punkten, welche in den Zellen liegen, leicht bestimmt werden (siehe Mapping von gemessenen Punkt-Daten auf Zellen in der GridMap). Wie an Grafik 1 zu sehen ist, werden vom Uhrsprungspunkt, also der Punkt im Raum an dem sich die Drohne befindet, Vektoren in Richtung der bekannten Zellreihen berechnet. Diese Vektoren bestimmen nun alle Punkte, die auf der jeweiligen Zellreihe und im Kegel liegen. Die einzelnen Vektoren werden wie folgt berechnet: Da V_RRot bekannt ist und alle Vektoren die innerhalb des Kegels liegen zu V_RRot den maximalen Winkel β haben (wäre der Winkel größer würde sich ja der Vektor ausserhalb des Beam-Winkelbereichs befinden), müssen logischerweise alle Vektoren die sich im Kegel befinden einen Winkel größer 0 und <= β zu V_RRot haben. Dieser Winkel wird als vielfaches von φ bezeichnet. Es wird nun schrittweise der Winkel der einzelnen Vektoren mit folgender Formel berechnet: P[] = U + λ * R_φ * V_RRot. Hierbei ist R_φ die Matrix mit der V_RRot rotiert wird, so dass der neue Vektor den entsprechenden Winkel zu V_RRot hat. λ ist die länge des Vektors, welche sich leicht errechnen lässt, da ja die Zellreihe und somit auch die Höhe bekannt ist. Grafik 1

Da der Winkel im dreidimensionalen Raum errechnet werden muss, tritt noch ein weiteres Problem auf, welches sich aber leicht beheben lässt. Grafik 2 zeigt einen Schnitt des Kegels. Bei der Berechnung des Winkels wird die Rotation um die x- und z-Achse durchlaufen. Hierbei kann es passieren, dass Rotationen entstehen wodurch der resultierende Vektor nicht mehr im Kegel liegen würde. Durch eine einfache Kreisberechnung kann bestimmt werden ob der entstehende Vektor im Kegel liegen würde. Der Radius des Kreises ist hierbei der Beam Winkel β und die x- und z-Rotationen erstrecken sich von -β bis +β, da von der Achse des Kegels aus in alle Richtungen rotiert werden muss. Durch die allgemeine Formel x² + y² = r² kann bestimmt werden ob ein Punkt mit Koordinaten x und y im Kreis liegt, wobei r der Radius des Kreises ist. die x- bzw. y-Koordinaten sind in diesem Fall die Winkel der Rotationen um die x- bzw. z-Achse. Der Radius ist gleich dem Beam Winkel β. Ein Vektor liegt also im Kegel wenn gilt: (x-Roatation)² + (z-Roatation)² <= β². Ohne diese Berechnung würde durch die Vektoren kein Kegel sondern eine Pyramide beschrieben werden.

Grafik 2

Schlussendlich kann es noch passieren, dass die berechneten Vektoren über die Grenzen des Kegels hinaus “schießen” (siehe Grafik 3). Dies stellt jedoch keine weiteren Probleme dar, da ja bekannt ist, dass die Länge eines jeden Vektors nicht länger als d sein darf, da der Abstand vom Sensor zum Boden des Kegels immer gleich ist. Sollte also bei der berechnung eines Vektors die länge des Vektors länger sein als d, so wird die länge des Vektors einfach auf d gesetzt. Dadurch dass nun bekannt ist, dass der der Vektor übers die Grenzen des Kegels hinaus “schießt” und seine länge nun auf d begrenzt wurde, ist auch der Punkt in einer Zelle, in der sich möglicherweisse ein Objekt befindet. Hierdurch wurde nun bereits die Frage geklärt, wie man die Zellen bestimmt in denen sich möglicherweisse ein Objekt befinden könnte.Grafik 3

Algorithmus in Pseudocode

Modellierung der Datenstruktur - GridMap

Idee

Eine GridMap ist eine Datenstruktur, die den dreidimensionalen Raum in einzelne Würfel unterteilt, die alle die Kantenlänge r besitzen. Neben einer x-, y- und z-Koordinate wird in jeder Zelle ein Wahrscheinlichkeitswert abgelegt, der darüber bestimmt ob ein Objekt oder auch nur ein Teil davon aus dem 3D-Raum innerhalb eines Würfels liegt. Die Würfel werden im folgenden als Zellen bezeichnet. Wenn der Ultraschallsensor ein Objekt lokalisiert hat, wird die korrespondierende Zelle aus der Gridmap ausgewählt und der Wahrscheinlichkeitswert dieser Zelle aktualisiert.

Interface

Implementierung der GridMap

Die Implementierung der GridMap speichert die Zellgröße, die Anzahl der Zellen, sowie einen Initial-Wert für die Wahrscheinlichkeit jeder Zelle. Die Daten selbst werden in einer Hashmap<int[], Float> abgelegt. Das Integer-Array ist dreidimensional und repräsentiert die drei Koordinaten x, y und z der jeweiligen Zelle. Zu jedem Koordinaten-Tripel wird der Wahrscheinlichkeitswert als Float gespeichert. Wird die GridMap anfangs initialisiert, muss eine Zellgröße, die Initial-Wahrscheinlichkeit und eine Zellanzahl übergeben werden. Aus letzterem Wert wird die Größe der HashMap bestimmt.

HashMap

Die der GridMap zurgunde liegende Datenstruktur ist eine HashMap. Diese wurde gezielt ausgewählt, da sie einen Zugriff von O(1) garantiert. Wenn die HashMap bei der Befüllungen einen Schwellwert überschreitet, wird sie durch die Laufzeitumgebung vergrößert und alles Hashes neu berechnet. Das erleichtert die Reorganisation erheblich. Zu Beginn der Implementierung war vorgesehen, die GridMap auf Basis einen dreidimensionalen Arrays zu erstellen. Bei Überläufen, insbesondere in den negativen Zahlenbereich, wären komplizierte Reorganisationen dieses Arrays zu tätigen, was durch die HashMap vom System selbst übernommen wird.

Hashing-Verfahren

Um einen Wert in der GridMap abzulegen, wird der Hash-Wert über die (x,y,z)-Koordinaten der Zelle gebildet. Da Java die hashcode()-Methode für float-Arrays nicht selbstständig überschrieben hat, wählten wir die statische hashcode(float[])-Methode aus der Klasse Arrays.

Mapping von gemessenen Punkt-Daten auf Zellen in der GridMap

Beim berechnen der Vektoren in dem Kegel des Sensors entstehen Punkte auf den Zellreihen. Diese Punkte liegen jeweils in genau einer Zelle. Im folgenden wird beschrieben wie zu einem Punkt im Raum die entsprechende Zelle errechnet wird. Die erste Zelle (also Zelle (0,0,0)) beginnt im Uhrsprung und erstreckt sich um die Zelllänge nach x, y und z. Alle weiteren Zellen bauen sich um die erste Zelle herrum auf. So beginnt die nächste Zelle in x-Richtung (also nach rechts) nach der ersten Zelle bei (r,0,0) (wobei r die Zelllänge ist), was bedeutet dass diese Zelle Zelle (1,0,0) ist. betrachtet man die Zelle in negativer x-Richtung von der ersten Zelle (also nach links) so beginnt diese bei (-r,0,0) und ist somit die Zelle (-1,0,0). Die Zelle links von Zelle (-1,0,0) beginnt bei (-2r,0,0) und ist somit die Zelle (-2,0,0). Das selbe Prinzip gilt auch für die y- und z-Achse. Die Zelle über der ersten Zelle beginnt bei (0,r,0) und ist somit Zelle (0,1,0). Die Zelle, welche räumlich vor der ersten Zelle liegt beginnt bei (0,0,r) und ist somit Zelle (0,0,1). Grafik 4 zeigt einen Teil einer GridMap und veranschaulicht das Prinzip.Grafik 4 Die Berechnung einer Zelle in Abhängigkeit von einem Gegebenen Punkt ist für positive x-, y- oder z-Werte nicht sehr kompliziert. Man berechnet hierfür erst einmal den Teil welcher “übersteht” und zieht diesen dann von den x-, y- und z-Werten des Punktes ab und teilt dann durch die Zelllänge, also: Seien x,y,z die Koordinaten des Punktes, welche alle >= 0 sind, r die Zelllänge und x_z, y_z und z_z die Koordinaten der Zelle, dann gilt:

x_z = (x-(x%r))/r

y_z = (y-(y%r))/r

z_z = (z-(z%r))/r

Bei Punkten mit negativen x-, y- oder z-Werten funktioniert dieses Verfahren jedoch leider nicht. Angenommen man hätte eine Zelllänge von r = 10 und einen Punkt (-3,2,-1), so würde man die Zelle (-1,0,-1) erwarten. Das Ergebniss ist jedoch die Zelle (0,0,0). Das liegt daran, dass man bei negativen Werten “abrunden” und nicht “aufrunden” muss. Der Punkt (-3,2,-1) müsste also auf (-10,0,-10) fallen und somit die Zelle (-1,0,-1) ergeben. Für negative Werte eines Punktes gilt also folgendes: Seien x,y,z die Koordiaten des Punktes, welche alle < 0 sind, r die Zelllänge und x_z, y_z und z_z die Koordinaten der Zelle, dann gilt:

x_z = (x-(r+(x%r)))/r , falls x%r < 0

x_z = x/r , falls x%r = 0

y_z = (y-(r+(y%r)))/r , falls y%r < 0

y_z = y/r , falls y%r = 0

z_z = (z-(r+(z%r)))/r , falls z%r < 0

z_z = z/r , falls z%r = 0

Wahrscheinlichkeitswert für eine Zelle setzen

Um die Wahrscheinlichkeit einer Zelle zu setzen, muss zuerst die Zelle, die mit einem Punkt korrespondiert, mit dem obigen Verfahren bestimmt werden. Für diese Zelle wird die alte Wahrscheinlichkeit festgehalten. Wurde die Zelle bisher noch nicht tangiert, ist die A-Priori-Wahrscheinlichkeit gesetzt. In unserer Implementierung liegt diese bei 0.5. Mit der bool’schen Variable cellOccupied wird der Methode mitgeteilt, ob die betrachtete Zelle potentiell besetzt (true) oder unbesetzt (false) ist. Für den ersteren Fall wird die neue temporäre Wahrscheinlichkeit newProb für den aktuellen Zeitschritt berechnet aus (1.0 + oldProb) / 2. Wenn die Zelle potentiell unbesetzt ist, wird die alte Wahrscheinlichkeit durch 2 geteilt und newProb zugewiesen ((0.0 + oldProb)/2). Da die Formel, die die gesamte Wahrscheinlichkeit für eine Zelle bestimmt (siehe nächster Abschnitt) aus Brüchen besteht und in diesen durch Null geteilt werden könnte, wird für den Fall, dass die neue temporäre Wahrscheinlichkeit newProb Null wird, diese auf 0.001 gesetzt. Nun kann die im folgenden Abschnitt beschriebene Formel zur Berechnung der gesamten Wahrscheinlichkeit einer Zelle angewandt werden.

Neue Wahrscheinlichkeit = 1/(1+((1-newProb)/newProb) * (initProbability/(1-initProbability))*((1-oldProb)/oldProb)))

Für viele Messungen, konvergiert diese Formel gegen 1, falls die Zelle mit einem Objekt besetzt ist und gegeben 0, falls sie unbesetzt ist. Es gibt alternative Formeln, die aber den Nachteil haben, dass die Wahrscheinlichkeit gegen einen Wert zwischen 0 und 1 konvergiert und man sich geeignete Schwellwerte überlegen muss, um zu bestimmen, ob eine Zelle besetzt oder unbesetzt ist.

Ausdehnung der GridMap

Um die GridMap später zeichnen zu können, müssen die Dimensionen bekannt sein. Der GridMap liegt eine HashMap zu Grunde, die im Prinzip deutlich größer sein kann, als die belegten Werte. Beim Zeichnen will man aber nur den Bereich, der auch belegt ist, zeichnen. Für die Ermittlung des belegten Bereiches wurden die Methoden getMaxBounds() und getMinBounds() implementiert. Intern werden triviale Maximum- und Minimum-Suchen eingesetzt um die höchsten und niedrigsten x-, y- und z-Werte zu finden.

GridMap leeren

Für den Fall, dass eine GridMap komplett geleert werden soll, wurde die clear()-Methode implementiert. Die alte HashMap wird hierbei einfach durch eine neue Instanz ersetzt.

Ausblick

Durch diese Arbeit ist das mathematische Modell, sowie eine Implementierung des Modells gegeben. Folgende Arbeiten können an verschiedenen Punkten anknüpfen. Diese sollen nun erörtert werden.

Abtastrate

Beim Abtasten der Kreisfläche des Kegels wird der doppelte Beam-Winkel in 1°-Schritten durchlaufen. Dadurch wird ein Quadrat mit Seitenlänge 2 * Beam-Winkel beschrieben. Mit der Abfrage der Kreisbedingung werden nur diejenigen Winkel-Konfigurationen beachtet, die sich tatsächlich in der Kreisfläche befinden. Bei dieser Vorgehensweise, werden die gleichen Zellen mehrmals von unterschiedlichen Punkten berührt und es muss festgehalten werden, welche Zellen schon betrachtet worden sind, damit nicht mehrmals die Wahrscheinlichkeit einer Zelle verändert wird. Hier könnte man sich eine dynamische Abtastrate für den Winkel Phi überlegen, der in jeder Zellebene die Kreisfläche durchläuft und dabei alle Kästchen genau einmal trifft. Hierfür wäre ein analytisches Verfahren notwendig. Da die Berechnung der Abtastung auf schnellen Rechnern abläuft, funktioniert die jetzige Implementierung ohne Probleme. Sollte es durch andere Konfigurationen Schwierigkeiten mit der Performanz geben, kann auch über eine stochastische Lösung der Abtastung nachgedacht werden. Die Idee wäre hierbei randomisiert Punkte innerhalb der Kreisfläche zu bestimmen. Durch die Statistik und die ständige Wiederholung des Verfahrens, würden alle Zellen im Schnitt abgedeckt sein und es wären weniger Berechnungen notwendig.

Grafische Implementierung

Da durch die vorliegende Implementierung eine Datenstruktur (GridMap) vorliegt, die die jeweiligen Wahrscheinlichkeitswerte für Objekte innerhalb der Zellen enthält, kann sie ohne größeren Aufwand durch Grafikbibliotheken, wie OpenGL, gezeichnet werden. Dadurch erhält man die Raumtopologie als Reliefdarstellung.

Coverage Maps

In der vorliegenden Implementierung werden die Wahrscheinlichkeiten einer Belegung einer Zelle die Werte für 0 für nicht belegt, 0.5 für nicht beeinflusst und 1 für belegt annehmen. Damit kann eine Zelle komplett gemalt werden, sobald der Wert 1 darin enthalten ist. Diese Maps werden Occupancy Maps genannt und bilde eine binäre Struktur. Neben den Occupancy Maps gibt es aber auch solche Strukturen, die Teilbelegungen durch Objekte mit beachten. Wenn ein Teil eines Objektes eine Zelle nur zu 20% belegt, kann das in einer Struktur gespeichert werden, die sich Coverage Map nennt. Dadurch wird die Granularität der Reliefdarstellung erhöht und die Raumtopologie genauer beschrieben.

Referenzen

C. Stachniss: Robotic Mapping and Exploration, Springer-Verlag Berlin Heidelberg, 2009 Adam Milstein, University of Waterloo, Canada: Occupancy Grid Maps for Localization and Mapping (http://cdn.intechopen.com/pdfs/5368/InTech-Occupancy_grid_maps_for_localization_and_mapping.pdf)

C. Stachniss: Universität Freiburg, Mapping and Exploration with Mobile Robots using Coverage Maps: (http://www.informatik.uni-freiburg.de/~stachnis/pdf/stachniss03iros.pdf)

Ressourcen

RoboView-Framework