Planning Problem (HTN)

The Domain Description is the rulebook and capability catalog for the planner. It formally defines:

• Operators: The atomic, executable actions. Each operator has preconditions (logical conditions that must be true for it to run) and effects (how it changes the world state).
• Task Schemas: Templates for both Primitive Tasks (which map directly to operators) and Compound Tasks (high-level, abstract goals).
• Methods: The recipes for decomposition. Each method specifies how a single Compound Task can be broken down into a network of smaller subtasks (which can be compound or primitive), provided its preconditions are met. This description is reusable across many different planning problems within the same operational domain, such as logistics, manufacturing, or software deployment.

The Initial World State is a complete snapshot of the environment at the start of the planning process. It is a set of grounded logical propositions that describe what is true. For example:

• (robot-at dock-1)
• (package-loaded pkg-a truck-1)
• (battery-level robot-1 85) The planner uses this state to evaluate the preconditions of operators and methods. A method or operator is only applicable if all its preconditions are logically satisfied by the current world state. This component grounds the abstract planning problem in a specific, concrete scenario.

The Initial Task Network is the 'to-do' list given to the planner. It specifies the high-level goal(s) that need to be accomplished, expressed as one or more Compound Tasks. This is not a simple goal state (a desired set of conditions); it is a task to be performed.

For instance, instead of a goal (delivered pkg-a warehouse-5), the initial task network would contain the compound task (deliver pkg-a warehouse-5). The planner's job is to recursively decompose this task using methods from the domain description until it produces a sequence of executable primitive actions (operators) that, when applied to the initial state, result in the package being delivered.

A Planning Problem P is formally defined as the triple: P = (D, s0, t0) where:

• D is the Domain Description.
• s0 is the Initial World State.
• t0 is the Initial Task Network. The planner's algorithm searches for a Solution Plan—a fully decomposed network where all tasks are primitive and ordering constraints are satisfied. The plan is valid if, when the primitive actions are executed in sequence starting from s0, they successfully accomplish the decomposition of t0.

HTN planning fundamentally differs from Classical (STRIPS-style) Planning:

• Classical: Given an initial state and a goal state, find any sequence of actions that transforms one into the other.
• HTN: Given an initial state and an initial task network, find a sequence of actions by recursively decomposing tasks according to provided methods. HTN is not just about achieving a state; it's about performing tasks in a prescribed, often procedurally constrained, manner. This makes HTN more expressive for modeling complex, hierarchical procedures but requires more upfront knowledge engineering in the domain description.

Consider a robot warehouse problem:

• Domain (D): Contains operators like drive, load, unload. Contains compound tasks like transport-package. Contains a method: (transport-package ?p ?loc) can be decomposed into [navigate-to ?p, pick-up ?p, navigate-to ?loc, drop ?p].
• Initial State (s0): (robot-at charging-station), (package-at pkg-1 shelf-a).
• Initial Task (t0): (transport-package pkg-1 loading-dock). The HTN planner decomposes t0 using the method, checks preconditions for each new subtask (e.g., navigate-to requires knowing the robot's location), and eventually outputs a primitive sequence: [drive charging-station shelf-a, load pkg-1, drive shelf-a loading-dock, unload pkg-1].

The overarching planning formalism in which a Planning Problem is defined. An HTN represents tasks at multiple levels of abstraction, from high-level goals to primitive actions. The planner's job is to find a valid decomposition path through this hierarchy.

• Core Idea: Break down 'what' needs to be done (tasks) before deciding 'how' to do it (actions).
• Contrast with Classical Planning: Classical planners search through sequences of actions; HTN planners search through possible task decompositions.

The knowledge base that defines the rules of the planning world. It is a mandatory component of a Planning Problem (HTN). This description includes:

• Operators: Definitions of primitive, executable actions (preconditions & effects).
• Methods: Recipes for decomposing compound tasks into subtask networks.
• Task Schemas: Templates for all possible tasks (primitive and compound).
• Axioms & Constraints: Additional logical rules and limitations (e.g., resource limits).

Without a domain description, a planner has no knowledge of how to act or decompose tasks.

The starting goal specification for the planning problem. It is not a single goal state but one or more high-level compound tasks that need to be accomplished. This network is the root of the decomposition tree.

• Example: [achieve(goal_state)] or [build(house), paint(house)].
• Role in Planning: The planner's objective is to transform this initial network into a network containing only primitive tasks (actions) that are executable from the initial world state.

A task that corresponds directly to an executable action (operator) in the world. It is the leaf node in an HTN decomposition. Primitive tasks have no further subtasks; they are carried out by the execution engine.

• Characteristics: Defined by an operator with preconditions (must be true to start) and effects (changes to the world state).
• Example: pick_up(block_A), turn_valve(left, 90_degrees).
• End State of Planning: A solution plan is a sequence of ordered primitive tasks.

A high-level, abstract 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 'what' without specifying 'how'.

• Role: They provide the hierarchical structure. The initial task network typically contains compound tasks.
• Decomposition: A single compound task may have multiple methods, each representing a different way to achieve it under different conditions.
• Example: build_wall() is a compound task; methods might decompose it into [lay_foundation(), stack_blocks(), apply_mortar()].

A decomposition rule that specifies one way to accomplish a compound task. A method is defined by:

1. Task Head: The compound task it decomposes.
2. Preconditions: Logical conditions that must hold in the current state for this method to be applicable.
3. Subtasks: The network of (compound or primitive) tasks that replace the parent task.
4. Ordering Constraints: Temporal relations between the subtasks.

• Key Function: Methods encode procedural knowledge (different ways to do things). The planner searches through applicable methods to find a decomposition that leads to a feasible primitive action sequence.