PlanML. Eine Markupsprache für routenbasierte Navigationspläne

Die vorliegende Diplomarbeit PlanML, eine Sprache zur Darstellung routenbaierter Navigationspläne auf XML-Basis. Routenbasierte navigation bedeutet in diesem Fall, dass Pläne auf Basis von Routen in topologischen Netzwerken formuliert werden. Solche Netzwerke stellen real-existierende Orte und Orstverbindungen durch ein abstraktes Graphenkonzept in Knoten- und Kantenform dar. Ein besonderes Merkmal der PlanML-Topologien ist sein hierarchischer Ansatz. Routen können dadurch in PlanML-Netzwerken auf verschiedenen Granularitätsstufen parallel beschrieben werden. Dazu werden in dieser Arbeit sogenannte hierarchische Graphen und hierarchische Pfade eingeführt. Desweiteren schafft PlanML die Möglichkeit zur Verkettung von Plänen aus verschiedenen navigationsdomänen (z.B. Autonavigation, In-Building-Navigation, Zugreisen). Dies geschieht durch die Zusammenfassung von Teilplänen zu Metaplänen. Verknüpft werden die einzelnen Teile über spezielle Transferaktionen, die Netzübergänge beschreiben. Damit die PlanML-Struktur den vielfältigen Besonderheiten der verschiedenen Navigationsdomänen gerecht wird, also insbesondere netzwerkspezifisches Wissen kodieren kann, können in jedem PlanML-Dokument externe, modulare Datenstrukturen eingebettet werden.

Inhaltsverzeichnis

• 1. Einführung
  • 1.1. Motivation
  • 1.2. Anforderungen und Ziele
  • 1.3. Anwendungsszenario
    • 1.3.1. Ein Planungsbeispiel
    • 1.3.2. Beispielarchitektur eines Planungssystems
  • 1.4. Übersicht
• 2. Navigation, Orientierung und Planen
  • 2.1. Navigation
  • 2.2. Orientierung im Raum
  • 2.3. Handlungsplanung und Agenten
• 3. Planen in hierarchischen Netzwerken
  • 3.1. Hierarchische Graphen
    • 3.1.1. Mathematische Grundlagen
    • 3.1.2. Weiterführende Definitionen
    • 3.1.3. Namenskonventionen und graphische Darstellungen
  • 3.2. Abbildung topographischer Strukturen auf hierarchische Graphen
    • 3.2.1. Beschränkung auf wohlgeordnete eineindeutige hierarchische Graphen
    • 3.2.2. Abbildung von Orten auf Knoten in hierarchischen Graphen
    • 3.2.3. Modellierung von Orten
    • 3.2.4. Beziehungen zwischen Knoten
    • 3.2.5. Semantik der hierarchischen Relation H bei Ortsabbildungen
    • 3.2.6. Beispiel Teil 1: Konstruktion einer Gebäudetopographie in einem hierarchischen Graphen
    • 3.2.7. Kantentypen
    • 3.2.8. Semantik von Kanten und Abbildung von Ortsverbindungen auf hierarchische Graphen
    • 3.2.9. Beispiel Teil 2: Konstruktion von Ortsverbindungen
  • 3.3. Hierarchische Pfade und Routen
    • 3.3.1. Hierarchische Pfade
    • 3.3.2. Darstellungsformen hierarchischer Pfade
    • 3.3.3. Semantik hierarchischer Pfade für Navigationsnetzwerke und Pläne
• 4. Anwendungsfälle hierarchischer Graphen
  • 4.1. Vom hierarchischen Graph zum Plan
  • 4.2. Unterschiedliche Netzwerkmodelle für unterschiedliche Netze
    • 4.2.1. Spezialfälle und undefinierte Ortsknoten
    • 4.2.2. Straßennetze für Automobile
    • 4.2.3. Straßennetze für Fußgänger
    • 4.2.4. Öffentlicher Personennahverkehr
    • 4.2.5. In-Building Netzwerke
    • 4.2.6. Flug-, Schiff- und Fernzugverbindungen
    • 4.2.7. Administrative Strukturen
  • 4.3. Planen mit hierarchischen Pfaden
    • 4.3.1. Verknüpfung von Netzwerken mit kompatiblen hierarchischen Modellen
    • 4.3.2. Aneinanderreihung von Plänen nicht kompatibler Modelle
