Comment inclure les connaissances des agents dans la planification ?

La génération automatique de plans d'action est un sous-domaine de l’intelligence artificielle depuis ses origines. Le problème général est : étant donné des descriptions de l’état initial INIT, d’un but à atteindre BUT et d’un ensemble d'actions ACT dont dispose un agent, est-ce que cet agent peut enchaîner les actions de ACT de sorte à ce qu’elles amènent de INIT à BUT ? Les applications et l’échelle de complexité peuvent être très variées, allant de la réparation d’un pneu de vélo crevé à la planification d’une carrière. Étant donné la difficulté inhérente de ces problèmes, plusieurs hypothèses ont été faites afin de les simplifier. Dans la planification dite classique on suppose un environnement statique : toutes les modifications sont provoquées par l’agent planificateur qui possède une connaissance parfaite de l’état initial et des effets des actions. Sous ces hypothèses, l’existence d’un plan est décidable : il existe des algorithmes calculant en un temps fini s’il existe un plan ou non. Mieux, l'efficacité des algorithmes de planification s'est améliorée de manière spectaculaire : lors des compétitions annuelles les meilleurs planificateurs réussissent à résoudre des problèmes de référence (benchmarks) avec plusieurs milliers de variables.

Ces succès permettent d’aborder des questions plus complexes en planification. En effet, dans des contextes plus réalistes il y a plusieurs agents, artificiels ou humains, avec des connaissances de départ différentes et avec des capacités d’observation limitées. On parle alors de planification épistémique : l’état initial décrit non seulement le monde, mais aussi ce que les agents savent et ignorent ; il en est de même pour le but ; finalement, les actions ont des effets non seulement sur le monde mais aussi sur les connaissances des différents agents en fonction de ce qu’ils en observent. De surcroît, ces connaissances portent non seulement sur le monde, mais aussi sur les connaissances d'autres agents, voire sur leurs connaissances à propos des connaissances d’un tiers, etc. : on parle alors de connaissances d'ordre supérieur. Par exemple, un robot interagissant avec un humain doit pouvoir prendre en compte la perspective de ce dernier : il a besoin d’une connaissance d’ordre deux (et si la connaissance de l’humain en question est à propos de la connaissance du robot alors ce dernier dispose d’une connaissance d’ordre trois, etc.) On sait que de telles connaissances sont fondamentales pour l’interaction entre agents : leur absence rend difficiles la communication et la compréhension mutuelle.  

La planification épistémique est nettement plus difficile que la planification classique : le problème de l’existence d’un plan est indécidable, c’est-à-dire que pour tout algorithme il existe des problèmes pour lesquels l’algorithme ne se termine pas. Afin de rendre le problème décidable les chercheurs ont imposé des restrictions sévères sur les actions : ou bien les agents ne peuvent communiquer que des faits du monde (ce qui exclut la communication de connaissances) ou bien toutes les actions doivent être publiques (ce qui exclut par exemple les appels téléphoniques entre deux agents non observés par des tiers). Un groupe de chercheurs de l’IRIT vient de concevoir une approche plus générale qui permet de lever ces restrictions. Un type de problème qui peut maintenant être résolu de manière automatique est celui des problèmes de bavardage (gossip problems) : dans l’état initial, n agents ont chacun une information qui n’est connue d’aucun autre agent ; le but est la connaissance partagée d’ordre deux de toutes les informations ; et les agents communiquent par appels téléphoniques. Par exemple après une catastrophe ou un attentat, on peut imaginer un groupe d’amis essayant de savoir si chacun va bien. Il est alors tout à fait réaliste qu’un ami ne se contente pas de savoir que tout le monde va bien : il aimerait aussi rassurer les autres et aimerait donc qu’il y ait connaissance partagée d’ordre deux (telle que tout le monde sait que tout le monde sait que tout le monde va bien) ; voire d’ordre trois ou au-delà. De plus, les chercheurs de l’IRIT ont démontré que cette classe de problèmes moins restreinte est non seulement décidable, mais a aussi la même complexité que la planification classique, rendant ainsi possible l’utilisation de logiciels existants.