GT MAFTEC

Planification Multi-Agents, Flexible, Temporelle, Epistémique et Contingente

Activités du GT

Responsables

Description

Contexte — L’objectif traditionnel de la communauté planification, comme nous pouvons le voir par exemple lors de la conférence ICAPS (International Conference on Automated Planning and Scheduling), est la génération de plans pour un agent individuel, où il est supposé qu’aucun autre agent n’interagit avec cet agent. Ce problème de base, connu sous le nom de planification classique, suppose que les actions de l’agent (appelées « actions STRIPS ») sont décrites par leurs effets positifs et négatifs en termes d’ajout et de suppression de propositions atomiques et que l’agent a une information parfaite (connaissance complète de l’état actuel de toutes ces propositions atomiques). Beaucoup de progrès ont été accomplis pour ce genre de tâches de planification. Il y a près de vingt ans un langage standardisé pour les tâches de planification classiques a été défini, PDDL (Planning Domain Definition Language). Ceci a permis de formuler des benchmarks et d’organiser une compétition internationale de planification (IPC) entre planificateurs automatiques à ICAPS. Tout au long de la dernière décennie, ces compétitions ont été marquées par des progrès constants, et maintenant il est considéré que les tâches de planification pour lesquelles aucun algorithme polynomial n’existe peuvent néanmoins être calculées de manière satisfaisante : les tâches avec des milliers d’objets et prédicats peuvent souvent être résolues par des programmes de génération de plans en quelques secondes.

Au-delà de la planification classique, la génération de plans pour un agent individuel ayant une information incomplète a également été étudiée au cours des 25 dernières années : la planification conformante permet aux agents d’avoir une connaissance incomplète de la situation initiale, mais sans actions d’observation (sensing), alors que la planification contingente permet de telles actions.

Forte des progrès spectaculaires obtenus pour les tâches mono-agent, la communauté planification est de plus en plus intéressée par les tâches multi-agents, impliquant, par exemple, des essaims de robots ou des interactions robot-humain. Il existe maintenant un atelier DMAP (Distributed and Multi-Agent Planning) qui est affilié à ICAPS et dont la quatrième édition a eu lieu en 2016. Les articles qui y sont présentés étendent des techniques et algorithmes pour le cas mono-agent au cas multi-agent. Une compétition préliminaire de planificateurs distribués ou multi-agents a également été organisée à ICAPS 2015 dans l’optique d’ouvrir une catégorie multi-agent (Multi-Agent Planning track) pour les compétitions IPC à venir.

Le raisonnement sur les connaissances et les croyances d’un agent (y compris les croyances d’ordre supérieur, à savoir, les croyances sur les connaissances des autres agents) est le sujet traditionnel de la logique épistémique étudiée en philosophie et en informatique. Dans les années 1990, il y a eu un « tournant dynamique » : les logiques épistémiques dynamiques représentent également les effets des actions sur les connaissances des agents. Récemment, certains auteurs ont commencé à examiner les problèmes de planification dans ce cadre. Le but de ce groupe de travail est de pousser cette convergence plus loin.

Objectifs — L’objectif principal de ce groupe de travail est de fédérer les recherches sur les différentes thématiques de la planification dans le but de modéliser et résoudre des problèmes complexes du monde réel dans lesquels de nombreux agents (humains ou automatiques) interagissent de manière coopérative et robuste via des actions physiques, de communication et d’observation pour atteindre des buts communs dans un environnement partiellement imprédictible. D’importants aspects du plan résultant sont qu’il prenne en compte les croyances de chacun des agents qui peuvent changer au cours du temps, qu’il permette l’exécution simultanée d’actions, qu’il soit suffisamment flexible pour autoriser des agents individuels à faire eux-même certains choix, et qu’il soit robuste à l’échec de certaines actions ou à des changements dans l’environnement. Ceci implique inévitablement d’aller au delà des hypothèses restrictives de la planification classique dans le but d’obtenir le niveau d’expressivité requis, et dans un même temps de développer des algorithmes efficaces afin d’être capable de résoudre des problèmes de planification du monde réel. De telles applications réalistes nécessitent un cadre théorique étendu incorporant les aspects suivants :

Multi-agent : la plupart des applications actuelles de la planification nécessitent l’intervention et la coopération entre plusieurs agents (chaque agent étant soit artificiel soit humain).

Plans flexibles : pour que, si possible, chaque agent (ou groupe d’agents) ait un certain degré d’autonomie concernant, par exemple, l’instant de début ou de fin d’une action ou alors les actions utilisées pour atteindre un sous-but, tout en étant soumis à des contraintes garantissant la correction du plan. Ceci est important pour ne pas imposer des choix arbitraires à des agents humains.

Temporel : pour prendre en compte la nature non-instantanée de certaines actions, conditions ou buts, comme le fait que les actions puissent se superposer (ce qui est essentiel pour la modélisation correcte de problèmes nécessitant la concurrence des actions).

Epistémique : pour modéliser les croyances de chaque agent (l’aspect épistémique, incluant des croyances d’ordre supérieur) aussi bien que l’état physique du monde (l’aspect ontique), en permettant la découverte interactive et dynamique de la connaissance par des actions d’observation (sensing) et de communication avec conditions et effets épistémiques.

Contingent : pour permettre la construction de plans qui soient robustes au fait que les agents puissent avoir une connaissance incomplète de l’état initial, que les croyances puissent être inconsistantes avec l’état courant du monde (à cause d’événements exogènes ou non-observés) et que le résultat de certaines actions puisse être imprévisible.

Certaines combinaisons limitées de ces cinq aspects ont été précédemment étudiées. Les premiers résultats sont prometteurs et semblent indiquer qu’il soit possible, via des transformations de problèmes, de réutiliser une large part des travaux déjà effectués en planification classique. Bien sûr, l’interaction entre ces différents aspects de la planification que nous voulons intégrer dans un planificateur unique pourra conduire à de nouvelles questions théoriques intéressantes et de nouveaux défis pratiques qui sont impossibles à prévoir avant d’entreprendre ces recherches.