基于协作机制的多Agent追捕研究

Chapter 1 Introduction1.1. MotivationCoalition formation, considered as a major focus in social systems, is animportant method of cooperation. In general, coalition formation between theagents is goal-directed and short-lived. Coalitions are formed in order toachieve a specific objective and dissolve when it is acp lished. Coalitionformation has received a considerable amount of attention in recent res earch[1][2]. In multi-agent systems, the interactions are controlled by some types ofimplicit or explicit organizations. These interactions generally control some o fthe systems behaviors, such as authority structures, requirement relations, anddata flows. Horling and Lesser[3]define the organization of a multi-agentsystem as follows the set of roles, relationships, and authority structures whichcontrol its behavior;. Otherwise, an organizational structure can reduce theglobal flexibility of the system, adversely influencing the putation ormunication overhead, and accentuate plexity to the system .Consequently, Ferber[4]proposed AALAADIN organizational model based onthree principal axes (AGR): Agent, Group and the Role used simultaneously todescribe the concrete agents organizations.Multi-agent cooperative pursuit is a nown multi-agent problem. Based onidentical conditions between pursuers and evaders, the pursuit-evasion problemcan be classified into single object pursuit and multi-object pursuit. The mainobjective of Multi-Agent pursuit-evasion games is how to lead one group ofpursuers to cooperate with each other in order to capture anoth er group ofevaders. Also, this problem has been considered in many references and itsapplications were inspired by an equally diverse set of approaches and usefultechniques, such as Graph theory[5], Polygonal environment[6] [7], Datamining[8], and Reinforcement learning[9]. In this ind of problem, the pursuersand evaders are presented in different inds of types. The type of a pursuerdenotes its pursuit capacity. Otherwise, the type of an evader reflects thenumber and type of pursuers required to capture this evader............1.2. General definitions of an Agent and Multi-agent systemsIn the past, the term agent; has been followed by a variety of sub-disciplines of Artificial Intelligence and puter science. The concept agents;became mon in robotics, data munications and concurrent systemsresearch, as well as software engineering, AI and distributed AI. An outstandingarticle in a British national daily paper made the following assumption: Agent-based puting (ABC) is liely to be the next significant breathrough insoftware development;[14].A plete programming paradigm has been named Agent OrientedProgramming;[15]. And yet each of these purposes appeals to a quite view ofagency. It is thus important to explore the question what is an agent?; verycarefully.The dictionary defines an agent as: one who, or that which, exerts poweror produces an effect;[16]. Although this definition is not very helpful, it doesat least denote that action is somehow implicated, and in effect it does seem atfirst glance that the notion of action is inextricably bound to that o f agency:Agents do things, they act: that is why they are called agents;[17].A tacit hypothesis is that agents play an active role, allowing actions thataffect their environment, rather than passively allowing their environment toaffect them: one often hears, in AI wor, of the agent of an action. Two wordsfrequently used to describe agentive action are autonomy and rationality.Autonomy generally signifies that an agent wors without direct human (orother) intervention or orientation. Rationality is not so readily tied down, but it is frequently employed in the pseudo-game-theoretic sense of an agentoptimizing its acting with respect to some valuation function;[18]. A principleof rationality implicitly supposes that an agent has independent goals that itwants; to reach..........Chapter 2 Pursuit coalition formation based onOrganization and Marov Decision Process2.1 IntroductionSelf-Organization relates to the process through which a system modifiesits current organization in order to adapt to changes in its objectives and theenvironment, without explicit external intervention. The self -organizingcapacity observed in many natural and artificial systems is very similar to theemergent collective intelligence in distributed multi-agent systems. A group ofagents interacting independently can form advantageous coalitions, which areby and large distributed and sometimes self-organizing. The coalition structuresare based on crucial factors such as agent types, their motivation to collaborate,the reward distribution methods and the perceived coalition values. In recentresearch activities, self-Organization principles are bined with several otherprinciples such as entropy[121]where the authors used the contradictionbetween the emergent self-organization and the second law of thermodynamics.This paradox is detailed through the coupling between the macro -level thathosts the self-organization (entropy reduction) and the micro-level (where someprocesses increase the entropy considerably). The micro-level is used asentropy sin allowing overall system entropy to increase while sequesteringthis increase from the interactions where self-organization is required. AndReinforcement Learning[122]where the novel self-organization mechanismproposed permits agents to self-organize the underlying wor during thelearning process. In addition, it uses information from learning to lead the self -organization process. Consequently, this wor is the first to focus on thiscooperation between learning and self-organization. This self-organizationmechanism uses heuristics with the aim of transferring the achieved nowledgeacross the different steps of self-organization. In this proposal we have focusedon the extraction of a coalition formation algorithm from AGR organizationalmodel in order to allow the alliance of the pursuers in the form of pursuitgroups............2.2 Environment descriptionIn robotics, the goal ahead is usually to move efficiently and quicly inorder to achieve a specific position in the environment. Thus, States generallydefine geographical positions. Therefore, the deposition of the environmentinto a grid of cells of the same size seems ideal as representation. In thisrepresentation each cell corresponds to a specific State.The pursuit coalition is constituted at the beginning of the tas, and willdismiss when the tas is acplished. Next time when confronting withsimilar tas, it is necessary to interact again and constitute a new coalition. Inorder to decrease the munication cost and avoid repeated information ininteractions, the concept of tying is introduced here............Chapter 3 Pursuit cooperation based on the access optimization and thedynamic reorganization...........473.1.Introduction........473.2.Fuzzy logic in multi-agent systems.........483.3.Yet Another Multi-Agent Model .....493.4.Pursuers coalition formations based on YAMAM organizational model.....513.5.Extension: Agent-Group-Role-Membership Function ..........543.6.Coalition formation algorithm based on AGRMF..........563.7.Simulation experiments....593.8.Summary....63Chapter 4 A decentralized cooperative pursuit based on game theoreticprinciples..........654.1.Introduction........654.2.The Iterated Elimination of Dominated Strategies .......694.3.Coalition formation algorithm based on IEDS.......714.4.NetLogo simulation platform..........744.5.Simulation experiments...........774.6.Summary...........82Chapter 5 Pursuit path planning based on an extension of Bug -Algorithms.....845.1.Introduction.......845.2.Bug Algorithms.........865.3.Problem description..........875.4.Pursuit path planning based on sensors detection..........895.5.Reward Bug-Algorithm.....905.6.Pursuit processing based on the Reward Bug-Algorithm .....92Chapter 5 Pursuit path planning based on an extensionof Bug-Algorithms5.1. IntroductionPursuit-Evasion game is a nown problem in Multi-agent systems. Thisproblem is approached through the elaboration of different tas coordinationand path planning mechanisms. This chapter proposes a new sensor-basedobstacle avoidance method extended from Bug-Algorithms with the aim ofproviding an efficient path planning to the pursuers during the targets' capture.Noting that, the environment is deposed on a grid of cells, in which MarovDecision Process (MDP) principles are implemented to lead the motion of theagents. In relation to Bug-Algorithms, this method increases the utilization ofthe sensors data to improve the decision maing regarding the obstacle'sleaving point. This fact maes this method goal-oriented and decreases thepursuers' path to the goal. Moreover, we showcase the performance of thismethod through a parative study with our previous wors in which Bug -2-algorithm was used to avoid the obstacles encountered. In relation to theprecedent chapters, the wor proposed in this chapter focuses on theimprovement of the path planning of the pursuers. However, we have used thecoalition formation proposed in section 3.6 of this thesis to coordinate thedifferent tass. Moreover, the results obtained in this chapter are pared withthe results obtained in Chapter 3 of this thesis.Obstacle avoidance constitutes an essential part of autonomous control asit maes agents capable of reaching the target without collision problems[108].Path planning involves the generation of the shortest path from source todestination in accordance to the sensorial information of environment. Manyobstacle avoidance algorithms are proposed recently, based on differentprinciples such as Particle Swarm Optimization (PSO) and Reinforcementlearning[109] [110], eye gaze and blins[111] [112] [113], as well as parallel linesdistance measurement system (IBPLDMS)[114].

