Hierarchical Voronoi graphs : spatial representation and reasoning for mobile robots / Jan Oliver Wallgrün.

Includes bibliographical references.

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 -- 2. Robot Mapping -- 2.1. A Spatial Model for What? -- 2.1.1. Navigation -- 2.1.2. Systematic Exploration -- 2.1.3. Communication -- 2.2. Correctness, Consistency, and Criteria -- 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.3. Relational Representations -- 2.3.4. Organizational Forms -- 2.4. Uncertainty Handling Approaches -- 2.4.1. Incremental Approaches -- 2.4.2. Multi-pass Approaches -- 2.5. Conclusions -- 3. Voronoi-Based Spatial Representations -- 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 and Weaknesses of the Representation -- 4. Simplification and Hierarchical Voronoi 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 -- 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.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 -- 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.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.3. Incorporation into the Search Algorithm -- 6.4. Combining Minimal Route Graph Mapping and AGVG Representations -- 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 -- 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 the Work Described in Chaps. 3 - -- 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 -- 1. The Recursive Bayes Filter -- 2. Parametric Filters -- 2.1. Kalman Filter -- 2.2. Extended Kalman Filter -- 3. Nonparametric Filters -- 3.1. Particle Filter -- 3.2. Rao-Blackwellized Particle Filter and FastSLAM -- Appendix B. Qualitative Spatial Reasoning -- 1. Qualitative Constraint Calculi -- 2. Weak vs. Strong Operations -- 3. Constraint Networks and Consistency -- 4. Checking Consistency.

Machine converted from AACR2 source record.