Research On Overlapping Coalition Formation In Multi-sgent Systems

In multi-agent systems (MAS), coalition formation is an important wayfor agents to cooperate with each other to solve complex distributedintelligent control problems. Therefore, how to form an effective and stablecoalition is very important in MAS. However, many existing works has onlydeal with formation of non-overlapping coalition, which allows one agent tojoin only one task and easily produces a big waste of agents’ resources.Against this background, in this dissertation we will focus onoverlapping coalition formation. Our aim is to achieve each agent cancompete for task freely without any resource conflict and provide atheoretical and methodological guidance for many complicated controlproblemsThe main research contents and innovative contributions of thisdissertation are as follows:(1) We review some existing works for binary encoding basednon-overlapping coalition formation algorithms. Then we show that the mainalgorithms for encoding repairing in the paper [J. Yang, Z. Luo, Coalitionformation mechanism in multi-agent systems based on genetic algorithms,Applied Soft Computing.7(2)(2007)561-568] are not workable. At last, wediscuss the underlying cause for those questions and give some usefulinformation for guiding encoding repairing.(2) We propose an overlapping coalition formulation algorithm based onvirtual coalition. Overlapping coalition formation is a very challenging topicin complex intelligent systems.When an agent with insufficient resourcesmay join in several different tasks but can not satisfy those tasks’ need at thesame time, resource conflicts will take place. To tackle such scenarios, thisdissertation mainly focuses on how to revise an invalid two-dimensionalbinary encoding into a valid one to resolve conflicts o ver the usage of jointresources. A dynamic virtual coalition is proposed to inherit the surplusresources of all feasible co alitions to join and help other invalid coalitions.Finally, contrastive experiments are made to show that the proposed algorithm does not discard any invalid encoding and is more effective toresolve possible resource conflicts.(3) We propose a fair payoff distribution for overlapping coalitionformation. Payoff distribution is a difficult problem in coalition formation inmulti-agent systems (MAS), because the reasonability of payoff distributionwill directly affect the positivity of agents and the stability of coalitions. Inthis dissertation, we pay attention to the payoff distribution in overlappingcoalition formation (OCF), where an agent can join more than one tasks atthe same time. We present a fair payoff distribution for OCF, allocate tasksbased on bargaining, and distribute payoff according to the principles of“more pay for more work” and “non-reducing utility”. Finally, arepresentative case analysis shows that the proposed strategy can solveresource conflict perfectly and ensure the stability of coalitions.