Dynamic Distributed BackJumping

We consider Distributed Constraint Satisfaction Problems (DisCSP) when control of variables and constraints is distributed among a set of agents. This paper presents a distributed version of the centralized BackJumping algorithm, called the {\\it Dynamic Distributed BackJumping} - \\algoname{DDBJ} algorithm. The advantage is twofold: \\algoname{DDBJ} inherits the strength of synchronous algorithms that enables it to easily combine with a powerful dynamic ordering of variables and values, and still it maintains some level of autonomy for the agents. Experimental results show that \\algoname{DDBJ} outperforms the \\algoname{DiDB} and \\algoname{AFC} algorithms by a factor of {\\it one to two} orders of magnitude on hard instances of randomly generated DisCSPs.


Published in:
Recent Advances in Constraints, 71-85
Presented at:
Joint ERCIM/CoLogNet International Workshop on Constraint Solving and Constraint Logic Programming, CSCLP 2004, Lausanne, Switzerland, June 23-25, 2004
Year:
2005
Publisher:
Springer-Verlag
Note:
LNAI-3419
Other identifiers:
Laboratories:


Note: The status of this file is: Anyone


 Record created 2006-12-07, last modified 2019-12-30

n/a:
Download fulltext
PDF

Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)