BFSDPOP: DPOP Based on Breadth First Search Pseudo-Tree for Distributed Constraint Optimization

DPOP is an efficient algorithm based on the Depth First Search (DFS) Pseudo-tree for distributed constraint optimization problems in multiagent systems (MAS). DFS Pseudotree is able to help achieve parallelism due to the relative independence of nodes lying in different branches. However, we often get a chain-like pseudo-tree with few branches in our experiments, which greatly impairs the algorithm performance. Therefore we propose a new DPOP algorithm called BFSDPOP which uses Breadth First Search (BFS) Pseudotree as the communication structure. The two advantages are that BFS Pseudo-tree can help the algorithm achieve more parallelism as it has more branches; and BFS Pseudotree shortens the communication path and requires less communication time because the height of a BFS Pseudo-tree is often much lower than that of a DFS Pseudo-tree from the same constraint graph. To overcome the cross edge constraints in BFS Pseudo-tree which can easily result in large utility message size, a method of Cluster Removing is proposed. In the experiment, we compare BFSDPOP with the original DPOP and the result shows that BFSDPOP outperforms the original DPOP in most cases, which demonstrate the excellent attributes that BFS Pseudo-tree has over DFS Pseudo-tree.