Concurrent Backtrack Search on DisCSPs

May 2004

Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2004)

Volume

Proceedings of the Seventeenth International Florida Artificial Intelligence Research Society Conference (FLAIRS 2004)

All Papers

A distributed search algorithm for solving distributed constraint satisfaction problems (DisCSPs) is presented. The proposed algorithm is composed of multiple search processes (SPs) that operate concurrently. Concurrent search processes scan nonintersecting parts of the search space. Each SP is represented by a unique data structure, containing a current partial assignment (CPA), that is circulated among the different agents. The splitting of the search space, leading to several concurrent SPs is achieved by splitting the domain of one or more variables. The proposed algorithm generates concurrent search processes dynamically, starting with the initializing agent, but occurring also at any number of agents during search. The Concurrent BackTracking (ConcBT) algorithm is presented and an outline of the correctness proof is given. Experimental evaluation of the algorithm, on randomly generated DisCSPs, is presented. ConcBT outperforms asynchronous backtracking (ABT) (Yokoo2000) on random DisCSPs with different patterns of message delays. Load balancing for ConcBT is achieved by adding concurrent search trees dynamically, performing re-splitting of the search space by the use of a simple heuristic.