Erstellung einer zweidimensionalen Karte einer unbekannten Umgebung mit einem mobilen Roboter Holger Friedrich 06.02.2002 - 07.10.2002

Diese Diplomarbeit legt - zusammen mit der Arbeit von Tobias Barth - die Grundlagen für autonomes Fahren mit einem mobilen Roboter im Innenraum-Bereich, also in so genannten Indoor-Umgebungen (autonomes Fahren ist nicht Bestandteil der Arbeit).

Dazu wird ein Modell der dreidimensionalen Umwelt in Form einer zweidimensionalen Karte erstellt, das sich auf Messdaten stützt, die ein mobiler Roboter während der Fahrt mit seinen Sensoren aufnimmt.

Als Plattform für beide Diplomarbeiten dient der dafür eigens in unserer Arbeitsgruppe entwickelte Roboter, der die Umgebung mit einer Stereokamera, Infrarot-Sensoren, etc. wahrnehmen kann.

Das Kartographierungsproblem

Der Roboter soll ohne Verwendung absolut messender Positionssensoren (die auf fest installierte Hilfsmittel angewiesen sind) arbeiten. So steht man bei der Erkundung und Kartographierung unbekannten Gebiets vor zwei Problemen:

• Lokalisierung: Die Position und Orientierung des Roboters muss geschätzt werden. Dazu werden Messdaten verwendet, die den Zustand des Roboters beschreiben (z.B. Odometrie, d.h. Drehung der Räder).  Die verwendeten Sensoren arbeiten inkrementell, so dass sich die auftretenden Messfehler kumulieren und die durch Koppelnavigation gewonnene Positionsschätzung mit zunehmender Fahrstrecke immer mehr verfälschen. Hätte man bereits eine erstellte Karte, könnte man die Zahl der möglichen Positionen deutlich verringern.
• Kartenerstellung: Die Karte wird aus Messdaten erstellt, die während der Fahrt aufgenommenen werden. Es ist erforderlich, den Ort zum Zeitpunkt der Messung zu erhalten; dazu ist eine gut arbeitende Lokalisierung erforderlich.

Das Kartographierungsproblem besteht darin, sowohl Lokalisierung als auch Kartographierung zu "lösen". Neben so genannten SLAMB-Verfahren ("simultaneous localization and map building"), die beide Probleme auf einmal lösen (sehr komplex), gibt es auch Lösungsansätze mit getrennte Bearbeitung der Probleme (einfacher, dafür zu hoch angenommene Unsicherheiten).

In dieser Arbeit wird ein Kartographierungsverfahren vorgestellt, das Lokalisierungsdaten als Eingabe erhält (Positionsschätzung ist Teil der Diplomarbeit von Tobias Barth und wird mittels eines Kalman-Filters realisiert). Das Zusammenspiel der Arbeiten ist wie folgt:

Klicken Sie auf Bereiche dieses Bilds!

Kartenerstellung

Die Umwelt wird mittels einer geometrischen Repräsentation in Form zweidimensionalen Rasterkarte modelliert. D.h. die Welt wird auf die Fahrbahnebene projiziert, über die ein gleichmässiges Gitter gelegt wird. Jedes Feldelement enthält Informationen über die Belegung des Raums mit einem Hindernis.

Da sowohl Sensoren als auch die Lokalisierung potentiell fehlerbehaftete Ergebnisse liefern, enthält die Karte Informationen, die mit der Belegungswahrscheinlichkeit korrespondieren; man spricht auch von einer probabilistischen Rasterkarte.

Eingehende Messungen müssen wegen der Echtzeitanforderungen beim Betrieb von autonomen mobilen Robotern inkrementell in die Karte eingearbeitet werden. Die Daten werden zunächst mittels eines Modells interpretiert und dann mit der bestehenden Karte überlagert.

Das Zweikarten-Verfahren mit verzögerter Eintragung

An die erstellten Karten richten sich zwei Anforderungen:

• Aktualität: Zur Kollisionsvermeidung wird eine Repräsentation benötigt, die sich schnell den Gegebenheiten der direkten Umgebung des Roboters anpasst.
• Genauigkeit: Die erstellte Karte soll möglichst gut mit der Wirklichkeit übereinstimmen und wenig Widersprüchlichkeiten enthalten.

Weiterverarbeitende Algorithmen benötigen meist nur eine dieser Eigenschaften. Es scheint sinnvoll, zwei Karten zu erstellen:

• Die lokale Karte konstanter Grösse ist fest mit dem Roboter verbunden und repräsentiert dessen unmittelbare Umgebung (aktuell).
• Die globale Karte ist fest in der Umwelt verankert und wächst dynamisch.

Darüber hinaus werden die Daten verzögert in die globale Karte integriert, da die Positionsschätzung evtl. während des Verzögerungszeitraums noch verbessert werden kann. Beispielsweise kann der Inhalt der lokalen Karte (aktuell) mit dem Inhalt der globalen Karte verglichen werden, wenn bereits erkundete Bereiche erneut besucht werden. Durch einen solchen Algorithmus lässt sich die Positionsschätzung deutlich verbessern (d.h. auch, dass deren Unsicherheit abnimmt), sofern der kumulierte Fehler nicht zu groß ist.

Ergebnisse

1. Ergebnis einer Geradeausfahrt: Die Trajektorie des Roboters führt entlang des Gangs mit anschließender Wende. Deutlich erkennbar sind die platzierten Hindernisse (hell) und der (dunkel) markierte freie Bereich.
   Kartenpositionen außerhalb der Reichweite verwendeten Infrarotsensoren sind als unbekannt klassifiziert, sofern nicht Hindernisinformation von der Stereokamera geliefert wird.
   

    

2. Ergebnis einer Fahrt im zyklischen Gelände: Hier zeigt sich die Schwäche bisheriger inkrementeller Algorithmen zur Kartographierung, die den Schluss der Karte bei erneuter Einfahrt in bereits erkundetes Gebiet verfehlen.
   Hier ist Rückkopplung notwendig!
   

    

Fazit

• Kartographierung ist erfolgreich, wenn die Lokalisierung funktioniert.
• Störeinflüsse werden durch überlagerung von Einzelmessungen in der Karte reduziert.
• Güteparameter der Sensoren regeln den Einfluss von fehlerhaften Messungen.
• Verbesserung durch Rückkopplung (Vergleich von lokaler Karte mit einem Ausschnitt der globalen Karte) erscheint möglich, konnte aber im Rahmen dieser Arbeit nicht mehr realisiert werden.

Weitere Informationen über unseren Roboter findet man auf den Seiten der Arbeitsgruppe Visuelle Sensorik und Informationsverarbeitung von Prof. R. Mester.

Bei weiteren Fragen steht der Autor per E-Mail zur Verfügung.

Holger Friedrich