You are here

A General Framework for Reordering Agents Asynchronously in Distributed CSP

Authors: 

Mohamed Wahbi, Younes Mechqrane, Christian Bessiere, Ken Brown

Publication Type: 
Refereed Conference Meeting Proceeding
Abstract: 
Reordering agents during search is an essential component of the efficiency of solving a distributed constraint satisfaction problem. Termination values have been recently proposed as a way to simulate the min-domain dynamic variable ordering heuristic. The use of termination values allows the greatest flexibility in reordering agents dynamically 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 various heuristics other than min-domain. Our general framework is sound, complete, terminates and has a polynomial space complexity. We implemented 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.
Conference Name: 
CP2015
Proceedings: 
Proceedings of the 21st International Conference on Principles and Practice of Constraint Programming (CP'2015)
Digital Object Identifer (DOI): 
10.1007/978-3-319-23219-5_33
Publication Date: 
31/08/2015
Pages: 
463-479
Conference Location: 
Ireland
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No
Publication document: