Skip to Main content Skip to Navigation
Conference papers

Cycle-Based Singleton Local Consistencies

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 : We propose to exploit cycles in the constraint network of a Constraint Satisfaction Problem (CSP) to vehicle constraint propagation and improve the effectiveness of local consistency algorithms. We focus our attention on the consistency property Partition-One Arc-Consistency (POAC), which is a stronger variant of Singleton Arc-Consistency (SAC). We modify the algorithm for enforcing POAC to operate on a minimum cycle basis (MCB) of the incidence graph of the CSP. We empirically show that our approach improves the performance of problem solving and constitutes a novel and effective localization of consistency algorithms. Although this paper focuses on POAC, we believe that exploiting cycles, such as MCBs, is applicable to other consistency algorithms and that our study opens a new direction in the design of consistency algorithms. This research is documented in a technical report (Woordward, Choueiry, and Bessiere 2016).
Document type :
Conference papers
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01711585
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 18, 2018 - 11:06:43 AM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM
Document(s) archivé(s) le : Saturday, January 19, 2019 - 1:22:13 PM

File

14655-66728-1-PB.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-01711585, version 1

Collections

Citation

Robert J. Woodward, Berthe Y. Choueiry, Christian Bessière. Cycle-Based Singleton Local Consistencies. AAAI Conference on Artificial Intelligence, Feb 2017, San Francisco, United States. pp.5005-5006. ⟨lirmm-01711585⟩

Share

Metrics

Record views

147

Files downloads

15