La planification et la planification automatisées, parfois désignées simplement par le nom de AI Planning, sont une branche de l’intelligence artificielle qui concerne la réalisation de stratégies ou de séquences d’actions, généralement destinée à être exécutée par des agents intelligents, des robots autonomes et des véhicules sans pilote. Contrairement aux problèmes classiques de contrôle et de classification, les solutions sont complexes et doivent être découvertes et optimisées dans un espace multidimensionnel. La planification est également liée à la théorie de la décision.

Dans les environnements connus avec des modèles disponibles, la planification peut être effectuée hors ligne. Des solutions peuvent être trouvées et évaluées avant leur exécution. Dans des environnements inconnus de manière dynamique, la stratégie doit souvent être révisée en ligne. Les modèles et les politiques doivent être adaptés. Les solutions recourent généralement à des processus itératifs d’essais et d’erreur couramment observés en intelligence artificielle. Celles-ci incluent la programmation dynamique, l’apprentissage par renforcement et l’optimisation combinatoire. Les langues utilisées pour décrire la planification et la planification sont souvent appelées langues d’action.

Vue d’ensemble
À partir d’une description des états initiaux possibles du monde, des objectifs souhaités et d’un ensemble d’actions possibles, le problème de planification consiste à synthétiser un plan garanti (lorsqu’il est appliqué à l’un des états initiaux). générer un état contenant les objectifs souhaités (cet état est appelé état d’objectif).

La difficulté de la planification dépend des hypothèses simplificatrices utilisées. Plusieurs classes de problèmes de planification peuvent être identifiées en fonction des propriétés qu’ils ont sous plusieurs dimensions.

Les actions sont-elles déterministes ou non déterministes? Pour les actions non déterministes, les probabilités associées sont-elles disponibles?
Les variables d’état sont-elles discrètes ou continues? S’ils sont discrets, n’ont-ils qu’un nombre fini de valeurs possibles?
L’état actuel peut-il être observé sans ambiguïté? Il peut y avoir une observabilité totale et partielle.
Combien y a-t-il d’états initiaux, finis ou arbitrairement?
Les actions ont-elles une durée?
Plusieurs actions peuvent-elles être entreprises simultanément ou une seule action est-elle possible à la fois?
L’objectif d’un plan est-il d’atteindre un état d’objectif désigné ou de maximiser une fonction de récompense?
Y a-t-il un seul agent ou plusieurs agents? Les agents sont-ils coopératifs ou égoïstes? Est-ce que tous les agents construisent leurs propres plans séparément, ou les plans sont-ils construits de manière centralisée pour tous les agents?

Le problème de planification le plus simple possible, appelé problème de planification classique, est déterminé par:

un état initial unique connu,
actions sans durée,
actions déterministes,
qui ne peut être pris qu’un à la fois,
et un seul agent.

Étant donné que l’état initial est connu sans ambiguïté et que toutes les actions sont déterministes, l’état du monde après toute séquence d’actions peut être prédit avec précision, et la question de l’observabilité n’est pas pertinente pour la planification classique.

En outre, les plans peuvent être définis comme des séquences d’actions, car on sait toujours à l’avance quelles actions seront nécessaires.

Avec des actions non déterministes ou d’autres événements indépendants de la volonté de l’agent, les exécutions possibles forment un arbre et les plans doivent déterminer les actions appropriées pour chaque nœud de l’arbre.

Les processus de décision de Markov à temps discret (MDP) posent des problèmes de planification avec:

actions sans durée,
actions non déterministes avec probabilités,
observabilité totale,
maximisation d’une fonction de récompense,
et un seul agent.

Lorsque l’observabilité totale est remplacée par une observabilité partielle, la planification correspond à un processus de décision de Markov partiellement observable (POMDP).

S’il y a plus d’un agent, nous avons une planification multi-agents, qui est étroitement liée à la théorie des jeux.

Planification indépendante du domaine
Dans AI Planning, les planificateurs saisissent généralement un modèle de domaine (description d’un ensemble d’actions possibles modélisant le domaine), ainsi que le problème spécifique à résoudre spécifié par l’état initial et l’objectif, contrairement à ceux dans lesquels il n’existe pas domaine d’entrée spécifié. Ces planificateurs sont appelés « indépendants du domaine » pour souligner le fait qu’ils peuvent résoudre les problèmes de planification dans un large éventail de domaines. L’empilement de blocs, la logistique, la gestion du flux de travail et la planification des tâches du robot sont des exemples typiques de domaines. Par conséquent, un planificateur indépendant d’un seul domaine peut être utilisé pour résoudre les problèmes de planification dans tous ces domaines. D’autre part, un planificateur d’itinéraire est typique d’un planificateur spécifique à un domaine.

