Supervision : Amal EL FALLAH SEGHROUCHNI

Co-supervision : CORRUBLE Vincent

Coordination in Multi-Agent Systems : The timed patrolling problem with an open system setting

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.

2011-2013 Publications

• 2013
  • C. Poulet : “Coordination dans les systèmes multi-agents :Le problème de la patrouille en système ouvert”, thesis, phd defence 04/23/2013, supervision El fallah seghrouchni, Amal, co-supervision : Corruble, Vincent (2013)
• 2012
  • C. Poulet, V. Corruble, A. El Fallah‑Seghrouchni : “Working as a team: using social criteria in the timed patrolling problem”, Tools with Artificial Intelligence (ICTAI), 2012 IEEE 24^th International Conference on, Athènes, Greece, pp. 933-938, (IEEE) (2012)
  • C. Poulet, V. Corruble, A. El Fallah‑Seghrouchni : “Travailler en équipe : le choix social appliqué au problème de la patrouille multi-agents”, Actes des journées francophones sur les systèmes multi-agents (JFSMA '12), Honfleur, France (2012)
  • C. Poulet, V. Corruble, A. El Fallah‑Seghrouchni : “Auction-based strategies for the open-system patrolling task”, PRIMA - 15^th International Conference on Principles and Practice of Multi-Agent Systems, vol. 7455, Lecture Notes in Computer Science, Kuching, Malaysia, pp. 92-106, (Springer) (2012)
• 2011
  • C. Poulet, V. Corruble, A. El Fallah‑Seghrouchni, G. Ramalho : “The Open System Setting in Timed Multiagent Patrolling”, IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT), vol. 2, Lyon, France, pp. 373-376, (IEEE) (2011)
  • C. Poulet : “Étude du Problème de la Patrouille Multi-Agents en Système Ouvert”, Rencontres des Jeunes Chercheurs en Intelligence Artificielle 2011, Chambéry, France (2011)