Hierarchical graphs as organisational principle and spatial model applied to pedestrian indoor navigation [Elektronische Ressource] / vorgelegt von Edgar-Philipp Stoffel

Edgar-Philipp Stoffel

Description

rHieraPrchicalStoeGraphsIndoasEdgaOrganisationalM?nchen,PrincipleedestrianandoSpatialNavigationMor-PhilippdellApplied2009torHieraPrchicalStoeGraphsIndoasEdgaOrganisationaltoPrincipleedestrianandlSpatialNavigationMor-PhilippdelAppliedoDissertationzur Erlangung des akademischen Grades desDoktors der Naturwissenschaftenan der Fakultät für Mathematik, Informatik und Statistikder Ludwig–Maximilians–Universität Münchenvorgelegt vonEdgar Philipp Stoffelaus BukarestMünchen, den 21. April 2009Erstgutachter:Prof. Hans Jürgen Ohlbach (Ludwig–Maximilians–UniversitätMünchen)Zweitgutachter:Prof. Mike Rosner (University of Malta)Tag der mündlichen Prüfung:2. Juni 2009CONTENTSi Preliminaries 11 Introduction 31.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . 31.2 Goals and Addressed Questions . . . . . . . . . . 41.2.1 Contributions . . . . . . . . . . . . . . . . . 61.2.2 Issues not Covered . . . . . . . . . . . . . . 71.3 Organisation of this Thesis. . . . . . . . . . . . . . 72 Background 92.1 Challenges of Pedestrian Indoor Navigation . . . 92.1.1 Motivation: Characteristics of Indoor Environ ments . . . . . . . . . . . . . . . . . . . . . 92.1.2 General Modelling Principles . . . . . . . 122.1.3 Evaluating and Adapting Existing Approaches. . . . . . . . . . . . . . . . . . . . . . . . . 142.1.4 Summary . . . . . . . . . . . . . . . . . . . 182.2 Context Information and Cost Functions . . . . .

Sujets

• Mathematics

Informations

• Publié par: ludwig-maximilians-universitat_munchen
• Publié le: 01 janvier 2009
• Nombre de lectures: 21
• Poids de l'ouvrage: 10 Mo

Extrait