Planification des langues de modélisation de domaine
Les langages les plus couramment utilisés pour représenter les domaines de planification et des problèmes de planification spécifiques, tels que STRIPS et PDDL pour la planification classique, sont basés sur des variables d’état. Chaque état possible du monde est une affectation de valeurs aux variables d’état, et les actions déterminent la manière dont les valeurs des variables d’état changent lorsque cette action est entreprise. Dans la mesure où un ensemble de variables d’état induit un espace d’état de taille exponentielle, la planification, à l’instar de nombreux autres problèmes de calcul, souffre de la malédiction de la dimensionnalité et de l’explosion combinatoire.

Un autre langage permettant de décrire les problèmes de planification est celui des réseaux de tâches hiérarchiques, dans lesquels un ensemble de tâches est donné. Chaque tâche peut être réalisée par une action primitive ou décomposée en un ensemble d’autres tâches. Cela n’implique pas nécessairement des variables d’état, bien que dans des applications plus réalistes, les variables d’état simplifient la description des réseaux de tâches.

Algorithmes de planification
Planification classique
Recherche d’espace d’état d’enchaînement, éventuellement améliorée avec des méthodes heuristiques
recherche de chaînage arrière, éventuellement renforcée par l’utilisation de contraintes d’état (voir STRIPS, graphplan)
planification partielle

Planification classique
La planification traditionnelle repose sur deux hypothèses:

le déterminisme des actions. Par exemple, l’action « placer un cube sur la table » est déterministe. En l’exécutant, nous passons d’un état à un autre. Au contraire, « lancer un dé » n’est pas déterministe car il y a des valeurs possibles. L’action « lancer un dé » n’entre pas dans le champ de la planification traditionnelle.
l’observation parfaite. L’agent (le robot, le programme, etc.) connaît parfaitement l’état du monde.

Dans la planification classique, il s’agit de rechercher une séquence d’actions (par exemple, « prendre une casserole », « mettre de l’eau », « mettre des pâtes », « allumer un feu », « atteindre », « pour éteindre le Feu »). L’algorithme A * est un exemple typique d’un algorithme de planification classique, souvent utilisé dans les cours d’introduction pour sa simplicité. Voici quelques techniques algorithmiques utilisées dans les planificateurs classiques:

la recherche en avant dans un espace d’états: algorithme de planification de recherche heuristique (HSP), algorithme d’avance rapide (FF),
la recherche arrière dans un espace d’état,
la recherche avant dans un espace de plans, graphplan
assouplissement d’un problème de planification: calcul d’un problème détendu pour lequel il est plus facile de savoir s’il existe un plan qui aide à résoudre le problème initial
la transformation en problème de satisfiabilité d’une formule de logique propositionnelle.

Bylander a démontré en 1994 que la planification conventionnelle est complète par PSPACE.

Réduction à d’autres problèmes
réduction au problème de satisfiabilité propositionnelle (satplan).
réduction à la vérification de modèle – les deux sont essentiellement des problèmes de traversée d’espaces d’états, et le problème de planification classique correspond à une sous-classe de problèmes de vérification de modèle.

Planification temporelle
La planification temporelle peut être résolue avec des méthodes similaires à la planification classique. La principale différence réside dans le fait que la définition d’un état doit inclure des informations sur le temps absolu actuel et sur l’état d’avancement de l’exécution de chaque action active en raison de la possibilité de plusieurs actions se chevauchant dans le temps avec une durée simultanée. En outre, dans la planification en temps réel ou rationnel, l’espace d’états peut être infini, contrairement à la planification classique ou à la planification en temps entier. La planification temporelle est étroitement liée aux problèmes de planification. La planification temporelle peut également être comprise en termes d’automates temporisés.

Planification probabiliste
La planification probabiliste peut être résolue avec des méthodes itératives telles que l’itération de valeur et l’itération de stratégie, lorsque l’espace d’état est suffisamment petit. Avec une observabilité partielle, la planification probabiliste est également résolue avec des méthodes itératives, mais en utilisant une représentation des fonctions de valeur définies pour l’espace des croyances au lieu des états.

Planification basée sur les préférences
Dans la planification basée sur les préférences, l’objectif est non seulement de produire un plan, mais également de satisfaire les préférences spécifiées par l’utilisateur. Une différence par rapport à la planification basée sur les récompenses plus courante, correspondant par exemple aux PDM, les préférences n’ont pas nécessairement une valeur numérique précise.

Planification conditionnelle
La planification déterministe a été introduite avec le système de planification STRIPS, qui est un planificateur hiérarchique. Les noms d’action sont ordonnés dans une séquence et il s’agit d’un plan pour le robot. La planification hiérarchique peut être comparée à un arbre de comportement généré automatiquement. L’inconvénient est qu’un arbre de comportement normal n’est pas aussi expressif qu’un programme informatique. Cela signifie que la notation d’un graphe de comportement contient des commandes d’action, mais pas de boucles ni d’instructions if-then. La planification conditionnelle surmonte le goulot d’étranglement et introduit une notation élaborée similaire à un flux de contrôle, connu dans d’autres langages de programmation tels que Pascal. Cela ressemble beaucoup à la synthèse de programme, ce qui signifie qu’un planificateur génère un code source pouvant être exécuté par un interprète.

