TY  - BOOK
AU  - Wallgrün,Jan Oliver
TI  - Hierarchical Voronoi graphs: spatial representation and reasoning for mobile robots 
SN  - 3642103022
AV  - TJ211.4 .W34 2010
U1  - 629.893201516 22
PY  - 2010///]
CY  - Heidelberg, London
PB  - Springer
KW  - Robots
KW  - Dynamics
KW  - Mobile robots
KW  - Programming
KW  - Voronoi polygons
KW  - Spatial data infrastructures
N1  - 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
ER  -