hierarchical task network
In plain wordsA planning method that breaks a big task, such as 'travel to Paris', into smaller tasks, such as 'book a flight' and 'pack', using stored recipes, until only simple actions remain.
A planning formalism in which the objective is a network of tasks to perform rather than a goal state to reach. The planner refines the network by repeatedly replacing compound tasks with subtask networks according to methods — domain-specific recipes stating how a task can be accomplished and under what conditions — until only primitive actions, with STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.-style preconditions and effects, remain in a consistent order. Methods encode expert knowledge of how things are normally done, which prunes the search drastically and makes HTN planners fast and predictable on large practical problems, at the price of supplying that knowledge in advance. Planners such as SHOP and SHOP2 generate actions in the order they will be executed, so the current state is always known during planning. HTN planning is used in logistics, military operations, manufacturing, robotics and the control of non-player characters in video games; without restrictions it is more expressive than classical planning and undecidable.
Origin
Earl Sacerdoti's NOAH (1975) and Austin Tate's Nonlin (1977) introduced hierarchical task decomposition. Kutluhan Erol, James Hendler and Dana Nau gave HTN planning formal semantics and complexity results in 1994, and Nau's group released the SHOP (1999) and SHOP2 (2003) planners.
Usage note
Breaking goals into subtasks reappears in language-modellarge language model, n.: A computer program trained on enormous amounts of text to predict the words that come next. At vast scale, that simple skill lets it chat, answer questions, translate, summarize and write code. agents, but HTN methods are written in advance and their decompositions checked formally, whereas an LLM's decomposition is generated on the fly.
Related
- automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
- STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.
- Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them.
- plan-and-executeplan-and-execute, n.: An agent design that first writes out a complete step-by-step plan for a task, then carries out the steps one by one, revising the plan only when something goes wrong.
- means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken.
Sources
- Erol, K., Hendler, J. & Nau, D. S. (1994). HTN Planning: Complexity and Expressivity. Proceedings of AAAI-94.
- Nau, D. et al. (2003). SHOP2: An HTN Planning System. Journal of Artificial Intelligence Research 20, 379–404.
Mentioned in
automated planningautomated planning, n.: The branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes., task decompositiontask decomposition, n.: Breaking a big, vague job into smaller, concrete steps that can each be done and checked — the way a recipe splits a meal into stages., belief–desire–intention modelbelief–desire–intention model, n.: A way of designing software agents around three human-like ideas: what the agent believes about the world, what it wants, and which plans it has committed to carrying out., Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them.