Semantische Kartierung und Navigation für mobile Roboter E-Book

Klaus Uhl

• Herausgeber: Books on Demand
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Deutsch

Seitenzahl: 247

Veröffentlichungsjahr: 2014

Beschreibung

Autonome, mobile Serviceroboter dringen in immer mehr Anwendungsgebiete vor. In klassischen Anwendungen übernehmen Fahrerlose Transportfahrzeuge (FTF) seit Jahrzehnten Transportaufgaben in der Intralogistik von Betrieben. In den letzten Jahren wurden weitere Anwendungen, z.B. in der Gebäudereinigung, der Geländeüberwachung oder in der Landwirtschaft kommerziell erschlossen. Darüber hinaus wird ein breites Spektrum an Servicerobotikanwendungen erforscht. Diese reichen von autonomen, mobilen Manipulatoren für Fertigungsaufgaben in der Produktion und Kommissionieraufgaben in der Logistik über Assistenzroboter für die Alten- und Krankenpflege bis hin zu universellen Haushaltshilfen. Bei allen diesen Anwendungen ist die Fähigkeit zur Navigation eine Grundvoraussetzung für die Autonomie der mobilen Systeme. In dieser Dissertation wird ein Navigationssystem für mobile Roboter entworfen, das semantische Information im Umweltmodell vorhält, die Bewegungsmuster des Roboters in Abhängigkeit der semantischen Eigenschaften der lokalen Umgebung flexibel steuern kann und Navigationspläne erstellt, die an die Art und Weise angelehnt sind, wie Menschen einen Weg durch eine Umgebung beschreiben. Dabei wird ein semantisches Umweltmodell entworfen, aus dem mittels eines semantischen Modells von symbolischen Roboteraktionen ein Graph von sog. "semantischen Positionen", die ausschließlich über semantische Eigenschaften definiert sind, für die Navigationsplanung abgeleitet werden kann.

Leseprobe

Inhaltsverzeichnis

1 Einleitung

1.1 Anforderungen an das Navigationssystem

1.2 Zielsetzung und Beitrag der Arbeit

1.3 Aufbau der Arbeit

2 Stand der Forschung

2.1 Wissensrepräsentation

2.1.1 Ontologien

2.1.2 Beschreibungslogiken

2.1.3 Frame Logik

2.1.4 Vergleich der Formalismen

2.2 Semantik in der Servicerobotik

2.2.1 Spatial Semantic Hierarchy

2.2.2 Semantik in der Umweltmodellierung und Navigationsplanung

2.3 Symbolische Planung

2.3.1 S

TRIPS

2.3.2 Action Description Language (ADL)

2.3.3 Hierarchische Aufgabennetzwerke (HTN)

2.4 Zusammenfassung und Fazit

3 Systemarchitektur

3.1 Komponenten der Missionssteuerung

3.2 Systeme mit reduzierten Missionsanforderungen

3.3 Aufbau der Wissensbasis

3.4 Einordnung der Arbeit

4 Semantische Navigation

4.1 Semantische Regionenkarte

4.1.1 Semantische Merkmale

4.1.2 Topologische Merkmale

4.1.3 Geometriche Merkmale

4.1.4 Probabilistische Modellierung

4.2 Semantische Positionen

4.3 Semantische Navigationsplanung

4.3.1 Der Navigationsplanungsalgorithmus

4.3.2 Modellierung von Anwendungsklassen

4.3.3 Transformation des Aktionsmodells

4.3.4 Ableitung des Erreichbarkeitsgraphen

4.3.5 Semantische Navigations-Algebra

4.4 Semantische Lokalisierung

4.4.1 Semantischer Lokalisierungsalgorithmus

4.4.2 Regions-Korrespondenzproblem

4.4.3 Bestimmung der Modell-Wahrscheinlichkeiten

5 Semantische Kartierung

5.1 Lösung des Rechteck-Korrespondenzproblems

5.2 Schätzung der Regionsmerkmale

5.2.1 Regionsklasse

5.2.2 Nachbarschaft

5.2.3 Hierarchie

5.2.4 Regionsgeometrie

5.2.5 Gesamter Aktualisierungsalgorithmus

5.3 Semantisches SLAM mit komplexen Regionsmerkmalen

5.3.1 Messmodell für die Regionsgeometrie

5.3.2 Merkmalsdifferenz

5.3.3 R

EGION

SLAM-Algorithmus

5.4 Nachbearbeitung der Semantischen Regionenkarte

6 Umsetzung und experimentelle Validierung

6.1 Anwendung 1: Serviceroboter für Büroumgebungen

6.1.1 Taxonomie der Regionstypen

6.1.2 Einfaches Aktionsmodell

6.1.3 Komplexes Aktionsmodell

6.2 Anwendung 2: FTF für die Intralogistik in Krankenhäusern

6.2.1 Taxonomie der Regionstypen

6.2.2 Semantisches Modell der Roboteraktionen

6.2.3 Evaluation

6.3 Semantische Kartierung

7 Zusammenfassung und Ausblick

A Filter zur Zustandsschätzung

A.1 Markov-Annahme

A.2 Bayes-Filter

A.3 Diskreter Bayes-Filter

A.4 Zeitdiskreter Kalman-Filter

A.5 Partikelfilter

1. Einleitung

Autonome, mobile Serviceroboter dringen in immer mehr Anwendungsgebiete vor. In klassischen Anwendungen übernehmen Fahrerlose Transportfahrzeuge (FTF) seit Jahrzehnten Transportaufgaben in der Intralogistik von Betrieben. In den letzten Jahren wurden weitere Anwendungen, z.B. in der Gebäudereinigung, der Geländeüberwachung oder in der Landwirtschaft kommerziell erschlossen. Darüber hinaus wird ein breites Spektrum an Servicerobotikanwendungen erforscht. Diese reichen von autonomen, mobilen Manipulatoren für Fertigungsaufgaben in der Produktion und Kommissionieraufgaben in der Logistik über Assistenzroboter für die Alten- und Krankenpflege bis hin zu universellen Haushaltshilfen.