..........ConclusionThe wor summarized in this thesis presents five new methods for multi -agents coordination applied to the pursuit-evasion problem. Four of thesecontributions concerns tas planning, and one of these contributions relates tothe planning of movements. These contributions provide solutions forcentralized and decentralized multi-agents architectures.The study of problems of coordination multi-agents from the point of viewtas planning has allowed us to propose four new solutions. In fact, we haveproposed three approaches based on organizational modeling framewors whichare considered as the first wors applied to the pursuit-evasion problem. In thefirst approach, we have proposed a pursuit coalition formation algorithm basedon AGR organizational model in order to evaluate the impact of the agentsregrouping in non-overlapping groups on the pursuit processing.In the second approach, we have modeled the pursuit problem inaccordance to the concepts Agent, Role, Sill, and Tas forming YAMAMorganizational model. In other words, we have defined a pursuit groups accessmechanism based on the different agents sills which will be evaluated toobtain the role pursuer in a specific pursuit group with the aim of achieving aspecific tas (capturing the evader concerned).In the third approach, we have proposed a new organizational modelingframewor nown as AGRMF extended from AGR through the application offuzzy logic principles. The groups in this model are equipped with amembership function calculating the membership degree of each agent inrelation to each group. Moreover, we have extracted a dynamic pursuit coalitionformation algorithm from this model, in which the membership functiondynamically determines the access to the role pursuer proposed by the pursuitgroup concerned...........参考文献（略）