Hierarchical Voronoi Graphs - Spatial Representation and Reasoning for Mobile Robots

Foreword

Preface

Acknowledgements

Contents

Notation

Abbreviations

List of Figures

List of Tables

Chapter 1 Introduction

1.1 The Robot Mapping Problem

1.2 The Spatial Representation Perspective

1.3 The Uncertainty Handling Perspective

1.4 Combining Representation and Uncertainty Handling

1.5 Route Graphs Based on Generalized Voronoi Diagrams

1.6 Theses, Goals, and Contributions of This Book

1.7 Outline of This Book

Chapter 2 Robot Mapping

2.1 A Spatial Model for What?

2.1.1 Navigation

2.1.1.1 Localization

2.1.1.2 Path Planning

2.1.2 Systematic Exploration

2.1.3 Communication

2.2 Correctness, Consistency, and Criteria for Evaluating Spatial Representations

2.2.1 Extractability and Maintainability

2.2.2 Information Adequacy

2.2.3 Efficiency and Scalability

2.3 Spatial Representation and Organization

2.3.1 Basic Spatial Representation Approaches

2.3.2 Coordinate-Based Representations

2.3.2.1 Occupancy-Based Representations

2.3.2.2 Geometric Representations

2.3.2.3 Landmark-Based Representations

2.3.3 Relational Representations

2.3.3.1 View Graph Representations

2.3.3.2 Route Graph Representations

2.3.4 Organizational Forms

2.3.4.1 Plain Representation

2.3.4.2 Overlays

2.3.4.3 Hierarchical Organization

2.3.4.4 Patchworks

2.3.4.5 Combining Different Organizational Forms

2.4 Uncertainty Handling Approaches

2.4.1 Incremental Approaches

2.4.1.1 Single Hypothesis Approaches

2.4.1.2 Complete-State-Space Approaches

2.4.1.3 Multi-hypothesis Approaches

2.4.2 Multi-pass Approaches

2.5 Conclusions

Chapter 3 Voronoi-Based SpatialRepresentations

3.1 Voronoi Diagram and Generalized Voronoi Diagram

3.2 Generalized Voronoi Graph and Embedded Generalized Voronoi Graph

3.3 Annotated Generalized Voronoi Graphs

3.4 Hierarchical Annotated Voronoi Graphs

3.5 Partial and Local Voronoi Graphs

3.6 An Instance of the HAGVG

3.7 Stability Problems of Voronoi-Based Representations

3.8 Strengths andWeaknesses of the Representation

Chapter 4 Simplification and HierarchicalVoronoi Graph Construction

4.1 Relevance Measures for Voronoi Nodes

4.2 Computation of Relevance Values

4.3 Voronoi Graph Simplification

4.4 HAGVG Construction

4.5 Admitting Incomplete Information

4.6 Improving the Efficiency of the Relevance Computation

4.7 Incremental Computation

4.8 Application Scenarios

4.8.1 Incremental HAGVG Construction

4.8.2 Removal of Unstable Parts

4.8.3 Automatic Route Graph Generation from Vector Data

Chapter 5 Voronoi Graph Matching for Data Association

5.1 The Data Association Problem

5.1.1 Data Associations and the Interpretation Tree

5.1.2 Data Association Approaches

5.2 AGVG Matching Based on Ordered Tree Edit Distance

5.2.1 Ordered Tree Matching Based on Edit Distance

5.2.1.1 Edit Distance for Subtrees in AGVGs

5.2.2 Overall Edit Distance

5.2.3 Modeling Removal and Addition Costs

5.2.4 Optimizations

5.2.5 Complexity

5.3 Incorporating Constraints

5.3.1 Unary Constraints Based on Pose Estimates and Node Similarity

5.3.2 Binary Constraints Based on Relative Distance

5.3.3 Ternary Angle Constraints

5.4 Map Merging Based on a Computed Data Association

Chapter 6 Global Mapping: Minimal Route Graphs Under Spatial Constraints

6.1 Theoretical Problem

6.2 Branch and Bound Search for Minimal Model Finding

6.2.1 Search Through the Interpretation Tree

6.2.2 Best-First Branch and Bound Search Based on Solution Size

6.2.3 Expand and Update Operations

6.2.3.1 Update Operation

6.2.3.2 Expand Operation

6.2.4 Two Variants of the Minimal Model Finding Problem

6.3 Pruning Based on Spatial Constraints

6.3.1 Checking Planarity

6.3.2 Checking Spatial Consistency

6.3.2.1 Modeling Spatial Configurations in the Cardinal Direction Calculus

6.3.2.2 Modeling Spatial Configurations in the OPRA2 Calculus

6.3.3 Incorporation into the Search Algorithm

6.4 Combining Minimal Route Graph Mapping and AGVG Representations

Chapter 7 Experimental Evaluation

7.1 Relevance Assessment and HAGVG Construction

7.1.1 Efficiency of the Relevance Computation Algorithms

7.1.2 Combining the HAGVG Construction Methods with a Grid-Based FastSLAM Approach

7.2 Evaluation of the Voronoi-Based Data Association

7.3 Evaluation of the Minimal Route Graph Approach

7.3.1 Solution Quality

7.3.2 Pruning Efficiency

7.3.3 Absolute vs. Relative Direction Information

7.3.4 Overall Computational Costs

7.3.5 Application to Real AGVG Data

7.4 A Complete Multi-hypothesis Mapping System

7.4.1 Local Metric Mapping and Local AGVG Computation

7.4.2 Data Association for Node Tracking and History Generation

7.4.3 Global Mapping and Post-processing

7.4.4 Experiments

7.4.5 Discussion

Chapter 8 Conclusions and Outlook

8.1 Summary and Conclusions

8.1.1 Extraction and HAGVG Construction

8.1.2 Data Association and Matching

8.1.3 Minimal Route Graph Model Finding

8.1.4 Complete Mapping Approaches

8.2 Outlook

8.2.1 Extensions of theWork Described in Chaps. 3–6

8.2.2 Combining Voronoi Graphs and Uncertainty Handling

8.2.3 Challenges for Voronoi-Based Representation Approaches

8.2.4 Challenges for Qualitative Spatial Reasoning

8.2.5 The Future: Towards Spatially Competent Mobile Robots

Appendix A

Mapping as Probabilistic State Estimation

A.1 The Recursive Bayes Filter

A.2 Parametric Filters

A.2.1 Kalman Filter

A.2.2 Extended Kalman Filter

A.3 Nonparametric Filters

A.3.1 Particle Filter

A.3.2 Rao-Blackwellized Particle Filter and FastSLAM

A.3.2.1 Feature-Based FastSLAM

A.3.2.2 Grid-Based FastSLAM

Appendix B

Qualitative Spatial Reasoning

B.1 Qualitative Constraint Calculi

B.2 Weak vs. Strong Operations

B.3 Constraint Networks and Consistency

B.4 Checking Consistency

Bibliography