Efficient Methods for Qualitative Spatial Reasoning

摘要

The theoretical properties of qualitative spatial reasoning in the RCC8framework have been analyzed extensively. However, no empirical investigationhas been made yet. Our experiments show that the adaption of the algorithmsused for qualitative temporal reasoning can solve large RCC8 instances, even ifthey are in the phase transition region -- provided that one uses the maximaltractable subsets of RCC8 that have been identified by us. In particular, wedemonstrate that the orthogonal combination of heuristic methods is successfulin solving almost all apparently hard instances in the phase transition regionup to a certain size in reasonable time.