Red jerárquica de tareas

La red jerárquica de tareas (denominada también del inglés como: Hierarchical task network o abreviadamente HTN) es un algoritmo de planificación automática que crea un plan por descomposición de tareas en subtareas hasta lograr primitivas que pueden ser ejecutadas directamente. La dependencia entre las acciones se proporciona en forma de red (Network). La descomposición se aplica en cumplimiento de unas precondiciones según una jerarquía.

Concepto

Las restricciones entre las tareas se expresan mediante redes, a las que se denomina red de tareas. Una red de tareas es un conjunto de tareas ligadas con ciertas restricciones entre ellas. De esta forma se puede decir que una tarea dada es viable sólo si un conjunto de acciones (incluidas en la red) se han realizado cumpliendo con las restricciones existentes entre ellas (especificadas en la red). Una forma particular de representar una red jerárquica de tareas en un formalismo particular es mediante el uso de TÆMS.^[1]^[2]

Usos

Los algoritmos HTN proporcionan una forma adecuada de planificar recursos cuando existe de antemano una información jerárquica de la estructura del dominio. Los planificadores similares a HTN (que son los que se emplean en la práctica) poseen las mismas capacidades (son aplicables en los mismos dominios) que STRIPS.^[3] Los modelos teóricos sobre los que se fundamenta HTN les hacen más expresivos que STRIPS,^[4] pero no puede ser directamente empleado debido a su indecidibilidad.

Planificadores HTN

Los planificadores HTN independientes de dominio más conocidos son:

Nonlin, se trata de uno de los primeros sistemas de planificación HTN.
SIPE-2
O-Plan
UMCP, es probablemente el primero más completo HTN de los planificadores.
SHOP2, un planificador HTN desarrollado en la University of Maryland, College Park.

Referencias

↑ K. Decker (1995). [1]. Environment Centered Analysis and Design of Coordination Mechanisms. Ph.D. Thesis at University of Massachusetts, Department of Computer Science.
↑ Horling, Bryan; Victor Lesser and Regis Vincent and Tom Wagner and Anita Raja and Shelley Zhang and Keith Decker and Alan Garvey (1999). The Taems White Paper (pdf). Consultado el 19 de mayo de 2009. (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).
↑ M. Lekavy and P. Navrat (2007). Expressivity of STRIPS-Like and HTN-Like Planning. Lecture Notes in Artificial Intelligence, Vol. 4496 Agent and multi-agent Systems. Technologies and applications. 1st KES International Symposium, KES-AMSTA 2007, Wroclaw, Poland, May/June 2007. - Germany, Springer-Verlag Berlin Heidelberg, 2007. pp. 121-130
↑ K. Erol, J. Hendler and D. Nau. HTN Planning: Complexity and Expressivity. In Proc. AAAI-94

Véase también

Red simple de tareas - Simple Task Networks (STNs)
STRIPS

Datos: Q5753136

[1] K. Decker (1995). [1]. Environment Centered Analysis and Design of Coordination Mechanisms. Ph.D. Thesis at University of Massachusetts, Department of Computer Science.

[2] Horling, Bryan; Victor Lesser and Regis Vincent and Tom Wagner and Anita Raja and Shelley Zhang and Keith Decker and Alan Garvey (1999). The Taems White Paper (pdf). Consultado el 19 de mayo de 2009. (enlace roto disponible en Internet Archive; véase el historial, la primera versión y la última).

[3] M. Lekavy and P. Navrat (2007). Expressivity of STRIPS-Like and HTN-Like Planning. Lecture Notes in Artificial Intelligence, Vol. 4496 Agent and multi-agent Systems. Technologies and applications. 1st KES International Symposium, KES-AMSTA 2007, Wroclaw, Poland, May/June 2007. - Germany, Springer-Verlag Berlin Heidelberg, 2007. pp. 121-130

[4] K. Erol, J. Hendler and D. Nau. HTN Planning: Complexity and Expressivity. In Proc. AAAI-94

[1]

[2]

[3]

[4]