A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Engineering, School of Advanced Technologies

Thesis (Ph.D.) - Asian Institute of Technology, 1998

CSP over real intervals (ICSP) is an important class of CSP. Several applications involving continuous domains or imprecise data can be formulated as ICSPs. While the key feature of Finite CSPs is the {uFB01}niteness of the domains, the key idea behind solving ICSPS is the "approximation to finiteness" of infinite domains. Although not all basic results from Finite CSPs are applicable to ICSPs, arc-consistency techniques for Finite CSPs can be adapted to ICSPs by some kind of approximation based on Interval Arithmetic. The present research represents an attempt to develop constraint satisfaction algorithms for ICSPs in dynamic environments. For this purpose, we first devise an incremental constraint deletion technique for constraints over real intervals by which recomputation from scratch can be avoided and the time complexity is the same as that of algorithm for constraint addition. This constraint deletion technique helps to bring out the arc-consistency algorithm for dynamic CSPs over real intervals. Then we employ the resultant arc-consistency algorithm as a flat constraint solver in a hierarchy solver for constraint hierarchies over real intervals. The hierarchy solver makes use of dependency information among constraints to detect the possible causes of inconsistencies in the constraint hierarchy. One of the unique feature of this hierarchy solver is that there is a clear division between the flat solver and the hierarchy solver. Thanks to this feature, the hierarchy solver is general and we can adapt it to different domain/constraint speci{uFB01}c flat solvers to produce quickly different hierarchy solvers. The research is also devoted to the design and implementation of an HCLP system over real intervals with locally-predicate-better (lbp) comparator in order to enhance the expressiveness and usefulness of CLP(Intervals). Our prototype HCLP(RI,1pb) interpreter is somewhat close to a full-implementation approach and employs a simpli{uFB01}ed version of the above mentioned hierarchy solver as the constraint solver. Its computational model which is based on a simple operational semantics brings out to a simple and ef{uFB01}cient implementation. Due to the " glass box " approach adopted in the implementation, the interpreter is also extendible.