SHOP (Simple Hierarchical Ordered Planner)

A defining feature is its requirement for totally ordered task networks. Subtasks within a method's decomposition are provided in a strict linear order. The planner processes them sequentially:

• The first subtask in the network is fully decomposed (if compound) or added to the plan (if primitive).
• Only after it is completely resolved does SHOP proceed to the next subtask in the order. This simplifies the planning process by eliminating the need for complex partial-order planning algorithms to manage temporal constraints during search, making the algorithm simpler and often faster for domains where natural sequential order exists.

At the leaves of the decomposition tree are primitive tasks, which correspond directly to planning operators with executable semantics. In SHOP:

• A primitive task is an operator name with parameters.
• When SHOP selects a primitive task during decomposition, it instantiates the corresponding operator.
• It checks the operator's preconditions against the current simulated state.
• If satisfied, it applies the operator's effects to update the simulated state and appends the operator instance to the growing plan sequence. This direct mapping ensures the final output is a concrete, executable sequence of grounded actions.

The choice of how to decompose a compound task is governed by method preconditions. Each method has logical preconditions that are evaluated in the current simulated state at the moment the compound task is encountered.

• Selection Mechanism: SHOP non-deterministically chooses any method whose preconditions are true.
• Backtracking Point: If a chosen method leads to a dead-end (e.g., a subsequent primitive task's preconditions fail), the planner backtracks to this choice point to try a different applicable method.
• Expressive Power: Preconditions can test for the presence/absence of facts, numeric quantities, and can include complex logical expressions, allowing the domain expert to encode sophisticated knowledge about when a decomposition strategy is appropriate.

Under standard assumptions, SHOP is a sound and complete planner for HTN domains with totally ordered task networks.

• Soundness: Any plan returned by SHOP is guaranteed to be executable from the initial state and will achieve the top-level task (i.e., it is a valid solution).
• Completeness: If a valid plan exists for the given problem, SHOP's search algorithm will find it, provided the domain description and search control are correctly formulated and the search space is fully explored (e.g., via backtracking). These formal guarantees are critical for deploying SHOP-based planners in safety-critical or mission-critical applications where plan correctness is non-negotiable.

A task in an HTN that corresponds directly to an executable operator or action in the planning domain. It is a leaf node in the decomposition tree and has associated preconditions (conditions required for execution) and effects (changes to the world state).

• Role: The atomic, executable unit of a plan.
• Analogy: A function call in programming.
• Example: For a robot, 'PickUp(Object)' and 'MoveTo(Location)' are primitive tasks with defined preconditions (e.g., gripper empty, path clear) and effects (e.g., holding object, at location).

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

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

• Role: Encodes the procedural knowledge of how to do something.
• Key Feature: A single compound task can have multiple methods, allowing the planner to choose the most appropriate decomposition based on the current world state.

The core algorithmic process in HTN planning where a compound task is recursively replaced by a network of its subtasks using an applicable method. This process continues until the entire plan consists solely of primitive tasks. The record of this process forms a decomposition tree.

• Process: Compound Task -> Select Applicable Method -> Replace with Subtask Network -> Repeat on any new compound tasks.
• SHOP's Approach: SHOP performs decomposition in a forward-chaining, depth-first manner, interleaving it with state progression to check preconditions in the current simulated world state.

The complete formal specification of an HTN planning problem. It defines the 'world' the planner operates in and includes:

• Operators: Definitions of all primitive tasks (preconditions & effects).
• Methods: Definitions for decomposing all compound tasks.
• Task Schemas: Templates for compound and primitive tasks.
• Predicates: The vocabulary for describing world states.

A Planning Problem is then an instance consisting of a Domain Description, an Initial State, and an Initial Task Network (the top-level goal tasks).