Proceedings

Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks

Zhiguo Long, Michael Sioutis, Sanjiang Li

Download BibTeX Cite

Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence. Pages 1202-1207.

Abstract

We propose a new algorithm called DPC+ to enforce partial path consistency (PPC) on qualitative constraint networks. PPC restricts path consistency (PC) to a triangulation of the underlying constraint graph of a network. As PPC retains the sparseness of a constraint graph, it can make reasoning tasks such as consistency checking and minimal labelling of large qualitative constraint networks much easier to tackle than PC. For qualitative constraint networks defined over any distributive subalgebra of well-known spatio-temporal calculi, such as the Region Connection Calculus and the Interval Algebra, we show that DPC+ can achieve PPC very fast. Indeed, the algorithm enforces PPC on a qualitative constraint network by processing each triangle in a triangulation of its underlying constraint graph at most three times. Our experiments demonstrate significant improvements of DPC+ over the state-of-the-art PPC enforcing algorithm.

Zhiguo Long, Michael Sioutis, and Sanjiang Li. 2016. Efficient Path Consistency Algorithm for Large Qualitative Constraint Networks. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI-16. IJCAI, 1202–1207. https://ijcai.org/proceedings/2016/174
Welcome Future Conferences AI Journal Division IJCAI Proceedings About IJCAI IJCAI Awards