Hierarchical Voronoi graphs : spatial representation and reasoning for mobile robots /
Wallgrün, Jan Oliver,
Hierarchical Voronoi graphs : spatial representation and reasoning for mobile robots / Jan Oliver Wallgrün. - xxiii, 218 pages : illustrations (some colour) ; 24 cm
Includes bibliographical references.
Introduction -- The Robot Mapping Problem -- The Spatial Representation Perspective -- The Uncertainty Handling Perspective -- Combining Representation and Uncertainty Handling -- Route Graphs Based on Generalized Voronoi Diagrams -- Theses, Goals, and Contributions of This Book -- Outline of This Book -- Robot Mapping -- A Spatial Model for What? -- Navigation -- Systematic Exploration -- Communication -- Correctness, Consistency, and Criteria -- Extractability and Maintainability -- Information Adequacy -- Efficiency and Scalability -- Spatial Representation and Organization -- Basic Spatial Representation Approaches -- Coordinate-Based Representations -- Relational Representations -- Organizational Forms -- Uncertainty Handling Approaches -- Incremental Approaches -- Multi-pass Approaches -- Conclusions -- Voronoi-Based Spatial Representations -- Voronoi Diagram and Generalized Voronoi Diagram -- Generalized Voronoi Graph and Embedded Generalized Voronoi Graph -- Annotated Generalized Voronoi Graphs -- Hierarchical Annotated Voronoi Graphs -- Partial and Local Voronoi Graphs -- An Instance of the HAGVG -- Stability Problems of Voronoi-Based Representations -- Strengths and Weaknesses of the Representation -- Simplification and Hierarchical Voronoi Graph Construction -- Relevance Measures for Voronoi Nodes -- Computation of Relevance Values -- Voronoi Graph Simplification -- HAGVG Construction -- Admitting Incomplete Information -- Improving the Efficiency of the Relevance Computation -- Incremental Computation -- Application Scenarios -- Incremental HAGVG Construction -- Removal of Unstable Parts -- Automatic Route Graph Generation from Vector Data -- Voronoi Graph Matching for Data Association -- The Data Association Problem -- Data Associations and the Interpretation Tree -- Data Association Approaches -- AGVG Matching Based on Ordered Tree Edit Distance -- Ordered Tree Matching Based on Edit Distance -- Overall Edit Distance -- Modeling Removal and Addition Costs -- Optimizations -- Complexity -- Incorporating Constraints -- Unary Constraints Based on Pose Estimates and Node Similarity -- Binary Constraints Based on Relative Distance -- Ternary Angle Constraints -- Map Merging Based on a Computed Data Association -- Global Mapping: Minimal Route Graphs Under Spatial Constraints -- Theoretical Problem -- Branch and Bound Search for Minimal Model Finding -- Search Through the Interpretation Tree -- Best-First Branch and Bound Search Based on Solution Size -- Expand and Update Operations -- Two Variants of the Minimal Model Finding Problem -- Pruning Based on Spatial Constraints -- Checking Planarity -- Checking Spatial Consistency -- Incorporation into the Search Algorithm -- Combining Minimal Route Graph Mapping and AGVG Representations -- Experimental Evaluation -- Relevance Assessment and HAGVG Construction -- Efficiency of the Relevance Computation Algorithms -- Combining the HAGVG Construction Methods with a Grid-Based FastSLAM Approach -- Evaluation of the Voronoi-Based Data Association -- Evaluation of the Minimal Route Graph Approach -- Solution Quality -- Pruning Efficiency -- Absolute vs. Relative Direction Information -- Overall Computational Costs -- Application to Real AGVG Data -- A Complete Multi-hypothesis Mapping System -- Local Metric Mapping and Local AGVG Computation -- Data Association for Node Tracking and History Generation -- Global Mapping and Post-processing -- Experiments -- Discussion -- Conclusions and Outlook -- Summary and Conclusions -- Extraction and HAGVG Construction -- Data Association and Matching -- Minimal Route Graph Model Finding -- Complete Mapping Approaches -- Outlook -- Extensions of the Work Described in Chaps. 3 - -- Combining Voronoi Graphs and Uncertainty Handling -- Challenges for Voronoi-Based Representation Approaches -- Challenges for Qualitative Spatial Reasoning -- The Future: Towards Spatially Competent Mobile Robots -- Mapping as Probabilistic State Estimation -- The Recursive Bayes Filter -- Parametric Filters -- Kalman Filter -- Extended Kalman Filter -- Nonparametric Filters -- Particle Filter -- Rao-Blackwellized Particle Filter and FastSLAM -- Qualitative Spatial Reasoning -- Qualitative Constraint Calculi -- Weak vs. Strong Operations -- Constraint Networks and Consistency -- Checking Consistency. 1. 1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 2. 2.1. 2.1.1. 2.1.2. 2.1.3. 2.2. 2.2.1. 2.2.2. 2.2.3. 2.3. 2.3.1. 2.3.2. 2.3.3. 2.3.4. 2.4. 2.4.1. 2.4.2. 2.5. 3. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 4. 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. 4.8.1. 4.8.2. 4.8.3. 5. 5.1. 5.1.1. 5.1.2. 5.2. 5.2.1. 5.2.2. 5.2.3. 5.2.4. 5.2.5. 5.3. 5.3.1. 5.3.2. 5.3.3. 5.4. 6. 6.1. 6.2. 6.2.1. 6.2.2. 6.2.3. 6.2.4. 6.3. 6.3.1. 6.3.2. 6.3.3. 6.4. 7. 7.1. 7.1.1. 7.1.2. 7.2. 7.3. 7.3.1. 7.3.2. 7.3.3. 7.3.4. 7.3.5. 7.4. 7.4.1. 7.4.2. 7.4.3. 7.4.4. 7.4.5. 8. 8.1. 8.1.1. 8.1.2. 8.1.3. 8.1.4. 8.2. 8.2.1. 8.2.2. 8.2.3. 8.2.4. 8.2.5. Appendix A. 1. 2. 2.1. 2.2. 3. 3.1. 3.2. Appendix B. 1. 2. 3. 4.
3642103022 9783642103025
Robots--Dynamics
Mobile robots--Programming
Voronoi polygons
Spatial data infrastructures
TJ211.4 / .W34 2010
629.893201516
Hierarchical Voronoi graphs : spatial representation and reasoning for mobile robots / Jan Oliver Wallgrün. - xxiii, 218 pages : illustrations (some colour) ; 24 cm
Includes bibliographical references.
Introduction -- The Robot Mapping Problem -- The Spatial Representation Perspective -- The Uncertainty Handling Perspective -- Combining Representation and Uncertainty Handling -- Route Graphs Based on Generalized Voronoi Diagrams -- Theses, Goals, and Contributions of This Book -- Outline of This Book -- Robot Mapping -- A Spatial Model for What? -- Navigation -- Systematic Exploration -- Communication -- Correctness, Consistency, and Criteria -- Extractability and Maintainability -- Information Adequacy -- Efficiency and Scalability -- Spatial Representation and Organization -- Basic Spatial Representation Approaches -- Coordinate-Based Representations -- Relational Representations -- Organizational Forms -- Uncertainty Handling Approaches -- Incremental Approaches -- Multi-pass Approaches -- Conclusions -- Voronoi-Based Spatial Representations -- Voronoi Diagram and Generalized Voronoi Diagram -- Generalized Voronoi Graph and Embedded Generalized Voronoi Graph -- Annotated Generalized Voronoi Graphs -- Hierarchical Annotated Voronoi Graphs -- Partial and Local Voronoi Graphs -- An Instance of the HAGVG -- Stability Problems of Voronoi-Based Representations -- Strengths and Weaknesses of the Representation -- Simplification and Hierarchical Voronoi Graph Construction -- Relevance Measures for Voronoi Nodes -- Computation of Relevance Values -- Voronoi Graph Simplification -- HAGVG Construction -- Admitting Incomplete Information -- Improving the Efficiency of the Relevance Computation -- Incremental Computation -- Application Scenarios -- Incremental HAGVG Construction -- Removal of Unstable Parts -- Automatic Route Graph Generation from Vector Data -- Voronoi Graph Matching for Data Association -- The Data Association Problem -- Data Associations and the Interpretation Tree -- Data Association Approaches -- AGVG Matching Based on Ordered Tree Edit Distance -- Ordered Tree Matching Based on Edit Distance -- Overall Edit Distance -- Modeling Removal and Addition Costs -- Optimizations -- Complexity -- Incorporating Constraints -- Unary Constraints Based on Pose Estimates and Node Similarity -- Binary Constraints Based on Relative Distance -- Ternary Angle Constraints -- Map Merging Based on a Computed Data Association -- Global Mapping: Minimal Route Graphs Under Spatial Constraints -- Theoretical Problem -- Branch and Bound Search for Minimal Model Finding -- Search Through the Interpretation Tree -- Best-First Branch and Bound Search Based on Solution Size -- Expand and Update Operations -- Two Variants of the Minimal Model Finding Problem -- Pruning Based on Spatial Constraints -- Checking Planarity -- Checking Spatial Consistency -- Incorporation into the Search Algorithm -- Combining Minimal Route Graph Mapping and AGVG Representations -- Experimental Evaluation -- Relevance Assessment and HAGVG Construction -- Efficiency of the Relevance Computation Algorithms -- Combining the HAGVG Construction Methods with a Grid-Based FastSLAM Approach -- Evaluation of the Voronoi-Based Data Association -- Evaluation of the Minimal Route Graph Approach -- Solution Quality -- Pruning Efficiency -- Absolute vs. Relative Direction Information -- Overall Computational Costs -- Application to Real AGVG Data -- A Complete Multi-hypothesis Mapping System -- Local Metric Mapping and Local AGVG Computation -- Data Association for Node Tracking and History Generation -- Global Mapping and Post-processing -- Experiments -- Discussion -- Conclusions and Outlook -- Summary and Conclusions -- Extraction and HAGVG Construction -- Data Association and Matching -- Minimal Route Graph Model Finding -- Complete Mapping Approaches -- Outlook -- Extensions of the Work Described in Chaps. 3 - -- Combining Voronoi Graphs and Uncertainty Handling -- Challenges for Voronoi-Based Representation Approaches -- Challenges for Qualitative Spatial Reasoning -- The Future: Towards Spatially Competent Mobile Robots -- Mapping as Probabilistic State Estimation -- The Recursive Bayes Filter -- Parametric Filters -- Kalman Filter -- Extended Kalman Filter -- Nonparametric Filters -- Particle Filter -- Rao-Blackwellized Particle Filter and FastSLAM -- Qualitative Spatial Reasoning -- Qualitative Constraint Calculi -- Weak vs. Strong Operations -- Constraint Networks and Consistency -- Checking Consistency. 1. 1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 2. 2.1. 2.1.1. 2.1.2. 2.1.3. 2.2. 2.2.1. 2.2.2. 2.2.3. 2.3. 2.3.1. 2.3.2. 2.3.3. 2.3.4. 2.4. 2.4.1. 2.4.2. 2.5. 3. 3.1. 3.2. 3.3. 3.4. 3.5. 3.6. 3.7. 3.8. 4. 4.1. 4.2. 4.3. 4.4. 4.5. 4.6. 4.7. 4.8. 4.8.1. 4.8.2. 4.8.3. 5. 5.1. 5.1.1. 5.1.2. 5.2. 5.2.1. 5.2.2. 5.2.3. 5.2.4. 5.2.5. 5.3. 5.3.1. 5.3.2. 5.3.3. 5.4. 6. 6.1. 6.2. 6.2.1. 6.2.2. 6.2.3. 6.2.4. 6.3. 6.3.1. 6.3.2. 6.3.3. 6.4. 7. 7.1. 7.1.1. 7.1.2. 7.2. 7.3. 7.3.1. 7.3.2. 7.3.3. 7.3.4. 7.3.5. 7.4. 7.4.1. 7.4.2. 7.4.3. 7.4.4. 7.4.5. 8. 8.1. 8.1.1. 8.1.2. 8.1.3. 8.1.4. 8.2. 8.2.1. 8.2.2. 8.2.3. 8.2.4. 8.2.5. Appendix A. 1. 2. 2.1. 2.2. 3. 3.1. 3.2. Appendix B. 1. 2. 3. 4.
3642103022 9783642103025
Robots--Dynamics
Mobile robots--Programming
Voronoi polygons
Spatial data infrastructures
TJ211.4 / .W34 2010
629.893201516