Un des premiers exemples de planificateur conditionnel est «Warplan-C», qui a été introduit au milieu des années 1970. Jusqu’à présent, il n’était pas répondu à la question de savoir quelle était la différence entre une séquence normale et un plan complexe, qui contient des déclarations if-then. Cela concerne l’incertitude liée à l’exécution d’un plan. L’idée est qu’un plan peut réagir à des signaux de capteur inconnus du planificateur. Le planificateur génère deux choix à l’avance. Par exemple, si un objet a été détecté, l’action A est exécutée; si un objet est manquant, l’action B est exécutée. Un des principaux avantages de la planification conditionnelle est la capacité de gérer des plans partiels. Un agent n’est pas obligé de tout planifier du début à la fin, mais peut diviser le problème en morceaux. Cela permet de réduire l’espace d’états et de résoudre des problèmes beaucoup plus complexes.

Déploiement de systèmes de planification
Le télescope spatial Hubble utilise un système à court terme appelé SPSS et un système de planification à long terme appelé Spike.

Autres types de planification
En pratique, il ne vérifie que rarement les hypothèses de la planification classique. C’est pourquoi de nombreuses extensions ont vu le jour.

Planification conforme
Nous parlons de planification conforme (calendrier conforme) lorsque le système est dans un état incertain, mais aucune observation n’est possible. L’agent a alors des croyances sur le monde réel. Ces problèmes sont résolus par des techniques similaires à celles de la planification traditionnelle, mais dans lesquelles l’espace des états est exponentiel par rapport à la taille du problème, en raison de l’incertitude quant à l’état actuel. Une solution à un problème de planification conforme est une séquence d’actions.

La planification d’urgence
Planification d’urgence (planification de contingence) dans laquelle l’environnement est observable au moyen de capteurs, ce qui peut être défectueux. 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 que par un seul état parfaitement observable, comme dans le cas d’une planification classique.

Rintanen a démontré en 2004 que si l’on ajoutait une branche (planification conditionnelle), le problème de planification devenait EXPTIME – complet. Un cas particulier de planification contiguë est représenté par les problèmes FOND – pour « entièrement observables et non déterministes ». Si l’objectif est spécifié dans LTLf (logique temporelle linéaire sur trace finie), le problème est toujours EXPTIME-complete 16 et 2EXPTIME-complete pour une spécification spécifique dans LDLf.

Si, en outre, on ajoute une incertitude à la planification traditionnelle (c.-à-d. Une planification conforme), elle devient EXPSPACE-complète. Si nous ajoutons à la fois une branche et une incertitude (planification conforme et contingente), elle devient 2EXPTIME-complete.

Planification probabiliste
Kushmerick et al. introduit la planification probabiliste. Dans leur travail, l’effet des actions est décrit avec les 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, le robot tient le bloc avec une probabilité de 0,95; si la pince est humide, le robot tient le bloc avec une probabilité de 0,5.

Cela pose le problème de la génération de politique (ou stratégie) pour un processus de décision de Markov (MDP) ou (dans le cas général) un processus de décision de Markov partiellement observable (POMDP).

Planification non linéaire
La planification classique résout les sous-objectifs dans un ordre donné. Le problème est que cela conduit 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’une personne aux pieds nus soit dans le même état que lorsqu’il porte sa chaussure droite, sa chaussure gauche, sa chaussette droite et sa chaussette gauche. S’il cherche à atteindre les objectifs 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 cela est nécessaire (engagement au plus tard ou planification d’engagement moindre).

Dans l’exemple précédent, mettre la chaussure gauche doit être fait après avoir mis la chaussette à gauche. Pareil pour la droite. Par contre, l’exécution du plan pour la gauche est indépendante de l’exécution pour la droite. Le plan global est donc partiellement commandé.

Les planificateurs capables de traiter cette catégorie de problèmes sont dits être des ordres partiels (POP, NOAH, etc.).

Planification hiérarchique
Généralement, lors de la planification, on peut avoir une information hiérarchique sur les actions, c’est-à-dire une description de la décomposition des actions complexes. Par exemple, une action complexe comme « servir un café » peut être décomposée en une séquence de deux actions complexes « préparer un café » puis « apporter du 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 à un niveau élevé puis entrer dans les détails si nécessaire (comme le fait ABSTRIPS par exemple). L’objectif est ensuite décrit à l’aide d’un réseau de tâches hiérarchique (HTN).

