Dynamic Path Consistency for Spatial Reasoning

Overview & Synopsis

Dealing with spatial knowledge requires the consistency of spatial information. This consistency is usually enforced by constraint satisfaction techniques including constraint propagation through arc and path consistency. While theses techniques often assume that spatial information are static, this is in general not the case in the real world. Our goal is to propose an approach to maintain the consistency of spatial knowledge in a dynamic environment. To our best knowledge no work in spatial reasoning has addressed this issue. In this paper we use a spatial ontology called SpaceOntology to describe both objects and spatial relations namely topological and distance relations between these objects. Based on a dynamic path consistency algorithm, our proposed method maintains the consistency of spatial information after adding new instances of topological relations described by SpaceOntology of a given environment. In order to evaluate the performance of our dynamic path consistency method, we conducted several tests on instantiations of SpaceOntology in addition to randomly generated spatial constraint problems. The results of these tests demonstrate the efficiency of our method to deal with large size problems in a dynamic environment