Qualitative sichtbasierte Navigation in unstrukturierten Umgebungen

Die Vision intelligente, autonome, physikalische Roboter zu entwickeln, die autonom mit ihrer Umwelt interagieren, lässt sich fast bis auf die Ursprünge der künstlichen Intelligenz zurückführen. Ende der sechziger Jahre entwickelten Nilsson und Kollegen ([Nil84],[HFG⁺ 72]) am Stanford Research Institute (SRI) den autonomen Roboter Shakey, der in einer vereinfachten physikalischen Klötzchenwelt (engl. blocks world) autonom Planungsaufgaben lösen sollte.

Die Fähigkeit, von einer Futterstelle zurück zum Nest zu finden, sich gezielt in seinem Territorium bewegen zu können, oder den Weg vom Supermarkt zur eigenen Wohnung zu finden, ist eine der fundamentalen Aufgaben, die von fast jedem höheren Lebewesen bewältigt werden. Obwohl es gravierende Unterschiede in der Verarbeitung und Repräsentation des über die Navigation hinausgehenden Wissens gibt, deuten neue Ergebnisse der Kognitionswissenschaft darauf hin, dass die grundlegenden Mechanismen zur Navigation, trotz weitreichender physiologischer Unterschiede und folglich unterschiedlicher kognitiver und perzeptioneller Fähigkeiten, auch bei der zugrunde liegenden Sensorik und Aktuatorik, weitgehend identisch sind [WS02]. Obwohl die Problemstellung zur Navigation physikalischer Roboter und der Navigation natürlicher Systeme weitgehend identisch ist, sind die Unterschiede zwischen den verschiedenen Lösungsansätzen fundamental! Während selbst einfache Organismen wie Ameisen und Bienen mit einer im Vergleich z.B. zu Säugetieren ebenso wie zu Robotern relativ beschränkten kognitiven Kapazität und einfacher Perzeption/Sensorik Navigationsaufgaben ebenso erfolgreich wie robust lösen, sehen sich physikalische Roboter bei wechselnden Umweltbedingungen vor fundamentale Probleme gestellt. Dabei können physikalische Roboter heute auf eine hohe Rechenleistung und auf eine ausgefeilte Sensorik zurückgreifen.

Roboter-Navigation und -Lokalisation ist seit mindestens zwanzig Jahren ein sehr aktives Forschungsfeld und insbesondere in den letzten fünf Jahren wurden grosse Fortschritte erzielt. Während Stanford's Shaky nur extrem langsam in einer artifiziellen Umgebung zu navigieren vermochte, sind aktuelle Systeme in der Lage, auch komplexe Navigationsaufgaben wie die Kartographierung von Höhlen oder die Besucherführung in Museen zu lösen [TBB⁺ 98], [TBB^{+ 00], [THF+} 03]. Die Komplexität der Problemstellungen hat sich dabei beständig erhöht.

Der in diesem Kapitel spezifizierte Ansatz basiert auf zwei grundlegenden Hypothesen:

Das Navigationsproblem lässt sich konzeptionell in drei Klassen aufteilen (Details siehe Kapitel 3 und auch [TFBD00]):

Das in den vorherigen Kapiteln entwickelte Verfahren zur egozentrischen Navigation auf der Basis von Ordnungsinformationen erfordert zwei zentrale Vorbereitungsschritte. Im ersten Schritt muss zunächst empirisch die Anordnungstopologie der bei der Lokalisierung verwendeten Landmarkenkonfigurationen bestimmt werden.

In Kapiteln 4 und 5 wird formal nachgewiesen, dass die egozentrische Wahrnehmung von Ordnungsinformationen hinreichend für eine eindeutige qualitative Lokalisierung ist. Darauf basierend wird in Kapitel 5 ein formales Framework spezifiziert, welches beschreibt wie mit unvollständigen und/oder falschen Wahrnehmungen robust navigiert werden kann. In diesem Kapitel soll im Rahmen der Simulation mit QSNAPNAV-SIM empirisch bestimmt werden, bis zu welchem Grad mit unvollständigen und verrauschten Informationen navigiert werden kann. Ziel der Simulation mit QSNAPNAV-SIM ist nicht die Modellierung einer möglichst optimalen Navigation, sondern eine möglichst domänen- und sensor-unabhängige Simulation. Daher werden keine Optimierungen vorgenommen, die eine spezielle Domäne oder eine spezielle Sensorik voraussetzen.