Study On Heuristic Coalition Formation Algorithms In Cooperative Multi-Agent Systems

Multi-Agent Systems (MAS) are becoming more and more important recent yearsin the field of artificial intelligence. Agents of coalition usually achieve better results thanthat when they behave independently in many tasks. Coalition Structure Generationproblem represents an active research area in Multi-Agent Systems.Coalition structure is defined as a partition of all agents, that is to say, multipleindependent disjoint coalitions. The key problem in Multi-Agent Systems is which agentswill form a coalition and how to generate coalitions. Game Theory provides a solution forthis problem: in a given game we can get a stable result. However, finding theoptimal coalition structure is a NP-complete problem. It is a challenging combinatorialproblem; it is theoretically possible to find out the optimal coalition structure by traversesearch. The number of coalition partitions is a Bell number which grows exponentiallywith the number of all agents, so traverse searching turns to be not implementable as thenumber of agents grows.Based on the MAS model under wireless communication environment, this thesisproposes two heuristic algorithms for coalition structure generation from the perspectiveof game theory. The stability of coalition structures and the algorithm complexity are alsoanalyzed. In the proposed algorithms, agents may have different attitudes, that is, tomerge with other agents (coalition) or to split from a coalition by means of merge-split,and at last all agents form the optimal or second-best coalition structures. The simulationexperiments using Monte Carlo method show that the two algorithms achieve betterresults without traversing the search space. The two algorithms can improve individualagent’s utility by40.74%and43.37%respectively when Mt<=100, and the maximumerror is1.61%and0.91%compared with the optimal result when Mt<=20.