CP as a General-Purpose Constraint-Language

Book One

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 6

AI Architectures

In this paper we present the notion of concurrent, controllable constraint systems. We argue that purely declarative search formalisms, whether they are based on dependency-directed backtracking (as in Steele [Steele, 1980] or Bruynooghe [Bruynooghe and Pereira, 1985]) or bottom-up breadth-first (albeit incremental) definite clause theorem provers (as in deKleer’s ATM approach [deKleer, 1986]) or built-in general purpose heuristics (as in Laurier’s work [Lauriere, 1978]) are unlikely to be efficient enough to serve as the basis of a general purpose programming formalism which supports the notion of constraint-based computation. To that end we propose the programming language CP[!,1,&], based on the concurrent interpretation of definite clauses, which allows the user to express domain-specific heuristics and control the forward search process based on eager propogation of constraints and early detection of determinacy and contradiction. This control follows naturally from the alternate metaphor of viewing constraints as processes that communicate by exchanging messages. The language, in addition, allows for the dynamic generation and hierarchical specification of constraints, for concurrent exploration of alternate solutions, for pruning and merging sub-spaces and for expressing preferences over which portions of the search space to explore next.