- APPROCHES COLLECTIVES POUR LE PROBLEME DE LA PATROUILLE. - 1 PROBLÈME MULTI-AGENTS DE LA PATROUILLE. - Estimation de l’autosuffisance. - Le problème multi-agents de la patrouille consiste à faire parcourir un territoire à des agents de telle sorte que les différentes parties du territoire soient visitées le plus souvent possible par ces agents. - Dans le cadre du stage effectué au LORIA, nous abordons l’approche par l’intelligence en essaim pour le problème de la patrouille et de l’exploration multi-agents. - De plus, un autre objectif de ce stage est d’intégrer la limitation d’énergie au problème de la patrouille, de proposer un algorithme qui permette aux agents de coordonner les activités de patrouille et de recharge.. - La première introduit le problème multi-agents de la patrouille ainsi que les travaux antérieurs. - Dans une seconde partie, nous présentons l’intelligence collective et deux algorithmes, EVAP et CLInG, basés sur cette approche pour traiter le problème de la patrouille. - Enfin, la dernière partie est consacrée au problème de l’énergie dans la patrouille.. - 1 Problème multi-agents de la patrouille. - Elles reposent en général sur le marquage de l’environnement et définissent un moyen de communication et de calcul indirect entre les agents.. - Nous utilisons ceux se basant sur le calcul de l’oisiveté des nœuds (ou Idleness) qui peuvent être calculés au niveau d’un nœud ou au niveau du graphe.. - On trouve dans les travaux antérieurs deux types d’environnement utilisés par les modèles de la patrouille multi-agent : espace « discret » et espace « continu ». - Ce type de représentation convient pour le cas de la patrouille entre les lieux intérêts.. - La pré-connaissance de l’environnement est également une condition importante dans le problème de la patrouille. - En effet, elle influe sur le choix de l’algorithme de patrouille ainsi que sur sa performance.. - Les agents sont ici dotés d’une pré-connaissance de l’environnement. - La tâche de patrouille est exécutée sans connaissance de l’environnement. - Dans ce cadre, on peut utiliser des agents réactifs, ces derniers pouvant réaliser un apprentissage ou bien recourir à des techniques basées sur le marquage de l’environnement.. - Dans le cadre de ce stage, nous nous concentrons sur le problème de la patrouille en environnement inconnu, c'est-à-dire qu’il est impossible de disposer du graphe représentant l’environnement. - Le problème de la patrouille a été abordé ces dernières années selon des approches centralisées, heuristiques ou encore distribuées, mais toujours dans le cadre d’une représentation sous forme d’un graphe de l’environnement (un nœud étant un lieu prédéterminé qu’il faut visiter, une arrête un chemin reliant deux nœuds) et donc nécessairement une pré-connaissance de l’environnement. - On trouve dans [4] une solution reposant sur le principe d’optimisation par colonie de fourmis (ACO algorithms) mais qui nécessite là encore une pré-connaissance de l’environnement sous la forme d’un graphe. - Par conséquent, une telle technique n’est pas capable de s’adapter à un changement online du problème tel qu‘une modification de la topologie de l’environnement ou l’ajout ou la perte d’un certain nombre d’agents.. - • Flexible : l’adaptation à de brusques modifications de l’environnement.. - Le modèle EVAP que nous proposons pour le problème de la patrouille en environnement inconnu repose sur le dépôt d’une phéromone. - Pour chaque cellule c de l’env. - L’originalité de l’algorithme CLInG (Choix Local fondé sur une Information Globale) est d’introduire une seconde information dans l’environnement par la propagation des oisivetés maximales. - La Figure 6 présente les performances en oisiveté moyenne et maximale sur la map D pour le cas particulier de la patrouille. - En général, les performances des deux algorithmes sont proches de l’optimal théorique. - Le problème de l’énergie a été étudié au cours des dernières années, mais toujours dans le cadre du niveau physique. - D’après ce que nous savons, aucun papier ne se concentre exclusivement sur le problème de la patrouille avec limitation énergétique.. - physique, de l’installation du système de recharge et de l’interaction entre les robots et la station (cf. - L’étude du problème énergétique est indispensable pour le problème de la patrouille multi-robots. - Le problème de la recherche de station devient plus complexe dans notre contexte quand les agents ne sont pas dotés d’une pré-. - l’architecture d’agent réactif car le choix de la prochaine action en fonction de l’état des régions voisines offre l’avantage de la simplicité. - Cette approche repose sur la construction des champs numériques appliquée au problème de la fouille, qui a été introduit par Simonin, Charpillet et al. - On peut voir que ces champs numériques représentent la distance la plus courte de la station de recharge aux cellules portant ces valeurs. - Cet algorithme est à l’origine du Problème de l’Emplacement d’Installation qui a traité par Moujahed, Simonin et al. - Nous transposons ce problème au problème de l’optimisation de position du Tanker.. - L’influence de l’attraction baisse quand le Tanker se déplace vers l’agent. - L’intensité de la force répulsive est inversement proportionnelle à la distance entre les Tankers. - Comportement de l’Environnement. - Nous choisissons le point central de l’environnement comme position de la station de recharge (pour MARKA. - Un point remarquable de l’algorithme TANKER est que le tanker reste toujours au barycentre des agents travailleurs qui est la position optimale.. - A certains points de la simulation, les agents passent à. - Un avantage de MARKA est la capacité d’estimation de l’autosuffisance d’agent qui est très importante dans ce problème. - Cependant, il pose encore des problèmes au niveau de la découverte des stations de recharge.. - Ce stage concernait l’étude de l’approche par l’intelligence collective du problème multi-agent de la patrouille dans un environnement inconnu. - De plus, un autre objectif de ce stage était d’intégrer la limitation d’énergie au problème de la patrouille et de proposer un algorithme qui permette aux agents de coordonner les activités de patrouille et de recharge.. - • Robustesse : Le système est capable de se réorganiser de lui-même pour s’adapter aux différentes configurations de la patrouille.. - Nous avons également proposé deux modèles, MARKA et TANKER, pour traiter le problème de la patrouille avec limitation d’énergie. - Il est nécessaire d’approfondir de l’étude de TANKER et MARKA au niveau de la robustesse, de l’adaptation aux perturbations afin d’évaluer le comportement des robots. - Chevaleyre, Recent Advances on Multi-Agent Patrolling, Proceedings of the 17th Brazilian Symposium on Artificial Intelligence, pp.474 – 483, 2004 [2] E. - Chevaleyre, Le Problème Multiagent de la Patrouille, In Annales du LAMSADE No 4, 2005. - Chevaleyre, Theoretical analysis of multi-agent patrolling problem, Proceedings of the IEEE/WIC/ACM International Conference on Intelligent Agent Technology, pp.302 - 308, 2004. - Drogoul, Sharing a charging station without explicit communication in collective robotics, Proceedings of the 7 th International Conference on Simulation of Adaptive Behavior on From Animals to Animals, pp. - Luke, A pheromone-based utility model for collaborative foraging, Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp.36 – 43, 2004. - Multi-Agent Patrolling with Reinforcement Learning, Proceedings of the 3 rd International Joint Conference on Autonomous Agents and Multi-Agent Systems, pp.1122- 1129, 2004.. - Drogoul, Adaptive Patrol for a Group of Robots, Proceedings of the 2003 IEEE/RSJ, Intelligence Robots and Systems, Las Vegas, Nevada, pp. - Sukhatme, Staying alive: A docking station for autonomous robot recharging, Proceedings of the IEEE International Conference on Robotics and Automation, Washington D.C., pp.. - Vaughan, Recharging Robot Teams: A Tanker Approach, Proceedings of the International Conference on Advanced Robotics, pp. - Then we present the model CLInG [17] proposed in 2003 which introduces the diffusion of the idleness of areas to visit. - This problem was studied in recent years according to centralized, heuristic and distributed approaches, but always within a discrete representation of the environment, i.e. - Thus, various work based on graph search algorithms have been proposed, often deriving from the problem of the traveling salesman (cf. - a representation of the environment through a graph.. - Consequently, this type of solution is not able to self-adapt to online changes of the problem/environment, such as variations of the number of agents or moves of obstacles, etc.. - So, to deal with such a configuration of the problem (unknown environments) we think that swarm intelligence could be an efficient approach. - It is generally based on the marking of the environment, inspired by the ants’ pheromone drop, which defines an indirect calculation and means of communication among the agents [2].. - The diffusion process enables the propagation of the information by effect of vicinity, while evaporation allows removing gradually the information.. - In section 6 we synthesize these results to draw the interest of the two approaches.. - An efficient patrol in an environment (possibly dynamic) needs the delay between two visits of the same place to be minimal. - for which we do not have a graph of the areas to visit. - move to one of the four neighboring cells. - The swarm intelligence principle, inspired by the study of social insects [2], is based on the collective organization of the agents through their indirect communications in the environment. - This model only uses the evaporation process to exploit the remaining quantity of pheromone as an indicator of the time elapsed since the last visit of a cell (representing the idleness). - Thus, we define the agents behavior as a descent of the pheromone gradient (i.e. - The evaporation process of the pheromone in a cell is expressed by the following geometrical series on the quantity:. - The EVAP model can be seen as an extension of the Yanovski et al. - The principle of the EVAP agent behavior is the same as the gradient descent described in [12].. - 3.3 Interest of the swarm intelligence. - Suppose that an agent has visited three consecutive nodes of the following graph while dropping pheromones. - The originality of algorithm CLInG is adding second information into the environment by the diffusion of the maximum idleness. - This is a dual approach of the previous algorithm (EVAP), but this time, the information in the neighboring cells can come from further cells.. - The propagation of the maximum idleness allows exploiting the inherent environment’s properties and to transform objective information into subjective one which can be used directly by the agents. - The experiments of the 2 models were performed in 5 environments with growing complexity, taken or adapted from [1] and [18], cf. - The theoretical optimum idleness values are calculated as follows: Let c be the number of accessible cells of the environment. - Thus, the idleness of the departure cell will reach c-1. - Non Non----obstacle topology, Non obstacle topology, obstacle topology, obstacle topology, average average average average IIIIGI GI GI GI Figure 4 illustrates the average idleness of both methods for a variation of the agents number. - Figure 7.a shows the regularity of the pheromone deposit (the gradient) and as a consequence the optimum paths followed by agents. - We find here the problem identified by Wagner [18], due to the local vision of agents, of the choice between two nodes with equal interest (cf. - EVAP and and and and CLInG, Map E (screenshot) CLInG, Map E (screenshot) CLInG, Map E (screenshot) CLInG, Map E (screenshot) As we mentioned in section 3.3, the problem of the choice between several nodes, for the EVAP model, is reduced proportionately to the number of agents. - The objective of the previous section was to measure the interest of introducing the propagation of information compared to a model which only uses the evaporation process. - Initially, the system performs a first exploration of the environment, then, it changes brutally for more stable and effective behaviour.. - It is interesting to pay attention that in both methods the system self- organizes via the marking of the environment, and converges towards an effective patrolling (possibly optimal, see EVAP on map B).. - Algorithm CLING [16], one of the rare propositions, exploits the marking of the environment and the diffusion of information. - This difference of performance is reduced when the population increases, showing the collective nature of the proposed models. - So, the propagation process is proved to be an accelerator of the exploration phase of the multi-agent patrolling. - "Recent Advances on Multi- Agent Patrolling”, Proceedings of the 17th Brazilian Symposium on Artificial Intelligence, pp. - Chevaleyre, “The Patrolling Problem”,. - “Multi-Agent Patrolling with Reinforcement Learning”, Proceedings of the 3 rd international Joint Conference on Autonomous Agents and Multi-Agent Systems, pp. - Drogoul, “Adaptive Patrol for a Group of Robots”, Proceedings of the 2003 IEEE/RSJ, Intelligence Robots and Systems, Las Vegas, Nevada, pp