Coordination dans les systèmes multi-agents : Le problème de la patrouille en système ouvert
Institution:
Paris 6Disciplines:
Directors:
Abstract EN:
La patrouille temporelle multi-agent est un problème intéressant pour tester et comparer différentes méthodes de coordination multi-agent sur une tâche coopérative : la visite répétée et fréquente des zones d'intérêt d'un graphe. Cependant, le problème actuel est limité par des hypothèses fortes telles que la fermeture du système et la synchronicité des communications, ce qui limite sa complexité et son applicabilité. Dans cette thèse, nous proposons de lever ces hypothèses et d'étudier diverses stratégies de coordination au regard du nouveau problème. Dans un premier temps, nous proposons un cadre d'étude à la nouvelle tâche : formalisation, métriques, stratégies de référence. Dans un second temps, nous étudions l'impact de la levée de ces hypothèses sur les stratégies à base d'enchères. Nous proposons alors l'usage de mécanismes de gestion des entrées et sorties d'agents pour diminuer cet impact. Nous montrons aussi qu'il est possible d'égaler les performances des stratégies centralisées de référence de s'inspirant de la théorie du choix social computationnelle pour créer des stratégies à base d'enchères coopératives et décentralisées. Enfin, nous ouvrons le problème du passage à l'échelle du problème, tant sur la taille du graphe que sur la taille de la société d'agents, ainsi que celui de l’applicabilité du problème.
Abstract FR:
The timed multi-agent patrolling task is an interesting problem to test and compare coordination strategies on a cooperative task: visiting repetitively and frequently areas of interest in a graph. However, until now this task was limited by strong hypothesis: the system is closed, and the communications are synchronous. These hypotheses limit strongly both its complexity and applicability. In this thesis, we propose to lift these hypotheses and study the behaviour of various coordination strategies on the new task. In a first time, we propose a framework for the new problem: formal description, metrics, and strategies to use as references. In a second time, we show the impact of lifting these hypotheses on auction-based, decentralized strategies. We propose various mechanisms to cope with the open system setting and decrease its impact. We also show that it is possible to apply computational social choice theory concepts to the patrolling task and create cooperative, decentralized auction-based strategies that perform as well as centralized, reference strategies. Finally, we open the patrolling problem on the scaling perspective, both in terms of graph size and population size.