Skip to Main content Skip to Navigation
Journal articles

Nogood recording for static and dynamic constraint satisfaction problems

Abstract : Many AI synthesis problems such as planning, scheduling or design may be encoded in a constraint satisfaction problems (CSP). A CSP is typically defined as the problem of finding any consistent labeling for a fixed set of variables satisfying all given constraints between these variables. However, for many real tasks, the set of constraints to consider may evolve because of the environment or because of user interactions. The notion of dynamic cCSP (DCSP) [DD88 has been proposed to represent such evolutions. The problem we consider here is the solution maintenance problem in a DCSP. Naively applying usual satisfaction algorithms to this problem results in redundant search and inefficiency. A general approach to suppress redundancies in case of both restrictions and relaxations is to concisely represent the frontier of the solution space and justifications of this frontier in terms of set of constraints. This paper proposes a new class of constraint recording algorithms called nogood recording that may be used for solving both dynamic CSPs and usual CSP (called static CSPs here). It offers an interesting compromise, polynomially bounded in space, between an ATMS-like (Assumption-based Truth Maintenance System) approach, that would give a precise and exhaustive description of the frontier, and the usual constraint satisfaction algorithms (that discover a new frontier at each execution). We first introduce the principles used for nogood generation and then examine various recording schemes, on top of different tree search algorithms, characterizing the tradeoffs between the amount of recorded constraints and the pruning achieved. We then present experimental results and comparisons with various existing techniques for solving static or dynamic CSP.
Document type :
Journal articles
Complete list of metadata

https://hal.inrae.fr/hal-02709865
Contributor : Migration Prodinra Connect in order to contact the contributor
Submitted on : Monday, June 1, 2020 - 5:02:58 PM
Last modification on : Friday, June 12, 2020 - 11:32:20 AM

Identifiers

  • HAL Id : hal-02709865, version 1
  • PRODINRA : 136062

Collections

Citation

Thomas Schiex, G. Verfaillie. Nogood recording for static and dynamic constraint satisfaction problems. International Journal on Artificial Intelligence Tools, World Scientific Publishing, 1994, 3 (2), pp.187-207. ⟨hal-02709865⟩

Share

Metrics

Record views

15