Auf dieser Seite...
Um eine Navigation durch die Karte zu ermöglichen, muss ein Wegberechnungsalgorithmus vorhanden sein, der dem Roboter den Weg weist. Allerdings kann die Wegberechnung nur eine Richtfunktion erfüllen. Die Navigation beispielsweise durch eine Tür muss immer von Sensorik überwacht werden, damit Fehlberechnungen nicht in einem Zusammenstoß enden. Auch für den Abstand, in dem ein Hindernis umfahren wird, wird nicht durch die Wegberechnung gesteuert.
Einem Hindernis ausweichen
- Abb. 3.1: Traces
Im Idealfall kann das Ziel auf geradem Weg erreicht werden, ohne dass einem Hindernis ausgewichen werden muss. Um zu überprüfen, ob ein Hindernis den direkten Weg unterbricht, existiert für jedes Hindernis eine Funktion, die zurückgibt, ob sich ein Punkt (meistens die Roboterposition) auf seinem Trace befindet. Als Trace kann man sich den Bereich vorstellen, in dem man das Ziel nicht sehen kann, weil das Hindernis die Sicht nimmt (Abb. 3.1). Dabei wird überprüft, ob die Verbindungslinie von dem Punkt zum Ziel eine der Verbindungslinien der Points schneidet (rote Linie).
- Abb. 3.2: Endpoint nicht direkt erreichbar
Grundlage unseres Wegberechnungs-Algorithmus ist die eigentlich recht simple Idee, dass bei dem Umfahren eines Hindernisses einer seiner Points als Ansteuerungspunkt verwendet wird. Abbildung 3.1 soll dies veranschaulichen. Ein direkter Weg ist nicht möglich (Roboterposition liegt auf Trace), es muss deshalb ein Point des Hindernisses angesteuert werden, von dem man direkt zum Ziel kommt. Diese Points nennen wir Endpoints. Sie werden ermittelt, indem die beiden Points gesucht werden, von denen die restlichen Points alle rechts bzw. alle links liegen. Demnach besitzt ein Hindernis immer zwei Endpoints, bezeichnet mit EPA und EPB, die von der Position des Ziels abhängen.
Ist der Endpoint des Hindernisses nicht direkt erreichbar (Abb. 3.2), muss ein anderer Point gewählt werden, von dem danach der Endpoint angesteuert wird.
Programmfluss
- Abb. 3.3: Ablauf der Wegberechnung
Die Wegberechnung ist in zwei Teile aufgeteilt (PART A und B). Der erste und komplizierteste Teil der Wegberechnung wird immer dann durchgeführt, wenn die Karte geändert wurde (Hindernis hinzugefügt, neues Ziel definiert usw.). Dabei wird die Karte analysiert und vermessen. Die dabei ermittelten Werte werden in PART B benötigt. PART B liefert dem Roboter während der Fahrt eine Wegbeschreibung, die ihn zum Ziel führt. Damit PART B arbeiten kann, muss PART A abgeschlossen sein, da letzterer Daten berechnet, die von PART B gebraucht werden (Abb. 3.3).
- Abb. 3.4: Berechnung von A-Distance
PART A beginnt damit, von jedem vorhandenen Hindernis die EPs zu berechnen. Anschließend wird in jedem Hindernis von jedem Point die Entfernung zu EPA und EPB gemessen (Abb. 3.4) und in seinen Eigenschaften A- und B-Distance gespeichert. Diese beiden Eigenschaften der EPs selber sind dementsprechend immer 0.
Jeder Point besitzt auch die Eigenschaft X-Distance. Sie wird allerdings nur bei EPs verwendet und gibt die Entfernung zum Ziel an.
Später kann damit von mehreren Endpoints der mit der kleinsten Entfernung gewählt werden, indem einfach diese Eigenschaften verglichen werden.
Da die meisten EPs keine direkte Sichtverbindung zum Ziel haben, muss schon während PART A eine Wegberechnung ablaufen. Es wird also schon während PART A PART B ausgeführt.
Um dies zu ermöglichen, muss sichergestellt werden, dass, obwohl PART A noch nicht vollständig abgeschlossen ist, alle Daten der Points (A-, B- und X-Distance), auf die dabei zugegriffen wird, schon vorhanden sind. Dazu wird eine Liste angelegt, in der alle EPs nach der Anzahl der Traces, in denen sie liegen, sortiert sind. Die blauen Zahlen in der Grafik (Abb. 3.5) geben die Position der EPs in dieser Liste wieder.
Nun beginnt PART B, von den EPs an Position 0 (0 Traces, also direkter Weg zum Ziel) jeweils die Entfernung zum Ziel zu berechnen und sie als X-Distance abzuspeichern. X-Distance lässt sich hier leicht berechnen (b1), da keine Hindernisse im Weg sind.
- Abb. 3.5: Berechnung von X-Distance
An Position 1 (1 Trace, kein direkter Weg zum Ziel, ein Hindernis im Weg) ist das schon schwieriger. Als Beispiel dafür betrachten wir auf dem Bild (Abb. 3.5) den markierten Point (roter Kreis). Um von ihm aus zum Ziel zu kommen, muss einer der EPs angesteuert werden, deren Position in der Liste kleiner als 1 ist. In diesem Beispiel gibt es dafür drei Möglichkeiten, die alle getestet werden. Dies läuft folgendermaßen ab: Es wird bei allen dieser drei Endpoints überprüft, ob sie direkt erreichbar sind. Bei EPB von Hindernis 1 ist dies nicht der Fall. Deshalb wird nun getestet, ob irgendein anderer Point von Hindernis 1 erreichbar ist. Wurde so ein Point gefunden, wird die Entfernung errechnet, die man beim Ansteuern des Ziels über diesen Points zurücklegen müsste. Sie ist die Summe aus der Entfernung zu diesem Point (b3), B-Dist dieses Points (b2) und X-Distance von Endpoint B. Dieser Entfernungswert wird mit denen verglichen, die bei der Ansteuerung der anderen Endpoints (bzw. normalen Points, wenn jene nicht direkt ansteuerbar sind) entstehen. Am Ende wird der Point verwendet, der die kleinste Entfernung ergab. Dieser Entfernungswert wird als X-Distance von dem Beispiel-Endpoint, von dem wir ausgegangen sind, gespeichert.
Am Ende von PART A haben alle Points vollständige Eigenschaften, mit denen man feststellen kann, wie weit sie vom Ziel entfernt sind. Möchte man nun mit dem Roboter von einer bestimmten Position zum Ziel fahren, wird PART B aufgerufen, der zurückgibt, welcher Punkt dafür als nächstes angesteuert werden muss.
Falsche Berechnungen
Unser Wegberechnungs-Algorithmus gibt leider nicht immer sofort den richtigen Weg vor, was allerdings oftmals ohne große Bedeutung ist, da sich die Werte während der Fahrt korrigieren oder im schlimmsten Falle nur zu einem geringfügig längeren Weg führen.
- Abb. 3.6: Beispiel für falsche Berechnung
In dem Fall von Abbildung 3.6 steuert der Roboter zuerst den Endpoint von Hindernis 1 an. Da ein Hindernis nach dem Ausweichen immer am Endpoint verlassen wird, wird der Weg über den Point rechts unten (Hindernis 1, blauer Weg) nicht erkannt und Hindernis 2 angesteuert. Erst wenn der Point links oben (Hindernis 2) direkt erreichbar wird, fährt der Roboter einen Schlenker und nimmt nun den richtigen Weg. Die Konzentration auf die Endpoints hat also auch Nachteile, spart aber Rechenzeit.
- Abb. 3.7: Beispiel für falsche Berechnung
Auch die Berechnung von A- und B-Distance der einzelnen Points kann zu Fehlern führen, wie dieses Beispiel (Abb 3.7, links) zeigt. Einbuchtungen werden nämlich nicht berücksichtigt. Das hat zur Folge, dass der Weg länger geschätzt wird, als er wirklich ist. Der Roboter würde in diesem Fall links herum (roter Pfeil, grüner Weg) fahren.
Das Problem ist dabei nicht das Feststellen der Einbuchtungen sondern die Möglichkeit, dass in dieser Einbuchtung ein anderes Hindernis liegt, das den direkten Weg doch versperren würde (Abb 3.7, rechts). Da die Berechnung jedoch Hindernisintern abläuft, kann auf andere Hindernisse keine Rücksicht genommen werden.
Erweiterungen
Wie schon beschrieben wurde, ist es ohne weiteres möglich, das Orientierungssystem um neue Objekte zu erweitern. Für die automatische Aufzeichnung der Karte mögen normale Hindernisse vielleicht ausreichen, wenn sich der Roboter jedoch in einer komplizierten Umgebung bewegen soll, führt eine manuelle Hilfe manchmal zu besseren Ergebnissen. Denkbar wären zum Beispiel "Hauptstraßen", die dem Roboter Wege empfehlen oder vorschreiben. Soll ein Roboter zum Beispiel mehrere Gebäude überbrücken, wäre es ohne Probleme möglich, ihm zu verbieten, einen anderen Weg als die Straße zu nehmen.
Auch elektrische Türen (die normalerweise nur auf Körperwärme reagieren und deshalb einen Roboter nicht durchlassen würden) könnten eingespeichert werden, sodass automatisch ein Signal abgegeben wird, das die Tür öffnen lässt. Ein entsprechendes Interface dafür müsste natürlich vorhanden sein.
Die Liste ließe sich fortsetzen und beweist, wie viele Erweiterungsmöglichkeiten unser System bietet.