Planification par réseau de tâches hiérarchiques
La planification par réseau de tâches hiérarchiques (HTN) résout les problèmes en décomposant récursivement des tâches de haut niveau en sous-tâches à l'aide d'une bibliothèque de méthodes, plutôt qu'en recherchant directement des actions primitives pour atteindre un état cible.
Definition
La planification HTN représente un problème comme un réseau initial de tâches à exécuter et un ensemble de méthodes pour décomposer les tâches composées en sous-tâches ; une solution est une décomposition en actions primitives et exécutables qui respecte les contraintes des méthodes.
Scope
Ce sujet aborde le paradigme de la planification HTN : les tâches (primitives et composées), les méthodes qui spécifient comment décomposer une tâche composée en sous-tâches, et le processus de planification qui affine un réseau de tâches initial jusqu'à ce qu'il ne reste que des actions primitives exécutables. Il traite de l'expressivité et de la complexité de la planification HTN par rapport à la planification classique et des planificateurs HTN notables. Le modèle de planification classique, basé sur l'état cible, est traité dans les sujets connexes ; la planification HTN, quant à elle, encode des connaissances procédurales du domaine.
Core questions
- Comment les méthodes encodent-elles les connaissances du domaine sur la manière d'accomplir des tâches composées ?
- En quoi la décomposition de tâches diffère-t-elle de la recherche d'un état cible dans la planification classique ?
- Quelle est l'expressivité et la complexité computationnelle de la planification HTN par rapport à la planification classique ?
- Comment les contraintes d'ordonnancement et de précondition entre les sous-tâches sont-elles gérées pendant la décomposition ?
Key concepts
- tâches primitives et composées
- méthodes et décomposition
- réseaux de tâches
- contraintes d'ordonnancement
- connaissances procédurales du domaine
- expressivité HTN
- décomposition de tâches ordonnée
- SHOP2
Key theories
- Décomposition de tâches avec des méthodes
- La planification HTN remplace la recherche dirigée par un objectif par une décomposition récursive : les tâches composées sont étendues en réseaux de sous-tâches via des méthodes jusqu'à ce que toutes les tâches soient primitives, permettant ainsi d'encoder directement l'expertise humaine sur la manière d'exécuter les tâches.
- Expressivité et complexité de la planification HTN
- La planification HTN est strictement plus expressive que la planification STRIPS classique ; sous sa forme générale, l'existence d'un plan peut être indécidable, et les formes restreintes occupent des classes de complexité plus élevées, reflétant la puissance de la décomposition basée sur les méthodes.
- Planificateurs de décomposition de tâches ordonnée
- Les planificateurs HTN pratiques, tels que SHOP2, planifient en décomposant les tâches dans l'ordre où elles seront exécutées, ce qui leur permet d'évaluer les préconditions par rapport à des états entièrement déterminés et d'incorporer efficacement des connaissances riches du domaine.
Clinical relevance
La planification HTN est largement utilisée lorsque des procédures expertes sont connues et doivent être suivies, comme dans la planification des processus de fabrication, les opérations militaires et logistiques, la composition de services web, et la génération de jeux et d'histoires, car les méthodes permettent aux experts du domaine d'encoder des manières standard d'accomplir des tâches.
History
La planification hiérarchique trouve ses origines dans le système NOAH de Sacerdoti et les hiérarchies d'abstraction dans les années 1970. Erol, Hendler et Nau ont formalisé la planification HTN et analysé sa complexité au début des années 1990, et les planificateurs SHOP et SHOP2 (vers 2000-2003) ont fait de la planification HTN ordonnée une technologie pratique et largement utilisée.
Key figures
- Dana Nau
- Kutluhan Erol
- James Hendler
- Earl D. Sacerdoti
- Austin Tate
Related topics
Seminal works
- erol1994
- nau2003
Frequently asked questions
- En quoi la planification HTN diffère-t-elle de la planification classique ?
- La planification classique recherche toute séquence d'actions qui atteint un état cible, en utilisant uniquement les préconditions et les effets des actions. La planification HTN, quant à elle, part des tâches à accomplir et les décompose à l'aide de méthodes qui encodent la manière procédurale dont ces tâches sont normalement effectuées, elle s'appuie donc sur des connaissances du domaine plus riches.
- Pourquoi la planification HTN peut-elle être indécidable ?
- Parce que les méthodes peuvent décomposer une tâche composée en réseaux qui incluent d'autres tâches composées, le processus de décomposition peut récurser sans limite, un peu comme une grammaire générant des dérivations arbitrairement longues. Sous sa forme générale, décider si une décomposition valide existe est donc indécidable.