Gauthier Picard: Approches décentralisées pour l’allocation de tâches multi-agents et multi-modes

Dans cette présentation, nous abordons des modèles et techniques pour l’allocation de tâches dans un cadre multi-agents, comme dans des collectifs de robots autonomes. Dans ce contexte, un ensemble d’agents doit se coordonner pour décider de l’affectation d’une ou plusieurs tâches à chaque agent, en fonction du contexte opérationnel. Ce contexte peut inclure la position courante des agents, le trajet à effectuer pour atteindre les tâches, ou encore la fenêtre de validité des tâches. Même dans sa formulation la plus simple, ce problème peut s’avérer difficile à résoudre de manière optimale.

Dans un contexte distribué, de tels problèmes peuvent être résolus par des approches par enchères combinatoires coopératives, ou bien par des algorithmes approchés basés sur la séquentialisation ou la parallélisation de la constitution des lots de tâches. Cependant, ces différentes approches, bien que distribuées, reposent sur une résolution centralisée du problème de détermination des gagnants (WDP), où un commissaire-priseur détermine les gagnants et les informe. Pour pallier cette limitation opérationnelle, qui impose un point de défaillance unique au système, des approches par consensus proposent de décentraliser le WDP.

Nous nous intéresserons particulièrement aux cas où les tâches à allouer peuvent nécessiter la collaboration de plusieurs agents pour leur complétion, et peuvent être effectuées de plusieurs manières différentes. Ce cadre est motivé par un problème d’allocation de tâches d’observation de la Terre par une constellation de satellites gérée par plusieurs acteurs ayant des exigences de privacité des plans, qui servira d’exemple applicatif.