Consistency techniques in constraint networks

Abstract

Consistency techniques play an important role in studying constraint networks. We focus on two aspects of them: consistency as a pruning tool and consistency as a tool to relate local consistency and global consistency. For the first aspect, we mainly study arc consistency (AC). We find a simple and worst case optimal implementation for a well known algorithm AC-3. To enforce arc consistency on non-binary constraints is NP-hard. A class of monotonic constraints is identified and a polynomial AC algorithm is designed for them. For the second aspect, we relate consistency to set intersection. This relation allows us not only to unify several well-known results on consistency in a network but also to derive new results on consistency in a network from set intersection properties. For example we identify a tree convex network where a certain level of local consistency guarantees global consistency. It is also found that a properly m-tight constraint network can be made globally consistent after enforcing some level of local relational consistency. Another line of our work on the second aspect is the development of efficient and elegant algorithms for functional constraints and implicational constraints.