Chapter 1 Introduction
1.1. Motivation
Coalition 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 accomp 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 system’s 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 computation orcommunication overhead, and accentuate complexity 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 known 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 kind of problem, the pursuersand evaders are presented in different kinds 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 systems
In the past, the term “agent” has been followed by a variety of sub-disciplines of Artificial Intelligence and computer science. The concept “agents”became common in robotics, data communications 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 computing (ABC) is likely to be the next significant breakthrough insoftware development”[14].A complete 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 work, of the agent of an action. Two wordsfrequently used to describe agentive action are autonomy and rationality.Autonomy generally signifies that an agent works 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 it“wants” to reach.
.........
Chapter 2 Pursuit coalition formation based onOrganization and Markov Decision Process
2.1 Introduction
Self-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 combined 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 "sink" 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 network during thelearning process. In addition, it uses information from learning to lead the self -organization process. Consequently, this work is the first to focus on thiscooperation between learning and self-organization. This self-organizationmechanism uses heuristics with the aim of transferring the achieved knowledgeacross 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 description
In robotics, the goal ahead is usually to move efficiently and quickly inorder to achieve a specific position in the environment. Thus, States generallydefine geographical positions. Therefore, the decomposition 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 task, and willdismiss when the task is accomplished. Next time when confronting withsimilar task, it is necessary to interact again and constitute a new coalition. Inorder to decrease the communication 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...........47
3.1.Introduction........47
3.2.Fuzzy logic in multi-agent systems.........48
3.3.Yet Another Multi-Agent Model .....49
3.4.Pursuers’ coalition formations based on YAMAM organizational model.....51
3.5.Extension: Agent-Group-Role-Membership Function ..........54
3.6.Coalition formation algorithm based on AGRMF..........56
3.7.Simulation experiments....59
3.8.Summary....63
Chapter 4 A decentralized cooperative pursuit based on game theoreticprinciples..........65
4.1.Introduction........65
4.2.The Iterated Elimination of Dominated Strategies .......69
4.3.Coalition formation algorithm based on IEDS.......71
4.4.NetLogo simulation platform..........74
4.5.Simulation experiments...........77
4.6.Summary...........82
Chapter 5 Pursuit path planning based on an extension of Bug -Algorithms.....84
5.1.Introduction.......84
5.2.Bug Algorithms.........86
5.3.Problem description..........87
5.4.Pursuit path planning based on sensors detection..........89
5.5.Reward Bug-Algorithm.....90
5.6.Pursuit processing based on the Reward Bug-Algorithm .....92
Chapter 5 Pursuit path planning based on an extensionof Bug-Algorithms
5.1. Introduction
Pursuit-Evasion game is a known problem in Multi-agent systems. Thisproblem is approached through the elaboration of different task 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 decomposed on a grid of cells, in which MarkovDecision 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 making regarding the obstacle'sleaving point. This fact makes this method goal-oriented and decreases thepursuers' path to the goal. Moreover, we showcase the performance of thismethod through a comparative study with our previous works in which Bug -2-algorithm was used to avoid the obstacles encountered. In relation to theprecedent chapters, the work 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 tasks. Moreover, the results obtained in this chapter are compared withthe results obtained in Chapter 3 of this thesis.Obstacle avoidance constitutes an essential part of autonomous control asit makes 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 blinks[111] [112] [113], as well as parallel linesdistance measurement system (IBPLDMS)[114].
..........
Conclusion
The work summarized in this thesis presents five new methods for multi -agents coordination applied to the pursuit-evasion problem. Four of thesecontributions concerns task 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 viewtask planning has allowed us to propose four new solutions. In fact, we haveproposed three approaches based on organizational modeling frameworks whichare considered as the first works 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, Skill, and Task forming YAMAMorganizational model. In other words, we have defined a pursuit group’s accessmechanism based on the different agents’ skills which will be evaluated toobtain the role pursuer in a specific pursuit group with the aim of achieving aspecific task (capturing the evader concerned).In the third approach, we have proposed a new organizational modelingframework known 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.
..........
参考文献（略）