Research And Application On Multi-Agent Distributed Constraint Optimization Problem

With the rapid development of science and information technology, increasingly complex practical problems have been gradually beyond the scope of a single system. More and more people try to seek in the field of distributed multi-agent system.It’s a hot research on how to maximize Agent’s computing and service capacity. One traditional research is Robots Area Coverage Problem which means using the robot sensors to traversal target environment area as far as possible or meet the condition that the time is short or repetitive path is less. And now with the rising development of cloud computing, it has been a new hot research. Based on virtualization technology cloud market could provide resources also called Virtual Machine(VM) to users. How to allocate VMs efficiently is a great problem in the area. Generally, with the increase of cloud market size, it could be an NP-hard Problem. In this paper, we do the research on Multi-Agent Distributed Constraint Optimalization Problem, and the main contributions are as the follows:(1) Explore the multi-agent distributed constraint optimization problem, from the aspect of agent system and distributed constraint optimalization problem.(2) Study the solving rules on DCOP, and introduce the core algorithm in this paper, Max-sum algorithm emphatically, from the development, process and related theory detailedly.(3) Solve the cloud resource allocation problem with the research on DCOP. Propose mechanism based on Max-sum algorithm to find the nearly optimal solution.(4) Do the research on the structure of Max-sum, and propose a new way which based on marginal contribution to develop the algorithm.(5) Model the Robots Area Coverage Problem with DCOP, and using Max-sum algorithm to make the best coverage decision.