Bei allen diesen Anwendungen ist die Fähigkeit zur Navigation eine Grundvoraussetzung für die Autonomie der mobilen Systeme. Wichtige Eigenschaften eines Navigationssystems für mobile Roboter sind dabei Effizienz bei der Planung und Robustheit bei der Ausführung, insbesondere auch in einer weitläufigen und veränderlichen Umgebung. Ebenso wird heute vorausgesetzt, dass die Karte der Umgebung, welche für die Navigation benötigt wird, aus Sensordaten automatisch berechnet werden kann.

Andererseits dürfen aber auch Sicherheitsaspekte, wie sie insbesondere in der Maschinenrichtlinie [2] und dem Produktsicherheitsgesetz [72] geregelt sind, bei der Konzeption eines Navigationssystems nicht vollständig außer Acht gelassen werden. Denn wenngleich die Einhaltung der Sicherheitsbestimmungen üblicherweise in einer Sicherheitssteuerung auf der niedrigsten Ebene des Roboters erfolgt, so kann das Navigationssystem doch die Gefährdungen, die von einem Servieroboter ausgehen – und als Folge davon die Anforderungen an die Sicherheitssteuerung – maßgeblich beeinflussen. Die Vorhersagbarkeit des Roboterverhaltens muss mitunter über die maximale Flexibilität und Effizienz der Navigation gestellt werden, um die Gefahr zu minimieren, Menschen zu verletzen. Eine vollständig freie Navigation ist somit nicht immer möglich bzw. sinnvoll. Eine weitere, wünschenswerte Eigenschaft eines Navigationssystems besteht deshalb darin, das Roboterverhalten in den unterschiedlichen Bereichen einer Umgebung flexibel anpassen zu können.

Der verbreitete Ansatz einer rein metrischen oder topologischen Navigation wird mehr und mehr um Ansätze ergänzt, welche die Semantik der Umgebung berücksichtigen. Ein Roboter, der in der Lage ist, über die Regionen und Objekte seiner Umgebung sowie deren Beziehungen untereinander Schlussfolgerungen zu ziehen, kann einfacher und natürlicher mit den Menschen kommunizieren, die er unterstützen soll. Außerdem macht die Verwendung eines abstrakten, semantischen Umweltmodells die Navigationsplanung effizienter, die Navigation robuster und die Überprüfung sowie den Austausch des Roboterwissens leichter.

Der Stand der Forschung liefert verschiedene Ansätze, ein semantisches Umweltmodell zu formulieren. Dabei wird die Umgebung in Regionen zergliedert, denen eine spezifische Bedeutung zugeordnet wird (z.B. „Wohnzimmer“, „Küche“, etc. ). Des Weiteren können in den Regionen Objekte registriert werden. Sowohl die Regionen, als auch die Objekte sind mit einer Ontologie verknüpft, welche es erlaubt, implizites Wissen über ihre Eigenschaften abzuleiten. Bezüglich der Navigationsplanung bietet der Stand der Forschung jedoch nicht die oben geforderte flexible Anpassungsmöglichkeit des Roboterverhaltens. Die Planung erfolgt entweder nur auf der Ebene der Regionsübergänge und überlässt die Feinplanung innerhalb der Regionen einem untergeordneten, geometrischen Planer, oder sie erfolgt vollständig auf geometrischer Ebene. Somit klafft, wie in Bild 1.1 dargestellt ist, zwischen den verfügbaren Planungsansätzen eine Lücke. Bei der metrischen und topologischen Navigation erfolgt die Planung auf einem niedrigen Abstraktionsniveau, wobei feingranulare Pläne berechnet werden. Dagegen ist das Abstraktionsniveau und die Granularität der Pläne bei der symbolischen Aktionsplanung sehr hoch. Der Raum dazwischen wird bislang nicht gefüllt.

Bild 1.1.: Der Stand der Forschung im Bereich der Navigationsplanung deckt nur den unteren und oberen Bereich des Abstraktions bzw. Granularitätsspektrums ab. Dazwischen klafft eine Lücke (rot schraffiert).

1.1. Anforderungen an das Navigationssystem

Um ein flexibles und effizientes System, das einen möglichst hohen Grad an Autonomie besitzt, erreichen zu können, müssen bei der Konzeption des Navigationssystems eine Reihe von Anforderungen berücksichtigt werden.

Semantische Information Eine semantische Modellierung des Umweltmodells ermöglicht es, durch Inferenz implizites und generalisiertes Wissen zu nutzen. Aus diesem Grund vereinfacht die Verwendung von semantischer Information verschiedene Aufgaben der Navigation von mobilen Robotern und macht sie effizienter und robuster. Dies trifft insbesondere auf die Pfadplanung, die Lokalisierung des Roboters in der Umgebung sowie die Mensch-Maschine-Interaktion zu [16, 48, 68]. Außerdem erleichtert eine semantische Modellierung die Interaktion der unterschiedlichen Komponenten einer Robotersteuerung.

Das Umweltmodell, mit dem das Navigationssystem arbeitet, soll daher auf einer semantischen Modellierung der verarbeiteten Informationen aufgebaut sein.

