Hierarchical Voronoi Graphs (eBook)

Foreword 5
Preface 6
Acknowledgements 7
Contents 9
Notation 13
Abbreviations 15
List of Figures 16
List of Tables 19
Chapter 1 Introduction 20
1.1 The Robot Mapping Problem 21
1.2 The Spatial Representation Perspective 22
1.3 The Uncertainty Handling Perspective 22
1.4 Combining Representation and Uncertainty Handling 23
1.5 Route Graphs Based on Generalized Voronoi Diagrams 24
1.6 Theses, Goals, and Contributions of This Book 25
1.7 Outline of This Book 27
Chapter 2 Robot Mapping 29
2.1 A Spatial Model for What? 32
2.1.1 Navigation 32
2.1.1.1 Localization 33
2.1.1.2 Path Planning 33
2.1.2 Systematic Exploration 34
2.1.3 Communication 34
2.2 Correctness, Consistency, and Criteria for Evaluating Spatial Representations 35
2.2.1 Extractability and Maintainability 36
2.2.2 Information Adequacy 36
2.2.3 Efficiency and Scalability 36
2.3 Spatial Representation and Organization 37
2.3.1 Basic Spatial Representation Approaches 37
2.3.2 Coordinate-Based Representations 38
2.3.2.1 Occupancy-Based Representations 38
2.3.2.2 Geometric Representations 40
2.3.2.3 Landmark-Based Representations 42
2.3.3 Relational Representations 44
2.3.3.1 View Graph Representations 44
2.3.3.2 Route Graph Representations 46
2.3.4 Organizational Forms 49
2.3.4.1 Plain Representation 50
2.3.4.2 Overlays 50
2.3.4.3 Hierarchical Organization 51
2.3.4.4 Patchworks 52
2.3.4.5 Combining Different Organizational Forms 53
2.4 Uncertainty Handling Approaches 54
2.4.1 Incremental Approaches 55
2.4.1.1 Single Hypothesis Approaches 55
2.4.1.2 Complete-State-Space Approaches 56
2.4.1.3 Multi-hypothesis Approaches 57
2.4.2 Multi-pass Approaches 59
2.5 Conclusions 60
Chapter 3 Voronoi-Based SpatialRepresentations 62
3.1 Voronoi Diagram and Generalized Voronoi Diagram 62
3.2 Generalized Voronoi Graph and Embedded Generalized Voronoi Graph 64
3.3 Annotated Generalized Voronoi Graphs 66
3.4 Hierarchical Annotated Voronoi Graphs 67
3.5 Partial and Local Voronoi Graphs 68
3.6 An Instance of the HAGVG 70
3.7 Stability Problems of Voronoi-Based Representations 71
3.8 Strengths andWeaknesses of the Representation 72
Chapter 4 Simplification and HierarchicalVoronoi Graph Construction 76
4.1 Relevance Measures for Voronoi Nodes 77
4.2 Computation of Relevance Values 81
4.3 Voronoi Graph Simplification 86
4.4 HAGVG Construction 89
4.5 Admitting Incomplete Information 90
4.6 Improving the Efficiency of the Relevance Computation 92
4.7 Incremental Computation 97
4.8 Application Scenarios 99
4.8.1 Incremental HAGVG Construction 99
4.8.2 Removal of Unstable Parts 99
4.8.3 Automatic Route Graph Generation from Vector Data 99
Chapter 5 Voronoi Graph Matching for Data Association 102
5.1 The Data Association Problem 102
5.1.1 Data Associations and the Interpretation Tree 103
5.1.2 Data Association Approaches 105
5.2 AGVG Matching Based on Ordered Tree Edit Distance 107
5.2.1 Ordered Tree Matching Based on Edit Distance 109
5.2.1.1 Edit Distance for Subtrees in AGVGs 110
5.2.2 Overall Edit Distance 114
5.2.3 Modeling Removal and Addition Costs 115
5.2.4 Optimizations 116
5.2.5 Complexity 116
5.3 Incorporating Constraints 117
5.3.1 Unary Constraints Based on Pose Estimates and Node Similarity 118
5.3.2 Binary Constraints Based on Relative Distance 121
5.3.3 Ternary Angle Constraints 123
5.4 Map Merging Based on a Computed Data Association 126
Chapter 6 Global Mapping: Minimal Route Graphs Under Spatial Constraints 129
6.1 Theoretical Problem 130
6.2 Branch and Bound Search for Minimal Model Finding 139
6.2.1 Search Through the Interpretation Tree 140
6.2.2 Best-First Branch and Bound Search Based on Solution Size 142
6.2.3 Expand and Update Operations 144
6.2.3.1 Update Operation 147
6.2.3.2 Expand Operation 149
6.2.4 Two Variants of the Minimal Model Finding Problem 150
6.3 Pruning Based on Spatial Constraints 152
6.3.1 Checking Planarity 152
6.3.2 Checking Spatial Consistency 155
6.3.2.1 Modeling Spatial Configurations in the Cardinal Direction Calculus 156
6.3.2.2 Modeling Spatial Configurations in the OPRA2 Calculus 157
6.3.3 Incorporation into the Search Algorithm 159
6.4 Combining Minimal Route Graph Mapping and AGVG Representations 160
Chapter 7 Experimental Evaluation 163
7.1 Relevance Assessment and HAGVG Construction 163
7.1.1 Efficiency of the Relevance Computation Algorithms 163
7.1.2 Combining the HAGVG Construction Methods with a Grid-Based FastSLAM Approach 166
7.2 Evaluation of the Voronoi-Based Data Association 168
7.3 Evaluation of the Minimal Route Graph Approach 172
7.3.1 Solution Quality 173
7.3.2 Pruning Efficiency 176
7.3.3 Absolute vs. Relative Direction Information 179
7.3.4 Overall Computational Costs 182
7.3.5 Application to Real AGVG Data 184
7.4 A Complete Multi-hypothesis Mapping System 186
7.4.1 Local Metric Mapping and Local AGVG Computation 186
7.4.2 Data Association for Node Tracking and History Generation 187
7.4.3 Global Mapping and Post-processing 187
7.4.4 Experiments 187
7.4.5 Discussion 188
Chapter 8 Conclusions and Outlook 193
8.1 Summary and Conclusions 193
8.1.1 Extraction and HAGVG Construction 194
8.1.2 Data Association and Matching 195
8.1.3 Minimal Route Graph Model Finding 195
8.1.4 Complete Mapping Approaches 196
8.2 Outlook 197
8.2.1 Extensions of theWork Described in Chaps. 3–6 197
8.2.2 Combining Voronoi Graphs and Uncertainty Handling 198
8.2.3 Challenges for Voronoi-Based Representation Approaches 199
8.2.4 Challenges for Qualitative Spatial Reasoning 201
8.2.5 The Future: Towards Spatially Competent Mobile Robots 201
Appendix A 203
Mapping as Probabilistic State Estimation 203
A.1 The Recursive Bayes Filter 204
A.2 Parametric Filters 206
A.2.1 Kalman Filter 206
A.2.2 Extended Kalman Filter 207
A.3 Nonparametric Filters 208
A.3.1 Particle Filter 208
A.3.2 Rao-Blackwellized Particle Filter and FastSLAM 209
A.3.2.1 Feature-Based FastSLAM 210
A.3.2.2 Grid-Based FastSLAM 210
Appendix B 211
Qualitative Spatial Reasoning 211
B.1 Qualitative Constraint Calculi 211
B.2 Weak vs. Strong Operations 214
B.3 Constraint Networks and Consistency 214
B.4 Checking Consistency 216
Bibliography 218