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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [31 references]  Display  Hide  Download
https://hal-lirmm.ccsd.cnrs.fr/lirmm-01276190
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 18, 2018 - 12:42:49 PM
Last modification on : Thursday, October 18, 2018 - 1:15:40 PM
Long-term archiving on: Saturday, January 19, 2019 - 2:04:56 PM

File

cp15-agile.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-01276190, version 1

Collections

LIRMM | CNRS | 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, Aug 2015, Cork, Ireland. pp.463-479. ⟨lirmm-01276190⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

239

Files downloads

143

Contact

Informations

CCSD