Concurrent Backtrack Search on DisCSPs. Conference Paper uri icon

abstract

  • 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 DisCSP...

publication date

  • May 1, 2004