Path-Consistency: When Space Misses Time

No. 1: Agents, AI in Art and Entertainment, Knowledge Representation, and Learning

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 13

Data Consistency

Within the framework of constraint programming, particulary concerning the Constraint Satisfaction Problems (CSPs), the techniques of preprocessing based on filtering algorithms were shown to be very important for the search phase. In particular, two filtering methods have been studied, these methods exploit two properties of local consistency: arc- and path-consistency. Concerning the arc-consistency methods, there is a linear time algorithm (in the size of the problem) which is efficient in practice (Bessiere, Freuder, and Régin 1995). But the limitations of the arc-consistency algorithms requires often filtering methods with higher order like path-consistency filterings. The best path-consistency algorithm proposed is PC-6, a natural generalization of AC-6 to path-consistency. Its time complexity is O(n^3d^3) and its space complexity is O(n^3d^2), where n is the number of variables and d is the size of domains. We have remarked that PC-6, though it is widely better than PC-4, was not very efficient in practice, specialy for those classes of problems that require an important space to be run. Therefore, we propose here a new path-consistency algorithm called PC-7, its space complexity is O(n2d2) but its time complexity is O(n^3d^4) i.e. worse than that of PC-6. However, the simplicity of PC-7 as well as the data structures used for its implementation offer really a higher performance than PC-6. Furthermore, it turns out that when the size of domains is a constant of the problems, the time compPexity of PC-7 becomes, like PC-6, optimal i.e. O(n^3).