Solution Reuse in Dynamic Constraint Satisfaction Problems

Constraint Satisfaction

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Advances in Backtracking

Many AI problems can be modeled as constraint satisfaction problems (CSP), but many of them are actually dynamic: the set of constraints to consider evolves because of the environment, the user or other agents in the framework of a distributed system. In this context, computing a new solution from scratch after each problem change is possible, but has two important drawbacks: inefficiency and instability of the successive solutions. In this paper, we propose a method for reusing any previous solution and producing a new one by local changes on the previous one. First we give the key idea and the corresponding algorithm. Then we establish its properties: termination, correctness and completeness. We show how it can be used to produce a solution, either from an empty assignment, or from any previous assignment and how it can be improved using filtering or learning methods, such as forward-checking or nogood-recording. Experimental results related to efficiency and stability are given, with comparisons with well known algorithms such as backtrack, heuristic repair or dynamic backtracking.