Forward Bounding on a Pseudo Tree for DCOPs
Distributed constraint optimization problems (DCOP) are a popular way of representing and solving multi agent coordination problems. Complete search algorithms for solving DCOPs fall into two groups: algorithms that use a pseudo tree (ADOPT [10] bnb ADOPT [12] NCBB [1] and algorithms that do not use one (AFB [4] ConcFB [11] Each of these groups has different limitations. The algorithms that use a pseudo tree are dependent upon the existence of a good (minimal depth) pseudo tree. However, highly constrained problems tend to have bad trees. On the other hand, non pseudo tree algorithms can fail to take advantage of the possibility of dividing the problem into smaller sub problems, which can boost the performance of the algorithm. A new algorithm, PT SFB, is presented which incorporates a hybrid approach of the two groups, in an attempt to take the best from each one. Every agent identifies when it is possible to divide the remaining problem (given a partial assignment) into smaller sub problems that can be solved independently. When the remaining problem cannot be divided at a given point, a sequential assignment will take place, which outperforms pseudo tree algorithms in these cases. In all cases the proposed algorithm performs forwardbounding. An extensive experimental evaluation is presented, comparing PT SFB to several state of the art algorithms.