Plan Refinement

Plan refinement is fundamentally iterative. It begins with a skeletal plan containing one or more high-level goal tasks. The planner selects a non-primitive (compound) task, finds an applicable decomposition method, and replaces that task with the method's specified network of subtasks. This process repeats recursively on the new subtasks until the entire plan consists solely of primitive tasks (executable operators). This stepwise approach allows for backtracking if a decomposition path leads to a dead end.

Refinement is state-dependent. A method is only applicable if its preconditions are satisfied by the current world state at the point where its parent task is to be executed. This means the planner must simulate or reason about the evolving world state as it refines the plan. For example, a method to 'Navigate to Location X' might have different decompositions (e.g., 'Call Elevator' then 'Ride Elevator' vs. 'Take Stairs') depending on the precondition 'Is elevator operational?' being true or false in the current simulated state.

During refinement, each decomposition method application introduces new constraints into the plan. These are not just actions, but also:

• Ordering Constraints: Specifying that subtask A must precede subtask B.
• Causal Links: Ensuring that a precondition of a later task is established by the effect of an earlier one.
• Variable Bindings: Unifying parameters between tasks (e.g., the 'package' being picked up is the same one later delivered).
• Resource Constraints: Allocating and tracking limited resources. The planner must ensure all constraints are mutually consistent throughout the refinement process.

HTN planners like SHOP (Simple Hierarchical Ordered Planner) perform refinement in a forward-chaining, depth-first manner. They start from the initial state and the initial task network, decomposing tasks in the order they would be executed. This interleaves planning with state progression, allowing the planner to immediately detect if a decomposition makes the world state inconsistent with future task preconditions. This forward search is highly efficient for domains where the order of tasks is largely determined by the methods, making it more goal-directed than blind state-space search.

The output of plan refinement is not just a flat sequence of actions; it is a hierarchical plan or decomposition tree. This structure preserves the 'why' behind each action—showing which high-level goal it serves and which method justified its inclusion. This is critical for:

• Explainability: Debugging why a plan failed.
• Replanning: Efficiently modifying only the branch of the tree affected by a change.
• Execution Monitoring: Understanding the context of a failing low-level action. The hierarchy provides a map from strategic intent to tactical operations.

Plan refinement fundamentally differs from classical state-space planning (like STRIPS). Instead of searching through a space of world states by applying actions, HTN planning searches through a space of partially refined plans by applying decomposition methods. The search is guided by the task hierarchy, not just state heuristics. This allows HTN planners to encode complex procedural knowledge (the 'how-to') directly into the domain's methods, often making them more efficient for problems with known hierarchical structure, such as manufacturing processes or military logistics.

A skeletal plan is a partially specified, abstract plan generated early in the HTN planning process. It contains high-level compound tasks that must be refined through task decomposition into primitive, executable actions. This intermediate representation serves as the direct input to the plan refinement process, guiding the search for a concrete solution.

• Acts as a blueprint for refinement.
• Contains ordering constraints between abstract tasks.
• Is progressively made more concrete until fully executable.

Task decomposition is the fundamental algorithmic operation in HTN planning where an abstract, compound task is recursively replaced by a network of subtasks using an applicable method. This process is the engine of plan refinement, transforming goals into actionable steps.

• Driven by decomposition methods stored in a task library.
• Respects preconditions defined for each method.
• Continues recursively until only primitive tasks (operators) remain.

A decomposition tree is a visual or logical tree structure that records the complete hierarchical breakdown of a high-level goal into its constituent actions during HTN planning. It is the explicit trace of the refinement process, showing how each compound task was decomposed.

• Root node is the initial goal task.
• Internal nodes are compound tasks and the methods applied to them.
• Leaf nodes are the final primitive tasks in the solution plan.

A method (or decomposition method) is a schema that defines a possible way to decompose a specific compound task into a network of subtasks, provided its preconditions are satisfied. Methods are the domain knowledge that guides the refinement process.

• Encodes expert knowledge for solving a type of task.
• Specifies subtasks and ordering constraints between them.
• A compound task may have multiple applicable methods, creating choice points for the planner.

A primitive task is a task in an HTN that corresponds directly to an executable operator in the planning domain. It is an atomic action with defined preconditions and effects. The goal of plan refinement is to reduce all tasks to primitive tasks.

• Represented by planning operators.
• Causes state transitions when executed.
• The building blocks of the final solution plan.

A compound task is a high-level, abstract task that cannot be executed directly. It must be decomposed into a network of subtasks (which may be other compound tasks or primitive tasks) using a method. Compound tasks are the subjects of refinement.

• Represents a goal or objective requiring multiple steps.
• Defined in the domain description.
• Forms the initial task network given to the planner.