Réseau hiérarchisé de tâches

En intelligence artificielle, la planification avec réseaux hiérarchisés de tâches (abrégé en planification HTN pour hierarchical task network) est une approche à la planification automatique où les actions sont structurées. Différemment par rapport à la planification classique, en planification HTN sont introduites des tâches complexes (dites même "hiérarchiques") qui peuvent être découpées en sous-tâches. Cette hiérarchie de tâches permet de décrire le problème de planification à plusieurs niveaux, en partant de tâches plus abstraites pour terminer en des tâches élémentaires directement applicables.

Définition formelle

Un problème de planification HTN est défini par une tuple >$\left\langle S,A,T,s_{0},G\right\rangle$ où

• $S$ est un ensemble d'états,
• $A$ est un ensemble d'actions,
• $T$ est une fonction de transition qui à un état et une action associe un état t.q. $T:S\times A\rightarrow S$,
• $s_{0}\in S$ est l'état initial,
• $G\subseteq S$ est l'ensemble d'états but.

L'ensemble d'actions $A$ est découpé en

• actions primitives (ou élémentaires) qui correspondent en tout et pour tout à des actions STRIPS ;
• actions complexes (ou hiérarchiques ou abstraites) sont définies par un "nom" identificatoire de chaque action, un ensemble de préconditions, un ensemble de méthodes qui correspondent à des actions soit élémentaires qu'abstraites définissant les sous-tâches et des contraintes temporelles les ordonnant.

Planificateurs HTN

Voici une liste de planificateurs HTN :

• Nonlin, un des premiers planificateurs HTN
• SIPE-2
• O-Plan
• UMCP, le premier planificateur HTN prouvé
• SHOP2, a un planificateur HTN développé à l'University of Maryland, College Park
• PANDA, un système pour la planification hybride, qui étend la planification HTN développé à l'université d'Ulm, en Allemagne
• HTNPlan-P, un planificateur HTN basé sur les préférences

Complexité

La planification HTN est indécidable en général, c'est-à-dire qu'il n'existe pas d'algorithme pour planifier un problème HTN dans le cas général. La démonstration d'indécidabilité mentionnée par Erol et al. s'effectue par réduction depuis le problème de savoir si l'intersection de deux langages algébriques est non vide, qui est indécidable.

Des restrictions syntaxiques décidables ont été identifiées. Certaines problèmes HTN peuvent être résolus en les traduisant efficacement en planification classique (en PDDL par exemple).