Research On Cooperation And Coordination In Multi-agent Systems

Automatic computing is striding forward to pervasive,network-oriented, intelligent,agent-based,and humanized computation.Multi-agent computing is an advanced computing mode emerging right after distributed computing and peer-to-peer computing.Its problem solving process is very close to the way of thinking human being do.Unlike traditional algorithm designing which has to analyze the problem comprehensively,multi-agent computing only needs to assign agents their targets and then keeps free while these agents will automatically achieve client's targets by their active interaction.Building multi-agent systems for large and distributed problems makes computer system more intelligent and further liberates people from their work.Agent-oriented software engineering makes programming more humanized with software designing complying with how people think.Agent based society simulation combines computer science and sociology, which makes computer technology penetrate into humanity science.It is convinced that Multi-agent computing can prosper computer technology.However,lots of effort should be made before multi-agent computing can really have a variety of outstanding properties as its concept says.As far as agent-based systems are concerned,agent construction,communication language designing, mechanisms of cooperation and coordination are three key problems to be solved urgently.Therein,ability to interact aiming at cooperation and coordination is the very point that distinguishes multi-agent computing from other computing modes. The same as human society,cooperation and coordination is an important method to solve large and complicated problems.This dissertation has actively investigated this issue,and made some achievements at some sub-directions.Research on cooperation of multiple agents concentrates on organization building,alliance forming,and task allocation.Organization and alliance are the infrastructure of multi-agent cooperation,while task allocation instantiates cooperation relationship among agents.Here,as for task allocation in multi-agent systems,considering agent topology and capability of different levels,on the basis of past task allocation algorithm in parallel computing we come up with two task allocation algorithms adaptable to agent topology among cooperative and heterogeneous agents.One tries to get optimal agent combination by brute-force searching on account of the two parameters topology and heterogeneity.The other gets suboptimal allocation scheme but with lower time complexity.In large scale multi-agent systems and when tasks arrive dynamically,above-mentioned algorithms seem incompetent.Hence,we go on with research on allocation of multiple task flows,and propose a Q-learning based distributed and self-adaptable algorithm.This algorithm can not only adapt to task arrival process on itself,but also fully consider the influence from task flows on other agents.Besides,its distributed property guaranteed that it can be applied to open multi-agent systems with local view.Reinforcement learning makes allocation adapt to system load and node distribution.It is verified that this algorithm improves task throughput,and decreases average execution time per task.As for coordination in multi-agent systems,related work can be divided into three parts,which are colony mental state models,multi-agent planning,and social laws. Each of them has their own advantage and effectiveness.Our work on this problem extends research on multi-agent planning.However,plans by our two models means action selection policy for achieving a certain target,rather than a series of actions in the traditional manner.Stochastic policy makes plans more flexible. Multi-agent learning is a promising method in obtaining action policy.In this dissertation we analyze conflict game which implies a competing relationship between agents arising frequently in multi-agent domains,define agent's optimal responding policy based on Nash equilibrium of matrix games,and then find such policy using reinforcement learning a model-free method.Policy by this model dramatically brings down the frequency of conflicts,enhancing coordination of agents' behaviors.Furthermore,in the view of long-term utility,policy is fair to some extent,in favor of system stability.In general-sum games,many algorithms are likely to be exploited and consequently acquire less utility.After examining time-related policy and adaptability,we believe that dynamic policy with the two important attributes helps agents make more rational decisions and responses maximizing their payoff,avoiding risk of being exploited in mixed multi-agent environment.Once agents are deployed and applied in large scale,agent society will become a special multi-agent system.Social attributes of agents become more and more important.Apart from mental states such as belief,desire,intention,personality will also play an important role in agent action selection.Modeling other agents on account of their personality benefits making more harmonious policy.Under this background,we put personality into action selection of agents,and based on qualitative decision theory build an individualized action selection model.Different qualitative decision making principles correspond to different personality.Selection according to these decision making principles leads to diversity of agents' actions. Furthermore,considering complexity and hardship on description of personality,and advantage that artificial neural network is capable of depicting functions difficult to understand,therefore a new individualized action selection model is proposed based on neural network.Compared with the one based on qualitative decision making theory,this model has stronger ability to describe personality,from extreme to subtle types.Besides,a simulation platform for multi-agent system is developed using tool kit SWARM which aims to model complex adaptive systems.And application of personality is investigated by a practical instance,making significance and realistic value of personality more explicit.Although the principle behind these models is simple,it is a new attempt and elementary exploration in another way to research on mental states of agents except for traditional symbol logic,making it possible to reflect chaos and complexity of agent society from multiple aspects.In sum,with cooperation and coordination in multi-agent systems as research subject,through broad investigation and deep exploration,this dissertation proposed several beneficial models and algorithms on task allocation,learning based behavior coordination,and individualized action selection as follows.Algorithm on task allocation adaptable to network topology among cooperative heterogeneous agentsAlgorithm on dynamic task allocation of multiple task flows based on Q-learningMechanism on reinforcement learning for multi-agent conflict game based on regret valueMechanism on reinforcement learning of dynamic policy for general-sum game under mixed multi-agent environmentModels on agent individualized action selection based on qualitative decision theoryModels on agent individualized action selection based on artificial neural network...