Revising Qualitative Constraint Networks: Definition and Implementation

Qualitative Spatial and Temporal Reasoning is a central topic in Artificial Intelligence. In particular, it is aimed at application scenarios dealing with uncertain information and thus needs to be able to handle dynamic beliefs. This makes merging and revision of qualitative information important topics. While merging has been studied extensively, revision which describes what is happening when one learns new information about a static world has been overlooked. In this paper, we propose to fill the gap by providing two revision operations for qualitative calculi. In order to implement these operations, we give algorithms for revision and analyze the computational complexity of these problems. Finally, we present an implementation of these algorithms based on a qualitative constraint solver and provide an experimental evaluation.