Cooperative Dynamic Multi-CBJ Search for DisCSPs Academic Article uri icon

abstract

  • A multi search process version of the sequential assignment, distributed Conflictbased BackJumpig algorithm is presented. Multi-CBJ benefits greatly from sharing of Nogoods among search processes. It also improves when the multi-search process is dynamic, generating CBJ processes during search with a dynamic heuristic that controls load balancing. The resulting algorithm, Cooperative Dynamic Multi-CBJ, is much faster and more efficient than asynchronous algorithms like ABT and AF C. The multi-search version of asynchronous backtracking (ABT) turns out to be unsuccessful. Apparently, the existing asynchroniety of ABT prevents it from benefiting from the use of multi search processes. Its performance actually deteriorates with additional search processes. Finally, the hypothesis that multi-search flourishes when message delays are dominant is checked …

publication date

  • January 1, 2007