Dynamic Coalition Formation In Distributed Heterogenous Multi-Agent Systems

Generally,complex tasks can be fulfilled via the cooperation of heterogeneous agents,which could be realized through coalition formation.Meanwhile,communication is the base of the cooperation in distributed multi-agent systems(DMASs).Therefore,when agents take multiple responsibilities,how to efficiently form coalitions is one of the keys to improving the task execution capability of DMASs.However,those coalition structures that fulfill the needs of communication are not necessarily suitable for task execution,and vice versa.Consequently,it is pressing to make a tradeoff between the two responsibilities,and design a framework to form an optimized coalition structure.Considering the dynamics of tasks,heterogeneous structure of the agents and uncertainty about other agents' decisions,it is a big challenge to solve the cooperation problem under complex tasks.The thesis focuses on the cooperation of multiple agent taking two responsibilities,i.e.,communication and task execution.Based on the theories of cooperative game,Bayesian and complex networks,we analyze the relationship between communication and task execution,then formulate the problem of complex task allocation into a dynamic coalition formation problem and propose optimal methods for dynamic coalition formation.Our main contributions are listed as following:1.By considering the communication and task execution constraints,a multiresponsibility-oriented coalition formation framework is proposed for agents to cooperate under complex circumstances,based on the cooperative game theory.Firstly,the relationship between the two responsibilities is analyzed,based on which the problem is decomposed into two sub-problems,i.e.,the dynamic task coalition formation and communication coalition re-construction problems.Secondly,a multi-responsibilityoriented coalition formation framework is proposed,which integrates two algorithms for communication coalition formation and task execution formation,respectively.2.For the problem of dynamic task coalition formation,in dealing with the heterogeneous DMASs and the dynamic tasks,this thesis designs a novel market-based mechanism for real-time task allocation.Firstly,the main factors of the real-time task allocation problem are analyzed,and the problem based on the coalition game theory is formulated.Then,a social network for communication is employed in this problem,and a negotiation mechanism is proposed for agents forming coalitions on timely emerging tasks.In the mechanism,an auction algorithm is utilized for real-time agent assignment on coalitions,and a mutual-selecting method is proposed to acquire better performance on agent utilization rate and task completion rate.Finally,our experimental results demonstrate that our market-based mechanism outperforms decentralized approaches in the literature w.r.t.the task completion rate(30% better on average).3.For the communication coalition re-construction problem,a constrained Bayesian overlapping coalition game model(CBOCG)is developed to formulate the problem,and a task-allocation-efficiency-oriented communication coalition utility function is defined to optimize a coalition structure for the CBOCG.By considering the geographical location dependence between two responsibilities,constrained agent strategies are defined to map agent strategies to potential location choices.Based on design above,this thesis proposes a distributed Location Pruning Self-adaptive algorithm(LPSA)for the constrained Bayesian overlapping coalition formation.4.A local centrality-based method is proposed for dynamic social networks reconstruction in distributed multiagent systems.Specifically,based on local information a novel Local Centrality(LC)is designed for each agent to evaluate its vitality in the employed communication networks.By considering the influencing factors in identifying vitality and the feature of the dynamic social network,the total power of a node is divided into two parts,i.e.,the structure power and execution ability power.The structure power can be obtained by the local structural power,which reveals the communication activity of the local networks of each node.Meanwhile,the ability of task execution of each node can be obtained by the local ability power.Through integrating the two powers,a new LC is designed to evaluate and reconstruct a dynamic social network.Based on the proposed local centrality,we design the Distributed Re-Construction Algorithm(DRA),for reconstructing the dynamic social network.To test its efficiency on communication reconstruction,the DRA is integrated into our former proposed dynamic task allocation algorithm and forms a new dynamic task allocation algorithm.Finally,the experiment results show that the newly improved algorithm performs better w.r.t.completion rate the task when compared to other dynamic task allocation algorithms,which reflects the efficiency of the communication network reconstructed by DRA.