Planification (intelligence artificielle)

Un problème de planification classique est défini généralement comme un problème de recherche dans un graphe. Chaque état qui décrit l'environnement dans lequel le planificateur cherche un plan est représenté par un nœud dans le graphe et chaque arête entre deux nœuds représente une action qui fait la transition d’un état à un autre.

Formellement un problème de planification classique est défini par une tuple ${\displaystyle \left\langle S,A,T,s_{0},G\right\rangle }$ où

• ${\displaystyle S}$ est un ensemble d'états,
• ${\displaystyle A}$ est un ensemble d'actions,
• ${\displaystyle T}$ est une fonction de transition qui à un état et une action associe un état t.q. ${\displaystyle T:S\times A\rightarrow S}$,
• ${\displaystyle s_{0}\in S}$ est l'état initial,
• ${\displaystyle G\subseteq S}$ est l'ensemble d'états but.

On parle de planification contingente (contingent planning) où l'environnement est observable grâce à des senseurs, qui peuvent être fautifs. Pour un problème de planification contingente, un plan n'est plus une séquence d'actions mais un arbre de décision car chaque étape du plan est représentée par un ensemble d'états plutôt qu'un seul état parfaitement observable comme dans le cas de la planification classique[16]. Les actions choisies dépendent de l'état du système. Par exemple, s'il pleut, l'agent choisit de prendre le parapluie, et sinon, il peut décider de ne pas le prendre.

Rintanen utilise la terminologie planification conditionnelle (conditionnal planning, comme mentionné par Rintanen dans son article[17] de 2004, p. 1). Mikael L. Littman démontre en 1998 que si on ajoute du branchement (planification contingente), le problème de planification devient EXPTIME-complet[18]. Ce résultat est redémontré par Jussi Rintanen en 2004[17]. Un cas particulier de planification contigente est représentée par les problèmes FOND – pour "fully-observable and non-deterministic". Si le but est spécifié en LTLf (logique temporelle linéaire sur trace finie) alors le problème est toujours EXPTIME-complet[19] et 2EXPTIME-complet pour une spécification du but en LDLf.

On parle de planification conformante (conformant planning, comme mentionné par Rintanen dans son article[17] de 2004, p. 1) où l'agent est incertain de l'état du système, et que l'agent ne peut faire aucune observation. L'agent a alors des croyances sur le monde réel. Ces problèmes sont résolus par des techniques semblables à celles de la planification classique, mais où l'espace des états est exponentiel dans les dimensions du problème, à cause de l'incertain sur l'état actuel. Une solution pour un problème de conformant planning est une séquence d'actions. Haslum et Jonsson ont démontré que le problème de planification conformante est EXPSPACE-complet[20].

Rintanen a démontré que, si on ajoute à la fois du branchement et de l'incertain (planification à la fois conformante et contingente), le problème devient 2EXPTIME-complet[15]. Dans ce problème, les agents ont une information partielle sur l'état du système mais peuvent disposer de certaines actions d'observation de l'état - par exemple, vérifier s'il pleut ou pas - et ainsi gagner de l'information sur l'état du système.

Kushmerick et al. ont introduit la planification probabiliste[21]. Dans leurs travaux, l'effet des actions est décrite avec des probabilistes. Il donne l'exemple de l'action `le robot prend un bloc' décrite de la manière suivante : si la pince du robot est sèche, alors le robot tient le bloc avec une probabilité 0.95 ; si la pince est humide, alors le robot ne tient le bloc qu'avec une probabilité de 0.5.

Cette problématique est du ressort de la théorie de la décision dans l'incertain. Ceci mène au problème de la génération de politique (ou stratégie) dans un arbre de décision ou dans un diagrame d'influence. Si l'hypothèse Markovienne est posée alors on se place dans le cadre d'un Processus de décision markovien (MDP) ou (dans le cas général) un Processus de décision markovien partiellement observable (POMDP).

La planification classique résout les sous-buts dans un ordre donné. Le problème est que cela amène parfois à détruire ce qui a déjà été construit. Ce phénomène est connu sous le nom d'anomalie de Sussman.

Supposons qu'un individu pieds nus doive se retrouver dans l'état où il porte sa chaussure droite, sa chaussure gauche, sa chaussette droite et sa chaussette gauche. S'il cherche à réaliser les buts dans l'ordre de l'énoncé, il échouera.

