Coordination d’agents de planification hétérogènes en interaction à l’aide de la théorie des jeux – CHIP-GT

La planification automatisée est couramment utilisée pour décider d'une séquence d'actions tout en anticipant leurs effets en vue d'optimiser une (ou plusieurs) métrique(s). Elle est utilisée pour décider à court ou long terme, pour la planification des actions d'un ou plusieurs agents et pour raisonner à un niveau stratégique ou tactique, voire jusqu'à calculer des actions exécutables par un agent.
D'un autre côté, les méthodes de la théorie des jeux sont couramment exploitées à un niveau stratégique (haut niveau d'abstraction), pour calculer les stratégies permettant d'optimiser l'espérance des récompenses d'un agent, tout en considérant les stratégies (aléatoires) des autres agents.
La théorie des jeux est utile, entre autres, dans le cadre des jeux non-coopératifs. Dans ces jeux, très fréquemment rencontrés dans les applications, les joueurs ne se coordonnent pas, soit parce que leurs objectifs (utilités) sont différents, soit parce que leurs possibilités de communication sont limitées. Combiner les méthodes de la planification automatisée et de la prise de décision séquentielle dans l'incertitude avec la théorie des jeux peut être bénéfique, en particulier pour résoudre des problèmes de planification multi-agents, impliquant le choix de stratégies à court terme et l'exécution de plans à long terme.
Le but du projet CHIP-GT est de proposer un cadre théorique et des algorithmes pour cette classe de problèmes de planification. A cette fin, des méthodes de la théorie des jeux non coopératifs et de la planification automatisée sous incertitude (planification de tâches et de mouvements) seront combinées. Le premier objectif de CHIP-GT est d'établir un formalisme approprié pour définir et analyser la classe de problèmes que nous avons l'intention de résoudre. Cela comprend l'étude de la complexité du calcul de stratégies jointes (équilibres de Nash) des agents, ainsi que de la possibilité d'un passage à l'échelle en conditions réelles. Ce passage à l'échelle nécessite l'établissement de procédures de réparation de plans (pour tenir compte des effets imprévus des actions en environnement réel), l'inclusion d'agents potentiellement nombreux (quelques dizaines), contrôlables et non-contrôlables. Nous travaillerons donc à concevoir l'architecture d'un cadre informatique capable de combiner la théorie des jeux avec la planification automatisée, en nous concentrant spécifiquement sur l'exécutabilité des plans calculés : prise en compte de nouvelles informations détectées, réparations de plans flexibles si nécessaire, etc...
Des algorithmes de la théorie des jeux et de la planification seront implémentés en tant que modules principaux du cadre (back end). Par ailleurs une interface (front-end) de modélisation d'agents planificateurs en interaction sera développée. Pour illustrer l'applicabilité des méthodes développées dans CHIP-GT, nous utiliserons des benchmarks issus du domaine des "Green Security Games" (GSG), dans lesquels les agents doivent décider de stratégies de conservation de la biodiversité dans les milieux naturels et planifier des actions exécutables tout en tenant compte de la topologie complexe du terrain d'étude et l'incertitude liée à l'environnement et autres agents (coopératifs et non-coopératifs). Pour un pipeline de validation plus réaliste, CHIP-GT travaillera à la fois en utilisant des données environnementales et en construisant un simulateur de GSG "génériques". Les résultats obtenus seront utiles dans les domaines de la planification dans l'incertain et de la théorie des jeux, mais également dans le cadre de l'écologie théorique et des sciences de la conservation de la biodiversité.