 |
HAL-LIRMM - Open Archive |  |
Conference papers
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.
Cited literature [31 references]
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 : Monday, January 11, 2021 - 5:24:12 PM
Long-term archiving on: : Saturday, January 19, 2019 - 2:04:56 PM
Contributor : Joël Quinqueton <>
Submitted on : Thursday, October 18, 2018 - 12:42:49 PM
Last modification on : Monday, January 11, 2021 - 5:24:12 PM
Long-term archiving on: : Saturday, January 19, 2019 - 2:04:56 PM
File
cp15-agile.pdf
Files produced by the author(s)