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 metadata

Cited literature [4 references]  Display  Hide  Download
Contributor : Christian Bessiere Connect in order to contact the contributor
Submitted on : Wednesday, October 17, 2018 - 5:27:49 PM
Last modification on : Monday, October 11, 2021 - 1:24:08 PM
Long-term archiving on: : Friday, January 18, 2019 - 3:37:11 PM


Files produced by the author(s)




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⟩



Record views


Files downloads