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. Einfuhrung
1.1. Motivation
1.2. Anforderungen und Ziele
1.3. Anwendungsszenario
1.3.1. Ein Planungsbeispiel
1.3.2. Beispielarchitektur eines Planungssystems
1.4. Ubersicht
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. Weiterfuhrende Definitionen
3.1.3. Namenskonventionen und graphische Darstellungen
3.2. Abbildung topographischer Strukturen auf hierarchische Graphen
3.2.1. Beschrankung 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 Gebaudetopographie 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 fur Navigationsnetzwerke und Plane
4. Anwendungsfalle hierarchischer Graphen
4.1. Vom hierarchischen Graph zum Plan
4.2. Unterschiedliche Netzwerkmodelle fur unterschiedliche Netze
4.2.1. Spezialfalle und undehnierte Ortsknoten
4.2.2. Strafiennetze fiir Automobile
4.2.3. Strafiennetze fiir Fufiganger
4.2.4. Offentlicher 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. Verkniipfung von Netzwerken mit kompatiblen hierarchischen Mo- dellen
4.3.2. Aneinanderreihung von Planen nicht kompatibler Modelle
5. PlanML
5.1. Definition der Sprache
5.1.1. Plane
5.1.2. Orte (Knoten)
5.1.3. Aktionen (Kanten)
5.1.4. Metaplane
5.1.5. Transferaktionen
5.2. Anwendungsbeispiel
5.2.1. Die Autofahrt
5.2.2. Der Ubergang zur S-Bahn
5.2.3. Die Fahrt im Nahverkehrsnetz
6. SchluR
6.1. Verwandte Arbeiten
6.2. Zusammenfassung der Ergebnisse
6.3. Ausblick
A. W3C XML Schema von PlanML
B. Vollstandiger Quelltext des Beispiels
Literaturverzeichnis
Zusammenfassung
Die vorliegende Diplomarbeit beschreibt PlanML, eine Sprache zur Darstellung routenba- sierter Navigationsplane auf XML-Basis. Routenbasierte Navigation bedeutet in diesem Fall, dass Plane auf Basis von Routen in topologischen Netzwerken formuliert werden. Solche Netzwerke stellen real-existierende Orte und Ortsverbindungen durch ein abstrak- tes Graphenkonzept in Knoten- und Kantenform dar.
Ein besonderes Merkmal der PlanML-Topologien ist sein hierarchisclier Ansatz. Routen konnen dadurch in PlanML-Netzwerken auf verschiedenen Granularitatsstufen parallel beschrieben werden. Dazu werden in dieser Arbeit sogenannte hierarchische Graphen und hierarchische Pfade eingefuhrt.
Desweiteren schafft PlanML Mdglichkeiten zur Verkettung von Planen aus verschiedenen Navigationsdomanen (z.B. Autonavigation, In-Building-Navigation, Zugreisen). Dies geschieht durch die Zusammenfassung von Teilplanen zu Metaplanen. Verkmipft werden die einzelnen Teilplane iiber spezielle Transferaktionen, die Netziibergange beschreiben.
Damit die PlanML-Struktur den vielfaltigen Besonderheiten der verschiedenen Navigationsdomanen gerecht wird, also insbesondere netzwerkspezifisches Wissen kodieren kann, konnen in jedem PlanML-Dokument externe, modulare Datenstrukturen eingebet- tet werden.
Abbildungsverzeichnis
1.1. Beispielarchitektur eines Plaungssystems mit Metaplaner und mehreren Aus- gabegeraten
3.1. Zwei Beispiele fur Untergraphen in einem wohlgeordneten eineindeutigen hier- archischen Graph. . Die rot markierten Knoten und Kanten bilden den kom- pletten Untergraph von V\. Die griin markierten den direkten kompletten Untergraphen von V
3.2. graphische Darstellungen hierarchischer Beziehungen
3.3. Mehrdeutige Ortsabhangigkeit (links) und zwei mogliche Auflosungen
3.4. Gebaude mit mehreren Stockwerken und Flugeln, die sich durchdringen
3.5. Aufloung potentieller Mehrdeutigkeiten
3.6. Beispiele fur Knotenbeziehungen
3.7. Bahnhofsplan Berlin Siidkreuz
3.8. Hierarchischer Graph Bahnhof Siidkreuz (nur Knoten)
3.9. die fiinf Kantentypen
3.10. Bahnhofsgraph mit Kanten. Im Knoten Verteilerebene sind nicht alle Kanten verzeichnet
3.11. Hierarchischer Pfad im Graph (rot markiert)
3.12. Pfadreprasentation in einer hierarchischen Struktur
4.1. hierarchisches Autobahnnetzwerk nach Rose[36]
4.2. Eine Kreuzung mit Knoten und Kanten auf Stufe 3 des Strahenmodells
4.3. Beispielkonstruktion eines OPNV-Netzes auf Stufe 1 und
4.4. Drei Graphen, die durch vertikale Transferkanten miteinander in Verbindung stehen (aus[42])
5.1 Ausgabe des Routenplaner ma 24[2]
Kapitel 1. Einfuhrung
1.1. Motivation
Navigationssysteme und Routenplaner haben in den letzten Jahren Einzug in unseren Alltag gehalten. Viele Neuwagen sind inzwischen mit ausgereiften Systemen ausgestat- tet, die Strafienrouten in Wort und Bild darstellen und Strabenatlanten langsam den Rang ablaufen. Bus-, Bahn- oder Flugverbindungen lassen sich heutzutage bequem iiber Internetdienste abrufen. Der Nutzer gibt in ein Onlineformular Start- und Zielort an und erhalt einen detaillierten Plan der gewiinschten Verbindung, inklusive Abfahrts- und Ankunftszeiten sowie der notigen Umsteigeaktionen. Aktuelle Forschung beschaftigt sich mit der Navigation von Personen durch Flughafen, Bahnhofen, Krankenhausern und anderen Gebauden sowie auf Straben und offentlichen Platzen. Ein Passagier konnte bei- spielsweise an einem Flughafen iiber sein PDA Informationen iiber seinen gegenwartigen Aufenthaltsort und den Weg zum Abfluggate anzeigen lassen. Insbesondere fur blinde Personen oder Rollstuhlfahrern wiirden solche tragbaren Navigationssysteme eine grobe Hilfe sein.
All diesen Planungsszenarien ist eines gemein: sie basieren auf routenbasierter Navigation. Routen sind Sequenzen von Orten, die zusammen mit Anweisungen wie man von einem Ort zum nachsten kommt einen Plan beschreiben[47]. Dieser Ansatz ist effektiv und sehr natiirlich, sowohl fiir Menschen, Roboter und vermutlich auch fiir Tiere[20]
Diese strukturelle Gemeinsamkeit kdnnte man ausnutzen, um eine Planungsplattform zu schalfen die die vielen unterschiedlichen Planungssysteme vereint und so ganz neue Moglichkeiten der Navigationsplanung schafft. An diese Plattform konnten netziibergrei- fende Anfragen wie diese gestellt werden:
“ Wie komme ich von meiner Wohnung in Bad Tolz zum Miinchener Flughafen, Gate 34?”
“Wie komme ich am schneJlsten von Hamburg nach Berlin? Mit der Bahn, dem Auto oder dem Flugzeug?”
“ Welche New Yorker Sehenswurdigkeiten konnte ich ols rollstuhlfahrender Tourist bequem innerhalb eines Tages besuchen?”
Die resultierenden Plane sind nicht mehr auf ein einzelnes Netzwerk, beispielsweise dem Automobilstrabennetz oder Busnetz beschrankt, vielmehr konnen mehrere Unterplane aus verschiedensten Netzwerken miteinander verbunden werden. Vorraussetzung fur die Konstruktion einer solchen Plattform sind unter anderem festgelegte Schnittstellen, so- wohl fiir die Kommunikation nach auben (Anfrage, Ausgabe), als auch intern (z.B. zwi- schen angeschlossenen Planungssystemen). Auberdem sollten die angeschlossenen Netz- werke, trotz ihrers sehr unterschiedlichen Charakters, eine einheitliche, flexible und mach- tige Datenstruktur benutzen, um Routen mit vergleichbarer Aussagekraft formulieren zu konnen und so eine gemeinsame Darstellungsform von resultierenden Planen zu ermogli- chen.
Bis dato sind Konzepte fiir solche universellen Planungsplattformen allerdings noch nicht ausgereift.
1.2. Anforderungen und Ziele
Diese Arbeit will einen Beitrag zur Entwicklung einer solchen univerellen Planungsplatt- form leisten. Es soil eine Darstellungsform fiir Navigationsplane, eine Plansprache, formu- liert werden, die den komplexen Anspriichen solcher Plattformen geniigt. In Anlehnung an diverse andere XML-Projekte (z.B. MathML, GraphML) wurde diese Sprache PlanML getauft. Folgende Designkriterien bilden die Grundlage fiir PlanML:
Routenbasiert. Routenbasierte Navigationsplane sind effektive und sehr natiirliche For- men der Wegbeschreibung, sowohl fiir Menschen, Roboter und vermutlich auch fiir Tiere[20]. Alle gangigen Planungssysteme basieren auf routenbasierter Navigation und dem damit eng verbundenen topologischen Netzwerkkonzept. PlanML-Plane sind natiirlich ebenfalls routenbasiert. Ein passendes Netzwerkkonzept wird eben- falls in dieser Arbeit vorgestellt.
Universell. Damit PlanML alle (routenbasierte) Navigationsszenarios abdecken kann, muss die Sprache auf der einen Seite extrem flexibel sein damit Plane die Cha- rakteristiken der Szenarios integrieren konnen. Gleichzeitig muss die Sprache eine einheitliche Struktur aufweisen um Schnittstellen fiir Applikationen generieren zu konnen. PlanML lost dieses Problem indem der Sprachkern das routenbasierte Konzept umsetzt und szenariospezifische Informationen fiber Zusatzmodule einge- bunden werden.
Integration von Teilplanen. Wie oben beschrieben, sollen Plane liber Netzwerkgrenzen hinweg formuliert werden. PlanML muss also auch Konstrukte zur Formulierung von Netzwerkiibergangen anbieten. Da solche Ubergange kein Bestandteil der Netze sind, miissen sie extern erzeugt werden. In dieser Arbeit wird ein Architekturkon- zept vorgestellt, in dem ein sogenannter Metaplaner diese Aufgabe iibernimmt.
Hierarchisch. Einige aktuelle Ansatze erweitern Navigation mit einem hierarchischen Konzept. Ein Plan kann verschiedene Granularitatsstufen beriicksichtigen, die von sehr allgemein (z.B. Stadteebene) bis zu sehr speziell (z.B. Beschreibung einzel- ner Kreuzungen oder gar Abbiegespuren) reichen kdnnen. Je nach vorhandener Ortskenntnis, kann zwischen den Granularitatsstufen gewahlt werden. Diese Arbeit unterstiitzt diesen Ansatz und stellt ein eingens hierarchisches Konzept vor, sowohl fur PlanML als auch fur das zugrundeliegende topologische Netzwerk.
XML-basiert. XML ist mittlerweile ein Quasistandard zur Darstellung von Datenstruk- turen. XML-Parser sind sehr ausgereift und erfreuen sich weiter Verbreitung. Auch Transformer wie XSLT werden immer beliebter. PlanML nutzt die hierarchischen Strukturierungsmoglichkeiten von XML um Planhierarchien elegant umzusetzen.
1.3. Anwendungsszenario
In diesem Abschnitt sollen denkbare Anwendungen von PlanML anhand eines Planungs- beispiels und eines Architekturbeispiels demonstriert werden. Beide Beispiele sollen au- Lerdem bestimmte Aspekte der Problemstellung nochmals hervorheben.
1.3.1. Ein Planungsbeispiel
Dieses zugegebenermafien komplexe Planungsbeispiel wird sich aus fiinf Teilplanen zu- sammensetzen:
Nehmen wir an Herr Muller ist Mitarbeiter am Lehrstuhl PMS am Institut fur Infor- matik der LMU Miinchen. Sein Arbeitsplatz ist in Zimmer Z1.14 im Institutsgebaude, Oettingenstrabe 67, Miinchen. Schon seit langerer Zeit bittet ihn seine Schwiegermutter ihr beim Unkrautjaten in ihrem Garten in Hamburg zu helfen. Da Herr Muller mit Ver- zogerungsstrategien keinen Erfolg mehr hat, beschliefit er am kommenden Freitag gleich nach Feierabend (18:00 Uhr) direkt nach Hamburg zu reisen um die Gartenarbeit am Wo- chenende zu erledigen. Seine Schwiegermutter kommt natiirlich fur alle Umkosten auf, sodass Herr Muller den bequemsten Weg wahlt und kurzfristig einen Flug buchen will. Er informiert sich auf der Internetseite der Fluggesellschaft liber mogliche Verbindungen und erfahrt, dass nur der Flug am Freitagabend um 19.30 in Frage kommt (alle anderen Maschinen sind ausgebucht).
In 1,5 Stunden von der Oettingenstrabe zum Flughafen inklusive Parkplatzsuche, Ein- checken, Gepackaufgabe etc. scheinen Herrn Muller doch ein sehr knapper Zeitrahmen zu sein, zumal Herr Muller erst seit einigen Wochen nach Mlinchen gezogen ist, und noch keine Ortskenntnis besitzt.
Interaktion mit einem Metaplaner Zum Gluck hat er Zugriff auf das brandneue, inter- aktive Metaplanungssystem des Instituts. Herr Muller startet die Software und wird als erstes aufgefordert, Start- und Zielort einzugeben. Zusatzlich kann Herr Muller bestimm- te Bedingungen fur die Reise festlegen. Er gibt "‘Oettingenstrafte 67, Miinchen"’ und "‘Flughafen Miinchen"’ ein, markiert als Ausfuhrungszeitraum "‘Freitag, 18.00-19.30"’ und wahlt als bevorzugtes Fortbewegungsmittel "‘Automobil"’ aus. Das Metaplanungssystem konsultiert daraufhin den angeschlossenen Autonavigationsplaner und berechnet die schnellste Route. Da die geschatzte Fahrtdauer mit lhlOmin nur knapp im gewiinsch- ten Zeitrahmen liegt, priift der Metaplaner unaufgefordert alternative Verbindungen mit Bus und S-Bahn im Miinchner OPNV-Netz. Da die schnellste Verbindung mit lh35min noch mehr Zeit in Anspruch nimmt, wird die Autofahrt gewahlt und Herrn Muller an- gezeigt. Da dar Metaplaner auch Zugriff auf einen Gebaudeplaner fur den Flughafen Miinchen besitzt, bietet er dem verdutzten Herrn Muller an, durch Angabe der Flug- nummer, einen Wegeplan vom Parkdeck bis zum Abfluggate zu erstellen. Herr Muller war zwar schon dfters am Miinchner Flughafen, aber bei geschatzten zwanzig Minuten Restzeit will er keine Zeit verlieren und lasst das System den neuen Teilplan an den Autoroutenplan anhangen. Aus Neugier startet Herr Muller gleich noch eine Anfrage, ob Plane auch fur das Institutgebaude an der Oettingenstrafie erstellt werden kdnnen. Der Metaplaner findet ein passendes System im Netz des Instituts und fragt Herrn Muller nach seiner Zimmernummer (das System trifft automatisch die Annahme, dass sein Auto auf dem Institutsparkplatz steht). Dieser Teilplan wird an erster Stelle eingefugt.
Im Anschlufi bietet der Metaplaner Herrn Muller noch an, auch den Rest der Reise zu planen. Aus der Flugnummer wird gefolgert, dass wohl Hamburg das Ziel sein wird es wird nachgefragt, wo sich das genaue Ziel befindet oder ob ein AnschluMug geplant ist. Herr Muller hat sich mit seiner Schwiegermutter am Hamburger Fischmarkt verabredet, um schnell noch einen Straufi Blumen besorgen zu konnen und um sie dann zu Kaffe und Kuchen einzuladen. Das Metaplansystem kontaktiert den Fahrplandienst des Hamburger OPNV und bietet Herrn Muller die nachstbeste Verbindung an. Nach erfolgter Bestatigung wird auch dieser Teilplan angehangt (ein Planungsmodul fur den Hamburger
Flughafen befindet sich leider noch in Aufbau). Die Ubergange von einem Teilplan zum nachsten regelt der Metaplaner iiber sogenannte Transferaktionen. Die erste Transferk- tion weist Herrn Muller beispielsweise darauf hin, dass er nun am Parkplatz sein Auto suchen, einsteigen, und auf die Oettingenstrafie fahren muss. Der resultierende Metaplan kann nun als PlanML-Dokument auf das PDA von Herrn Muller iibertragen werden.
Technische Uberlegungen Da ein PDA als Ausgabegerat gewahlt wurde, miissen auch die Plane an die besonderen Eigenschaften dieses Gerats angepasst werden. Vorrausset- zung ist naturlich, dass der Metaplaner und die angschlossenen Planungssysteme Ausga- beformate fur PDAs unterstiitzen. Ferner muss das PDA die notige Software besitzen, um den (Meta-)plan interpretieren zu konnen.
Fur PDAs waren eine grafische Darstellung in Form eines Umgebungsplan mit ein- gezeichneter Route, eine sprachgestiitzte Ausgabe der einzelnen Planschritte, oder eine Darstellung der Plane in Textform (z.B. tabellarisch) denkbar. Fur alle Ausgabeformate miissen die entsprechenden Daten im Metaplan vorhanden sein.
Weiterhin muss beriicksichtiget werden, dass die fiinf Teilplane fur unterschiedliche Planungsdomanen konzipiert sind. Wegeplane in Gebauden sind auf Fufiganger zuge- schnitten und beschreiben Orte und Aktionen auf eine andere Art wie beispielsweise der Autoroutenplan oder der OPNV-Plan. Das jeweilige Ausgabegerat muss die unterschied- lichen Planungskontexte beriicksichtigen und eventuell eine Strabenkreuzung anders auf- bereiten wie eine Busstation oder einen Gebaudeflur.
Noch zu beachten ware, dass ein PlanML-Plan verschiedene Granularitatsstufen von Orten und Aktionen einbinden kann. Eine PlanML-Interpretersoftware sollte auch dafiir passende Prasentationsformen linden (z.B. eine Art Zoomfunktion).
1.3.2. Beispielarchitektur eines Planungssystems
Um die Starken von PlanML voll ausschdpfen zu kdnnen, muss die Architektur eines Planungssystems auf PlanML ausgerichtet werden. Abbildung 1.1 illustriert einen denkbaren Architekturansatz. Dieser Ansatz ist sehr schematisch und dient hier nur der Demonstration. Eine ausgereiftere Ausarbeitungen von Architekturmodellen ware eine Zielsetzung fur zukiinftige Arbeiten.
Zentrale Elemente in Abbildung 1.1 sind der sogenannte Metaplaner und der Planin- tegrator. Der Benutzer stellt eine Plananfrage an den Metaplaner der eine Routensuche iniziiert und angeschlossene Planungssysteme kontaktiert. Diese Planungsysteme (rechte Seite in der Abbildung) iibernehmen die Routensuche in einer bestimmten Netzwerk- domane. Korrespondierend zum vorher vorgestellten Beispiel werden in der Abbildung
Abbildung in dieser Leseprobe nicht enthalten
vier Anfragen an einen Automobilroutenplaner, einen Gebaudeplaner (des Flughafen Miinchen), einen Flugplaner und an den OPNV-Planer in Hamburg gestellt. Resultieren- de Plane sind PlanML-Dokumente die mit domanenspezifischen Informationen versehen sind und an den Planintegrator iibergeben werden. Der Planintegrator verkettet die Plane zu einen sogenannten Metaplan mit Hilfe von Netzwerkiibergangen (Transferaktio- nen). Diese werden vom Metaplaner erzeugt und zwischen den Teilplanen eingefugt. Der Metaplaner bewertet aufierdem die Qualitat des Metaplans und startet gegebenenfalls abgeanderte Plananfragen. Ein fertiger Metaplan ist wieder ein PlanML-Dokument und kann nun von Ausgabegeraten interpretiert werden (linke Seite). Dabei konnen prinzipiell alle Ausgabegerate unterstiitzt werden, fur die Kodierungsinformationen vom Planungs- system in das PlanML-Dokument eingefugt wurden. In Abbildung 1.1 sind alle Elemente, die nicht direkt mit der Verarbeitung von PlanML-Dokumenten zu tun haben grau dar- gestellt. Methoden zur funktionellen Anpassung von PlanML-Planen an Ausgabegerate und Netzwerkdomanen werden in dieser Arbeit noch genauer beschrieben.
1.4. Ubersicht
Die Struktur dieser Diplomarbeit besteht aus einem kurzen Einfiihrungsteil, gefolgt von theoretischen Grundlagen, die im spateren Verlauf mit praxisbezogenen Beispielen den Weg zur Spezifizierung der Syntax und Semantik von PlanML dienen.
Kapitel 2 erleutert in knapper Form interessante Forschungsergebnisse aus den Berei- chen Navigation, raumliche Wahrnehmung und Planung. Ansatze, die fur PlanML relevant sind werden besonders hervorgehoben
Kapitel 3 fiilirt ein neues hierarchisches Graphenkonzept. Zunachst werden mathemati- sche Grundlagen und Definitionen gegeben. Schrittweise wird dann die Verwendung von hierarchischer Graphen zur Konstruktion von raumlichen Topologien gezeigt, nebst eines sehr ausfiihrliclien Beispiels in zweo Teilen um einen Praxisbezug herzu- stellen. Zum Abschlufi werden in den hierarchischen Graphen Pfade definiert, und so ein Ubergang zur Planungseben geschaffen.
Kapitel 4 beschaftigt sich mit konkreten Moglichkeiten hierarchischer Plane zur Dar- stellung von Planungsdomanen in topologischen Netzwerken. Viele gangige Do- manen wie beispielsweise Autonavigation oder Indoor-Navigation werden genauer betrachtet. Im Anschlufi werden Moglichkeiten zur Verkmipfung von Planen aus verschiedenen Domanen diskutiert und ein Metaplankonzept eingefuhrt.
Kapitel 5 widmet sich nunmehr mit der Syntax von PlanML. Alle semantischen Kon- zepte der beiden vorangegangenen Kapitel werden ebenfalls integriert. Die ein- zelnen PlanML-Sprachkonstrukte werden der Reihe nach eingefiihrt. Zum Schluft wird nochmals mit Hilfe eines Beispielsszenarios die Erstellung eines ausfuhrliches PlanML-Dokument demonstriert.
Kapitel 6 fasst alle bisherigen Ergebnisse zusammen, stellt verwandte Arbeiten vor und gibt einen Ausblick auf mogliche Anschluftarbeiten.
Kapitel 2. Navigation, Orientierung und Planen
Menschen sind mobile Lebewesen. Wie konnen uns beinahe unbeschrankt auf festem Un- tergrund bewegen, mit technischen Hilfsmitteln sogar auf dem Wasser oder in der Luft. Damit dies moglich ist, sind wir mit einer Reihe von Sinnen ausgestattet die es uns er- lauben, unsere Umgebung wahrzunehmen. Mit unseren Beinen konnen wir uns gezielt fortbewegen. Es ist daher nicht weiter verwunderlich, dass wir ein ausgepragtes raumli- ches Vorstellungsvermogen besitzen, dass hervorragend zur Navigationsplanung geeignet ist. In diesem Kapitel sollen wichtige Erkenntnisse aus den Gebieten der Navigation, der raumlichen Wahrnehmung und des Planens knapp erortert werden. Diese Erkenntnisse ebnen den Weg fur fortgeschrittene Planungskonzepte wie PlanML.
2.1. Navigation
Die Navigation ist ein Forschungsgegenstand, der traditionell interdisziplinare Aufmerk- samkeit erfahrt. Auch wenn sich die Form der Navigation oder die Art der Agenten unterscheiden, es treten immer ahnliche Szenarien und Probleme auf. Daher lasst sich menschliche Navigation gut mit der Navigation anderer biologischer Organismen verglei- chen, und auch die Navigation kiinstlicher Agenten wie Roboter basiert heutzutage auf vergleichbaren Voraussetzungen. Werner et al.[47, 48], geben eine Ubersicht fiber dieses Themas aus verschiedenen Fachbereichen wie der Biologie, Psychologie, Linguistik, AI-Forschung und der Geographic.
Die Navigation als solches beruht dabei auf einem immer wiederkehrenden Grundmo- tiv: Wie kann sich ein Agent in einer raumlichen Umgebung zurechthnden? Die raumlichen Umgebungen sowie die verwendeten Strategien unterscheiden sich mitunter stark. Ein Tourist, der sich in einer fremden Stadt mit Hilfe einer Stadtkarte zurechtfindet; Ameisen, die im Wiistensand anhand der Sonnenposition und Geruchspfaden Futterquel- len wiederhnden[46] ; Vogel, die sich beim Flug in ihr Winterquartier am Erdmagnetfeld orientiern[49] oder auch Labormause, die sich den Weg durch ein Labyrinth eingepragt haben, all diese Beispiele spiegeln verschiedene Facetten der immer gleichen Problematik wieder.
Agenten stehen zur Losung eines Navigationsproblems eine Reihe von Sensoren zur Verfiigung, die ein raumliches Wahrnehmung ermoglichen. Tiere benutzen ihre Sinnesor- gane wie Augen, Ohren, Nasen und teilweise auch exotischere Sinnesorgane zum Erken- nen von Magnetfeldern oder Elektrizitat. Roboteragenten benutzen technische Sensoren wie GPS-Empfanger, Kompasse, Kameras und ahnlichem. Menschen konnen ihrerseits sowohl ihre Sinnesorgane nutzen als auch auf technische Hilfsmittel zuriickgreifen.
Die Zahl der denkbaren Navigationsstrategien ist indes sehr hoch. Nach Trullier lassen sich alle Strategien vier verschiedene Kategorien zuordnen[47, 44]:
Fuhrung (Guidance) beschreibt Falle, in denen sich ein Agent an hand externer Richt- werten orientiert. Der Agent versucht ein vordefiniertes Kriterium zu erfiillen. Die genaueren raumlichen Begebenheiten oder die exakte Position spielt keine Rolle. Im wohl einfachsten Fall folgt der Agent einer Markierung, beispiels- weise ein Marathonlaufer der blauen Linie, die den Streckenverlauf andeutet, oder ein Autofahrer dem Strafienverlauf. Komplexer sind dagegen Gradient- strategien, zum Beispiel die Fortbewegung in Richtung einer immer starker riechenden Futterquelle, oder entlang von Magnetfeldlinien.
Standorterkennung - ausgeloste Reaktion (Place Recognition - Triggered Response). Der Agent versucht bestimmte Orte im Raum zu erkennen, und fiihrt daraufhin festgelegte Aktionen aus. Wiederum ist die relative Lage von Or- ten nicht von Bedeutung. Die grobte Herausforderung bei solchen Strategien ist die korrekte Identihkation der Orte. Es werden sensorische Inputs verwen- det und mit vordefinierten Zustanden abgeglichen. Dabei konnen besonders herausstechende Objekte (Landmarks) hilfreich sein. Probleme treten aller- dings auf, wenn Orte fur den Agenten nicht unterscheidbar sind, also den gleichen Zustand ausldsen. Aufterdem besteht immer die Gefahr, dass senso- risches Rauschen die Wahrnehmung verfalscht.
Topologische Navigation (Topological Navigation) ist ahnlich der Place Recognition, verwendet allerdings topologische Netzwerke zur Orientierung. Ein Agent erkennt nicht nur festgelegte Orte sondern auch mdgliche Verbindungen zwi- schen diesen Orten mitsamt den auszufiihrenden Aktionen. Er sucht nach Routen im Netzwerk um zu einem gewunschten Ziel zu gelangen. Weiterfiih- rendes raumliches Wissen fiber genaue Richtungen oder Distanzen ist auch bei diesem Konzept irrelevant. Folglich ist das Wissen auf die topologische Lage von Orten beschrankt. Vom Netzwerk nicht erfasste Orte konnen nicht verarbeitet werden. Ein typisches Beispiel fur eine rein topologische Navi- gationsstrategie sind Netzplane des offentlichen Nahverkehrs. Ein Fahrgast sucht sich eine Route zum gewiinschten Ziel, ohne an der genauen Lage der Stationen interessiert zu sein.
Metrische Navigation (Metrical Navigation) ist die wohl uneingeschrankteste aber mitunter auch komplexeste Form der Navigation. Im Gegensatz zu den zwei vorhergehenden Konzepten werden keine eindeutig festgelegte Objekte bzw. Zustande mehr unterschieden. Die Agent kennt vielmehr ausreichend raum- liches Wissen fiber Distanzen und Winkel um zu jeden Zeitpunkt seine aktu- elle Position im Raum sowie die Beziehung zu anderen Objekten erfassen zu konnen. Metrische Navigation beschreibt auch keine vordehnierten Aktionen mehr, sodass der Agent stets selbst Aktionen fur seinen aktuellen Zustand berechnen muss. Gebaude- oder Stadtplane sind beispielsweise Grundlagen fur metrische Navigationsstrategien. Der ausfiihrende Agent muss allerdings in der Lage sein, Distanzen und Winkel auch im realen Raum zumindest ab- zuschatzen. In diese Kategorie gehoren auch Pfadintegrationsstrategien. Hier kann der Agent den zuriickgelegten Weg und seine aktuelle Position in Relation zur Startposition oder dem angepeilten Zielort auszudriicken, indem alle bisher vollzogenen Bewegungen einbezogen werden. So konnen ausgereifte Suchstrategien entworfen werden, um beispielsweise den Ausgang aus einem Labyrinth zu finden[39]. Metrische Navigation wurde auch schon erfolgreich angewandt, um mit Hilfe von autonomen Robotern Regionen zu erkunden und ihre Daten automatisch in topologische Netzwerke umzuwandeln.
Diese Arbeit beschaftigt sich in erster Linie mit routenbasierter Navigation, der eng mit der oben beschriebenen Kategorie der topologischen Navigation verkniipft ist. Agenten bewegen sich bei dieser Strategic von einem festgelegten Wegpunkt zum nachsten indem sie einer bestimmten Route folgen[47]. Die Route ist bestimmt durch eine Kette von Wegpunkten und Beschreibungen um von einem Wegpunkt zum nachsten zu gelan- gen. In verschiedenen Arbeiten konnte gezeigt werden, dass insbesondere fur Menschen und Robotern, aber vermutlich auch fur Tiere verschiedene Auspragungen der routen- basierten Navigation eine dominante Rolle spielen[47, 41, 5, 20]. Beispielsweise neigen Menschen dazu, Fragen nach dem Weg (“wo ist der ndchste Backer”), in Routenform zu beantworten. (“die Strafie runter zur nachsten Kreuzung, dann links...v)[20, 45]. Rou- tenbasierte Navigation ist also auch die bevorzugte Strategie zur (verbalen) Vermittlung von Wegplanen und damit wie pradestiniert fur PlanML. Allerdings ware es verkehrt, solche routenbasierte Plane rein auf die aufgefiihrten Merkmale der topologischen Navigation zu beschranken. Mitunter ist es sinnvoll, zum Beispiel metrische Informationen iiber Distanzen oder Richtungen einzubeziehen (“fahren Sie 250 Meter geradeaus”) oder Orientierung nicht allein auf deiinierte Orte zu beschranken (”suchen Sie den nachs- ten Abgang”). Nach Remolina und Kuipers haben topologische Netze drei Elemente gemein[34]: Der Gerbrauch von sensorischen Input zur Identifikation von Ortsknoten, Verbindungsrelationen zwischen Orten, und lokale metrische Informationen die mit den Verbindungen assoziiert werden. Sie betonen jedoch, dass keine allgemeingiiltige Auffas- sung von topologischen Netzen existiert und ihre Form dem jeweiligen Szenario oder den verwendeten Algorithmen angepasst werden sollte.
2.2. Orientierung im Raum
Sobald von Navigation die Rede ist, muss in irgendeiner Form raumliche Wahrnehmung der Umgebung statthnden. Orientierung im Raum ist ein sehr komplexer Vorgang. Fur Menschen (fur das menschliche Gehirn) lasst sich die Representation raumlichen Wis- sens in mehrere Wissensverarbeitungsformen unterteilen[21]. Zunachst werden Formen nach raumlichen und zeitlichen Dimensionen unterscheiden. Hippocambische Prozesse verarbeiten weite Distanzen und grofen Zeitraumen, Partetalprozessen beschaftigen sich mit der direkten Umgebung um den Korper und kurzfristigen Zeitraumen[1]. Desweite- ren werden Verarbeitungsformen nach der Art der bendtigten raumlichen Wahrnehmung einteilen. Die egozentrische Sicht verarbeitet den Raum aus Sicht des Subjekts. Objek- te werden in Relation zu dessen Position wahrgenommen. Egozentrische Sichten haben allerdings den Nachteil, dass das Raumwissen aktiv angepasst werden muss, wenn sich Position oder Blickrichtung andert, auftretende Fehler pflanzen sich kummulativ bei jeder neuen Anpassung fort. Eine allozentrische Sicht setzt hingegen Orte und Objekte in Relation zueinander und bedient sich Landmarks als fixen Orientierungspunkten. Die eigene Position und Blickrichtung kann iiber sensorische Hinweise in der Umgebung berechnet werden. Diese Sicht lasst sich mit einer kognitiven Landkarte im Kopf vergleichen.
Sowohl allozentrische als auch egozentrische Formen der Representation raumlichen Wissens konnen bei Routenbeschreibung sinnvoll eingesetzt werden. Dabei wird insbe- sondere der Orientierung an Landmarks eine grofie Bedeutung zugschrieben. Es konnte beispielsweise gezeigt werden, dass es Menschen viel einfacher fallt einen Weg zu linden, wenn sie Informationen iiber gut erkennbare Objekte in der Umgebung besitzen, anstatt nur mit Hilfe von Strafiennamen und metrischen Daten[10]. Navigationsplane werden also durch die Verwendung von Landmarks fur Menschen besser verstandlich. Laut Michon und Denis existieren drei wichtige Motive, warum Landmarks zur Navigation essentiell sind[29]: Zum Anzeigen, wo eine Aktion ausgefiihrt werden soil, um Verkniipfungen zum nachsten Routenabschnitt zu schaifen und zum Uberpriifen, ob man noch auf dem rich- tigen Weg ist. Ubertragen auf die routenbasierte Navigation wiirde dies bedeuten, dass sowohl Ortsknoten also auch Verbindungen in topologischen Netzwerken um Landmark- informationen angereichert oder gar durch diese bestimmt werden sollten. Um Landmarks effektiv in resultierende Navigationsplanen einsetzen zu konnen, sollte ihre Lage relativ zum Agenten angegeben werden (vgl. Egozentrische Sicht), also als Abstand und Winkel zur Position und Blickrichtung des Agenten.
2.3. Handlungsplanung und Agenten
Das Planen wurde schon friih als eigenstandige Disziplin der KI-Forschung und als Er- weiterung einfacher Problemlosungsansatze angesehen[38]. Da strategisches Navigieren Handlungsplanung voraussetzt[48], sind die Grundlagen des Planens, wie der Ausdruck eigentlich schon nahelegt, auch fur PlanML interessant.
Agenten Die KI-Forschung verwendet oft sogenannte Agenten bei der Analyse von Pro- blemstellungen. Nach Russell ist ein Agent alles, was seine Umgebung durch Sensoren wahrnehmen kann und mit Hilfe sogenannter Aktoren Handlungen in dieser Umgebung ausfiihren kann[38]. Ein menschlicher Agent benutzt als Sensoren seine Augen, Ohren und andere Sinnesorgane und seine Hande, Fiihe und andere Korperteile als Aktoren. Roboteragenten konnen beispielsweise auf Kameras oder Infrarot-Distanzmesser zuriick- grcifcn und Handlungen durch Grcifarmc oder ahnlichcm Ausfiihren. Agenten miisscn jedoch nicht zwingend in der physischen Welt existieren. Software Agenten bearbeiten Bitfolgen als Ein- und Ausgabe und erfiillen so auch die Agentenkriterien. Diese Arbeit spielt insbesondere die Klasse der mobilen Agenten eine Rolle, also Agenten, die sich in ih- rer Umgebung autonom bewegen konnen[2]. Fuhganger, Autofahrer oder auch Roboter mit Radern sind Beispiele mobiler Agenten. Oft macht es Sinn Mensch und Fortbewegungs- mittel (z.B. das Auto) als Einheit zu betrachten, um auf veranderte Wahrnehmungsbe- ziige (Strafiensysteme) und Handlungsmdglichkeiten zu beriicksichtigen (Beschleunigen, Bremsen, Einlenken).
Planungssysteme Agenten dienen nun als ausfuhrende Instanzen von Plane. Plane sind mogliche Losungen von Planungsproblemen. Ein Planungsproblem wird klassisch durch folgende Teile bestimmt[38]:
- Ein Ausgangszustand, also eine Beschreibung der Welt.
- Einen Zielzustand.
- Eine Menge von Aktionsbeschreibungen (Operatoren)
Ein Plan ist nun eine Sequenz von Aktionen[38], die es dem Agenten ermoglichen den Zielzustand zu erreichen. Plane, die auf Basis dieser klassischen Definition erstellt wur- den haben allerdings gewisse Einschrankungen. Sie sind linear, sodass keine Nebenlaufig- keit moglich ist. Auherdem konnen ausfuhrende Agenten nicht flexibel auf Veranderun- gen der Umgebung reagieren und Aktionen oder Ziele neuen Begebenheiten anpassen. Die Ausgangsbedingungen mussen also exakt formuliert werden und etwaige unbere- chenbare Einfliisse ausgeschlossen werden. Neuere, erweiterte Ansatze berucksichtigen diese Probleme und erweitern die Definition unter anderem um Fehlerbehebungs- und Optimierungsaspekte[23, 38, 14]. Aktuell lassen sich mit PlanML auch nur lineare Plane darstellen. Durch die Einbeziehung von Zustandsbeschreibungen (entspricht Ortsbe- schreibungen) in die PlanML-Struktur ist es dem Agenten jedoch moglich, seine Zustande zu validieren und gegebenenfalls den Plan zu iiberarbeiten.
Plansuche Die Suche nach einer geeigneten Aktionssequenz kann sehr schnell sehr kom- plex werden. Im Allgemeinen ist der Suchraum extrem grofi. Zwar eignen sich alle gan- gigen Suchverfahren (Breitensuche, Tiefensuche, Backtracking etc.), jedoch sind diese Standardverfahren oft zu ineffizient. Deswegen verwendet man gerne Suchverfahren, die auf ein bestimmtes Szenario zugeschnitten sind. Im Falle der routenbasierten Navigation bieten sich Algorithmen an, die effizient Pfade in Graphen suchen. Zu nennen waren Dijkstra’s Shortest Path Algorithmus und Edmonds-Karp Maximum Flow Algorithmus, zusammen mit diversen Optimierungsheuristiken (z.B. A[3] )[42]. Vertiefende Information zu den Themen Anfrage, Suche, Optimierung in Navigationssystemen und Wayfinding finden sich in der einschlagigen Literatur (z.B. [22, 40, 35, 12, 16, 34, 43]).
Kapitel 3. Planen in hierarchischen Netzwerken
Dieses Kapitel beschaftigt sich mit den theoretischen Grundlagen von PlanML. Es wird ein formaler Unterbau entwickelt, auf dessen Basis zunachst topologische Netzwerke und spater Plane konstruiert werden konnen.
3.1. Hierarchische Graphen
An dieser Stelle soil ein spezieller Typ von hierarchisclien Graphen vorgestellt werden, mit dessen Hilfe hierarchische Ortsbeziehungen und insbesondere Ortsverbindungen in einer ausreichenden Komplexitat modelliert werden konnen. Folgenden Ideen waren dabei ausschlaggebend:
- Orte sollen durch Knoten reprasentiert werden. Davon ausgehend sollen Orte, die innerhalb eines gofieren Ortes liegen, auch im Graph durch eine geeignete Relation dargestellt werden.
- Diese Relation soil stets Aufschluss dariiber geben konnen, in welcher Tiefe sich ein Ort in der hierarchischen Struktur befindet oder welche hierarchische Beziehung zwei beliebige Knoten zueinander haben.
- Verbindungen zwischen zwei Orten sollen durch Kanten zwischen den zugeordne- ten Knoten realisiert werden. Da eine Verbindung von a nach b im Allgemeinen nicht reversibel sind (z.B. Einbahnstrafie), sollen gerichtete Kanten verwendet werden. Auch Mehrfachverbindungen von a nach b seien gestattet (z.B. zwei parallele Passagen).
3.1.1. Mathematische Grundlagen
Alle hier vorgestellten Definitionen sind Erweiterungen von Standardkonstrukten der klassischen Graphentheorie[15].
Abbildung in dieser Leseprobe nicht enthalten
G = (V,E,H)
V ist die Menge aller Knoten (vertices) und der Relation E C V x V der Kanten (edges). Eine Kante verbindet genau dann einen Knoten a mit einem Knoten b (von anach b) wenn gilt:
(a, b) G E, mit a,b G V
Die Kanten sind also gerichtet und konnen auch identische Start- und Endknoten besitzen (Selbstbezug).
Zusatzlich sei die Relation H C V x V definiert, welche die hierarchische Beziehung zwischen Knoten zum Ausdruck bringt. Ein Knoten a liegt innerhalb von b (geschrieben: a -< b), wenn gilt:
Abbildung in dieser Leseprobe nicht enthalten
Man sagt: “a ist ein Unterknoten (Nachkommenknoten) von 6” bzw. “b ist ein Uber- knoten (Vorgangerknoten) von a”.
Ein Knoten a liegt direkt innerhalb von b wenn gilt:
Abbildung in dieser Leseprobe nicht enthalten
a ist dementsprechend ein direkter Unterknoten (Sohnknoten) von b.
Definition 2: Untergraph Somit lassen sich auch Untergraphen (Nachkommengra- phen) beschreiben. Seien [Abbildung in dieser Leseprobe nicht enthalten] So gilt:
Abbildung in dieser Leseprobe nicht enthalten
Definition 3: direkter Untergraph Gjist wiederum ein direkter Untergraph graph) von Knoten c, wenn folgende Bedinung erfiillt ist:
Abbildung in dieser Leseprobe nicht enthalten
Definition 4: kompletter Untergraph Sei [Abbildung in dieser Leseprobe nicht enthalten]
V \ Vi. Weiterhin seien nun [Abbildung in dieser Leseprobe nicht enthalten] und genauso [Abbildung in dieser Leseprobe nicht enthalten] (alle definierten Kanten und hierarchischen Knotenbezie- hungen der Knotenteilmenge Vi). Dann ist G*ist der komplette Untergraph von c wenn
Abbildung in dieser Leseprobe nicht enthalten
Definition 5: direkter kompletter Untergraph Die letzten beiden Dehnitionen lassen sich kombinieren, sodass der komplette direkte Untergraph [Abbildung in dieser Leseprobe nicht enthalten] von u/bestimmt ist als:
Abbildung in dieser Leseprobe nicht enthalten
Solche (direkte) komplette Untergraphen spielen spater eine wichtige Rolle in der Mo- dellierung von topologischen Netzwerken. Sie werden als Verfeinerung von Ortsknoten in ein Netzwerk eingefiigt. Abbildung (3.1) verdeutlicht den Unterschied zwischen den Dehnitionen 4 und 5 anschaulich.
3.1.2. Weiterfiihrende Definitionen
Mit H wurde eine zusatzliche Relation dehniert, die ahnlich wie E binare Beziehungen zwischen Knotenpaaren auszudriicken vermag. Um damit die fur uns notigen Strukturen modellieren zu konnen, miissen einige Einschrankungen an G vorgenommen werden.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 3.1.: Zwei Beispiele fiir Untergraphen in einem wohlgeordneten eineindeutigen hierarchischen Graph. . Die rot markierten Knoten und Kanten bilden den kompletten Untergmph von V\. Die griin markierten den direkten kompletten Untergraphen von V2
Abbildung in dieser Leseprobe nicht enthalten
Ein hierarchischer Graph, der alle drei oberen Eigenschaften erfiillt, wird als wohlge- ordneter hierarchischer Graph bezeichnet.
Lemma: Man kann zeigen, dass in einem solchen Fall kein Knoten weder direkt. (1)
noch indirekt (2 und 3) in sich selbst enthalten ist, also keine Schleifen vorhanden sind.
Definition 7: eineindeutige Zuordnung Die Relation H besitzt eine eineindeutige Zuordnung falls gilt:
Abbildung in dieser Leseprobe nicht enthalten
Definition 8: Wurzelknoten r E V ist ein Wurzelknoten von G (ist Element der
Menge root(G)) wenn gilt:
Abbildung in dieser Leseprobe nicht enthalten
Kapitel 3. Planen in hierarchischen Netzwerken Die Menge der Wurzelknoten fur einen Knoten a sei definiert als rootG(a) = root(G) n {v e V| a -A v e H}
Lemma: Wenn G wohlgeordnet mit eineindeutiger Zuordnung ist, dann gilt: Jeder Kno ten v G V ist entweder ein Wurzelknoten oder besitzt genau einen direkten Oberknoten. (ohne Beweis) Weiterhin lafit sich jedem kompletten direkten Untergraph Gi genau ein Oberknoten zuordnen.
Lemma: Man kann zeigen, dass es in einem wohlgeordneten hierarchischen Graphen mindestens einen Wurzelknoten geben muss. Und das in einem solchen Graph der Knoten a entweder mindestens einen Wurzelknoten hat oder selbst ein Wurzelknoten ist.
Hierarchiebaume: Aus diesen beiden Lemmta lafit sich folgern, dass in einem wohl geordneten hierarchischen Graph die Relation H einen Wald aus Baumen aufspannt, aus dem man leicht die hierarchischen Beziehungen einzelner Knoten zueinander ablesen kann. Abbildung 3.2 zeigt zwei mdgliche Darstellungsformen eines solchen Walds (Da nur ein Wurzelknoten existiert liegt ein Baum vor). In Tiefenstufe 3 wurden aus Platzgriinden nicht alle Knoten markiert.
Definition 9: Tiefe eines Knoten Die (hierarchische) Tiefe depth(c) eines Knoten c ist definiert als:
Abbildung in dieser Leseprobe nicht enthalten
Lemma: In einem wohlgeordneten Graph ist die Tiefe der Knoten stets endlich. Wenn noch die Beziige eineindeutig sind, so ist die Tiefe eines Unterknotens die Tiefe seines Oberknoten +1.
Definition 10: Tiefe eines Untergraphen Sei G^ein direkter Untergraph der (mogli- chen) Oberknoten {vo ... vn} C V eines wohlgeordneten Graphen G. Dann ist die Tiefe depth(Gi)definiert durch:
Abbildung in dieser Leseprobe nicht enthalten
Besitzt der Graph zusatzlich eineindeutige Beziige, so gilt fur die Tiefe bzgl. des einzig moglichen Vaterknotens Vj:
Abbildung in dieser Leseprobe nicht enthalten
[Abbildung in dieser Leseprobe nicht enthalten]diese Definitionen auch flir direkte komplette Untergraphen.
Der Baum in Abbildung 3.2 verdeutlicht die Tiefe einzelner Knoten und Untergraphen.
3.1.3. Namenskonventionen und graphische Darstellungen
In dieser Arbeit werden die Beispiele und Illustrationen speziellen Namenskonventionen folgen urn zum einen eine leichtere Lesbarkeit und Vergleichbarkeit zu gewahren, zum an- deren um nicht immer die komplette formale Struktur des Beispiels explizit erwahnen zu miissen. Dabei wird stets von einem wohlgeordneten eineindeutigen Graph ausgegangen.
Abbildung in dieser Leseprobe nicht enthalten
Wobei alle a» jeweils eine Ziffer oder einen Buchstaben entsprechen. Die Zeichenkette a 102 ... an beschreibt dabei die hierarchische Lage des Knoten wie im folgenden Beispiel erleutert:
Nehmen wir den Knoten V1321. Dieser Knoten ist direkter Unterknoten von V132, wel- cher widerum direkter Unterknoten von U13 welcher schliehlich innerhalb des Wurzel- knoten V\ liegt. Die alleinige Angabe von V1321 impliziert also die Existenz der drei Oberknoten sowie der entsprechenden Relationen in H.
Falls Knoten im Text mit einem bestimmten bezeichneter Ort assoziiert wird, kann die kursive Bezeichnung anstelle der oben genannten Notation verwendet werden. Beispiele: Marienplatz, P12.
Abbildung in dieser Leseprobe nicht enthalten
verbindet den Knoten Vaia2...an mit dem Knoten b2...bm- Die Kante E2U geht zum Beispiel von V1321 nach V214. Falls mehrere Kanten mit gleichen Start- und Endknoten existieren, werden diese druchnummeriert. (z.B. EE2^^)
Bei benannten Knoten konnen dessen Bezeichner verwendet werden: [Abbildung in dieser Leseprobe nicht enthalten] graphische Representation: In dieser Arbeit werden verschiedene Darstellungsformen hierarchischer Graphen verwendet. Verschachtelte Graphen, wie sie in zum Beispiel in Abbildung (3.6) verwendet werden, erlauben eine recht intuitives Verstandnis der “liegt innerhalb”-Beziehung, werden jedoch auch schnell umibersichtlich, wenn viele Ebenen und Kantentypen beriicksichtigt werden.
Baumartige Darstellungen wie in Abbildung (3.2) konnen die Struktur des Graphen mitunter besser visualisieren, haben allerdings auch den Nachteil, dass Kanten schwer darzustellen sind.
3.2. Abbildung topographischer Strukturen auf hierarchische Graphen
In diesem Abschnitt soli gezeigt werden, wie hierarchische Graphen zum abstrahieren topographischer Strukturen verwendet werden. Die resultierenden Topologien stellen eine eigene ontologische Ebene dar (siehe auch Abschnitt (4.1)).
3.2.1. Beschrankung auf wohlgeordnete eineindeutige hierarchische Graphen
Die Defmitionen 6 und 7 sind sinnvolle Einschrankungen fur H, um hierarchische Graphen zur Modellierung von Ortsrelationen brauchbar zu machen. Knoten sollen hierbei iiblicherweise Orte3 reprasentieren (siehe Abschnitt 4.2.2). Die Relation H erhalt dement- sprechend die Bedeutung fiir zwei Orte A und B:
[...]
1 Benannt nach den vorwiegend aktiven Hirnarealen.
2 In diesem Kontext sind nicht (nur) mobile Softwareagentensysteme gemeint, die zwischen Computer- systemen frei migrieren und dort Aktionen ausfiihren konnen.
3 Der Begriff “Ort” sei in diesem Zusammenliang erstmal einfach nur eine beliebige zusammenh.angende Struktur im Raum. Im weiteren Verlauf dieses Abschnitts wird dieser Begriff etwas differenzierter betrachtet.
-
-
-
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.