Abstraktion und hierarchische Struktur Um effizient Navigationspfade planen und ausführen zu können, ist – gerade in großen Umgebungen – eine hierarchische Planungs- und Ausführungsstruktur zwingend notwendig. Es ist aufwändig, einen langen Pfad detailliert auf einer exakten metrischen Karte zu planen. Effizienter ist es, zunächst einen abstrakten topologischen Pfad zu berechnen und diesen anschließend in einer Detailplanung abschnittsweise zu einer exakten Bahn zu verfeinern. Dementsprechend gibt es auch nicht eine einzelne Darstellung der Umgebung, die für alle Schritte der Planung und Ausführung geeignet ist (siehe [38]).

Das Umweltmodell soll die Informationen über die Umgebung daher auf verschiedenen Abstraktionsstufen zur Verfügung stellen können.

Flexible Steuerung der Bewegungsmuster Die Navigationsplanung soll in der Lage sein, die auszuführenden Roboteraktionen in Abhängigkeit von semantischen Attributen der lokalen Umgebung auszuwählen. Dadurch ist es möglich, die Bewegungsmuster des Roboters flexibel zu steuern und z. B. abhängig vom Typ der Region, in der sich der Roboter befindet, unterschiedliche Navigationsstrategien zu erhalten.

Abstrakte Navigationsplanung Die Navigationsplanung soll sich an der Art und Weise orientieren, wie Menschen einen Weg durch eine Umgebung beschreiben. Ein Navigationsplan soll nicht aus einer Reihe von geometrischen Trajektorien oder einer Liste von topologisch verknüpften Orten bestehen, die in den Sensordaten eindeutig identifiziert werden können. Er soll vielmehr an eine Wegbeschreibung wie z. B. „fahre den Gang entlang und biege an der zweiten Gang-Kreuzung nach links ab“ angelehnt sein, die sich auf Entitäten in der Umgebung bezieht. Ein so aufgebauter Navigationsplan hat Vorteile gegenüber rein metrischen oder topologischen Plänen:

Da der Plan aus sehr abstrakten Navigationsanweisungen besteht, ist er robuster gegenüber Diskrepanzen zwischen der realen Umgebung und dem Umweltmodell, welches der Planung zugrunde liegt.

Bei einer geometrischen Planung werden die Trajektorien überall nach demselben Schema erzeugt. Bei einer topologischen Planung sind die Stützpunkte eines Navigationspfads durch die topologische Karte fest vorgegeben. Durch die vorgeschlagene Orientierung am Menschen und durch die Nutzung der geforderten semantischen Karteninformation kann eine höhere Flexibilität bei der Steuerung des Roboterverhaltens in den unterschiedlichen Bereichen einer Umgebung erreicht werden.

Navigationspläne dieser Art sind für Menschen deutlich einfacher zu erfassen und nachzuvollziehen.

Beim Entwurf der Navigationsplanung sind auch die oben aufgeführten Anforderungen an das Umweltmodell zu berücksichtigen.

Lokale metrische Karten mit lokalen Bezugssystemen Prinzipiell ist es möglich, für die lokale Bahnplanung und Regelung einfache Regelmechanismen, die ohne eine Karte der Umgebung auskommen, zu verwenden. Dieser Ansatz wird z. B. von Kuipers und Byun vorgeschlagen [39]. Oft ist es aber hilfreich, wenn der Roboter über eine möglichst exakte metrische Karte seiner unmittelbaren Umgebung verfügt. In Anwendungen, wie z. B. bei fahrerlosen Transportfahrzeugen, in denen bestimmte Objekte oder Lokalitäten von der Sensorik des Roboters nicht erfasst werden können, sondern über metrische Relationen zum Umfeld lokalisiert werden müssen, ist dies sogar zwingend notwendig.

Für die Unterstützung der lokalen Bahnplanung und Regelung soll das Umweltmodell daher die Möglichkeit enthalten, metrische Karten zu hinterlegen. Das Kartenformat (2D oder 3D, Merkmalskarte oder Belegtheitskarte) soll dabei offen bleiben, damit für jeden Roboter, auf dem die semantische Missionssteuerung zum Einsatz kommt, das am besten geeignete Kartenformat verwendet werden kann.

Die Verwendung eines einzelnen, globalen Koordinatensystems für das gesamte Umweltmodell bringt aber, insbesondere bei wachsender Größe der Umgebung, verschiedene Probleme mit sich. Bei der Kartierung der Umgebung wird es umso schwieriger, eine konsistente Karte zu berechnen, je größer die Umgebung ist. Die Fehler in der berechneten Karte, die sich aus der ungenauen Lokalisierung des Roboters und dem Rauschen der Sensor-Messungen ergeben, summieren sich umso mehr, je größer die zurückgelegten Strecken werden. Um diese Fehler zu kompensieren, werden aufwändigere Kartierungsverfahren und ein überproportional höherer Rechenaufwand benötigt.

Für den praktischen Einsatz genügt es i. d. R. jedoch, nur für lokale Umgebungen, welche die Sensorreichweite nicht signifikant überschreiten, Karten mit lokalen Bezugssystemen zu erstellen und vorzuhalten (siehe [6]). Aus diesem Grund sollen die hinterlegten, lokalen metrischen Karten nicht in einem globalen Bezugssystem registriert werden, sondern ihre eigenen lokalen Bezugssysteme verwenden.

Behandlung von sensorisch nicht vollständig erfassbaren Entitäten Gebäude können eine sehr große Ausdehnung haben. Deshalb können auch Regionen, wie z.B. Gänge, entsprechend lang sein. In großen Gebäudekomplexen können Verbindungsgänge Längen von mehreren hundert Metern erreichen. Wegen der begrenzten Reichweite aller existierenden Sensoren kann nicht sichergestellt werden, dass ein Roboter eine Region mit seinen Sensoren immer vollständig erfassen kann. Außerdem können Hindernisse den Sichtbereich der Sensoren einschränken, wodurch ebenfalls verhindert wird, dass die Ausdehnung einer Region vollständig erfasst werden kann.

