En inteligencia artificial , la planificación de redes de tareas jerárquicas (HTN) es un enfoque de planificación automatizada en el que la dependencia entre acciones se puede dar en forma de redes estructuradas jerárquicamente.
Los problemas de planificación se especifican en el enfoque de red jerárquica de tareas proporcionando un conjunto de tareas, que pueden ser:
Una solución a un problema HTN es entonces una secuencia ejecutable de tareas primitivas que se pueden obtener de la red de tareas inicial descomponiendo tareas compuestas en su conjunto de tareas más simples e insertando restricciones de orden.
Una tarea primitiva es una acción que se puede ejecutar directamente dado que el estado en el que se ejecuta respalda su condición previa. Una tarea compuesta es una tarea compleja compuesta por un conjunto parcialmente ordenado de tareas adicionales, que pueden ser primitivas o abstractas. Una tarea objetivo es una tarea de satisfacer una condición. La diferencia entre tareas primitivas y otras tareas es que las acciones primitivas se pueden ejecutar directamente. Tanto las tareas compuestas como las de objetivo requieren la realización de una secuencia de acciones primitivas; sin embargo, las tareas objetivo se especifican en términos de condiciones que deben cumplirse, mientras que las tareas compuestas sólo se pueden especificar en términos de otras tareas a través de la red de tareas que se describe a continuación.
Las restricciones entre tareas se expresan en forma de redes, llamadas redes de tareas (jerárquicas). Una red de tareas es un conjunto de tareas y restricciones entre ellas. Una red de este tipo se puede utilizar como condición previa para que otra tarea compuesta o objetivo sea factible. De esta manera, se puede expresar que una tarea determinada es factible sólo si se realizan un conjunto de otras acciones (las mencionadas en la red), y se hacen de tal manera que se satisfagan las restricciones entre ellas (especificadas por la red). . Un formalismo particular para representar redes de tareas jerárquicas que se ha utilizado bastante ampliamente es TAEMS .
Algunos de los sistemas de planificación HTN independientes del dominio más conocidos son:
La planificación de la HTA es estrictamente más expresiva que la STRIPS , hasta el punto de resultar indecidible en el caso general. [10] Sin embargo, muchas restricciones sintácticas de la planificación de HTN son decidibles, con complejidades conocidas que van desde NP-completo hasta 2-EXPSPACE-completo, [11] y algunos problemas de HTN se pueden compilar eficientemente en PDDL , un lenguaje similar a STRIPS. [12]