0 avis
Solution reuse in dynamic constraint satisfaction problems
Archive ouverte
Edité par CCSD -
* INRA - Unité de Biométrie, Centre de Toulouse (FRA) Diffusion du document : INRA - Unité de Biométrie, Centre de Toulouse (FRA). International audience. 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.
Consulter en ligne
Suggestions
Du même auteur
