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.
nguyen_2005_dynamic_distributed_backjamping.pdf
openaccess
282.86 KB
Adobe PDF
617abb136701c7fe78c935e35fa999fb