Multi-Agent Based Approaches To Solving Distributed Constraint Optimization Problems

With the development of the communications infrastructure, computer technology and the applications of computer network, a passel of difficult requirements of new applications have occurred in the fields of scientific computing, business activities and so on. The distributed constraint optimization problem (DCOP) is one typical problem among them. The DCOP is a kind of optimization problem oriented to large-scale, open and dynamic network environments, which has been widely applied in many fields such as computational grid, multimedia networks, E-business, enterprise resource planning (ERP) and so on. Besides the features such as non-linear and constraint-satisfaction which traditional optimization problems have, the DCOP has its distinct features including dynamic evolution, regional information, localized control and asynchronous updating of network states. It has become a challenge for computer researchers to find out a large-scale, parallel as well as intelligent solution for the DCOP.Decentralized control in terms of multi-solver rather than central and global control is adopted by a desired DCOP solving mechanism. During the DCOP solving process, multi solvers autonomously run . Each solver possesses regional knowledge of the problem in question, but not the global information of the whole problem space. The compute environment where the multi solvers situate is not static but dynamically evolving. Because the agent technology matches most features of the DCOP solving mechanism, it has been considered as a promising solution to it. However, the problem solving system of the DCOP is required to be self-adaptive for dealing with the stochastic and dynamically evolving features of the DCOP. Furthermore, it is also required to be self-organized due to the features of regional information, localized controlling and asynchronous updating of network states However, the solving mechanism for the DCOP provided by current agent technologies can not meet above requirements. So, To present a general approach for solving the DCOP by considering the features of the DCOP and integrating the self-adaptive and self-organized mechanisms into agent technology is able to not only shed new light to solving large-scale and complex DCOP but also push the academic and industrial research of agent technology. Based on the analysis of related research and existing methods, we put forward a self-organized multi-agent based general approach to solving the DCOP. Using this approach, facing the all kinds of DCOPs in different fields such as complex network analysis, multi-agent learning, e-business and middleware based Web intelligent application system, the thesis has presented several specific multi-agent based algorithms for different DCOPs. The main results obtained by this thesis are listed as follows:(1) The thesis has analyzed the related concepts, theories and methods about solving DCOP based on self-organized multi-agent, including the concepts and features of agent, distributed artificial intelligence and multi-agent system, self-organization theory, swarm intelligence, constraint optimization problem, distributed constraint optimization problem, distributed complex network clustering, multi-agent learning, auctions in E-commerce based on agent, and so on.(2) The thesis has presented a general approach to solving the DCOP based on self-organized multi-agent. After analyzing and summarizing the existing research methods for solving DCOP, this thesis has pointed out the shortcomings of the existing algorithms for solving DCOP. So far, there have been a lot of methods for solving DCOP. However, most of them are not completely decentralized and require prior knowledge such as the global structures of networks as their inputs. Unfortunately, for many applications, the assumption that we can obtain the global views of networks beforehand is not true due to their huge sizes, geographical distributions or decentralized controls. To solve this problem, this thesis has presented a general approach to solving DCOP based on self-organized multi-agent. The method is named as SODC. Compared with the existing algorithms, the SODC has two main advantages. Firstly, it is a completely decentralized algorithm. Without global information of the whole network, it demonstrates the self-organizing behaviors based on divide and conquer strategy, in which multiple autonomous agents distributed in networks work together to solve the DCOP through a proposed self-organization mechanism. Secondly, it demonstrates better performance in both efficiency and effectiveness.(3) The thesis has presented an agent based decentralized algorithm for clustering complex networks. After thoroughly analyzing the complex networks'structures and the features of existing algorithms of complex network clustering, this thesis has shown that though many related methods have been proposed and applied to different areas including complex network analysis, gene network analysis and web clustering engine, most of them are centralized. They need centralized disposal strategy and are not suitable for dealing with distributed networks, whose global structures are hard to be obtained due to their huge sizes, geographical distributions, decentralized controls or updating randomly. In this thesis, based on the SODC, we present a multi-agent based decentralized algorithm called as D-P*, in which a group of autonomous agents work together to cluster a network through a proposed self-aggregation and self-organization mechanism. Compared with the existing algorithms, the D-P* runs concurrently and asynchronously without any synchronized mechanism. It is able to rapidly find an approximately optimal network cluster structure hidden in the given network.(4) The thesis has presented a distributed multi-agent Q-learning algorithm. After analyzing the features and the essence of reinforcement learning and Q-learning, this thesis has shown that the typical Q-learning algorithm is not suitable for multi-agent learning because the size of state-action space is huge and will exponentially grow as the number of agents increasing and that multi-agent learning is more widely than single agent learning. Based on the SODC, the thesis has presented an online multi-agent learning algorithm called as MQ-L. It integrates many good features such as sharing Q function, dynamic updating search strategy and action-state space pruning and so on. Essentially, the MQ-L is an approach to solving distributed constraint optimization problem, in which multiple agents collaborate to maximize their sharing Q function defined beforehand based on their respective local information. Experiments have shown that the MQ-L algorithm greatly improves the performance of multi-agent learning compared with the typical Q-learning algorithm.(5) The thesis has investigated the application of mobile agent in e-commerce. After analyzing and discussing the main issues in establishing autonomous auction system, the thesis has shown that multi-agent based auction system is a distributed constraint optimization problem in essence. An agent plays with others based on its local information and constraint conditions to maximize its own cost function. However, distinct from all DCOPs discussed above, agents in the auctions compete rather than work together with others to maximize their own profits. According to some predefined auction protocols, agents in an auction system compete as well as compromise each other in order to get into a fix point state corresponding to a globally optimal solution in which every agent's profit is maximized. Based on the SODC and the game theory, the thesis has presented a mobile agent based autonomous auction model. The model supports to model auction hall, search auction hall, locate trade partners, synchronize different roles involved in an auction transaction and provides two typical auction protocols, which are the first price sealed-bid auction and double auction. After receiving tasks, agents in the model can autonomously search auction halls distributed in networks, take part in auctions and return the final auction results to their respective owners. (6) The thesis has developed a web intelligent system integrated development platform based on agent middleware technology. It has shown that the existing middleware can preferably solve traditional problems frequently occurred in the process of developing distributed systems in most application fields. However, there exist some disadvantages listed as follows: first, it is difficult to support the abstraction, encapsulation and expendability of special issues (especially distributed constraint optimization problems) effectively. Second, it is difficult to meet the requirements of rapid building and effective running web based intelligent application system. Based on the adequate analysis of current middleware and intelligent application system, by adopting the agent technology and the strategies for solving the DCOP presented in above chapters, the thesis has presents an intelligent agent middleware based solution for rapidly building and effectively running the web intelligent applications. It has implemented the collaboration of distributed and heterogeneous intelligent components and permitted accessing, reusing and sharing the distributed and heterogeneous knowledge. The web intelligent application system integrated development platform based on agent middleware and several expert systems for different producing fields have been developed by utilizing the solution. They have demonstrated good results in practice.The research results of the thesis including the general approach to solving the DCOP, the decentralized approach for clustering complex networks, multi-agent reinforcement learning, autonomous auction model for e-business and agent middleware based web intelligent application system, will greatly enrich and push the studies of the DCOP as well as the agent in both theoretical and technological aspects.