INTELLIGENT BACKTRACKING IN CLP(R)

CLP(R) is a constraint logic programming language in which constraints can be expressed in the domain of real numbers. Computation in this s pecialized domain gives access to information useful in intelligent ba cktracking. In this paper, we present an efficient constraint satisfac tion algorithm for linear constraints in the real number domain and sh ow that our algorithm directly generates minimal sets of conflicting c onstraints when failures occur. We demonstrate how information gleaned during constraint satisfaction can be integrated with unification fai lure analysis. The resulting intelligent backtracking method works in the context of a two-sorted domain, where variables can be bound to ei ther structured terms or real number expressions. We discuss the imple mentation of backtracking and show examples where the benefit of pruni ng the search tree outweighs the overhead of failure analysis.