Collective Singleton-based Consistency for Qualitative Constraint Networks: Theory and Practice
Michael Sioutis (Örebro University)
11 oct. 2018 - 14:00Partial singleton weak path-consistency is essential for tackling challenging fundamental reasoning problems associated with qualitative constraints networks. Briefly put, partial singleton weak path-consistency ensures that each base relation of each of the constraints of a qualitative constraint network can define a singleton relation in its corresponding partially weakly path-consistent subnetwork. In this talk, we propose a stronger local consistency that couples partial singleton weak path-consistency with the idea of collectively deleting certain unfeasible base relations by exploiting singleton checks. We then propose an algorithm for enforcing this new consistency and a lazy variant of that algorithm for approximating the new consistency, both of which outperform the respective algorithm for enforcing partial singleton weak path-consistency in a given qualitative constraint network . With respect to the lazy algorithmic variant in particular, we show that it runs up to 5 times faster than our original exhaustive algorithm whilst exhibiting very similar pruning capability. We formally prove certain properties of our new local consistency and our algorithms, and motivate their usefulness through demonstrative examples and a thorough experimental evaluation with random qualitative constraint networks of the Interval Algebra and the Region Connection Calculus from the phase transition region of two different generation models. Finally, we provide evidence of the crucial role of the new consistency in tackling the minimal labeling problem of a qualitative constraint network, which is the problem of finding the strongest implied constraints of that network.