Leveraging Variable Elimination for Efficiently Reasoning about Qualitative Constraints

摘要

We introduce, study, and evaluate a novel algorithm in the context of qualitative constraint-based spatial and temporal reasoning that is based on the idea of variable elimination, a simple and general exact inference approach in probabilistic graphical models. Given a qualitative constraint network N, our algorithm utilizes a particular directional local consistency, which we denote by (sic)-consistency, in order to efficiently decide the satisfiability of N. Our discussion is restricted to distributive subclasses of relations, i.e., sets of relations closed under converse, intersection, and weak composition and for which weak composition distributes over non-empty intersections for all of their relations. We demonstrate that enforcing (sic)-consistency in a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability, and obtain similar useful results for the problems of minimal labelling and redundancy. Further, we present a generic method that allows extracting a scenario from a satisfiable network, i.e., an atomic satisfiable subnetwork of that network, in a very simple and effective manner. The experimentation that we have conducted with random and real-world qualitative constraint networks defined over a distributive subclass of relations of the Region Connection Calculus and the Interval Algebra, shows that our approach exhibits unparalleled performance against state-of-the-art approaches for checking the satisfiability of such constraint networks.