.png){kind=icon}
.png){kind=icon}
Return
An improved DPOP algorithm based on breadth first search pseudo-tree for distributed constraint optimization
.png){kind=icon}
PRE
AI
DOI：10.1007/s10489-017-0905-4.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Depth First Search (DFS) pseudo-tree is popularly used as the communication structure in complete algorithms for solving Distributed Constraint Optimization Problems (DCOPs) from multiagent systems. The advantage of a DFS pseudo-tree lies in its parallelism derived from pseudo-tree branches because the nodes in different branches are relatively independent and can compute concurrently. However, the constructed DFS pseudo-trees in experiments often come to be chain-like and greatly impair the performances of solving algorithms. Therefore, we propose a new DPOP algorithm using a Breadth First Search (BFS) pseudo-tree as the communication structure, named BFSDPOP. Compared with a DFS pseudo-tree, a BFS pseudo-tree is more excellent on the parallelism as it has much more branches. Another notable advantage is that the height of a BFS pseudo-tree is much lower than that of a DFS pseudo-tree, which gives rise to the shorter communication paths and less communication time. The method of Cluster Removing is also presented to allocate cross-edge constraints to reduce the size of the largest message in BFSDPOP. In the experiment, BFSDPOP with a BFS pseudo-tree and original DPOP with a DFS pseudo-tree are compared on three types of problems - graph coloring problems, meeting scheduling problems and random DCOPs. The results show that BFSDPOP outperforms original DPOP in most cases, which proves the excellent attributes of BFS pseudo-tree over DFS pseudo-tree.
Keywords:
Multiagent system
Distributed constraint optimization
Breadth first search pseudo-tree
DPOP
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.