Skip to Main content Skip to Navigation
Conference papers

A Reactive Strategy for High-Level Consistency During Search

Robert J. Woodward 1 Berthe Y. Choueiry 1 Christian Bessière 2
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Constraint propagation during backtrack search significantly improves the performance of solving a Constraint Satisfaction Problem. While Generalized Arc Consistency (GAC) is the most popular level of propagation, higher-level consistencies (HLC) are needed to solve difficult instances. Deciding to enforce an HLC instead of GAC remains the topic of active research. We propose a simple and effective strategy that reactively triggers an HLC by monitoring search performance: When search starts thrashing, we trigger an HLC, then conservatively revert to GAC. We detect thrashing by counting the number of backtracks at each level of the search tree and geometrically adjust the frequency of triggering an HLC based on its filtering effectiveness. We validate our approach on benchmark problems using Partition-One Arc-Consistency as an HLC. However, our strategy is generic and can be used with other higher-level consistency algorithms.
Document type :
Conference papers
Complete list of metadatas

Cited literature [4 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01897930
Contributor : Christian Bessiere <>
Submitted on : Wednesday, October 17, 2018 - 5:27:49 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Long-term archiving on: : Friday, January 18, 2019 - 3:37:11 PM

File

0193.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Robert J. Woodward, Berthe Y. Choueiry, Christian Bessière. A Reactive Strategy for High-Level Consistency During Search. IJCAI: International Joint Conference on Artificial Intelligence, Jul 2018, Stockholm, Sweden. pp.1390-1397, ⟨10.24963/ijcai.2018/193⟩. ⟨lirmm-01897930⟩

Share

Metrics

Record views

196

Files downloads

169