Multi-Agent Pursuit-evasion Based On Coordination Mechanisms

Agent-Based Models(ABMs)seek to clone human behavior in a virtual reality,or artificial environment.In an artificial environment,the agents’ decision-makers operate with each other,with the aim of producing possible phenomena understandable by social scientists.This definition may be not sufficiently clear to those who are not exp erts in Distributed Artificial Intelligence(DAI),but it provides a clear signification if we take into consideration that all of us are acquainted with video games,which reflect a specific type of ABM.As a matter of fact,video games integrate players in a virtual world in which some characters(the agents)interact: monsters,pursuers,evaders,astronauts,soldiers,and so on.Each of these agents undertakes a specific rules` protocol of behavior(a behavior algorithm)regarding the behavior in individ ual case and,most importantly,the case where the agent interact with other encountered agents.However,there exist so many possibilities that random encounters can readily transform the game into any of a number of very different results.Video games pr oduce possible events from the interactions between the agents implemented,some of which could be quite improbable.Multi-agent pursuit-evasion(PE)in unknown environment becomes one of the most interesting challenges in different areas based on agents such as task coordination and path planning.The general objective of this thesis is to propose coalition mechanisms for multi-agent systems based on organizational frameworks and game theoretic principles in order to examine and contribute in resolving the issue related to multi-agent pursuit-evasion problems.These coalition mechanisms will allow the cooperation of the agents and the coordination of their tasks to achieve global objectives promptly and effectively.On the other hand concerning the path p lanning,we propose a motion strategy based on the stochastic Markov Decision Process(MDP).Also,we develop an obstacle avoidance algorithm allowing an efficient behavior of the agents when an obstacle is encountered.The goal of the simulations effectuated is to showcase how these different mechanisms affect the evaders’ capturing time and the internal development of the pursuers during the pursuits.This thesis includes five chapters:Chapter 1 introduces the main objectives of our work as well as a gen eral discussion of the related works.In fact,we focus on the exploration of the different task and path planning methods applied to Multi-agent systems.Moreover,we take into consideration the application of these mechanisms in relation to the Pursuit-Evasion problem.These chapters conclude with a specification regarding the position of our work.Chapter 2 presents the proposition of a coalition formation algorithm based on Agent-Group-Role organizational model(AGR).This algorithm is applied to the Pursuit-Evasion problem in order to measure the impact of the pursuit groups’ formation and their stability on the capture of different evaders.In this model,the agents integrate the groups via the acquisition of the role proposed by the group.During the coalition formation,the agents have to execute a set of specific tasks from the creation to the dissolution of the group in order to achieve the objectives fixed.To control the motion strategies of the agents,we have based on Markov decision process pri nciples(MDP),which allow the formalization of sequential decision problems in cooperative multi-agent systems through the reward and transition functions.Chapter 3 resumes two other task coordination mechanisms based on organizational principles.With the aim of defining a pursuit group access mechanism,we propose a task coordination mechanism based on YAMAM organizational model(Yet Another Multi-Agent Model).Precisely,we determine how the concepts Agent,Role,Task,and Skill forming this framework are projected on the pursuit-evasion problem and used to optimize the task sharing between the pursuit groups.Furthermore,we develop a flexible organizational model extended from the AGR organizational model by the introduction of an access mechanism bas ed on fuzzy logic principles.The aim of this model is to allow the interaction,organization and the dynamic reorganization of the different groups.In relation to the pursuit-evasion problem,we have extracted coalition formation algorithms with differen t flexibility degrees from the proposed organizational model to highlight the positive effect imposed by the dynamic reorganization on the evaders’ capturing time as well as on the development of the pursuers during the execution of the tasks.In chapter 4,we propose a decentralized coalition formation algorithm based on the Iterated Elimination of Dominated Strategies(IEDS).This game theory process is common to solve problems that require the iterative withdrawal of dominated strategies in order to dete rmine the equilibrium provided via this method.Chapter 5 is focused on the processing of the complex obstacles such as U and H encountered during the pursuit of targets.In other words,we propose a new obstacle avoidance process based on Bug-Algorithms and the rewards generated through the application of MDP.This new process is known as Reward Bug Algorithm(RBA).In relation to the precedent Bug-Algorithms,this method increases the use of the environment’s data returned via the sensors equipping the pursuers.Moreover,we demonstrate how RBA improves the goal orientation of the pursuers as well as their decision concerning the obstacles’ leaving points.