Efficiently Enforcing Path Consistency on Qualitative Constraint Networks by Use of Abstraction

Efficiently Enforcing Path Consistency on Qualitative Constraint Networks by Use of Abstraction

Michael Sioutis, Jean-François Condotta

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 1262-1268. https://doi.org/10.24963/ijcai.2017/175

Partial closure under weak composition, or partial weak path-consistency for short, is essential for tackling fundamental reasoning problems associated with qualitative constraint networks, such as the satisfiability checking problem, and therefore it is crucial to be able to enforce it as fast as possible. To this end, we propose a new algorithm, called PWCα, for efficiently enforcing partial weak path-consistency on qualitative constraint networks, that exploits the notion of abstraction for qualitative constraint networks, utilizes certain properties of partial weak path-consistency,and adapts the functionalities of some state-of-the-art algorithms to its design. It is worth noting that, as opposed to a related approach in the recent literature, algorithm PWCα is complete for arbitrary qualitative constraint networks. The evaluation that we conducted with qualitative constraint networks of the Region Connection Calculus against a competing state-of-the-art generic algorithm for enforcing partial weak path-consistency, demonstrates the usefulness and efficiency of algorithm PWCα.
Keywords:
Knowledge Representation, Reasoning, and Logic: Geometric, Spatial, and Temporal Reasoning
Knowledge Representation, Reasoning, and Logic: Qualitative Reasoning