Arc-Consistency in Dynamic Constraint Satisfaction Problems

Christian BessièreAAAI 1991

Abstract

Traditional arc-consistency algorithms are efficient for static problems but struggle when constraints are removed, often requiring a full restart. This paper introduces DnAC-4, a dynamic algorithm that tracks "justifications" for value deletions, allowing it to incrementally restore valid values when constraints are relaxed—drastically reducing redundant computation in evolving environments.

Introduction

Constraint Satisfaction Problems (CSPs) are fundamental to AI, modeling complex tasks like scheduling and design. Since solving CSPs is NP-complete, "filtering" techniques like arc-consistency are employed to prune values that cannot be part of a solution. However, standard algorithms assume a static problem. In real-world Dynamic CSPs (DCSPs), constraints are frequently added or removed. While algorithms like AC-4 handle additions incrementally, they lack the memory to handle removals efficiently, often necessitating a full restart. This paper proposes DnAC-4 to provide true incrementality for both constraint addition and relaxation.

The DnAC-4 Algorithm

DnAC-4 evolves the classic AC-4 algorithm by incorporating justifications, a concept from Truth Maintenance Systems (TMS).

Justification and Relaxation

During constraint addition (restriction), DnAC-4 records the specific constraint responsible for each value deletion. When a constraint is removed (relaxation), the algorithm consults these justifications. If a value was deleted solely due to the removed constraint, it is restored to the domain.

Justification tracking in DnAC-4: recording the specific constraints that cause value deletions.

To maintain consistency, the algorithm ensures "well-foundedness," preventing circular logic in deletions. While recording justifications requires more initial memory and computation, this "investment" pays off during relaxation by avoiding redundant work.

Experimental Evaluation

The algorithm was tested on randomly generated DCSPs defined by connectivity ($pc$) and compatibility ($pu$). Tests spanned various variable counts (8, 12, 16) and domain sizes.

Key Results

DnAC-4 consistently outperformed AC-4 in dynamic scenarios. The primary metric was the reduction in consistency checks.

Performance comparison: DnAC-4 shows significant gains in consistency checks compared to restarting AC-4.

As shown in the results, DnAC-4 achieved a gain of 46% to 49% across most problem classes. Even after a single relaxation, the time saved by incremental restoration outweighed the overhead of tracking justifications during the restriction phase.

Conclusion

DnAC-4 demonstrates that treating constraint satisfaction as a logical dependency system allows for efficient handling of dynamic environments. While currently focused on binary constraints, the principles are extensible. Future work involves testing on real-world datasets, such as peptide synthesis planning, where propagation chains may offer even greater opportunities for optimization.

Summary updated

BibTeX
@inproceedings{bessiere1991arc,
  author = {Christian Bessière},
  title = {{Arc-Consistency in Dynamic Constraint Satisfaction Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}

Loading related content...

Figure