Planificación de Redes de Tareas Jerárquicas
La planificación de redes de tareas jerárquicas (HTN) resuelve problemas descomponiendo recursivamente tareas de alto nivel en subtareas utilizando una biblioteca de métodos, en lugar de buscar directamente sobre acciones primitivas para alcanzar un estado objetivo.
Definition
La planificación HTN representa un problema como una red inicial de tareas a realizar y un conjunto de métodos para descomponer tareas compuestas en subtareas; una solución es una descomposición en acciones primitivas y ejecutables que respeta las restricciones de los métodos.
Scope
Este tema cubre el paradigma de planificación HTN: tareas (primitivas y compuestas), métodos que especifican cómo descomponer una tarea compuesta en subtareas, y el proceso de planificación que refina una red de tareas inicial hasta que solo quedan acciones primitivas ejecutables. Aborda la expresividad y complejidad de la planificación HTN en relación con la planificación clásica y los planificadores HTN notables. El modelo de planificación clásico, basado en el estado objetivo, se trata en los temas relacionados; la planificación HTN, en cambio, codifica el conocimiento de dominio procedimental.
Core questions
- ¿Cómo codifican los métodos el conocimiento del dominio sobre cómo realizar tareas compuestas?
- ¿En qué se diferencia la descomposición de tareas de la búsqueda de un estado objetivo en la planificación clásica?
- ¿Cuál es la expresividad y la complejidad computacional de la planificación HTN en comparación con la planificación clásica?
- ¿Cómo se manejan las restricciones de orden y precondición entre subtareas durante la descomposición?
Key concepts
- tareas primitivas y compuestas
- métodos y descomposición
- redes de tareas
- restricciones de ordenación
- conocimiento de dominio procedimental
- expresividad HTN
- descomposición de tareas ordenada
- SHOP2
Key theories
- Descomposición de tareas con métodos
- La planificación HTN reemplaza la búsqueda dirigida a objetivos con la descomposición recursiva: las tareas compuestas se expanden en redes de subtareas a través de métodos hasta que todas las tareas son primitivas, lo que permite codificar directamente la experiencia humana sobre cómo realizar las tareas.
- Expresividad y complejidad de la planificación HTN
- La planificación HTN es estrictamente más expresiva que la planificación clásica STRIPS; en su forma general, la existencia del plan puede ser indecidible, y las formas restringidas ocupan clases de complejidad más altas, lo que refleja el poder de la descomposición basada en métodos.
- Planificadores de descomposición de tareas ordenadas
- Los planificadores HTN prácticos como SHOP2 planifican descomponiendo tareas en el orden en que se ejecutarán, lo que les permite evaluar las precondiciones frente a estados completamente determinados e incorporar eficientemente un rico conocimiento del dominio.
Clinical relevance
La planificación HTN se utiliza ampliamente donde se conocen y deben seguirse procedimientos expertos, como la planificación de procesos de fabricación, operaciones militares y logísticas, composición de servicios web, y generación de juegos e historias, porque los métodos permiten a los expertos del dominio codificar formas estándar de realizar tareas.
History
La planificación jerárquica se remonta a NOAH de Sacerdoti y las jerarquías de abstracción en la década de 1970. Erol, Hendler y Nau formalizaron la planificación HTN y analizaron su complejidad a principios de la década de 1990, y los planificadores SHOP y SHOP2 (alrededor de 2000-2003) hicieron de la planificación HTN ordenada una tecnología práctica y ampliamente utilizada.
Key figures
- Dana Nau
- Kutluhan Erol
- James Hendler
- Earl D. Sacerdoti
- Austin Tate
Related topics
Seminal works
- erol1994
- nau2003
Frequently asked questions
- ¿En qué se diferencia la planificación HTN de la planificación clásica?
- La planificación clásica busca cualquier secuencia de acciones que alcance un estado objetivo, utilizando solo las precondiciones y efectos de las acciones. La planificación HTN, en cambio, parte de las tareas a realizar y las descompone utilizando métodos que codifican cómo, procedimentalmente, se realizan normalmente esas tareas, por lo que se basa en un conocimiento de dominio más rico.
- ¿Por qué la planificación HTN puede ser indecidible?
- Debido a que los métodos pueden descomponer una tarea compuesta en redes que incluyen más tareas compuestas, el proceso de descomposición puede recursar sin límite, de manera similar a una gramática que genera derivaciones arbitrariamente largas. En su forma general, decidir si existe una descomposición válida es, por lo tanto, indecidible.