Multi-Hierarchical Representation of Large-Scale Space

by Fernandez, Juan A.; Gonzalez, Javier

• ISBN13: 9781402001055
• ISBN10: 1402001053
• Format: Hardcover
• Copyright: 2001-11-01
• Publisher: Kluwer Academic Pub

Summary

This book formalizes multiple abstraction (arranging knowledge hierarchically using more than one hierarchy) based on graphs, and studies in-depth its implications in path search, graph isomorphism, and in the automatic construction of multi-hierarchical structures. It also describes its application as a model of the large-scale space environment of mobile robots, including real mobile robots and a well-known computational model of the human cognitive map: the Spatial Semantic Hierarchy. This book is intended for PhD students and in general for robotics, computer science, and artificial intelligence researchers.

Table of Contents

Introduction	1	(8)
Abstraction and Hierarchies of Abstraction	1	(2)
Multiple Abstraction and the Task-Driven Paradigm	3	(4)
Contents of this Book	7	(2)
Hierarchies of Abstraction in Literature	9	(8)
Large-Scale Space Modeling	9	(3)
Artificial Intelligence	12	(1)
Cognitive Science	13	(1)
Other Areas	14	(3)
A Formal Model of Multiple Abstraction	17	(54)
Motivation	17	(2)
Formalization of the Plain Graph Model	19	(9)
Basic Definitions	19	(1)
The Set of Costs	20	(1)
Optimality of Costs	21	(1)
Paths	21	(2)
Path Searching in Plain Graphs	23	(2)
Other Path Searching Schemes	25	(2)
NP-Completeness in Plain Graphs	27	(1)
Formalization of the Hierarchical Graph Model	28	(14)
Definitions Concerning Hierarchical Concepts	28	(1)
Definitions Concerning Nodes	29	(1)
Abstraction Function for Nodes	30	(1)
Chains of Abstraction	31	(1)
Clusters and Subgraphs	31	(1)
Annotations	32	(1)
Definitions Concerning Arcs	33	(1)
Abstraction Function for Arcs	33	(1)
Classification of Arcs	34	(1)
Annotations	35	(1)
Cost Intervals	35	(2)
Different Hierarchical Levels to See the Same Information	37	(1)
Paths in AH-graphs	38	(1)
Abstracting Paths	39	(1)
Refining Paths	40	(1)
Classes of Hierarchical Graphs	41	(1)
Connected AH-graphs	41	(1)
AH-graphs with and without Forgetfulness	41	(1)
Complete AH-graphs	42	(1)
Formalization of the Multihierarchical Graph Model	42	(6)
General Definitions	43	(1)
Multihierarchies	43	(3)
Abstraction Paths in Multihierarchies	46	(1)
Labelled Multi-AH-graphs	47	(1)
Some implementation Issues of the Multi-AH-graph Model	48	(20)
Automatic Construction of the Multi-AH-graph Model	48	(1)
Automatic Clustering	49	(1)
Automatic Relations	50	(1)
Automatic Optimization of Multihierarchies	51	(1)
Storage Issues	52	(1)
Validating the Model	53	(1)
Isomorphism Implementation	54	(7)
Implementation of H-isomorphism	61	(4)
H-isomorphism in Multihierarchies with Several Ground Levels	65	(1)
Relation Between Isomorphism and H-isomorphism	65	(1)
When Does H-Isomorphism Imply Conventional Isomorphism?	66	(1)
When Does Conventional Isomorphism Imply H-Isomorphism?	67	(1)
Summary	68	(3)
Hierarchical Path Search	71	(44)
Hierarchical Path Search in Single Hierarchies	72	(1)
Algorithms for Hierarchical Path Search	73	(2)
Classic Refinement	73	(1)
Path Marking	74	(1)
Alternating Opportunism	74	(1)
Left-Wedge	74	(1)
Mixed Methods	74	(1)
Pros and Cons of Hierarchical Path Search	75	(5)
Problem Dependency	75	(1)
Sub-Optimality	76	(1)
Bad Clustering	77	(1)
Hierarchical Backtracking	78	(2)
Hierarchical Path Search in AH-graphs	80	(9)
A General Hierarchical Path Search Algorithm	83	(5)
More Specific Hierarchical Path Search Algorithms	88	(1)
Optimality of Hierarchical Path Search in AH-graphs	89	(5)
Optimality of Paths in Algorithms Without Materialization of Costs	90	(2)
Optimality of Paths in Algorithms With Materialization of Costs	92	(2)
Some Conclusions on the Optimality of Hierarchical Path Search in AH-graphs	94	(1)
Computational Cost of Hierarchical Path Search	94	(1)
Classification of Search Problems	95	(3)
Goodness of Hierarchical Path Search	98	(1)
Hierarchical Path Search in Multiple Hierarchies	98	(13)
Solving a Single Search Problem in a Multihierarchy	99	(1)
Experiments	100	(3)
Sovling Multiple Search Problems in a Multihierarchy	103	(3)
Experiments	106	(1)
Multiple Representations in a Multihierarchy	107	(4)
Summary	111	(4)
Automatic Generation of Multiple Hierarchies of Abstraction	115	(56)
Task-Driven Automatic Construction of Hierarchies	115	(8)
The Task-Driven Paradigm for Multiple Hierarchy Construction	116	(1)
Obtaining Hierarchical Information	117	(2)
Problems of the Task-Driven Paradigm	119	(2)
Utility of the Task-Driven Paradigm	121	(2)
Overview of CLAUDIA	123	(2)
The Ground Information Interface (GI2)	125	(4)
Information Provided by the GI2	125	(1)
Ground Concepts	126	(1)
Ground Relations	126	(1)
Implementation Issues of the GI2	127	(1)
Complex Relations	127	(1)
Percept Equality	128	(1)
Forgetfulness / Reinforcement of Ground Information	129	(1)
The Abstraction Construction and Optimization Subsystem (ACO)	129	(32)
The Clustering Module	129	(1)
OEET (Optimality Edge Elimination Test) Algorithm	130	(1)
OSHA (Optimal Search Hierarchy Approach) Algorithm	130	(1)
Seed-Size Algorithm	130	(1)
Cohesion Forces Algorithm	131	(1)
Partition Enumeration Algorithm	132	(1)
Approximation Algorithms to NP-Complete Clustering Problems	133	(2)
The Single-Hierarchy Constructor Module	135	(1)
Type of the Arcs	136	(1)
Label of the Hierarchy in the Multihierarchy	136	(1)
Parameters for H-Isomorphism Detection	136	(1)
Procedures for Abstracting Annotations	137	(5)
The Multihierarchy Optimizer Module	142	(2)
A Definition of the ``Goodness'' of a Multihierarchy	144	(1)
Agent, Environment, and Task Define ``Goodness''	144	(1)
Classification of Search Problems	145	(1)
Prediction of the Computational Cost of Solving a Search Problem	146	(2)
Calculating the Goodness of a Multihierarchy	148	(2)
The Space of Multihierarchies	150	(2)
Exploring the Neighbours of a Multihierarchy	152	(1)
Utility of the Hierarchies of a Multihierarchy	153	(1)
Algorithms for Multihierarchy Optimization	154	(1)
Optimization of Multihierarchies by Hill-Climbing	154	(2)
Generation of the Neighbours of a Multihierarchy	156	(3)
Other Techniques for the Optimization of Multihierarchies	159	(2)
Evaluation of the Automatic Multiple Abstraction System	161	(7)
Summary	168	(3)
Multiple Hierarchies of Abstraction for Mobile Robots	171	(32)
Large-Scale Space Modeling for Mobile Robots	171	(3)
A Mobile Robot with a Model of Large-Scale Space	174	(14)
Formalizing the Connection Between CLAUDIA and the SSH	188	(14)
The Spatial Semantic Hierarchy	189	(4)
Formalizing Regions at the SSH Topological Level	193	(6)
Connecting the SSH Topological Level to CLAUDIA	199	(3)
Summary	202	(1)
Conclusions	203	(6)
Appendix A. NP-Completeness Overview	209	(4)
Appendix B. Algorithm for Hierarchical Path Search	213	(8)
Appendix C. The Cohesion Forces Clustering Algorithm	221	(4)
Appendix D. The OEET Clustering Algorithm	225	(20)
D.1. Introduction	225	(1)
D.2. The OEET Algorithm	226	(19)
D.2.1. First Stage: Retrieving Path Information	229	(1)
D.2.2. Second Stage: Arc-Elimination Test and Arc-Erasing Process	230	(1)
Behaviour of the Optimal Paths	231	(1)
Behaviour of the Non-Optimal Paths	232	(13)
Appendix E. Computational Cost of Hierarchical Path Search	245	(10)
E.1. Computational Cost in Hierarchies with Two Hierarchical Levels	246	(6)
E.2. Computational Cost in Hierarchies with More Than Two Hierarchical Levels	252	(3)
Appendix F. Sufficient Condition for Optimality When There is No Materialization of Costs	255	(6)
F.1. When the Cost of Refining Paths is a Constant	256	(1)
F.2. When the Cost of Refining Paths is Bounded by the Costs of the Arcs	257	(4)
References	261	(12)
Index	273