The Study On Communication Structures Of Complete DCOP Algorithms

Distributed constraint optimization problem(DCOP) is a promising framework for modeling distributed reasoning tasks that arise in Multi-Agent systems. In the recent years, many excellent algorithms have been proposed for solving a DCOP. These algorithms can be divided into complete algorithms and incomplete algorithms. Incomplete algorithms use local search to find the optimal solution and are suitable for solving the large-scale problems but potentially get trapped in local minima. By contrast, complete algorithms are intended for the global optimal solution by means of traversing the search space and are suitable for solving the small and medium scale problems. The paper focuses on the study on performance of complete algorithms. The performances of complete algorithms depend not just on the solving strategies, but on agent communication structure that is formed on the preprocessing stage. While many optimization methods have been put forward concerning the solving strategy for complete algorithms, the optimization study of agent communication structure is studied well. Hence, the study on agent communication structure is of great theoretical and practical significance. This paper intends to study tree-based communication structure in terms of the attributes of agents and the characteristics of constraint graph. The detailed work is done as follows:① The paper firs provides an overview of DCOP and introduces its related definitions. Then, communication structures of complete algorithms illustrated in detail. In addition, the formations of chain structure and tree structure are described, and the typical complete algorithms based on these structures are introduced, respectively.② A kind of method is proposed to construct the communication structure based on node contribution. The method adopts the idea of arc consistency, which uses the node contribution to sort the nodes so as to build tree-based communication structure. The higher contribution a node, the higher priority the node to be sorted. The method makes it possible to reach the global optimal solution more promptly. The experimental comparisons on different agent communication structures shows that this method can help the algorithm to prune the search space promptly and improve the efficiency.③ A kind of method is proposed to construct the communication structure based on graph cut-vertex. The method utilizes the features of constraint graph formed from DCOP and finds cut-vertex of constraint graph to build a tree-based communication structure for improving the parallelism. Also, with the absence of cut-vertex, the method based on node contribution is introduced. The experimental results show that the proposed method can achieve a better algorithm performance due to good parallelism and ability to prune the search space. Then, the two methods are compared to reveal which types of problems they are suitable for solving.④In order to verify the feasibility of the proposed communication structure method, the meeting problems are solved by the complete algorithms with the communication structure cpmstricted by the method based on graph cut-vertex. Comparing to complete algorithms with communication structure based on node connection edge, the experimental results show that communication structure based on graph cut-vertex leads to the better optimization performance, which proves to be feasible in practical use.