Efficiently reasoning about qualitative constraints through variable elimination
- Publication Type:
- Conference Proceeding
- Citation:
- ACM International Conference Proceeding Series, 2016, 18-20-May-2016
- Issue Date:
- 2016-05-18
Open Access
Copyright Clearance Process
- Recently Added
- In Progress
- Open Access
This item is open access.
© 2016 ACM. 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 M, our algorithm enforces a particular directional local consistency on M, which we denote by ←-consistency. 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 ←-consistency on a given qualitative constraint network defined over a distributive subclass of relations allows us to decide its satisfiability. 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, shows that our approach exhibits unparalleled performance against competing state-of-the-art approaches for checking the satisfiability of such constraint networks.
Please use this identifier to cite or link to this item: