A General Framework for Reordering Agents Asynchronously in Distributed CSP - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2015

A General Framework for Reordering Agents Asynchronously in Distributed CSP

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

Dates and versions

lirmm-01276190 , version 1 (18-10-2018)

Identifiers

Cite

Mohamed Wahbi, Younes Mechqrane, Christian Bessiere, Kenneth N. Brown. A General Framework for Reordering Agents Asynchronously in Distributed CSP. CP 2015 - 21st International Conference on Principles and Practice of Constraint Programming, Aug 2015, Cork, Ireland. pp.463-479, ⟨10.1007/978-3-319-23219-5_33⟩. ⟨lirmm-01276190⟩
167 View
163 Download

Altmetric

Share

More