Efficiently Reasoning about Qualitative Constraints through Variable Elimination
Lists
Only you see this
Abstract
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 enforces a particular directional local consistency on N, 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.
BibTeX
@inproceedings{sioutis2016efficiently,
author = {Michael Sioutis and Zhiguo Long and Sanjiang Li},
title = {{Efficiently Reasoning about Qualitative Constraints through Variable Elimination}},
booktitle = {SETN},
year = {2016},
doi = {10.1145/2903220.2903226},
}