Das Umweltmodell muss mit solchen unvollständigen Messungen von Regionsmerkmalen umgehen können.

Behandlung von sensorisch nicht erfassbaren Entitäten Unabhängig davon, mit welcher Kombination von Sensorik ein Roboter ausgestattet ist, gibt es immer Objekte oder Lokalitäten, die von der Sensorik nicht erfasst werden können. Dies gilt insbesondere bei kommerziellen Robotersystemen, wo die Kosten für den Bau des Roboters eine Rolle spielen und deshalb die Anzahl der Sensoren sowie deren Kosten so gering wie möglich gehalten werden muss.

Das Umweltmodell soll diese Situation abbilden können, indem es erlaubt, Entitäten ausschließlich über Relationen zu anderen Entitäten, die mit der vorhandenen Sensorik erfasst werden können, zu definieren und zu lokalisieren.

Für die semantische Kartierung stellt diese Situation ein Problem dar. Es ist nicht möglich, Entitäten zu kartieren, die von der Sensorik des Roboters nicht erfasst werden können. Diese Lücke soll durch zwei weitere Anforderungen geschlossen werden:

Es soll möglich sein, die Karten, die von der semantischen Kartierung berechnet wurden, manuell um weitere Entitäten zu erweitern.

Es soll möglich sein, Karten, die für den Einsatz auf einem Roboter mit wenig Sensorik notwendig sind, auf einem anders aufgebauten

Messroboter

zu erstellen, der über mehr bzw. teurere Sensorik verfügt.

Die Anwendung dieser beiden Maßnahmen ist insbesondere dann interessant, wenn die Karte einer Umgebung zu einem bestimmten Zeitpunkt erstellt wird und anschließend auf einer ganzen Flotte von mobilen Robotern zum Einsatz kommt. Bei fahrerlosen Transportsystemen (FTS) ist diese Vorgehensweise gängige Praxis. Sie kann aber grundsätzlich auch in anderen Situationen angewendet werden, wenn mehrere mobile Roboter in einer statischen oder quasi-statischen Umgebung eingesetzt werden sollen und eine ständige Aktualisierung des Umweltmodells nicht notwendig ist.

Unabhängigkeit von der Implementierung der Robotersteuerung Das System zur semantischen Kartierung und Navigation soll unabhängig von der Implementierung einer Robotersteuerung sein, auf dem sie zum Einsatz kommt. Insbesondere sollen weder Annahmen getroffen werden, in welcher Form die Fähigkeiten des Roboters umgesetzt sind, noch sollen diesbezüglich Vorgaben gemacht werden. So wird sicher gestellt, dass die semantische Kartierung und Navigation mit minimal möglichem Aufwand auf unterschiedliche Ziel-Roboter portiert werden kann.

1.2. Zielsetzung und Beitrag der Arbeit

Ein Navigationssystem für einen mobilen Roboter besteht aus folgenden Komponenten:

Eine Kartierungskomponente berechnet aus den Sensormessungen des Roboters bei Bedarf eine Karte der Umgebung oder aktualisiert diese.

Ein Navigationsplanungsalgorithmus plant, gegeben die aktuelle Position des Roboters und das Navigationsziel, in der Umgebungskarte einen Pfad vom Start- zum Zielpunkt.

Eine Ausführungskomponente führt die einzelnen Abschnitte des geplanten Pfades sequenziell aus.

Eine Lokalisierungskomponente errechnet kontinuierlich die aktuelle Position des Roboters in der Umgebungskarte.

Das Umgebungsmodell spezifiziert die Information, die in der Umgebungskarte erfasst wird. Es bildet das Vokabular für ein einheitliches Verständnis der Umgebung und wird von allen zuvor genannten Komponenten verwendet.

Das Navigationssystem eines Roboters, der in einer unbekannten Umgebung in Betrieb genommen wird, durchläuft dabei den Prozess, der in Bild 1.2 dargestellt ist. Zunächst wird eine Karte der Umgebung erstellt. Anschließend kann der Roboter in der Umgebung navigieren.

Bild 1.2.: Schematischer Prozess vom „unwissenden“ Roboter bis zur erfolgreichen Ausführung eines Navigationsplans.

Das Ziel dieser Arbeit besteht im Entwurf und der prototypischen Implementierung eines Navigationssystems für mobile Roboter mit den beschriebenen Komponenten, welches die in Abs. 1.1 aufgeführten Anforderungen berücksichtigt und möglichst umfassend erfüllt. Der Protoyp soll in einer Simulationsumgebung evaluiert werden.

Um dieses Ziel zu erreichen, wird ein abstraktes Umweltmodell mit semantischen, topologischen und geometrischen Merkmalen zur strukturellen Repräsentation der Umgebung entworfen. Darüber hinaus werden semantische Positionen formuliert, die über semantische Relationen zu Entitäten des Umweltmodells beschrieben werden. Sie dienen als diskrete, abstrakte Stützpunkte für die Navigationsplanung sowie die Lokalisierung. Es wird ein Algorithmus entwickelt, der ein Modell von Roboteraktionen, das auf Vor- und Nachbedingungen basiert, in eine Menge von Regeln transformiert, mit denen unter Verwendung eines Inferenzwerkzeugs aus dem strukturellen Umweltmodell automatisch ein topologischer Navigationsgraph aus semantischen Positionen abgeleitet werden kann. Die Navigationsplanung erfolgt anschließend als Kürzeste-Wege-Suche auf dem Navigationsgraphen. Um den Prozess in Bild 1.2 vollständig abzubilden, wird ein semantisches Kartierungsverfahren entwickelt, mit dem das abstrakte Umweltmodell aus vorverarbeiteten und abstrahierten Sensormessungen automatisch berechnet werden kann. Außerdem wird eine Möglichkeit zur Lokalisierung auf semantischen Positionen bzw. im Navigationsgraphen aufgezeigt.

