The Study On Inference Based Complete DCOP Algorithms And Experiment Platform Implementation

Distributed Constraint Optimization is the model for Multiagent System and is widely applied in solving problems of distributed planning, distributed scheduling and distributed resource allocation, where disaster rescue, multiagent teamwork, distributed robots, meeting scheduling and sensor networks are typical applications. The DPOP algorithm is a Dynamic Programming based inferencing algorithm and is also one of the most efficient DCOP complete algorithm. Its prominent advantage over many other algorithms makes it really appropriate to solve real-life problems. This paper carries out the research work by improving the performance of DPOP algorithm from communication structure and conducts the experiment on autonomously developed platform DCOPSolver. The detailed work is done as follows:(1) The paper first gives an overview on present DCOP research situation and latest dynamics. Then it introduces the detailed notations and definitions in DCOP, including constraint graph, communication structure and the three typical types of problem: graph coloring, meeting scheduling and random DCOP. The paper also gives a detailed illustration on DPOP algorithm, which is the main study subject of this paper.(2) The paper proposes a new algorithm named BFSDPOP using Breadth First Search Pseudo-tree as communication structure. Compared with DFS Pseudo-tree used by DPOP, BFS pseudo-tree has much more branches and much shorter message transmission paths, which can help BFSDPOP achieve better parallelism and communication efficiency. The paper also proposes the ClusterRemoving algorithm to allocate the cross edges on BFS pseudo-tree to control the involved message size.(3) The paper proposes another new algorithm named CVDPOP using Depth First Search Pseudo-tree as communication structure. The DFS pseudo-tree is constructed by strategy of best cut vertex and maximal degree first strategy, which can help construct a better DFS pseudo-tree because with more branches.(4) Considering the high complexity of present DCOP algorithm experimental platforms, this paper also proposes a new platform named DCOPSolver with simpler functions and easier new-algorithm-integrating system. All experiments in this paper are conducted in DCOPSovler. By comparing runtime and maximal dimensions of the largest message of DPOP, BFSDPOP and CVDPOP on solving problems of graph coloring, meeting scheduling and random DCOP, the result shows that BFSDPOP and CVDPOP both have a prominent advantage over the original DPOP, which proves the the positive effect of BFS pseudo-tree and best cut vertex and maximal degree first strategy on improving the algorithm efficiency and performance.