Skip to Main content Skip to Navigation
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Joël Quinqueton Connect in order to contact the contributor
Submitted on : Thursday, October 18, 2018 - 12:42:49 PM
Last modification on : Friday, October 22, 2021 - 3:07:33 PM
Long-term archiving on: : Saturday, January 19, 2019 - 2:04:56 PM


Files produced by the author(s)


  • HAL Id : lirmm-01276190, version 1



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⟩



Record views


Files downloads