1.3. Aufbau der Arbeit

Der Aufbau der Arbeit ist in Bild 1.3 schematisch dargestellt. Kapitel 2 gibt einen Überblick über den Stand der Forschung. Dabei werden die drei Themenbereiche „Wissensrepräsentation“, „Semantik in der Servicerobotik“ und „symbolische Planung“ beleuchtet und bewertet.

Kapitel 3 stellt die Systemarchitektur vor, in welche die vorliegende Arbeit eingebettet ist. Zunächst wird die semantische Missionssteuerung mit ihren Komponenten in ihrer vollständigen Ausprägung vorgestellt. Anschließend wird eine reduzierte Form der Missionssteuerung eingeführt, die zum Einsatz kommt, wenn die Missionsaufgabe neben der Navigation keine weitergehenden perzeptorischen oder planerischen Fähigkeiten erfordert. Darüber hinaus wird der Aufbau der Wissensbasis, welche alle informationstragenden Elemente der Arbeit enthält, erläutert. Schließlich wird die Arbeit in die Systemarchitektur eingeordnet.

Das Konzept der semantischen Navigation wird in Kapitel 4 erläutert. Zunächst wird die semantische Regionenkarte als abstraktes Umweltmodell mit semantischen, topologischen und metrischen Merkmalen eingeführt sowie die Eigenschaften von semantischen Positionen erläutert. Anschließend wird das Konzept der Navigationsplanung vorgestellt und der Algorithmus zur Transformation einer semantischen Regionenkarte mittels eines semantischen Modells der Roboteraktionen in einen Navigationsgraphen erläutert. Zuletzt wird ein Konzept für die semantische Lokalisierung auf dem Navigationsgraphen präsentiert.

Bild 1.3.: Aufbau der Arbeit.

Kapitel 5 beschäftigt sich mit der semantischen Kartierung. Nach der Betrachtung eines speziellen Korrespondenzproblems, das sich aus dem Aufbau der komplexen Kartenmerkmale ergibt, wird die Aktualisierung der einzelnen semantischen, topologischen und geometrischen Teil-Merkmale beschrieben. Anschließend werden die einzelnen Aktualisierungsalgorithmen zu einem uniformen SLAM-Algorithmus zusammengefügt. Zuletzt wird erläutert, welche Nachbearbeitungsschritte erforderlich sind, bevor eine semantische Regionenkarte für die Navigationsplanung verwendet werden kann.

Das Kapitel 6 wendet das Konzept der semantischen Kartierung und Navigation auf zwei konkrete Anwendungsklassen an: Einen Serviceroboter für Büroumgebungen sowie ein FTF für die Intralogistik in Krankenhäusern. Nach einer Beschreibung der Anwendung werden jeweils die semantischen Aktionsmodelle entwickelt und Experimente zur Navigationsplanung vorgestellt sowie deren Ergebnisse bewertet. Anschließend wird die semantische Kartierung evaluiert.

Die Arbeit schließt in Kapitel 7 mit einer Zusammenfassung und einem Ausblick auf zukünftige Arbeiten.

2. Stand der Forschung

Im Folgenden wird der Stand der Forschung in drei Themenfeldern beleuchtet, die für diese Arbeit besonders relevant sind. Das erste Themenfeld betrachtet Formalismen und Techniken zur Wissensrepräsentation. Hierbei wird insbesondere auf ontologiebasierte Verfahren eingegangen und Möglichkeiten zur Repräsentation von räumlichen Gebilden aufgezeigt. Das zweite Themenfeld befasst sich mit der Anwendung von semantischen Methoden und Technologien in der Servicerobotik. Dabei liegt der Fokus auf dem Einsatz von Semantik für die Navigation und die Umweltmodellierung. Im dritten Themenfeld werden schließlich Methoden zur Planung von symbolischen Aktionssequenzen erläutert. Da für das Konzept dieser Arbeit probabilistische Planungsverfahren keine Rolle spielen, beschränkt sich die Betrachtung auf deterministische Ansätze.

Im Zusammenhang mit der semantischen Kartierung kommen probabilistische Filter zur Zustandsschätzung (Bayes- und Kalman-Filter) zum Einsatz. Diese stellen aber im Bereich der Navigation von mobilen Robotern so grundlegende Verfahren dar, dass sie hier nicht weiter betrachtet werden. Anhang A liefert einen Überblick über die verwendeten Verfahren. Ebenso werden die Algorithmen zur Suche von kürzesten Pfaden in Graphen, welche bei der semantischen Navigationsplanung verwendet werden, hier nicht näher erläutert.

2.1. Wissensrepräsentation

Wissensrepräsentation und Schlussfolgern stellen ein Gebiet der künstlichen Intelligenz dar, welches sich mit der Frage beschäftigt, wie Wissen symbolisch repräsentiert und automatisch verarbeitet werden kann [7]. Dabei spielen Ontologien und Ontologie-Systeme eine große Rolle. Im Folgenden wird zunächst definiert, was man im Kontext der künstlichen Intelligenz unter einer Ontologie versteht, welche Kriterien beim Entwurf einer Ontologie berücksichtigt werden sollten, welche Rollen Ontologien spielen können und welche Vorteile sie bringen. Anschließend werden Beschreibungslogiken (und als Spezialfall davon die Technologien des Semantic Web) sowie Frame-Logiken als formale Sprachen zur Repräsentation von Ontologien und Wissensbasen erläutert.

2.1.1. Ontologien

