Réseau hiérarchisé de tâches

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

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

L'ensemble d'actions ${\displaystyle 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.

Voici une liste de planificateurs HTN :

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

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[9]. La démonstration d'indécidabilité mentionnée par Erol et al.[9] 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[10]. Certaines problèmes HTN peuvent être résolus en les traduisant efficacement en planification classique (en PDDL par exemple)[11].