Graphes de planification et heuristiques

Les graphes de planification et les heuristiques indépendantes du domaine sont les techniques qui ont permis d'accélérer la planification classique, en analysant de manière compacte l'atteignabilité et en estimant automatiquement la distance d'un état à l'objectif.

Definition

Un graphe de planification est une structure en couches qui intercale des niveaux de propositions et d'actions avec des contraintes mutex pour approximer l'atteignabilité ; les heuristiques de planification sont des fonctions, souvent calculées à partir de telles structures ou de problèmes relaxés par suppression, qui estiment le coût pour atteindre l'objectif à partir d'un état.

Scope

Ce sujet couvre la structure de données des graphes de planification introduite par Graphplan, incluant les niveaux de propositions et d'actions ainsi que les relations d'exclusion mutuelle (mutex) qui identifient les faits et actions ne pouvant coexister. Il aborde également la famille d'heuristiques indépendantes du domaine dérivées de problèmes relaxés (notamment en ignorant les effets de suppression) qui animent les planificateurs modernes basés sur la recherche heuristique. Il est également traité de la manière dont l'information d'atteignabilité est calculée et utilisée pour guider la recherche. Le modèle de planification classique sous-jacent est abordé dans le sujet connexe.

Core questions

• Comment un graphe de planification représente-t-il les propositions et actions atteignables niveau par niveau ?
• Que sont les relations mutex, et comment capturent-elles l'incompatibilité entre les faits et les actions ?
• Comment la relaxation par suppression est-elle utilisée pour dériver des heuristiques de planification admissibles ou informatives ?
• Comment ces heuristiques transforment-elles la planification en une recherche heuristique efficace ?

Key concepts

• graphe de planification
• niveaux de propositions et d'actions
• exclusion mutuelle (mutex)
• Graphplan
• relaxation par suppression
• heuristiques h-max et h-add
• heuristique FF et plans relaxés
• recherche heuristique en avant

Key theories

Graphe de planification et Graphplan

Graphplan construit un graphe de planification qui encode de manière compacte quelles propositions et actions sont atteignables à chaque niveau et quelles paires sont mutuellement exclusives, puis extrait un plan en effectuant une recherche rétrograde à travers cette structure, accélérant considérablement la planification.

Heuristiques de relaxation par suppression

Ignorer les effets de suppression des actions conduit à un problème de planification relaxé beaucoup plus facile à résoudre ; le coût de résolution de cette relaxation fournit des heuristiques informatives, souvent admissibles (telles que h-max et h-add et l'heuristique FF) qui guident la recherche en avant.

Planification par recherche heuristique

Les planificateurs classiques de pointe combinent des heuristiques dérivées automatiquement avec une recherche en premier le meilleur ou gloutonne et des améliorations telles que les opérateurs préférés, atteignant ainsi de solides performances générales sur des domaines variés.

Clinical relevance

Les graphes de planification et les heuristiques de relaxation par suppression constituent la technologie fondamentale des planificateurs primés lors de compétitions, utilisés en robotique, en logistique et en contrôle autonome. Ils permettent à des planificateurs indépendants du domaine de résoudre rapidement des problèmes de grande envergure sans nécessiter de guidage de recherche manuel.

History

Graphplan de Blum et Furst (1995, version journal 1997) a introduit le graphe de planification et a révolutionné la vitesse de planification. La fin des années 1990 et les années 2000 ont vu l'essor des heuristiques de relaxation par suppression, avec le planificateur FF (Hoffmann et Nebel, 2001) puis Fast Downward (Helmert, 2006) qui ont établi la recherche heuristique en avant comme l'approche dominante.

Key figures

• Avrim L. Blum
• Merrick L. Furst
• Jörg Hoffmann
• Bernhard Nebel
• Malte Helmert

Seminal works

• blum1997
• hoffmann2001

Frequently asked questions

Qu'est-ce qu'un mutex dans un graphe de planification ?

Une relation mutex (exclusion mutuelle) indique deux propositions ou deux actions qui ne peuvent pas être toutes deux valides ou appliquées au même niveau, par exemple parce qu'une action supprime une précondition de l'autre. Les mutex rendent le graphe de planification une approximation plus précise de l'atteignabilité réelle.

Pourquoi ignorer les effets de suppression donne-t-il une heuristique utile ?

Sans effets de suppression, l'atteinte d'un objectif n'annule jamais un autre, de sorte que le problème relaxé est beaucoup plus facile à résoudre et jamais plus difficile que l'original. Le coût du plan relaxé est donc une borne inférieure ou une estimation éclairée du coût réel, ce qui en fait une heuristique efficace pour guider la recherche.