Dynamic Constraint Satisfaction Problems

The thesis partially fulfills the requirements for the degree of Doctor of Natural Sciences (abbreviation RNDr. before the name) at the Charles University. The thesis deals with the same problem which I studied in my diploma thesis. I have obtained some new interesting results about the studied problem after the successful defence of my diploma thesis. I decided to present these new results with the complete set of experiments in the this thesis. The thesis is structured similarly as my diploma thesis. However it contains more theoretical results, more experimets and the printed version is provided with the CD with complete source code of the experimental constraint satisfaction system and with original experimental results (hundreds of megabytes). Many comments and reviews of the previsous work (diploma thesis and papers) are utilized in this thesis. Comments from other experts was an important contribution to the improvements of the work.

Abstract: Constraint satisfaction problems (CSPs) are a type of combinatorial (optimization) problems that invite much interest in many practical applications. CSP is defined by a set of variables, to which values must be assigned, and a set of constraints that restrict these assignments. Since many problems of practical interest require a dynamic environment, the model of CSP was extended to a dynamic CSP (DCSP), in which the set of variables and/or constraints can be modified during the constraint resolution process. To simplify the constraint satisfaction problem for search algorithms, consistency (filtering) techniques like arc-consistency are usually applied. In this thesis, we study the problem of maintaining arc-consistency in DCSPs. We propose several new dynamic arc-consistency algorithms that yield a better compromise between time and space in comparison to similar existing algorithms like DNAC-4, DNAC-6 and AC|DC. The highlight of the work is a new algorithm that outperforms so far fastest algorithm for maintaining arc consistency in dynamic problems DNAC-6. In order to do performance experiments we have developed a library SPlan written in C++. This library solves DCSPs and the new algorithms as like as the comparable existing ones are implemented as a part of the library. Experimental results on randomly generated DCSPs demonstrate the practical efficiency of our new algorithms.

Here you can download the above abstract and the whole rigoros thesis:

Abstract 

Thesis 

Keywords: constraint programming, dynamic problems, arc consistency, dynamic arc consistency,
DnAC-4, DnAC-6, AC|DC, AC3.1|DC, AC|DC-2, AC|DC-2i