Planification temporelle
La planification du temps vous permet d’exprimer les temps d’action, les conditions au début, à la fin et pendant l’action, ainsi que les effets au début et à la fin des actions. PDDL 2.1 inclut la planification du temps. La méthode TLP-GP 1 construit un graphe puis résout les contraintes temporelles à l’aide d’un solveur SMT. Un retour en arrière en cas d’incohérence. Rintanen a démontré que la planification temporelle simultanée (plusieurs instances de la même action parallèle est possible) est EXPSPACE-complete. D’autre part, si nous assouplissons ces conditions, nous pouvons nous ramener à la planification conventionnelle et, par conséquent, la planification temporelle avec ces restrictions devient PSPACE-complete.

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

Planification multi-agents
La planification multi-agents étudie l’achèvement d’une tâche par plusieurs agents, par exemple plusieurs robots. La génération du plan et son exécution sont alors souvent distribuées / décentralisées. La coopération entre les agents est un aspect important des plans. Il existe également un algorithme de planification centralisé, qui repose sur une généralisation de STRIPS au cadre multi-agents, appelé MA-STRIPS. L’algorithme a ensuite été rendu rendu, en utilisant un solveur CSP distribué pour gérer la coordination entre agents. Les auteurs, Nissim, Brafman et Domshlak, ont vérifié de manière expérimentale que leur algorithme était meilleur que la planification centralisée lorsque les agents interagissaient peu.

Une des difficultés majeures de la planification multi-agents est l’explosion combinatoire de toutes les actions, qui est exponentielle en nombre d’agents. En 2011, Jonsson et Rovatsos proposent une solution pour contrer ce problème qui se réduit au planning classique des agents uniques. Il existe également une nouvelle utilisation des techniques de parallélisation pour la planification d’algorithmes à l’échelle.

Planification épistémique
Le problème de planification épistémique est de prendre en compte la connaissance des agents dans la description des états et des actions. En règle générale, l’objectif est une formule de la logique modale épistémique, telle que « l’agent 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. Le problème de planification est indécidable dans toute sa généralité.

Objectif :

Au-dessus (A, B) Λ Au-dessus (B, C)
Etat initial :

[Au-dessus (A, Tableau) Λ Au-dessus (B, Tableau) Au-dessus (C, A) Λ Verrou (A) Λ Verrou (B) Verrou (C) Déclaration (B) Déclaration (C)]
Actions disponibles:

Déplacer (b, x, y)
CONDITIONS PRÉALABLES: ci-dessus (b, x) Λ découvert (b) découvert (y) Λ bloc (b) bloc (y) (b ≠ x) (b ≠ y) (x ≠ y)
ADDITIONAL: ci-dessus (b, y) Λ découvert (x)
ANNULATIONS: ci-dessus (b, x) Λ découvert (y)
Move_tool (b, x)
PRECONDITIONS: ci-dessus (b, x) Λ découvert (b) découvert (y) Λ bloc (b) Λ (b ≠ x)
ADDITIONAL: ci-dessus (b, tableau) Λ découvert (x)
ANNULATIONS: ci-dessus (b, x)

Exemple

Exemple informel de planification.

Cible
avoir des fruits et des légumes dans le réfrigérateur

Etat initial
[réfrigérateur vide, à la maison, en pantoufles]

Actions disponibles (liste non ordonnée)
sortir à la maison,
porter des chaussures,
prendre les clefs de voiture,
atteindre le magasin en voiture,
atteindre le magasin à pied,
Rentrer à la maison,
placez vos achats dans le réfrigérateur,
entrez dans le magasin,
prendre des fruits,
prendre des légumes,
payer.

Solution possible (liste ordonnée)
[1- portez des chaussures, 2- prenez les clés de la voiture, 3- sortez de la maison, 4- allez au magasin en voiture, 5- entrez dans le magasin, 6- prenez des fruits, 7- prenez des légumes, 8- payez, 9- rentrer à la maison, 10 achats au réfrigérateur]

Une autre solution possible (liste ordonnée):
[1- portez des chaussures, 2- sortez, 3- allez au magasin à pied, 4- allez au magasin, 5- prenez des légumes, 6- prenez des fruits, 7- payez, 8- allez à la maison, achats de 9 places dans le réfrigérateur]

Conclusions
À partir de l’exemple, nous pouvons voir comment:

les solutions peuvent être multiples,
peuvent être des actions présentes qui doivent être effectuées, inévitablement, après d’autres (je ne peux pas me rendre au magasin en voiture si je n’ai pas pris les clés auparavant),
il peut exister des actions réversibles (prendre des fruits et des légumes),
il n’est pas nécessaire que le plan final contienne toutes les actions en cas d’actions multiples ou de séquences d’actions interchangeables (atteindre le magasin à pied ou en voiture).