Der Begriff „Ontologie“ stammt ursprünglich aus der Philosophie und stellt dort eine systematische Beschreibung der Realität durch Entitäten (Gegenstände, Eigenschaften und Prozesse) sowie deren Beziehungen zueinander dar. Im Bereich der künstlichen Intelligenz ist eine Ontologie eine explizite Spezifikation einer Konzeptualisierung. Eine Konzeptualisierung ist, wiederum, eine vereinfachte, abstrakte Sicht auf einen Ausschnitt der Welt, der für einen bestimmten Zweck repräsentiert wird. Sie ist durch die Entitäten (Objekte, Konzepte, etc. ) definiert, die für diesen Zweck von Interesse scheinen, sowie durch die Beziehungen, die zwischen den Entitäten existieren [24]. Präziser formuliert stellt eine Ontologie in der künstlichen Intelligenz ein technisches Artefakt dar, das ein spezifisches Vokabular zur Beschreibung einer bestimmten Domäne sowie explizite Annahmen bezüglich der Bedeutung der im Vokabular definierten Worte enthält. Üblicherweise werden die Annahmen einer Ontologie in Form einer logischen Theorie erster Ordnung formuliert oder können in eine solche überführt werden. Das Vokabular selbst liegt in Form von unären oder binären Prädikaten vor, wobei unäre Prädikate Konzepte und binäre Prädikate Relationen beschreiben. Der Begriff der „Konzeptualisierung“ bezeichnet in diesem Zusammenhang die philosophische Definition einer Ontologie als System von Kategorien, das eine bestimmte Sicht auf die Welt begründet. Somit ergibt sich folgende Definition einer Ontologie:

Definition 2.1 (Ontologie). Eine Ontologie ist eine logische Theorie, welche die angestrebte Bedeutung – und damit seine ontologische Bindung an eine bestimmte Konzeptualisierung – eines formalen Vokabulars definiert. Die angestrebten Modelle einer logischen Sprache, in der dieses Vokabular formuliert ist, werden durch seine ontologische Bindung eingeschränkt. Eine Ontologie spiegelt diese Bindung wider, indem sie die angestrebten Modelle approximiert [25].

Eine Ontologie formuliert also ein gemeinsames Vokabular, mit dem mehrere Agenten Anfragen und Zusicherungen austauschen können. Ein Agent bindet sich an eine solche Ontologie, wenn seine beobachtbaren Handlungen mit den Definitionen der Ontologie in Einklang stehen. Durch die ontologische Bindung sichert der Agent zu, das gemeinsame Vokabular, das in der Ontologie definiert ist, kohärent und konsistent zu verwenden. Bild 2.1 stellt die Zusammenhänge zwischen Vokabular, Konzeptualisierung, ontologischer Bindung und Ontologie dar.

Eine Ontologie ist nicht mit einer Wissensbasis zu verwechseln. Während eine Ontologie das Vokabular definiert, um über eine Domäne sprechen zu können, repräsentiert eine Wissensbasis das Wissen, welches benötigt wird, um Aufgaben in Bezug auf diese Domäne zu lösen oder Anfragen zu beantworten. Eine Wissensbasis muss sich also auch an eine Ontologie binden und deren Terminologie nutzen, um für andere Agenten von Nutzen zu sein.

Ontologien sind sprachabhängig, wohingegen Konzeptualisierungen sprachunabhängig sind. Die Approximation einer Ontologie bildet eine Obermenge der angestrebten Modelle. Nutzen nun zwei Ontologien, die zwei unterschiedliche Konzeptualisierungen modellieren, dieselbe Sprache, dann kann es vorkommen, dass sich die Approximationen der angestrebten Modelle überschneiden, nicht jedoch die angestrebten Modelle selbst. In diesem Fall verwenden beide Ontologien, zumindest teilweise, dasselbe Vokabular um unterschiedliche Konzepte zu beschreiben. Aus diesem Grund gibt es keine Garantie, dass sich zwei Systeme, deren Vokabular sich überschneidet, bezüglich einer bestimmten Information verständigen können. Dieses Problem lässt sich nur dadurch beheben, dass beide Systeme zum Informationsaustausch auf eine gemeinsame, übergeordnete Ontologie zurückgreifen. Diese Erkenntnis führt Guarino [25] dazu, Ontologien, abhängig von ihrer Allgemeingültigkeit, in drei Klassen zu unterteilen:

Bild 2.1.: Eine Ontologie approximiert die angestrebten Modelle einer Sprache, welche die Bindung an eine Konzeptualisierung darstellen.

Top-Level-Ontologien beschreiben sehr allgemeine Konzepte, die nicht von einer konkreten Aufgabe oder einer bestimmten Domäne abhängen. Sie können – je nach Umfang der modellierten Konzepte – als Basis und gemeinsames Austausch-Vokabular für eine breite Palette and spezialisierten Domänen-, Aufgaben- und Anwendungsontologien dienen [41]. Einige Vertreter dieser Klasse von Ontologien sind BFO (Basic Formal Ontology) [22], Cyc [43], DOLCE (a Descriptive Ontology for Linguistic and Cognitive Engineering) [42], GFO (General Formal Ontology) [27], PROTON (PROTo ONtology) [63] und SUMO (Suggested Upper Merged Ontology) [50].

Domänen- und Aufgabenontologien beschreiben das Vokabular einer generischen Domäne, Aufgabe oder Aktivität. Dabei verwenden und spezialisieren sie i. d. R. das Vokabular einer Top-Level-Ontologie.

Anwendungsontologien stellen die am stärksten spezialisierte Klasse von Ontologien dar. Sie beschreiben das Vokabular für eine spezielle Aufgabe, die in einer speziellen Domäne durchgeführt wird. Die Konzepte dieser Ontologien entsprechen häufig den Rollen, die Entitäten der Domäne während der Ausführung von bestimmten Aufgaben bzw. Aktivitäten einnehmen.

