Publié le 20 juillet 2021–Mis à jour le 22 juillet 2021
La génération automatique de plans constitue un problème de raisonnement difficile et même indécidable dès que les connaissances des agents sont impliquées. Dans un travail qui a été publié dans la revue Artificial Intelligence, des scientifiques de l’Institut de recherche en informatique de Toulouse (IRIT - CNRS/Toulouse INP/UT1 Capitole/UT2J/UT3 Paul Sabatier) ont réussi à identifier une nouvelle classe de problèmes décidables qui permet de planifier en prenant en compte des connaissances des agents.
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. (...)
