ebook ebooks e-book e-books downloaden bei MyEbooks.ch downloaden

Hierarchical Voronoi Graphs Spatial Representation and Reasoning for Mobile Robots

:	Jan Oliver Wallgrün
:	Hierarchical Voronoi Graphs Spatial Representation and Reasoning for Mobile Robots
:	Springer-Verlag
:	9783642103452
:	1
:	CHF 85.40
:

:	Maschinenbau, Fertigungstechnik
:	English

:	218
:	Wasserzeichen/DRM
:	PC/MAC/eReader/Tablet
:	PDF

What is space? Is there space when there are objects to occupy it or is there space only when there are no objects to occupy it? Can there be space without objects? These are old philosophical questions that concern the ontology of space in the philosophical sense of 'ontology' - what is the nature of space? Cognitive science in general and arti?cial intelligence in particular are less c- cerned with the nature of things than with their mental conceptualizations. In spatial cognition research we address questions like What do we know about space? How is space represented? What are the representational entities? What are the rep- sentational structures? Answers to these questions are described in what is called ontologies in arti?cial intelligence. Different tasks require different knowledge, and different representations of knowledge facilitate different ways of solving problems. In this book, Jan Oliver Wallgrün develops and investigates representational structures to support tasks of autonomous mobile robots, from the acquisition of knowledge to the use of this knowledge for navigation. The research presented is concerned with the robot mapping problem, the pr- lem of building a spatial representation of an environment that is perceived by s- sors that only provide incomplete and uncertain information; this information usually needs to be related to other imprecise or uncertain information. The routes a robot can take can be abstractly described in terms of graphs where alternative routes are represented by alternative branches in these route graphs.

	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