• 5. PlanML
  • 5.1. Definition der Sprache
    • 5.1.1. Pläne
    • 5.1.2. Orte (Knoten)
    • 5.1.3. Aktionen (Kanten)
    • 5.1.4. Metapläne
    • 5.1.5. Transferaktionen
  • 5.2. Anwendungsbeispiel
    • 5.2.1. Die Autofahrt
    • 5.2.2. Der Übergang zur S-Bahn
    • 5.2.3. Die Fahrt im Nahverkehrsnetz

Zielsetzung und Themenschwerpunkte

Die vorliegende Diplomarbeit befasst sich mit der Entwicklung einer XML-basierten Markupsprache namens PlanML, die zur Darstellung routenbasierter Navigationspläne dient. PlanML konzentriert sich auf die Modellierung von Plänen in topologischen Netzwerken, die reale Orte und Verbindungen durch ein abstraktes Graphenkonzept repräsentieren.

• Hierarchische Navigationspläne: PlanML ermöglicht die Modellierung von Plänen auf verschiedenen Granularitätsstufen durch die Einführung von hierarchischen Graphen und Pfaden.
• Verkettung von Plänen: Die Sprache unterstützt die Verknüpfung von Plänen aus unterschiedlichen Navigationsdomänen (z.B. Autonavigation, In-Building-Navigation) durch Metapläne und Transferaktionen.
• Netzwerkspezifische Informationen: PlanML erlaubt die Einbettung von externen, modularen Datenstrukturen, um netzwerkspezifisches Wissen zu kodieren.
• Anwendungsszenarien: Die Arbeit analysiert die Anwendung von PlanML in verschiedenen Navigationsszenarien wie Straßennetzen, In-Building-Navigation und öffentlichen Verkehrsmitteln.
• Planungsalgorithmen: Die Arbeit untersucht, wie PlanML die Entwicklung von effizienten Planungsalgorithmen für routenbasierte Navigation unterstützen kann.

Zusammenfassung der Kapitel

Kapitel 1 führt in das Thema Navigationsplanung ein und erläutert die Motivation, die Anforderungen und Ziele der Arbeit. Es wird ein Anwendungsszenario vorgestellt und eine Beispielarchitektur eines Planungssystems skizziert.

Kapitel 2 bietet eine Einführung in die Konzepte der Navigation, Orientierung und Handlungsplanung. Es werden grundlegende Prinzipien und Definitionen aus den Bereichen der Robotik und der künstlichen Intelligenz erläutert.

Kapitel 3 beschäftigt sich mit der Modellierung von Navigationsplänen in hierarchischen Netzwerken. Es werden hierarchische Graphen und Pfade definiert und ihre Anwendung im Kontext von Navigationsplänen beschrieben.

Kapitel 4 untersucht verschiedene Anwendungsfälle von hierarchischen Graphen in der Navigationsplanung, darunter Straßennetze, In-Building-Navigation und öffentliche Verkehrsmittel.

Kapitel 5 stellt PlanML, die XML-basierte Markupsprache für routenbasierte Navigationspläne, vor. Die Sprache wird detailliert beschrieben und anhand eines Anwendungsbeispiels illustriert.

Schlüsselwörter

PlanML, routenbasierte Navigation, Navigationsplanung, hierarchische Graphen, topologische Netzwerke, XML, Metapläne, Transferaktionen, In-Building-Navigation, Autonavigation, öffentlicher Personennahverkehr, Handlungsplanung, Agenten.

Details

• Hochschule: Ludwig-Maximilians-Universität München (Institut für Informatik)
• Note: 2,0
• Autor: Matthias Schmeißer (Autor:in)
• Erscheinungsjahr: 2006
• Seiten: 107
• Katalognummer: V116046
• ISBN (eBook): 9783640183821
• ISBN (Buch): 9783640184064
• Sprache: Deutsch
• Schlagworte: PlanML XML Navigation Routen Graphentheorie künstliche Intelligenz KI AI Routenplaner Navigationssystem