Vidal's library
Title: Concurrent Search for distributed CSPs
Author: Roie Zivan and Amnon Meisels
Journal: Artificial Intelligence
Volume: 170
Number: 4--5
Pages: 440--461
Year: 2006
DOI: 10.1016/j.artint.2005.12.005
Abstract: A distributed concurrent search algorithm for distributed constraint satisfaction problems (DisCSPs) is presented. Concurrent search algorithms are composed of multiple search processes (SPs) that operate concurrently and scan non-intersecting parts of the global search space. Each SP is represented by a unique data structure, containing a current partial assignment (CPA), that is circulated among the different agents. Search processes are generated dynamically, started by the initializing agent, and by any number of agents during search. In the proposed, ConcDB, algorithm, all search processes perform dynamic backtracking. As a consequence of backjumping, a search space can be found unsolvable by a different search process. This enhances the efficiency of the ConcDB algorithm. Concurrent Dynamic Backtracking is an asynchronous distributed algorithm and is shown to be faster than former algorithms for solving DisCSPs. Experimental evaluation of ConcDB, on randomly generated DisCSPs demonstrates that the network load of ConcDB is similar to the network load of synchronous backtracking and is much lower than that of asynchronous backtracking. The advantage of Concurrent Search is more pronounced in the presence of imperfect communication, when messages are randomly delayed.



@Article{zivan06a,
  author =	 {Roie Zivan and Amnon Meisels},
  title =	 {Concurrent Search for distributed {CSP}s},
  journal =	 {Artificial Intelligence},
  year =	 2006,
  volume =	 170,
  number =	 {4--5},
  pages =	 {440--461},
  abstract =	 {A distributed concurrent search algorithm for
                  distributed constraint satisfaction problems
                  (DisCSPs) is presented. Concurrent search algorithms
                  are composed of multiple search processes (SPs) that
                  operate concurrently and scan non-intersecting parts
                  of the global search space. Each SP is represented
                  by a unique data structure, containing a current
                  partial assignment (CPA), that is circulated among
                  the different agents. Search processes are generated
                  dynamically, started by the initializing agent, and
                  by any number of agents during search. In the
                  proposed, ConcDB, algorithm, all search processes
                  perform dynamic backtracking. As a consequence of
                  backjumping, a search space can be found unsolvable
                  by a different search process. This enhances the
                  efficiency of the ConcDB algorithm. Concurrent
                  Dynamic Backtracking is an asynchronous distributed
                  algorithm and is shown to be faster than former
                  algorithms for solving DisCSPs. Experimental
                  evaluation of ConcDB, on randomly generated DisCSPs
                  demonstrates that the network load of ConcDB is
                  similar to the network load of synchronous
                  backtracking and is much lower than that of
                  asynchronous backtracking. The advantage of
                  Concurrent Search is more pronounced in the presence
                  of imperfect communication, when messages are
                  randomly delayed.},
  keywords =     {multiagent distributed-search},
  url = 	 {http://jmvidal.cse.sc.edu/library/zivan06a.pdf},
  doi = 	 {10.1016/j.artint.2005.12.005}
}
Last modified: Wed Mar 9 10:16:33 EST 2011