SHOP (Simple Hierarchical Ordered Planner)

SHOP is a progression planner. It starts from the initial world state and simulates the execution of actions forward in time. As it decomposes tasks, it immediately applies the effects of chosen primitive actions to a working copy of the state. This interleaving of planning and state simulation allows SHOP to:

• Evaluate the preconditions of methods and operators in the current, simulated state.
• Prune irrelevant decomposition paths early, as methods whose preconditions are not met in the current state are not considered.
• Efficiently handle numeric preconditions and resource constraints by tracking state changes in real-time during the search.

The algorithm decomposes tasks using a depth-first recursive search through the hierarchy of methods. When faced with a compound task, SHOP:

1. Selects an applicable method from the domain description.
2. Decomposes the compound task into the method's specified subtask network.
3. Immediately recurses on the first subtask in that network. This creates a commitment strategy where the planner fully decomposes one branch of the task hierarchy to a sequence of primitive actions before backtracking to explore alternatives. This is efficient for domains where correct high-level method choices lead directly to valid primitive plans.

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 planning formalism where the solution is generated by recursively decomposing high-level, compound tasks into networks of smaller subtasks using methods, until a sequence of directly executable primitive tasks is found. This approach encodes domain-specific knowledge about how to achieve goals, making it more efficient for complex, structured problems than pure state-space search.

• Core Idea: Planning as task refinement, not state-space search.
• Key Advantage: Encodes procedural knowledge, leading to highly efficient planning in well-understood domains.
• Contrast with Classical Planning: Classical planners search for a sequence of actions that connect an initial state to a goal state. HTN planners search for a way to decompose a task into known procedures.

A high-level, abstract task in an HTN 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 represent goals or activities like 'Assemble Product' or 'Diagnose System Failure'.

• Role: Serves as a placeholder for abstract goals requiring refinement.
• Decomposition: Each compound task has one or more methods that define possible ways to achieve it.
• Example: The task 'Navigate to Office' is a compound task. A method might decompose it into: 'Walk to Garage', 'Drive to Building', 'Park Car', 'Enter Building'.

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).