Planification classique et STRIPS

La planification classique aborde le problème de la recherche d'une séquence d'actions pour atteindre un objectif dans un environnement déterministe, entièrement observable et statique, en utilisant la représentation factorisée de type STRIPS des actions par des préconditions et des effets.

Definition

La planification classique recherche une séquence d'actions déterministes qui transforme un état initial entièrement connu en un état satisfaisant l'objectif, où chaque action est décrite par les conditions qui doivent être remplies pour qu'elle s'applique et les changements qu'elle opère.

Scope

Ce sujet couvre le modèle de planification classique et ses hypothèses (actions déterministes, observabilité complète, agent unique, temps atomique), les représentations STRIPS et ADL/PDDL des états et des actions, les méthodes de résolution de base de la recherche dans l'espace d'états par progression (avant) et régression (arrière) et la planification par ordre partiel, ainsi que la complexité computationnelle de la planification propositionnelle. Les heuristiques et les graphes de planification sont traités dans le sujet connexe, et les variantes non déterministes ou probabilistes sont hors de portée.

Core questions

• Quelles hypothèses définissent le modèle de planification classique, et quand sont-elles appropriées ?
• Comment la représentation STRIPS factorise-t-elle un état en propositions et une action en préconditions et effets d'ajout/suppression ?
• En quoi la recherche par progression et par régression diffèrent-elles en tant que stratégies de planification ?
• Quelle est la complexité computationnelle de la planification classique en général ?

Key concepts

• modèle déterministe, entièrement observable
• préconditions et effets STRIPS
• listes d'ajout et de suppression
• PDDL et ADL
• recherche par progression (avant)
• recherche par régression (arrière)
• planification par ordre partiel
• complexité de l'existence d'un plan

Key theories

Représentation STRIPS

STRIPS décrit le monde comme un ensemble de propositions vraies et chaque action par une liste de préconditions ainsi que des listes d'ajout et de suppression ; ainsi, l'application d'une action ajoute et supprime simplement des propositions ; ce modèle factorisé est le fondement de presque tous les planificateurs classiques.

Recherche par progression et régression

Les plans classiques peuvent être trouvés en recherchant vers l'avant à partir de l'état initial en appliquant les actions applicables (progression) ou vers l'arrière à partir de l'objectif en calculant les sous-objectifs régressés (régression), la planification par ordre partiel assouplissant l'engagement envers un ordonnancement total des actions.

Complexité de la planification

Décider si un plan STRIPS propositionnel existe est PSPACE-complet en général, expliquant formellement pourquoi la planification est difficile et motivant les méthodes heuristiques et structurelles pour la rendre pratique.

Clinical relevance

Les représentations de planification classique constituent l'interface courante pour la planification de tâches robotiques, l'assemblage et la logistique automatisés, et toute application où des actions déterministes doivent être séquencées pour atteindre un objectif ; les planificateurs classiques basés sur PDDL sont les piliers du domaine et des Compétitions Internationales de Planification.

History

STRIPS a été développé au SRI vers 1971 pour contrôler le robot Shakey, introduisant le modèle d'action précondition/effet qui définit la planification classique. La planification par ordre partiel a mûri dans les années 1970-80, Bylander a établi la PSPACE-complétude de la planification propositionnelle en 1994, et la norme PDDL a ensuite unifié les références du domaine.

Key figures

• Richard E. Fikes
• Nils J. Nilsson
• Tom Bylander
• Earl D. Sacerdoti

Seminal works

• fikes1971
• bylander1994

Frequently asked questions

Quelles sont les hypothèses de la planification classique ?

La planification classique suppose un agent unique agissant dans un environnement déterministe, entièrement observable et statique, avec des actions prenant une unité de temps et un état initial entièrement connu. Relâcher l'une de ces hypothèses, par exemple en permettant l'incertitude ou la concurrence, conduit à des problèmes de planification plus riches au-delà du modèle classique.

Que signifient les listes d'ajout et de suppression STRIPS ?

Lorsqu'une action STRIPS est appliquée, les propositions de sa liste d'ajout deviennent vraies et celles de sa liste de suppression deviennent fausses ; toutes les autres propositions restent inchangées. Cette règle de mise à jour simple est ce qui fait de STRIPS une représentation compacte et computationnellement pratique de la façon dont les actions modifient le monde.