Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

https://hal.inrae.fr/hal-02775349
Contributor : Migration Prodinra Connect in order to contact the contributor
Submitted on : Thursday, June 4, 2020 - 2:32:29 PM
Last modification on : Friday, June 12, 2020 - 11:32:20 AM

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

9