Solution Plan: Definition & Role in AI Planning

HIERARCHICAL TASK NETWORKS

What is a Solution Plan?

In the context of Hierarchical Task Network (HTN) planning, a solution plan is the final, executable output of the decomposition process.

A solution plan is a fully decomposed, ordered sequence of primitive actions that, when executed from a known initial state, is guaranteed to achieve the planner's specified high-level goals. It represents the complete resolution of all abstract, compound tasks in the initial task network into directly executable steps, with all preconditions satisfied and ordering constraints logically enforced. This validated sequence is the concrete output of the HTN planning algorithm, ready for plan execution by an autonomous agent or control system.

The generation of a solution plan is the core objective of HTN planning, where methods recursively decompose tasks until only primitive operators remain. Unlike a skeletal plan, which contains abstract tasks, a solution plan is fully grounded and verifiable. In frameworks like SHOP, planning is interleaved with state progression to ensure each action's preconditions hold at execution time. This results in a hierarchical plan that is both a flat action sequence and a traceable decomposition tree, providing robustness for replanning if execution fails or the environment changes unexpectedly.

HIERARCHICAL TASK NETWORKS

Key Characteristics of a Solution Plan

A solution plan is the final, executable output of a Hierarchical Task Network (HTN) planner. It represents a complete, hierarchical breakdown of abstract goals into a sequence of primitive actions that are guaranteed to achieve the specified objectives from the initial state.

Fully Decomposed

A solution plan is the terminal product of recursive task decomposition, where all compound tasks have been replaced by networks of primitive tasks. There are no remaining abstract tasks requiring further breakdown. This decomposition is guided by methods from the domain description until only executable operators remain.

Executable Sequence

The plan consists of a sequence (or partially ordered set) of primitive actions. Each action is defined by an operator with clear preconditions and effects. When executed in order from the initial state, the preconditions of each action are satisfied by the effects of preceding actions, leading to a state where the goal conditions hold.

Hierarchical Structure

While the execution trace is linear, a true HTN solution plan often retains its hierarchical structure, forming a decomposition tree. This structure is crucial for:

Explainability: Tracing which high-level goal a specific action serves.
Replanning: Understanding which subtask failed if execution is interrupted.
Verification: Validating the logical soundness of the decomposition process itself.

State-Consistent

The plan is sound with respect to the initial world state. This means:

All ordering constraints between tasks are respected.
All preconditions for every action are provably met at the time of execution.
No resource constraints are violated (e.g., using more of a resource than is available).
The effects of actions are consistent and lead deterministically to the goal state.

Generated by HTN Planning

Solution plans are not arbitrary action lists; they are the specific output of HTN planning algorithms like SHOP (Simple Hierarchical Ordered Planner). These algorithms perform forward search interleaved with state progression, recursively applying decomposition methods to compound tasks starting from the initial task network.

Verifiable and Refinable

A solution plan is a concrete artifact that can be subjected to plan verification. Its hierarchical nature also makes it a starting point for plan refinement. If execution fails, replanning can occur not from scratch, but by backtracking to a specific point in the decomposition tree and applying alternative methods.

HIERARCHICAL TASK NETWORKS

How a Solution Plan is Generated

A solution plan is the final, executable output of a Hierarchical Task Network (HTN) planner, representing a complete sequence of primitive actions that achieves a specified goal from an initial state.

Generation begins with an initial task network, typically containing one or more high-level compound tasks. The HTN planner's core algorithm, such as SHOP (Simple Hierarchical Ordered Planner), performs task decomposition in a forward, depth-first search. It selects a non-primitive task, matches it against applicable methods from the domain description, and replaces it with the method's subtask network. This process recursively expands skeletal plans until only primitive tasks (operators) remain, all while respecting preconditions, ordering constraints, and resource constraints to ensure logical consistency.

The result is a hierarchical plan or a flattened sequence of actions—the solution plan. This plan is verifiable: when its operators are executed in order from the initial state, their effects cumulatively produce a world state where the goal conditions are satisfied. If execution fails or the environment changes, the system can trigger replanning, restarting the decomposition process from the new state. This deterministic, goal-directed generation is fundamental to automated planning systems and agentic cognitive architectures for complex workflow automation.

HIERARCHICAL TASK NETWORKS

Frequently Asked Questions

A Solution Plan is the final, executable output of a Hierarchical Task Network (HTN) planner. It represents a complete sequence of primitive actions that, when executed, will transform the initial world state into one that satisfies the specified goals. These questions address its core properties, generation, and role in autonomous systems.

A Solution Plan is a fully decomposed, executable sequence of primitive actions that, when executed from a defined initial state, is guaranteed to achieve the specified high-level goals. It is the final output of a Hierarchical Task Network (HTN) planner after all compound tasks in the initial task network have been recursively broken down via applicable methods until only primitive, directly executable operators remain.

Unlike a simple action list, a solution plan in HTN maintains traceability to the original hierarchical structure, often represented as a decomposition tree. It must satisfy all preconditions of its constituent actions and respect all ordering constraints and resource constraints defined in the domain description. The plan's validity is confirmed through plan verification, ensuring logical consistency and achievability before plan execution begins.

HIERARCHICAL TASK NETWORKS

Related Terms

A Solution Plan is the final output of an HTN planner. To understand its construction and properties, explore these core concepts from the planning domain.

Hierarchical Task Network (HTN)

The foundational planning formalism used to generate a Solution Plan. An HTN is a structured representation where high-level, compound tasks are recursively decomposed into networks of subtasks using methods. The decomposition process continues until only primitive tasks (executable actions) remain. This hierarchy provides a powerful abstraction for representing complex, procedural knowledge, separating the 'what' (the goal) from the 'how' (the method).

Primitive Task

A task that corresponds directly to an executable operator in the planning domain. In a Solution Plan, the final sequence is composed entirely of primitive tasks. Each primitive task has:

Preconditions: Logical conditions that must be true in the world state for the task to be executed.
Effects: The changes the task makes to the world state upon execution. Example: PickUp(Block_A), MoveTo(Location_B).

Compound Task

An abstract, high-level task that cannot be executed directly. It must be decomposed into a network of subtasks (which can be other compound tasks or primitive tasks) using an applicable method. Compound tasks define the problem's goals at various levels of abstraction. Example: BuildHouse() is a compound task. A method might decompose it into [LayFoundation(), ConstructWalls(), InstallRoof()].

Method (HTN)

A schema that defines one possible way to decompose a specific compound task. A method consists of:

Task: The compound task it decomposes.
Preconditions: Conditions that must hold for this decomposition to be valid.
Subtasks: The network of subtasks that replace the compound task. The planner selects among applicable methods during the search for a Solution Plan. Different methods represent different strategies or recipes for achieving the same high-level goal.

SHOP (Simple Hierarchical Ordered Planner)

A seminal, forward-chaining HTN planning algorithm. SHOP generates a Solution Plan by:

Progressing the world state forward from the initial state.
Decomposing tasks in a depth-first, ordered manner.
Interleaving planning with state progression, which makes it highly efficient. SHOP's approach ensures the generated plan is executable by construction, as preconditions are checked against the current simulated state during decomposition.

Decomposition Tree

A visual or logical tree structure that records the complete hierarchical breakdown performed by the HTN planner. The root is the initial goal task. Branches represent the application of methods. Leaves are the primitive tasks that form the final Solution Plan. This tree provides a trace of the planner's reasoning, showing how high-level intentions were mapped to low-level actions, which is crucial for debugging, explanation, and verification.

Frequently Asked Questions