Solving Difficult CSPs with Relational Neighborhood Consistency

Robert J. Woodward 1 Shant Karakashian 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 : Freuder and Elfe (1996) introduced Neighborhood Inverse Consistency (NIC) as a strong local consistency property for binary CSPs. While enforcing NIC can significantly filter the variables domains, the proposed algorithm is too costly to be used on dense graphs or for lookahead during search. In this paper, we introduce and characterize Relational Neighborhood Inverse Consistency (RNIC) as a local consistency property that operates on the dual graph of a non-binary CSP. We de- scribe and characterize a practical algorithm for enforcing it. We argue that defining RNIC on the dual graph unveils unsuspected opportunities to reduce the computational cost of our algorithm and increase its filtering effectiveness. We show how to achieve those effects by modifying the topology of the dual graph, yielding new variations the RNIC property. We also introduce an adaptive strategy to automatically select the appro- priate property to enforce given the connectivity of the dual graph. We integrate the resulting techniques as full lookahead strategies in a backtrack search procedure for solving CSPs, and demonstrate the effectiveness of our approach for solving known difficult benchmark problems.
Type de document :
Communication dans un congrès
AAAI'11: Conference on Artificial Intelligence, Aug 2011, San Francisco, California, United States. pp.112-119, 2011
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00748656
Contributeur : Joël Quinqueton <>
Soumis le : lundi 5 novembre 2012 - 17:05:21
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23
Document(s) archivé(s) le : mercredi 6 février 2013 - 03:56:20

Fichier

aaai11.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00748656, version 1

Collections

Citation

Robert J. Woodward, Shant Karakashian, Berthe Y. Choueiry, Christian Bessière. Solving Difficult CSPs with Relational Neighborhood Consistency. AAAI'11: Conference on Artificial Intelligence, Aug 2011, San Francisco, California, United States. pp.112-119, 2011. 〈lirmm-00748656〉

Partager

Métriques

Consultations de la notice

188

Téléchargements de fichiers

232