Algorithm For Coalition Structure Generation With Externalities

In recent years,muti-agent systems in artificial intelligence is more and more popular with people.In muti-agent systems.each agent take a way of cooperation to reach the target and finish the task,so that they can prove efficiency. Each agent is arranged in different coalition to form different coalition structures. So, the main problem is how to form a coalition and make it effective. However, finding the optimal coalition structure is a NP-hard problem; it is theoretically possible to find the optimal coalition structure by traverse search.The number of coalition partitions is a Bell number which grows exponentially with the number of all agents.So traverse searching is not good enough for the issue of time and resource, and we often get a suboptimal one.We fist put forward the background of the CSG and its problem, then descript basic theory of agent.We investigate the main research methods and its present problems and get breakthrough point of the passage.We put forward a pruning algorithm for the coalition structure graph.Coalition formation is a key topic on muti-agent systems.Much of the literature on muti-agent coalition formation has focused on Characteristic Function Games,where a coalition is not affected by how the other agents are arranged in a system.However,in a number of environments,there are significant externalities from coalition formation where the value of one coalition may be affected by the formation of other distinct coalitions.In this paper we focus on Partion Function Games using partion search.This method has proved the efficicey of the algorithm.We develop an anytime algorithm with either positive or negative externalities. We prove that it is possible to compute upper and lower bounds on the values of any set of coalitions and we can improve the worst case guarantee with further search.The efficiency of algorithm is improved and a satisfactory value is able to be gained at any time. The results show that to reach the bound.the PFG algorithm search less coalition structure than the CFG algorithm. With the optimization of the bound,it needs loonger time.The bigger the bound is.the more coalition struetures has to be searched and it requires more time.