Research On Optimal Overlapping Coalition Structure Generation With Cost Minimization

Overlapping coalition structure generation(OCSG)has always been a hot issue in multi-agent systems(MAS)and artificial intelligence.In OCSG,an agent is able to join in multiple coalitions at the same time,and one coalition can simultaneously take multiple tasks,which results in that the solution space is extremely complex.However,the existing random search methods based on evolutionary algorithms cannot guarantee the optimal solution.Moreover,it is assumed that the resources consumed by an agent for its tasks will not incur any cost,which makes it impossible to distinguish the difference between coalition structures.In particular,coalition structures with unconstrained cost often deviate from practical applications.Therefore,this dissertation focuses on the scenario where the consumed resources will produce cost and aims to pursue the optimal overlapping coalition structure with minimum cost.The main research work of the dissertation is as follows:(1)We introduce the research background and motivation of this dissertation.Based on the existing research on coalition formation,we analyze and summarize the problems existing in the current research on OCSG,and determine the research content of this dissertation.(2)We introduce the relevant theoretical basic knowledge of MAS and several typical evolutionary algorithms for solving the coalition structure generation problem.Particularly,we point out the characteristics of each algorithm and summarize the limitations of evolutionary algorithms on solving the coalition structure generation problem,leading to the research motivation of this dissertation.(3)A mathematical model of OCSG with cost minimization is constructed,and a serial generation algorithm for optimal overlapping coalition structure(called OCSG_COST)based on dynamic programming is proposed.The OCSG_COST algorithm can be regarded as an agent-oriented optimal search algorithm.Whether an agent is selected or not is determined by its weight,cost and the weight requirement of the task set.Then,according to the obtained optimal agent set and task set,we generate a coalition structure based on a greedy strategy.Compared with the existing algorithms,OCSG_COST can obtain the optimal overlapping coalition structure with cost in any constraint environment and has better applicability.(4)A parallel generation algorithm for optimal overlapping coalition structure(called OCSG_MCMF)based on the minimum cost maximum flow.The optimal OCSG problem with the lowest cost is mapped into a flow network model,in which the agent or task is a network node and each edge represents a feasible path that includes “capacity” and “unit cost”.When the flow on the edge of a task to the termination node is equal to the "capacity" on the edge,a task coalition is generated.The purpose of the OCSG_MCMF algorithm is to generate coalitions simultaneously and minimize the cost of the coalition structure.The experimental results show that OCSG_MCMF can parallel generate the optimal overlapping coalition structure according to the given task set,which is more flexible and efficient.