Kriterien für den Ontologieentwurf

Beim Aufbau einer Ontologie müssen verschiedene Entwurfsentscheidungen getroffen werden. Gruber [24] schlägt daher eine Reihe von objektiven Bewertungskriterien vor. Der Architekt einer Ontologie kann sich während des Entwurfsprozesses an diesen orientieren und sie anschließend verwenden, um den fertigen Entwurf noch einmal zu bewerten und ggf. Verbesserungen daran vorzunehmen.

Klarheit Eine Ontologie sollte die angestrebte Bedeutung der definierten Terme effektiv vermitteln. Die Definitionen sollten dabei objektiv sein, d. h. unabhängig von einem möglicherweise vorhandenen sozialen oder softwaretechnischen Kontext. Falls möglich, sollten Definitionen immer in Form von logischen Axiomen formuliert werden. Vollständige Definitionen, die alle hinreichenden und notwendigen Bedingungen enthalten, sollten partiellen Definitionen vorgezogen werden. Zusätzlich sollten alle Definitionen in natürlicher Sprache dokumentiert werden.

Kohärenz Schlüsse aus den Definitionen der Ontologie sollten immer mit dieser konsistent sein. Als Minimalanforderung müssen die logischen Axiome in sich und zusammen genommen widerspruchsfrei sein. Aber auch die informell in der natürlichsprachlichen Dokumentation formulierten Konzepte sollten stimmig sein.

Erweiterbarkeit Beim Entwurf einer Ontologie sollte immer darauf geachtet werden, dass die Definitionen eine konzeptuelle Grundlage für einen breiteren Bereich von Aufgaben bilden können. Außerdem sollte die Ontologie monoton erweiterbar sein. Eine Erweiterung oder Spezialisierung sollte nicht zur Folge haben, dass die vorhandenen Definitionen überarbeitet werden müssen.

Minimale Beeinflussung durch die Kodierung Agenten, die auf Basis einer Ontologie Wissen austauschen, können mit unterschiedlichen Systemen und Repräsentationsstilen implementiert werden. Deshalb sollte die Konzeptualisierung ausschließlich auf der Wissensebene stattfinden. Entscheidungen bezüglich der Repräsentation, die ausschließlich getroffen werden, weil sie die Implementierung eines Agenten vereinfachen, sollten vermieden werden.

Minimale ontologische Bindung Eine Ontologie sollte lediglich den minimal notwendigen Ausschnitt der Welt modellieren, der benötigt wird, um den beabsichtigten Wissensaustausch zu ermöglichen. Darüber hinaus gehende Annahmen sollten vermieden werden, um allen Parteien, die sich an diese Ontologie binden möchten, so viel Freiheit wie möglich zu geben, die Ontologie zu spezialisieren und zu instantiieren. Da die Bindung an eine Ontologie auf der konsistenten Nutzung des Vokabulars basiert, kann dies erreicht werden, indem die Ontologie die schwächste logische Theorie modelliert, die für den Wissensaustausch notwendig ist.

Bei der Bewertung dieser Kriterien müssen mitunter Kompromisse eingegangen werden. Deshalb hängt das Ergebnis der Bewertung vom verfügbaren Wissen und der erwarteten Verwendung der Ontologie ab. Dasselbe Kriterium kann in verschiedenen Anwendungen durchaus unterschiedlich bewertet werden und somit zu anderen Entwurfsentscheidungen führen.

Rollen und Vorteile von Ontologien

Jedes informationsverarbeitende System besitzt nach Guarino [25] seine eigene Ontologie, da es den verarbeiteten Symbolen, die entsprechend einer bestimmten Sicht der Welt verwendet werden, implizit oder explizit eine Bedeutung beimisst. Diese Ontologie explizit zu machen hat Vorteile, die entlang zweier orthogonaler Dimensionen eingeordnet werden können.

Die erste Dimension ist die zeitliche. Sie ist in die Entwicklungszeit und die Laufzeit aufgeteilt. Während der Entwicklungszeit ermöglicht die Verwendung einer Ontologie eine höhere Ebene der Wiederverwendung. Anstatt Software bzw. Softwarekomponenten kann Wissen wiederverwendet werden. Dadurch kann die Wiederverwendung und gemeinsame Nutzung von Wissen über eine Anwendungsdomäne auch auf heterogene Softwareplattformen sehr einfach ausgedehnt werden. Außerdem muss sich der Entwickler nicht mehr um so viele Implementierungsdetails kümmern und kann sich stattdessen stärker auf die Struktur der Anwendungsdomäne und auf die zu lösende Aufgabe konzentrieren. Da das Wissen über eine Anwendung in einer Ontologie formal spezifiziert wird, kann die Qualität und die Genauigkeit des Analyseprozess, der am Beginn jeder Softwareentwicklung steht, verbessert werden. Wenn sich die Anforderungen an ein informationsverarbeitendes System ändern, kann eine Ontologie auch das Re-Engineering vorteilhaft unterstützen. Die Ontologie wird also zu einem Werkzeug, das den Softwareentwurfsprozess unterstützt (Computer-Aided Software Engineering, CASE).

Verwendet ein informationsverarbeitendes System eine Ontologie zur Laufzeit, dann unterstützt sie die Kommunikation zwischen Softwareagenten. Die Agenten kommunizieren über Nachrichten, welche aus Ausdrücken bestehen, die aus dem Vokabular der Ontologie aufgebaut sind. Um die Nachrichten verstehen zu können, müssen sich alle Agenten an dieselbe Ontologie binden.

Die zweite Dimension ist die strukturelle Dimension und betrifft die verschiedenen Komponenten eines informationsverarbeitenden Systems. Hier ergeben sich nach Guarino folgende Vorteile:

