Von Johannes Dörr, Florian Manteuffel am 12.06.2009, aktualisiert am 14.06.2009 um 00:06 Uhr
Die Grundlage für eine zielgerichtete Navigation durch mehrere Hindernisse ist eine Karte. Mit Hilfe von Sensorik, mit der Hindernisse erkannt werden können, und Kenntnis der Eigenposition können Regionen als befahrbar oder nicht befahrbar vermerkt werden, sodass später auch weit entfernte Hindernisse, die außerhalb der Sensorreichweite liegen, bei der Navigation berücksichtigt werden können.
Ein oft verwendetes Prinzip ist das Speichern der Karte in einem zweidimensionalen Datenfeld. Jedes Element dieses Arrays speichert die Eigenschaft eines bestimmten Quadrates der Umgebung. Der große Nachteil ist jedoch die Form und die daraus entstehende Datenmenge.
- Auch leere Bereiche der Karte verbrauchen Speicherplatz, schließlich tragen die einzelnen Elemente mindestens die Information "befahrbar". Karten können demnach auch dann sehr speicherintensiv sein, wenn sie wenige Hindernisse speichern, diese aber weit auseinander liegen.
- Datenfelder müssen dimensioniert werden, wodurch die Größe der Karte und damit der Einsatzbereich des Roboters festgelegt wird. Ein Umdimensionieren zum Ändern der Kartengröße ist zwar in höheren Programmiersprachen durchaus möglich, jedoch meistens aufwändig. Auch der Zuwachs an benötigtem Speicherplatz darf hier nicht vergessen werden.
- Es muss eine Auflösung festgelegt werden, die angibt, in wie viele Elemente die Umgebung unterteilt wird (Maßstab). Eine große Auflösung führt zu einer großen Datenmenge, eine kleine zu Ungenauigkeiten und Fehlern.
Da die Karte unseres Roboters auch große Flächen verwalten können und außerdem höchst flexibel sein soll, haben wir ein neues Speicherverfahren programmiert. Hierbei existiert keine grafische Abbildung der Umwelt, sondern nur eine Ansammlung von Koordinaten, die die Positionen der Hindernisse angeben. Es wird also nur Speicherplatz für Hindernisse verwendet, freie Flächen ergeben sich aus dem Rest.
Ein Hindernis besteht aus mehreren, jedoch möglichst wenigen Points, die die Ecken darstellen. Der Bereich, der von den Points eingeschlossen ist, gilt als unbefahrbar. Die grundlegende Struktur sieht folgendermaßen aus:
Map
Obstacle(1) // Hindernis-Objekt
Precision // Precision-Eigenschaft
// des Hindernisses
Point(1) // Point (Einer der Eckpunkte
//des Hindernisses)
x-pos // x-pos-Eigenschaft des Points
y-pos // ...
a-distance
b-distance
x-distance
Point(2)
Point(3) // weitere Points möglich
Obstacle(2) // Hindernis-Objekt
// weitere Objekte möglich
- Abb. 2.2: Hindernis mit Points
Die virtuelle Karte enthält eine beliebige Anzahl von Hindernissen. Jedes dieser Hindernisse enthält die Eigenschaft "Precision" sowie eine beliebige Anzahl von Points. Alle Points enthalten die Eigenschaften für die x- und y-Koordinaten sowie für weitere Daten, die später erläutert werden, da sie erst für die Wegberechnung wichtig sind. Um eine möglichst genaue Abbildung der Umwelt zu ermöglichen, erhalten alle Hindernisse eine Precision-Eigenschaft, in die die geschätzte Genauigkeit des Hindernisses gespeichert wird. Später kann der Roboter dann entscheiden, ob er die Hinderniskoordinaten erneut abspeichern will, wenn die neue Messung eine genauere Beschreibung liefert. Dieses Verfahren wird weiter unten detaillierter beschrieben.
Ein Hindernis in der Karte ist also nicht bloß eine Ansammlung von nicht befahrbaren, quadratischen Flächen sondern ein wirklich zusammenhängendes Objekt. Für Erweiterungen des Systems hat dies den Vorteil, dass diese Objekte zusätzliche Eigenschaften (z.B. "gültig bis", Art des Hindernisses, etc.) bekommen oder weitere Objekt-Arten hinzugefügt werden können. Solche Objekte können Positionskontrollverfahren kennzeichnen, aber auch Hauptstraßen oder elektrische Türen darstellen.
Ein weiterer Vorteil ist, dass hier die Karte an kein Raster gebunden ist und somit alle oben angesprochenen Nachteile der Array-Methode ausgeschaltet sind. Wir haben mit dieser Methode also ein sehr flexibles und ausbaufähiges Speicherverfahren zur Verfügung.
