Solving Dynamic Constraint Satisfaction Problems

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 a new dynamic arc-consistency algorithm that yields a better compromise between time and space in comparison to similar algorithms like DnAC-4, DnAC-6 and AC|DC. In order to do performance experiments we developed a library SPlan written in C++. This library solves DCSPs and the new algorithm is a part of this library. Experimental results on randomly generated DCSPs demonstrate the practical efficiency of our new algorithm.

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

Abstract 

Diploma Thesis 

Keywords: constraint programming, dynamic problems, arc consistency, DnAC-6, AC|DC