Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
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.