Solution reuse in dynamic constraint satisfaction problems - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Access content directly
Conference Papers Year : 1994

Solution reuse in dynamic constraint satisfaction problems

Abstract

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.
No file

Dates and versions

hal-02775349 , version 1 (04-06-2020)

Identifiers

  • HAL Id : hal-02775349 , version 1
  • PRODINRA : 136065

Cite

G. Verfaillie, Thomas Schiex. Solution reuse in dynamic constraint satisfaction problems. American Association for Artificial Intelligence (AAAI), 1994, Seattle, United States. ⟨hal-02775349⟩
7 View
0 Download

Share

Gmail Facebook X LinkedIn More