Method (HTN)

Every method is associated with a specific compound task it can decompose. The method's head matches the name and parameters of this abstract, high-level task. For example, a method with the head Transport(Package, CityA, CityB) provides a way to achieve the goal of transporting a package between two cities. A single compound task may have multiple methods, each representing a different strategy for accomplishing it.

A logical expression that must evaluate to true in the current world state for the method to be applicable. Preconditions gate the use of a specific decomposition strategy.

• Example: A Fly(Passenger, AirportA, AirportB) method may have the precondition HasTicket(Passenger) AND Operational(Airplane). If the passenger has no ticket, this method is invalid, and the planner must seek an alternative (e.g., a Drive method).
• Preconditions are evaluated during planning, enabling context-sensitive decomposition.

The core body of the method: a partially ordered network of new tasks that replace the original compound task. These subtasks can be:

• Primitive Tasks: Directly executable actions (operators).
• Compound Tasks: Requiring further decomposition by other methods.
• The network can include ordering constraints (e.g., Subtask1 BEFORE Subtask2) and causal links to ensure the preconditions of later tasks are met by the effects of earlier ones.

The planner applies a method by instantiating its subtask network and inserting it into the evolving plan in place of the matched compound task. This process is recursive: new compound subtasks are selected and decomposed until the plan contains only primitive, executable actions. This recursion builds a decomposition tree, which is later flattened into a linear sequence of actions for execution.

It is critical to distinguish a Method from an Operator in HTN planning.

• Operator: Represents a single, atomic, executable action in the world (e.g., PickUp(Object), NavigateTo(Location)). Defined by its preconditions and direct effects on the world state.
• Method: A decomposition rule for an abstract task. It has no direct world effects. Its "effect" is to introduce more plan structure. Methods provide the "how-to" knowledge, while operators provide the "what-can-be-done" knowledge.

The collection of methods in an HTN domain description encodes expert procedural knowledge, making HTN planning highly efficient for known domains. For instance, methods for AssembleProduct would encode the specific, correct assembly steps for that product. This contrasts with classical planners that search through all possible action sequences; HTN planners search through known, sensible decomposition paths, which is often far more constrained and directed.

A Compound Task is a high-level, abstract goal within an HTN that cannot be executed directly. It serves as a placeholder that must be decomposed into a network of smaller subtasks using applicable Methods. For example, the task DeliverPackage is compound; it requires decomposition into subtasks like NavigateToDestination, ConfirmRecipient, and HandOverPackage. The planner's primary job is to recursively decompose compound tasks until only primitive tasks remain.

A Primitive Task (or Operator) is the atomic, executable unit in an HTN. It corresponds directly to an action that can be performed in the world, such as MoveRobot or GraspObject. Unlike a compound task, a primitive task is not decomposed further. It is defined by:

• Preconditions: Logical conditions that must be true for the action to be applicable.
• Effects: The changes to the world state that result from executing the action. The planning process is complete when all tasks in the network are primitive.

Task Decomposition is the fundamental process in HTN planning. It is the act of replacing a Compound Task in the current plan with a network of subtasks by applying an applicable Method. This process is recursive; newly introduced compound subtasks are further decomposed. The decomposition is guided by the method's Preconditions, which ensure the chosen decomposition is valid for the current world state. This creates a Decomposition Tree, visually mapping the high-level goal to executable actions.

A Precondition is a logical expression that defines the circumstances under which a planning Operator (primitive task) or a Method is applicable. For a method, preconditions guard its use; the method can only be selected to decompose a task if its preconditions are satisfied by the current world state. For example, a method for ChargeDevice may have the precondition BatteryLevel < 20%. Preconditions are critical for ensuring plans are contextually appropriate and feasible.

A Skeletal Plan is a partially specified, abstract plan generated during the intermediate stages of HTN planning. It contains a mix of Compound Tasks awaiting decomposition and Primitive Tasks that are ready for execution. The skeletal plan is progressively refined through Task Decomposition until it becomes a fully concrete Solution Plan. This concept highlights the hierarchical refinement nature of HTN planning, as opposed to constructing a plan purely from sequential actions.

SHOP is a seminal, forward-search HTN planning algorithm. It operates by performing Task Decomposition in a depth-first, progressive manner, interleaving planning with state progression. As SHOP decomposes tasks, it immediately applies the effects of chosen primitive actions to a simulated world state. This allows subsequent preconditions to be evaluated against an updated state, making the planning process highly efficient and grounded. SHOP exemplifies how methods are procedurally applied to find an executable sequence.