Pour résoudre ce type de problème, on peut passer à des plans partiellement ordonnés dans lesquels l'ordre entre les actions n'est fixé que lorsque c'est nécessaire (engagement au plus tard ou least commitment planning).

Dans l'exemple précédent, mettre la chaussure gauche doit se faire après avoir mis la chaussette gauche. Idem pour la droite. En revanche l'exécution du plan pour la gauche est indépendante de l'exécution pour la droite. Le plan global est donc partiellement ordonné.

Les planificateurs capables de gérer cette catégorie de problème sont dits à ordre partiel (POP, NOAH, etc).

Généralement, lorsque l'on planifie, on peut disposer d'une information hiérarchique sur les actions, c'est-à-dire une description sur comment des actions complexes se décomposent. Par exemple, une action complexe comme "servir un café" peut se décomposer en la séquence de deux actions complexes "préparer un café" puis "apporter le café". Ainsi, il existe des planificateurs, comme ABSTRIPS, qui en plus de la description des actions, prennent en entrée la description hiérarchique des actions. On peut par exemple commencer à planifier à haut niveau puis descendre dans le détail au besoin (comme le fait ABSTRIPS par exemple). L'objectif est alors décrit à l'aide d'un réseau hiérarchique de tâches (HTN pour hierarchical task network en anglais)[22].

La planification temporelle permet d'exprimer des durées d'actions, des conditions au début, à la fin et pendant l'action et des effets au début et à la fin des actions. Le langage PDDL 2.1 inclut la planification temporelle[23]. La méthode TLP-GP 1[24] construit un graphe, puis on résout des contraintes temporelles en utilisant un solveur SMT. On backtracke en cas d'inconsistance. Rintanen a démontré que la planification temporelle concurrente (plusieurs instances d'une même action en parallèle est possible) est EXPSPACE-complète. Par contre, si on relâche ces conditions, on peut se ramener à de la planification classique et donc la planification temporelle avec ces restrictions devient PSPACE-complète[25].

La planification générale consiste à produire un plan qui fonctionne pour plusieurs environnements de départ[26].

La planification multi-agents étudie la réalisation d'une tâche par plusieurs agents, par exemple plusieurs robots. La génération du plan et son exécution est alors souvent distribuée/décentralisée[27]^,[28]^,[29]. Un aspect important dans les plans est la coopération entre agents. Il existe aussi un algorithme de planification centralisé, qui s'appuie sur une généralisation de STRIPS au cadre multi-agents, appelée MA-STRIPS[30]. L'algorithme a ensuite été rendu distribué, en utilisant un solveur CSP distribué pour gérer la coordination entre agents[31]. Les auteurs, Nissim, Brafman et Domshlak, ont expérimentalement vérifié que leur algorithme est meilleur qu'une planification centralisée lorsque les agents ont peu d'interactions entre eux.

Une difficulté majeure de la planification multi-agent est l'explosion combinatoire de l'ensemble des actions, qui est exponentiel en le nombre d'agents. En 2011, Jonsson et Rovatsos propose une solution pour contrecarrer ce problème et se ramène à de la planification classique mono-agent[32]. Il y a aussi un gain à utiliser des techniques de parallélisation pour que les algorithmes de planification passent à l'échelle[33].

Le problème de planification épistémique consiste à prendre en compte les connaissances des agents dans la description des états et des actions[34]. Typiquement, l'objectif est une formule de la logique modale épistémique, comme "l'agent a sait que l'agent b que le bloc C est sur le bloc A" et les actions sont représentées avec des modèles d'actions de la logique épistémique dynamique[34]. Le problème de planification est indécidable dans toute sa généralité[35].

• Algorithmique de la planification en IA, Pierre Régnier, Editions Cépaduès, (ISBN 2-85428-658-8)
• (en) Malik Ghallab, Dana Nau et Paolo Traverso, Automated planning, Morgan Kaufmann, 2004 (ISBN 1-55860-856-7)
• (en) Michael R. Genesereth and Nils J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann, 1987 [détail de l’édition], chap. 12 Planning, pp. 285-306

• Planification de mouvement
• Recherche de chemin
• Apprentissage par renforcement
• Théorie de la décision dans l'incertain

• Portail de l'informatique théorique