rHieraPrchicalStoeGraphsIndoasEdgaOrganisationalM?nchen,PrincipleedestrianandoSpatialNavigationMor-PhilippdellApplied2009toDissertation
zur Erlangung des akademischen Grades des
Doktors der Naturwissenschaften
an der Fakultät für Mathematik, Informatik und Statistik
der Ludwig–Maximilians–Universität München
vorgelegt von
Edgar Philipp Stoffel
aus Bukarest
München, den 21. April 2009
SpatialEdgaasoStoerPrincipleNavigationdelAppliedGraphstoOrganisationalPandedestrianMoIndolHierarchicalr-PhilippErstgutachter:
Prof. Hans Jürgen Ohlbach (Ludwig–Maximilians–Universität
München)
Zweitgutachter:
Prof. Mike Rosner (University of Malta)
Tag der mündlichen Prüfung:
2. Juni 2009CONTENTS
i Preliminaries 1
1 Introduction 3
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Goals and Addressed Questions . . . . . . . . . . 4
1.2.1 Contributions . . . . . . . . . . . . . . . . . 6
1.2.2 Issues not Covered . . . . . . . . . . . . . . 7
1.3 Organisation of this Thesis. . . . . . . . . . . . . . 7
2 Background 9
2.1 Challenges of Pedestrian Indoor Navigation . . . 9
2.1.1 Motivation: Characteristics of Indoor Environ
ments . . . . . . . . . . . . . . . . . . . . . 9
2.1.2 General Modelling Principles . . . . . . . 12
2.1.3 Evaluating and Adapting Existing Approaches
. . . . . . . . . . . . . . . . . . . . . . . . . 14
2.1.4 Summary . . . . . . . . . . . . . . . . . . . 18
2.2 Context Information and Cost Functions . . . . . 19
2.2.1 The Context of Wayfinding . . . . . . . . 19
2.2.2 Examples for Indoor Environments . . . . 20
2.2.3 Using Formal Ontologies . . . . . . . . . . 21
2.2.4 Multi criteria Path Finding . . . . . . . . . 22
2.2.5 Summary . . . . . . . . . . . . . . . . . . . 25
3 Fundamentals of Hierarchical Graphs 27
3.1 Motivation: From Graphs to Hierarchical Graphs 27
3.2 Basic Definitions and Terminology . . . . . . . . 32
3.2.1 Preliminary Considerations . . . . . . . . 32
3.2.2 Three Approaches to Hierarchical Graphs 33
3.2.3 Further Definitions and their Classification 37
3.2.4 Important Questions for Spatial Applications
. . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Hierarchical Path Finding . . . . . . . . . . . . . . 40
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . 44
ii Core Design with Data Structures and Algorithms 47
4 Conceptual Design of a Hierarchical Graph System 49
4.1 Top Level System Architecture . . . . . . . . . . 49
4.1.1 Rationale: Distributed, Heterogeneous Spatial
Networks . . . . . . . . . . . . . . . . . . . 49
4.1.2 Hierarchical Organisation via Mediators . 53
4.1.3 Context AdaptivePathFindinginaHierarchy 56
4.2 Basic Operations and Consistent Construction of Hier-
archical Graphs . . . . . . . . . . . . . . . . . . . . 60
4.2.1 Hierarchisation via Node Refinement . . . 61
4.2.2 Basic Operations for Hierarchical Graphs 62
4.2.3 Maintaining a Consistent Hierarchy . . . 63
4.2.4 Consistent Path Finding over Multiple Levels
. . . . . . . . . . . . . . . . . . . . . . . . . 65
vTable of Contents
4.2.5 Consistency of the Basic Operations . . . . 70
4.2.6 Derivation of Other Useful . . 74
4.3 Summary . . . . . . . . . . . . . . . . . . . . . . . . 77
5 Applying Hierarchical Graphs to Indoor Environments 79
5.1 Why Hierarchicals for Navigation in Buildings?
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . 82
5.3 Modelling Aspects and Construction of the Hierarchy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.3.1 Interpretation of Floor Plans . . . . . . . . 83
5.3.2 The Underlying Geometric Model . . . . 85
5.3.3 Basic Mapping to a Flat Graph . . . . . . . 98
5.3.4 Hierarchisation . . . . . . . . . . . . . . . . 101
5.3.5 The Third Dimension . . . . . . . . . . . . 103
5.3.6 Summary . . . . . . . . . . . . . . . . . . . 110
5.4 Further Enhancements of the Hierarchy . . . . . . 111
5.4.1 Insufficiency of the Basic Model for Real Navi-
gation Problems . . . . . . . . . . . . . . . 111
5.4.2 Geometric Decomposition of Complex Regions
. . . . . . . . . . . . . . . . . . . . . . . . . 118
5.4.3 Extracting Meaningful Subgraphs from a Dual
Region Graph . . . . . . . . . . . . . . . . . 123
5.4.4 Summary . . . . . . . . . . . . . . . . . . . 133
5.5 Application: Query Processing Using the Hierarchy
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
5.5.1 Using the Hierarchical Structure for Path Find-
ing . . . . . . . . . . . . . . . . . . . . . . . 134
5.5.2 Principles and Versatile Methods for Deriving
Route Descriptions . . . . . . . . . . . . . . 139
5.6 Scenarios for Pedestrian Indoor Navigation . . . 148
5.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . 150
6 Status Review and Evaluation 151
6.1 Overview on the Implementation . . . . . . . . . . 151
6.2 Evaluation of the Hierarchy on Real Floor Plan Data152
iii Conclusion 157
7 Related Work 159
7.1 Use of Hierarchies for Modelling Spatial Networks 159
7.2 Indoor Navigation and Wayfinding . . . . . . . . . 162
7.2.1 General Issues . . . . . . . . . . . . . . . . . 162
7.2.2 Systems and Approaches . . . . . . . . . . 165
8 Summary and Future Work 169
8.1 Results . . . . . . . . . . . . . . . . . . . . . . . . . 169
8.2 Conclusion . . . . . . . . . . . . . . . . . . . . . . . 170
8.3 Directions for Future Research . . . . . . . . . . . 170
A Ontology for Context Information 173
Bibliography 195
Index 214
viLIST OF FIGURES
Figure 1 Overlaying a Floor Plan with a Graph [BM05]
. . . . . . . . . . . . . . . . . . . . . . . . . 6
Figure 2 Motion in Road Networks vs. Indoor Environ
ments . . . . . . . . . . . . . . . . . . . . . . 11
Figure 3 Visibility Graph . . . . . . . . . . . . . . . 15
Figure 4 SimplifyingaGeneralizedVoronoiDiagram[Wal04]
. . . . . . . . . . . . . . . . . . . . . . . . . 17
Figure 5 Unnatural Route Descriptions with Generalised
Voronoi Diagrams [Whi06] . . . . . . . . . 17
Figure 6 IllustrationoftheInternettopology(fromWikipedia)29
Figure 7 Nested Packages in UML Class Diagrams 30
Figure 8 Exemplary Hierarchical Graph . . . . . . . 32
Figure 9 Three Approaches for Defining Hierarchical
Graphs [Ste99]. . . . . . . . . . . . . . . . . 36
Figure 10 Example for Illustrating Different Methods of
Hierarchical Path Finding . . . . . . . . . . 41
Figure 11 Refinement Search in an Abstract Graph . 42
Figure 12 Auxiliary Graph between Border Nodes . 44
Figure 13 OpenLS Information Model [Ope] . . . . . 53
Figure 14 Hierarchical Graph System with a Mediator 54
Figure 15 Generalisation to Multiple Levels of Mediators
. . . . . . . . . . . . . . . . . . . . . . . . . 56
Figure 16 Excerpt from the Ontology Modelling Context
Information . . . . . . . . . . . . . . . . . . 58
Figure 17 ExampleforaHierarchicNodeRefinementFunc
tion . . . . . . . . . . . . . . . . . . . . . . . 62
Figure 18 CoherentPathsacrossMultipleLevelsofaBuild
ing . . . . . . . . . . . . . . . . . . . . . . . 66
Figure 19 Path Consistency for Border Nodes with Subor-
dinate Graphs . . . . . . . . . . . . . . . . 68
Figure 20 Basic Operations Exemplified on a Hierarchy
. . . . . . . . . . . . . . . . . . . . . . . . . 71
Figure 21 Merge Two Graph Systems . . . . . . . . . 74
Figure 22 Connect Two Nodes in Different Graphs . 75
Figure 23 Partition a Graph by Creating a Subgraph 76
Figure 24 Hierarchical Graph of a Building . . . . . 81
Figure 25 Indoor Navigation: System Design with Com-
ponents . . . . . . . . . . . . . . . . . . . . 82
Figure 26 Example for Two Planar Floor Plan Graphs 87
Figure 27 Implicit Regions Enclosed by Edges . . . . 87
Figure 28 CircularCorridorR withInnerandOuterBound 0
ary . . . . . . . . . . . . . . . . . . . . . . . 88
viiList of Figures
Figure 29 Exemplary Floor Plan with Regions in Different
Meshes . . . . . . . . . . . . . . . . . . . . 89
Figure 30 Strategy for Choosing the Next Boundary Line
. . . . . . . . . . . . . . . . . . . . . . . . . 90
Figure 31 Algorithm for Finding Polygons in a Floor Plan
Graph . . . . . . . . . . . . . . . . . . . . . 92
Figure 32 Flexible Room Dividers . . . . . . . . . . . 95
Figure 33 Problematic Cases for Polygonisation . . . 95
Figure 34 Transforming the Problematic Cases into Valid
Polygon Models . . . . . . . . . . . . . . . 97
Figure 35 Dual Region Graph for a Floor Plan . . . . 99
Figure 36 Door to Door as Alternative . . . . 99
Figure 37 Refining the Interior Structure of a Library 103
Figure 38 Connections among Floors and Mezzanines in
a Hierarchical Graph . . . . . . . . . . . . 104
Figure 39 Different Types of Staircases . . . . . . . . 107
Figure 40 Integrating Floor Plans . . . . . . . . . . . 108
Figure 41 Two Different Hierarchisations with Floors and
Wings . . . . . . . . . . . . . . . . . . . . . 108
Figure 42 Separate Towers on the same Floor Level . 109
Figure 43 Train Station: Separate Platforms Connected by
a Transit Area . . . . . . . . . . . . . . . . 110
Figure 44 Example of a Manually Overlaid Floor Plan 111
Figure 45 A Maze as an Example for a Complex Spatial
Region . . . . . . . . . . . . . . . . . . . . . 112
Figure 46 Imp