Research On Task Allocation Method Based On Coalition Formation Game

Coalition is an important research issue in multi-agent systems(MAS),and cooperation is the most important part of group work.MAS focuses on how to establish organizations,form coalitions and how to assign tasks in multi-agent cooperation.Organization and coalition are the basis of cooperation,and task allocation reflects cooperation.The formation of coalitions is a complex combinatorial optimization problem.It takes a lot of time to find an optimal coalition using traditional methods,so how to find a better coalition quickly and effectively is worth studying.The coalition formation game is an important cooperation model in MAS.The game theory becomes the main theoretical tool for analyzing MAS based on the game relationship,especially the game theory is used to analyze the cooperation between multiple agents.Agents gain benefits by forming coalitions to achieve a common goal.MAS which is based on game relationship is one of the prolific fields in the field of game theory and artificial intelligence.Therefore,it is very meaningful to study the reasons and processes of agents forming alliances through the cooperative game.This paper takes the study of task allocation based on coalition formation game as the background.The main contributions and research results are summarized as follows:(1)due to the complexity of some tasks and the limitation of participants’ skill or resource,the process of distribution inevitably involves cooperation between participants.Therefore,this paper focuses on forming a group that completes tasks in a coalition manner,and uses game theory to analyze conflict and cooperation between rational participants.We focuses on the cooperative game relationship between members.This paper introduces the relevant basic theoretical knowledge and related work,including the components of the coalition mechanism and the related work research of task allocation.(2)considering the constraints between Agents,the concept of social network is introduced to analyze the behavioral interactions between Agents.The structure limits the number of the coalitions.At the same time,based on this social network,we consider the relationship between participating members which is more practical in the real world.The formation model of mobile agent coalition is proposed.The corresponding CMA-CF mechanism and the solution of coalition value are introduced.The preference rule formed by the coalition is given.Finally,the performance simulation analysis of the algorithm is carried out,and the comparison on the other coalition formation mode is given.(3)considering the improvement of resource utilization,the concept of overlapping coalition game is introduced to analyze the coordination and cooperation between agents and the virtual agent is introduced to reduce the complexity of’ the formation process of overlapping coalitions.At the same time,the relationship between coalition partners will become an internal factor affecting the formation of coalitions.It is meaningful to study its influence on the selection of coalition members.It is necessary to form a strategic coalition among acquaintances.Here,we measure the partnership between the participants by cooperation degree,and the degree of collaboration is continuously updated according to the quality of the task completion.The effectiveness of the algorithm is verified by simulation experiments,achieving the best mapping from agent to task.