Red de tareas jerárquica

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 de tareas jerárquicas proporcionando un conjunto de tareas, que pueden ser:

1. tareas primitivas (estado inicial), que corresponden aproximadamente a las acciones de STRIPS ;
2. tareas compuestas (estado intermedio), que pueden considerarse como compuestas de un conjunto de tareas más simples;
3. tareas objetivo (estado objetivo), que corresponden aproximadamente a los objetivos de STRIPS , pero son más generales.

Una solución a un problema HTN es entonces una secuencia ejecutable de tareas primitivas que pueden obtenerse de la red de tareas inicial descomponiendo las tareas compuestas en su conjunto de tareas más simples e insertando restricciones de ordenamiento.

Una tarea primitiva es una acción que se puede ejecutar directamente si el estado en el que se ejecuta admite su condición previa. Una tarea compuesta es una tarea compleja formada por un conjunto parcialmente ordenado de tareas adicionales, que pueden ser primitivas o abstractas. Una tarea de objetivo es una tarea que consiste en satisfacer una condición. La diferencia entre las tareas primitivas y otras tareas es que las acciones primitivas se pueden ejecutar directamente. Tanto las tareas compuestas como las de objetivo requieren que se realice una secuencia de acciones primitivas; sin embargo, las tareas de objetivo se especifican en términos de condiciones que deben cumplirse, mientras que las tareas compuestas solo 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. Dicha red se puede utilizar como condición previa para que otra tarea compuesta o de objetivo sea factible. De esta manera, se puede expresar que una tarea dada es factible solo si se realiza un conjunto de otras acciones (las mencionadas en la red), y se realizan 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:

• NOAH, Redes de Jerarquías de Acción. ^[1]
• Nonlin, uno de los primeros sistemas de planificación de la hipertensión. ^[2]
• SIPE-2 ^[3]
• O-Plan, arquitectura de planificación abierta ^[4]
• UMCP, el primer sistema de planificación de HTA probablemente sólido y completo. ^[5]
• Plan IX/I ^[6]
• SHOP2, un planificador de HTN desarrollado en la Universidad de Maryland, College Park . ^[7]
• PANDA, un sistema diseñado para la planificación híbrida, una extensión de la planificación HTN desarrollada en la Universidad de Ulm, Alemania. ^[8]
• HTNPlan-P, planificación de la hipertensión basada en preferencias . ^[9]

La planificación HTN es estrictamente más expresiva que STRIPS , hasta el punto de ser indecidible en el caso general. ^[10] Sin embargo, muchas restricciones sintácticas de la planificación HTN son decidibles, con complejidades conocidas que van desde NP-completo a 2-EXPSPACE-completo, ^[11] y algunos problemas HTN se pueden compilar eficientemente en PDDL , un lenguaje similar a STRIPS. ^[12]

• TIRAS
• Sistema de control jerárquico : un sistema de control de retroalimentación muy adecuado para la planificación de HTN