Hierarchical Task Network (HTN) Planning José Luis Ambite* [* Based in part on presentations by Dana Nau and Rao Kambhampati] 1 Hierarchical Decomposition 2 Task Reduction 3 Hierarchical Planning Brief History (cid:131) Originally developed about 25 years ago (cid:131) NOAH [Sacerdoti, IJCAI 1977] (cid:131) NONLIN [Tate, IJCAI 1977] (cid:131) Knowledge-based (cid:198) Scalable (cid:131) Task Hierarchy is a form of domain-specific knowledge (cid:131) Practical, applied to real world problems (cid:131) Lack of theoretical understanding until early 1990’s [Erol et al, 1994] [Yang 1990] [Kambhampati 1992] (cid:131) Formal semantics, sound/complete algorithm, complexity analysis [Erol et al, 1994] 4 Deployed, Practical Planners (cid:131) SIPE, SIPE-2 [Wilkins, 85-] (cid:131) http://www.ai.sri.com/~sipe/ (cid:131) NONLIN/O-Plan/I-X [Tate et. al., 77-] (cid:131) http://www.aiai.ed.ac.uk/~oplan/ (cid:131) http://www.aiai.ed.ac.uk/project/ix/ (cid:131) Applications: (cid:131) Logistics (cid:131) Military operations planning: Air campaign planning, Non- Combatant Evacuation Operations (cid:131) Crisis Response: Oil Spill Response (cid:131) Production line scheduling (cid:131) Construction planning: Space platform building, house construction (cid:131) Space applications: mission sequencing, satellite control (cid:131) Software Development: Unix administrator's script writing 5 Deployed, Practical Planners Many features: (cid:131) Hierarchical decomposition (cid:131) Resources (cid:131) Time (cid:131) Complex conditions (cid:131) Axioms (cid:131) Procedural attachments (cid:131) Scheduling (cid:131) Planning and Execution (cid:131) Knowledge acquisition tools (cid:131) Mixed-initiative 6 7 O-Plan 8 HTN Planning (cid:131) Capture hierarchical structure of the planning domain (cid:131) Planning domain contains non-primitive actions and schemas for reducing them (cid:131) Reduction schemas: (cid:131) given by the designer (cid:131) express preferred ways to accomplish a task 9 HTN Formalization (1) (cid:131) State: list of ground atoms (cid:131) Tasks: (cid:131) Primitive tasks: do[f(x , …, x )] 1 n (cid:131) Non-primitive tasks: (cid:131) Goal task: achieve(l) (l is a literal) (cid:131) Compound task: perform[t(x , …, x )] 1 n (cid:131) Operator: (cid:131) [operator f(x , …, x ) (pre: l , …, l ) (post: l’ , …, l’ )] 1 n 1 n 1 n (cid:131) Method: (α, d) (cid:131) α is a non-primitive task and d is a task network (cid:131) Plan: sequence of ground primitive tasks (operators) 10