A Reactive Strategy for High-Level Consistency During Search - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Conference Papers Year : 2018

A Reactive Strategy for High-Level Consistency During Search

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.
Fichier principal
Vignette du fichier
0193.pdf (482.82 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-01897930 , version 1 (17-10-2018)

Identifiers

Cite

Robert J. Woodward, Berthe Y. Choueiry, Christian Bessiere. 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⟩
152 View
129 Download

Altmetric

Share

Gmail Mastodon Facebook X LinkedIn More