Research On Coalition Resource Games With The Preferences Of Multiple Agents

Coalition formation(CF)has been a hot topic in multi-agent systems(MAS)and artificial intelligence.In CF,coalitional resource games(CRGs)take into account resource constraint,consumption,and competition altogether,and provide a natural collaboration mechanism to make agents share scarce resources to achieve mutual satisfactory goals.However,the traditional CRGs assume that each agent can respond to all the goals,even if the agent is not interested in the goal at all,which makes CF deviate from the practical applications and brings a huge computational cost.Therefore,this dissertation considers the CRGs under the agent preferences over goals.In such case,each agent is only willing to contribute its own limited resources to the goals in its own interest set.The main work of this dissertation is as follows:(1)The existing work on CF is analyzed and summarized,based on which the drawbacks of existing research are discussed.(2)The mathematical modeling of CRGs with agent preferences over goals is proposed.Based on the analysis of the link between agent,goal,and coalition in the model,the concepts of "actual contribution amount" and "residual resource quantity" are put forward.In addition,the successful coalition problem with the agent preferences is redefined.Moreover,the computational complexity of the new successful coalition problem is deduced.(3)A maximal successful coalition generation algorithm is presented based on "least workload" and two-dimensional binary particle swarm optimization.First,the binary particle swarm optimization is extended to two-dimensional encoding.Next,whether each agent responses to a goal is determined by the least workload that the agent should contribute to the goal.Besides,a heuristic is developed to resolve the potential resource conflicts over the scarce resources.Finally,the experimental results demonstrate the effectiveness of the proposed approaches.(4)An improved maximal successful coalition generation algorithm is presented based on "contribution sharing".Since the "least workload" reduces the chance of agents to join the coalition,which is not conducive to the search of the maximal successful coalition,the resource contribution is spread on each member in a coalition to ensure that each available agent can participate in the coalition.After that,a more simple and effective encoding repair algorithm is proposed.The comparative results show that the proposed algorithm is particularly effective in large-scale settings.