Planification Automatisée
La planification automatisée est la branche de l'intelligence artificielle qui s'intéresse au calcul de séquences d'actions transformant un état initial du monde en un état objectif désiré, étant donné une description formelle des actions disponibles.
Definition
La planification automatisée est le calcul d'un plan — un ensemble d'actions ordonné (ou partiellement ordonné) — qui permet d'atteindre de manière démontrable un objectif à partir d'un état initial, étant donné un modèle décrivant comment chaque action modifie l'état du monde.
Scope
Ce domaine couvre la représentation des problèmes de planification (états, actions avec préconditions et effets, objectifs) et les algorithmes qui les résolvent : la planification classique dans des domaines déterministes et entièrement observables, les méthodes de graphes de planification et de recherche heuristique, la planification par réseaux de tâches hiérarchiques, et l'extension au temps, aux ressources et à l'ordonnancement. Il traite des formalismes standards tels que STRIPS et PDDL et de la complexité de la planification. La planification en situation d'incertitude probabiliste est liée au raisonnement sous incertitude, et l'apprentissage de modèles d'action ou de politiques à partir de données relève du sous-domaine de l'apprentissage automatique.
Sub-topics
Core questions
- Comment les actions, les états et les objectifs sont-ils représentés de manière suffisamment compacte pour décrire de vastes domaines ?
- Comment le problème de planification est-il exploré efficacement malgré un espace d'états exponentiellement grand ?
- Comment des heuristiques admissibles et informatives sont-elles dérivées automatiquement d'une description de domaine ?
- Comment les plans peuvent-ils être structurés hiérarchiquement, et comment les contraintes de temps et de ressources sont-elles incorporées ?
Key concepts
- états, actions, objectifs
- préconditions et effets
- STRIPS et PDDL
- recherche dans l'espace d'états avant et arrière
- graphes de planification
- heuristiques indépendantes du domaine
- réseaux de tâches hiérarchiques
- planification temporelle et ordonnancement
Key theories
- Représentation d'actions STRIPS
- Le formalisme STRIPS décrit les actions par des préconditions et des effets d'ajout/suppression sur un ensemble de propositions, offrant une représentation compacte et factorisée qui fait de la planification une recherche à travers des états symboliques plutôt qu'une énumération d'états du monde explicites.
- Recherche heuristique indépendante du domaine pour la planification
- Les planificateurs modernes conçoivent la planification comme une recherche heuristique et dérivent automatiquement des heuristiques à partir de la description du problème, par exemple en ignorant les effets de suppression ou en exploitant la structure causale, ce qui permet une performance générale robuste.
- La planification comme hiérarchie de classes de problèmes
- La planification couvre un spectre allant de la planification déterministe classique aux variantes hiérarchiques, temporelles et soumises à des contraintes de ressources, chacune avec des représentations et une complexité caractéristiques, organisées dans la théorie standard de la planification automatisée.
Clinical relevance
La planification automatisée est appliquée en robotique et dans les systèmes autonomes, les opérations spatiales et de mission, la logistique et les chaînes d'approvisionnement, la fabrication, ainsi que la génération de jeux et de récits ; les planificateurs dérivés de ces techniques ont contrôlé de véritables engins spatiaux autonomes et coordonnent des flux de travail complexes.
History
La planification automatisée a débuté avec STRIPS pour le robot Shakey au SRI vers 1971, en formulant la planification comme une démonstration de théorèmes sur des descriptions d'actions. Le domaine a progressé grâce à la planification à ordre partiel, la percée de Graphplan (1995), et l'émergence de planificateurs rapides de recherche heuristique indépendants du domaine et du standard PDDL à partir de la fin des années 1990, suivis à travers les Compétitions Internationales de Planification.
Key figures
- Richard E. Fikes
- Nils J. Nilsson
- Malik Ghallab
- Dana Nau
- Paolo Traverso
- Malte Helmert
Related topics
Seminal works
- fikes1971
- ghallab2004
- helmert2006
Frequently asked questions
- En quoi la planification automatisée diffère-t-elle de la recherche générale ?
- La planification automatisée est une forme de recherche, mais elle opère à partir d'une description déclarative et factorisée des actions (préconditions et effets) plutôt que d'une fonction de successeur opaque. Cette structure permet aux planificateurs de dériver automatiquement des heuristiques et de raisonner sur la pertinence des actions, ce qu'une recherche générique ne peut pas faire.
- Qu'est-ce que PDDL ?
- PDDL, le Planning Domain Definition Language, est un langage standard pour décrire les domaines et les problèmes de planification — objets, prédicats, actions, l'état initial et l'objectif. Il permet de comparer des planificateurs indépendants du domaine sur un banc d'essai commun, comme lors des Compétitions Internationales de Planification.