Efficient path consistency algorithm for large qualitative constraint networks

AAAI Press
Publication Type:
Conference Proceeding
Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, 2016, 2016-January pp. 1202 - 1208
Issue Date:
Full metadata record
Files in This Item:
Filename Description Size
174.pdfPublished version630.68 kB
Adobe PDF
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.
Please use this identifier to cite or link to this item: