Premium
HIERARCHICAL ARC CONSISTENCY FOR DISJOINT REAL INTERVALS IN CONSTRAINT LOGIC PROGRAMMING
Author(s) -
Sidebottom Greg,
Havens William S.
Publication year - 1992
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1992.tb00381.x
Subject(s) - local consistency , constraint logic programming , computer science , consistency (knowledge bases) , constraint programming , disjoint sets , constraint (computer aided design) , theoretical computer science , constraint satisfaction , algorithm , programming language , mathematical optimization , artificial intelligence , mathematics , geometry , combinatorics , probabilistic logic , stochastic programming
There have been many proposals for adding sound implementations of numeric processing to Prolog. This paper describes an approach to numeric constraint processing which has been implemented in Echidna, a new constraint logic programming (CLP) language. Echidna uses consistency algorithms which can actively process a wider variety of numeric constraints than most other CLP systems, including constraints containing some common nonlinear functions. A unique feature of Echidna is that it implements domains for real‐valued variables with hierarchical data structures and exploits this structure using a hierarchical arc consistency algorithm specialized for numeric constraints. This gives Echidna two advantages over other systems. First, the union of disjoint intervals can be represented directly. Other approaches require trying each disjoint interval in turn during backtrack search. Second, the hierarchical structure facilitates varying the precision of constraint processing. Consequently, it is possible to implement more effective constraint processing control algorithms which avoid unnecessary detailed domain analysis. These advantages distinguish Echidna from other CLP systems for numeric constraint processing.