A General Framework for Reordering Agents Asynchronously in Distributed CSP

Mohamed Wahbi 1 Younes Mechqrane 2 Christian Bessière 3 Kenneth N. Brown
1 UCC - University College Cork
2 LIMIARF - Laboratoire d'Informatique, Mathématiques appliquées, Intelligence Artificielle et Reconnaissance de Formes
3 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Reordering agents during search is an essential component of the efficiency of solving a distributed constraint satisfaction prob- lem. Termination values have been recently proposed as a way to sim- ulate the min-domain dynamic variable ordering heuristic. The use of termination values allows the greatest flexibility in reordering agents dy- namically while keeping polynomial space. In this paper, we propose a general framework based on termination values for reordering agents asynchronously. The termination values are generalized to represent var- ious heuristics other than min-domain. Our general framework is sound, complete, terminates and has a polynomial space complexity. We im- plemented several variable ordering heuristics that are well-known in centralized CSPs but could not until now be applied to the distributed setting. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP.
Type de document :
Communication dans un congrès
CP: Principles and Practice of Constraint Programming, Sep 2015, Cork, Ireland. 21st International Conference on Principles and Practice of Constraint Programming 2015
Liste complète des métadonnées
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01276190
Contributeur : Joël Quinqueton <>
Soumis le : jeudi 18 février 2016 - 22:35:47
Dernière modification le : jeudi 11 janvier 2018 - 06:26:23

Identifiants

  • HAL Id : lirmm-01276190, version 1

Collections

LIRMM | COCONUT | MIPS | UNIV-MONTPELLIER

Citation

Mohamed Wahbi, Younes Mechqrane, Christian Bessière, Kenneth N. Brown. A General Framework for Reordering Agents Asynchronously in Distributed CSP. CP: Principles and Practice of Constraint Programming, Sep 2015, Cork, Ireland. 21st International Conference on Principles and Practice of Constraint Programming 2015. 〈lirmm-01276190〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

65

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD