Compilation Formulation for Asynchronous Backtracking with Complex Local Problems

The Asynchronous BackTracklng (ABT) algorithm is a well known algorithm for solving distributed constraint satisfaction problems. However, several work which interest to ABT suppose that each agent owns one single variable. In this paper, we present the compilation formulation for Asynchronous Backtracking with complex local problems, resulting in the ABT-cf algorithm. The ABT-cf algorithm is described in detail and its correctness proof. An extensive experimental evaluation of the proposed algorithm is carried on random binary DisCSP. The performances of ABT-cf is compared to the standard ABT in which the distributed problem is reformulated by decomposition. Experimental evaluation shows that ABT-cf increases the performance of the distributed search and outperforms standard ABT by a large scale.