Qualitative spatial reasoning with topological information(用拓扑信息作定性空间推理)

The LNAI series reports state-of-the-art results in artificial intelligence re-search，development，and education，at a high level and in both printed and electronic form. Enjoying tight cooperation with the R＆D community，with numerous individuals，as well as with prestigious organizations and societies，LNAI has grown into the most comprehensive artificial intelligence research forum available.
The scope of LNAI spans the whole range of artificial intelligence and intelli-gent information processing including interdisciplinary topics in a variety of
application fields. The type of material published traditionally includes
proceedings（published in time for the respective conference）
post-proceedings（consisting of thoroughly revised final full papers）
research monographs（which may be based on PhD work）

在线阅读本书

Spatial knowledge representation and reasoning with spatial knowledge are relevant issues for many application areas such as robotics, geographical information systems, and computer vision. Exceeding purely quantitative approaches, more recently initiated qualitative approaches allow for dealing with spatial information on a more abstract level that is closer to the way humans think and speak.
Starting out with the qualitative, topological constraint calculus RCC8 proposed by Randell, Cui, and Cohn, this work presents answers to a variety of open questions regarding RCC8. The open issues concerning computational properties are solved by exploiting a broad variety of results and methods from logic and theoretical computer science. Questions concerning practical performance are addressed by large-scale empirical computational experiments. The most impressive result is probably the complete classification of computational properties for all fragments of RCC8.

1. Introduction
　1.1 Different Approaches for Representing Spatial Knowledge..
　1.2 Qualitative Spatial Representation and Reasoning
　1.3 Applications and Research Goals of
　　Qualitative Spatial Representation and Reasoning
　1.4 Topological Relations as a Basis for
　　Qualitative Spatial Representation and Reasoning
　1.5 Overview of This Book
2. Background
　2.1 Topology
　2.2 Propositional and First-Order Logics
　　2.2.1 Propositional Logic
　　2.2.2 Propositional Modal Logics
　　2.2.3 First-Order Logic
　2.3 Computational Complexity .
　　2.3.1 Tractability and NP-Completeness
　　2.3.2 Phase Transitions
　2.4 Constraint Satisfaction
　　2.4.1 Binary Constraint Satisfaction Problems and Relation Algebras
　　2.4.2 Relation Algebras Based on JEPD Relations
　2.5 Temporal Reasoning with Allen's Interval Algebra
3. Qualitative Spatial Representation and Reasoning
　3.1 History of Qualitative Spatial Reasoning
　3.2 Principles of Qualitative Spatial Reasoning
　3.3 Different Approaches to Qualitative Spatial Reasoning
　　3.3.1 Topology
　　3.3.2 Orientation
　　3.3.3 Distance
4. The Region Connection Calculus
　4.1 A Spatial Logic Based on Regions and Connection
　4.2 The Region Connection Calculus RCC-8
　4.3 Encoding of RCC-8 in Modal Logic
　4.4 Egenhofer's Approach to Topological Spatial Relations
5. Cognitive Properties of Topological Spatial Relations
　5.1 Psychological Background
　5.2 Empirical Investigation I: Grouping Task with Circular Regions
　　5.2.1 Subjects, Method, and Procedure
　　5.2.2 Results of the First Investigation
　　5.2.3 Discussion
　5.3 Empirical Investigation II: Grouping Task with Polygonal Regions
　　5.3.1 Subjects, Method, and Procedure
　　5.3.2 Results of the Second Investigation
　　5.3.3 Discussion
　5.4 Discussion and Outlook
6. Computational Properties of RCC-8
　6.1 Computational Complexity of RCC-8
　6.2 Transformation of RSAT to SAT
　　6.2.1 Analysis of the Modal Encoding
　　6.2.2 Determining a Particular Kripke Model
　　6.2.3 Transformation to a Classical Propositional Formula
　6.3 Tractable Subsets of RCC-8
　　6.3.1 Identifying a Large Tractable Subset of RCC-8
　　6.3.2 Maximality of 7is with Respect to Tractability
　6.4 Applicability of Path-Consistency
　　6.4.1 Applying Positive Unit Resolution to the Horn Clauses of RCC-8
　　6.4.2 Relating Positive Unit Resolution to Path-Consistency
　　6.4.3 Path-Consistency for the Full Set of Tractable Relations
　6.5 Finding a Consistent Scenario
　6.6 Discussion
7. A Complete Analysis of Tractability in RCC-8
　7.1 A General Method for Proving Tractability of Sets of Relations
　7.2 Candidates for Maximal Tractable Subsets of RCC-8
　7.3 A Complete Analysis of Tractability
　7.4 Finding a Consistent Scenario II: An hnproved Algorithm for All Tractable Subsets
……
8. Empirical Evaluation of Reasoning with RCC-8
9. Representationl Properities of RCC-8
10. Conclusions
A. Enumeration of the Relation of the Maximal Tractable Subsests of RCC-8
References
Index