Skeletal Plan

A skeletal plan is defined by its incompleteness. It contains abstract tasks (compound tasks) that have not yet been decomposed into primitive, executable actions. This distinguishes it from a solution plan, which is fully grounded. The planner's job is to iteratively refine this skeleton through task decomposition until no abstract tasks remain.

The plan explicitly maintains the parent-child relationships from the decomposition process. This is often visualized as a decomposition tree. This structure is crucial for:

• Traceability: Understanding which high-level goal a specific action serves.
• Replanning: If execution fails, the planner can backtrack to a higher-level abstract task and try an alternative method.
• Explanation: Providing a rationale for why certain actions are included.

The skeletal plan is the starting point for plan refinement. The planner selects an abstract task, finds an applicable decomposition method whose preconditions are satisfied, and replaces the abstract task with the method's subtask network. This process repeats in a depth-first (like SHOP) or other search order until the plan is fully primitive.

Beyond tasks, a skeletal plan encodes critical constraints that must be preserved during refinement:

• Ordering Constraints: Temporal relations (e.g., Task A before Task B).
• Causal Links: Protect a condition achieved by one task for use by another.
• Variable Bindings: Parameters of abstract tasks may be partially bound. These constraints guide and prune the search space during subsequent decomposition.

The validity of a skeletal plan is contingent on the current world state. An abstract task may have multiple possible decomposition methods; the choice depends on which method's preconditions hold. A change in the world state can invalidate the chosen decomposition path, necessitating replanning from a point higher in the hierarchy.

Generating a skeletal plan early allows the HTN planner to commit to a high-level strategy before detailing all low-level actions. This hierarchical search is often more efficient than flat state-space planning (like STRIPS) for complex domains, as it uses the domain's task library to prune vast areas of the search space that don't conform to sensible task decomposition.

A planning formalism where the solution is generated by recursively decomposing high-level, abstract tasks into networks of smaller subtasks using decomposition methods. This process continues until only primitive tasks (directly executable actions) remain. HTNs are the overarching architecture within which a skeletal plan is created and refined.

A high-level, abstract task in an HTN that cannot be executed directly. It must be decomposed into a network of subtasks using an applicable method. In a skeletal plan, many nodes are compound tasks awaiting further refinement. Examples include AssembleProduct or DiagnoseSystemFault.

A task that corresponds directly to an executable action or operator in the planning domain. It has defined preconditions and effects. The goal of refining a skeletal plan is to replace all abstract compound tasks with a sequence of primitive tasks. Examples include PickUp(Screwdriver) or SendAPIRequest(/api/validate).

A schema that defines one possible way to decompose a specific compound task into a network of subtasks. A method includes:

• Task Head: The compound task it decomposes.
• Preconditions: Logical conditions required for this decomposition to be valid.
• Subtasks: The network of (compound or primitive) tasks that implement the head. Planners choose among applicable methods to refine a skeletal plan.

The iterative process in HTN planning of replacing abstract tasks in a skeletal plan with more concrete subtasks. This involves:

1. Selecting an abstract (compound) task in the current plan.
2. Choosing an applicable method for that task.
3. Replacing the task with the method's subtask network. This loop repeats until the plan contains only executable primitive actions.

A tree structure that visually represents the complete hierarchical breakdown of a high-level goal task into its constituent primitive actions. It is the fully-expanded record of all plan refinement steps. The root is the initial goal, internal nodes are compound tasks and methods, and leaves are primitive tasks. A skeletal plan corresponds to a partially expanded decomposition tree.