Datenbank Eine Ontologie kann mit einem Datenbankschema verglichen werden, weshalb die Verwendung von Ontologien im Zusammenhang mit Datenbanken am offensichtlichsten ist. Zur Entwicklungszeit können Ontologien die Anforderungsanalyse sowie die Datenmodellierung unterstützen. Dabei kann das Datenmodell zunächst als Ontologie repräsentiert und später auf möglicherweise unterschiedliche Zielplattformen abgebildet werden. Darüber hinaus können Ontologien sowohl zur Entwicklungs-, als auch zur Laufzeit die Integration von unterschiedlichen Datenquellen unterstützten. Dazu können z. B. die unterschiedlichen Datenbank-Schemata auf eine gemeinsame Top-Level-Ontologie abgebildet werden.

Anwendungslogik Die Anwendungslogik eines informationsverarbeitenden Systems enthält eine Menge an Domänenwissen, das nicht in der Datenbank gespeichert wird. Eine Ontologie kann die Aufgabe übernehmen, dieses Domänenwissen explizit zu repräsentieren. Dadurch ergeben sich Vorteile in Bezug auf die Wartung, Erweiterung und Flexibilität des Systems. Muss das Domänenwissen aus bestimmten Gründen implizit in die Anwendungslogik kodiert werden, so kann zumindest ihre ontologische Bindung explizit repräsentiert werden, um die Anwendung transparenter zu machen.

Benutzerschnittstelle In der Benutzerschnittstelle kann eine Ontologie verwendet werden, um die Korrektheit der Benutzereingaben und Anfragen zu validieren. Lässt die Benutzerschnittstelle den direkten Zugriff auf die Ontologie zu, dann ist der Benutzer zudem in der Lage, die Ontologie zu durchsuchen, sich mit dem Vokabular des informationsverarbeitenden Systems vertraut zu machen und dieses besser zu verstehen und effektiver zu nutzen. Außerdem ist es möglich, dass der Benutzer sein eigenes Vokabular einbringt. Dieses wird mithilfe der Ontologie auf das Vokabular des informationsverarbeitenden Systems abgebildet.

2.1.2. Beschreibungslogiken

Beschreibungslogiken [3] stellen eine Familie von unterschiedlich ausdrucksmächtigen, logischen Sprachen zur Wissensrepräsentation dar. Sie repräsentieren Wissen über eine Anwendungsdomäne, in dem sie zunächst die relevanten Konzepte spezifizieren (die Terminologie) und diese anschließend verwenden, um Eigenschaften von Objekten und Individuen, die in der Domäne vorkommen, zu beschreiben. Im Gegensatz zu älteren Methoden zur Wissensrepräsentation, wie z. B. Semantische Netzwerke [59] und Frames [47], haben Beschreibungslogiken eine formal spezifizierte Semantik, die auf Prädikatenlogik erster Stufe basiert. Ein weiterer Unterschied zu den frühen Systemen besteht darin, dass bei Beschreibungslogiken das logische Schlussfolgern eine zentrale Rolle spielt. Sie stellen Inferenzmöglichkeiten zur Verfügung, die in vielen informationsverarbeitenden Systemen benötigt werden und auch von Menschen eingesetzt werden, um eine Anwendungsdomäne zu verstehen: Die Klassifikation von Konzepten und Individuen. Dabei berücksichtigen Beschreibungslogiken, dass Anfragen an ein wissensbasiertes System immer in akzeptabler Zeit beantwortet werden sollten.

Die Entscheidbarkeit und die Laufzeitkomplexität eines Inferenzproblems hängt von der Ausdrucksmächtigkeit der verwendeten Beschreibungslogik ab. Bei ausdrucksmächtigen Beschreibungslogiken hat die Inferenz eine hohe Laufzeitkomplexität oder ist sogar unentscheidbar. Ausdrucksschwache Beschreibungslogiken sind dagegen entscheidbar und haben eine geringe Laufzeitkomplexität. Allerdings reicht ihre Audrucksmächtigkeit möglicherweise nicht aus, um die wichtigen Konzepte einer gegebenen Anwendungsdomäne zu spezifizieren.

Bild 2.2.: Architektur einer Wissensbasis, die auf einer Beschreibungslogik basiert.

Eine Wissensbasis, die auf einer Beschreibungslogik basiert, besteht aus zwei Komponenten.

Terminologische Box (T-Box) Die T-Box definiert die Terminologie, d. h. das Vokabular einer Anwendungsdomäne. Eine Terminologie besteht aus Konzepten und Rollen. Konzepte charakterisieren eine Menge von Individuen mit ähnlichen Eigenschaften, während Rollen Beziehungen zwischen jeweils zwei Individuen beschreiben. Konzepte und Rollen können entweder atomar über ihren Namen oder in Form einer komplexen Beschreibung in der Syntax der jeweiligen Beschreibungslogik spezifiziert werden.

Assertinale Box (A-Box) Die A-Box enthält Aussagen (Fakten) über benannte Individuen, die mit den Begriffen des Vokabulars, also der T-Box, formuliert sind.

Über das reine Speichern von Terminologien und Fakten hinaus, bieten beschreibungslogikbasierte Systeme auch Inferenzdienste an. Typische Inferenzaufgaben für Terminologien (also die T-Box) sind

die Überprüfung, ob eine Terminologie

erfüllbar

ist, d. h. ob sie keine widersprüchlichen Definitionen enthält, und

die Überprüfung, ob eine Definition (ein Konzept oder eine Rolle) generischer ist als eine andere, d. h. ob die erste Definition die zweite subsumiert.

In Bezug auf die A-Box sind folgende Inferenzaufgaben interessant: