Efficient path consistency algorithm for large qualitative constraint networks

Zhiguo Long, Michael Sioutis, Sanjiang Li

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.
BibTeX
@inproceedings{long2016efficient,
  author = {Zhiguo Long and Michael Sioutis and Sanjiang Li},
  title = {{Efficient path consistency algorithm for large qualitative constraint networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=H1WFDXMOWH},
}

Loading related content...

Figure