Goal stack, nonlinear and hierarchical planning
Goal stack (linear) planning, nonlinear (partial-order) planning, and hierarchical task-network (HTN) planning: definitions, algorithms, examples (blocks world and HTN sandwich), and exam guidance.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Planning is how an AI agent chooses actions to reach goals from a starting state. Engineers use goal-stack, nonlinear (partial-order) and hierarchical planning when designing robot controllers, automated workflows, or intelligent agents that must sequence or decompose tasks under constraints.
Key ideas
Start with basic definitions and assumptions.
- State: a complete description of the world at a moment, usually represented as a set of positive ground atoms (predicates with no variables), under a closed-world assumption (any atom not in the set is false). Example: {On(A,Table), Clear(A), On(B,Table), Clear(B)}.
- Action (or operator): a change that can be applied to a state. In STRIPS-like form, an action has a name, a precondition set, an add list and a delete list.
- Notation (defined):
Action(name(params): precond -> add-list, del-list).
- Notation (defined):
- Precondition: a literal (or conjunction of literals) that must hold in the current state for the action to be executable.
- Add list: literals that become true after action execution.
- Delete list: literals that become false after action execution.
- Plan: a (finite) sequence or partial order of actions that, when executed from the initial state, leads to a state satisfying the goal formula.
- Goal: a set (conjunction) of literals the agent must achieve.
Assumptions used here (state-space STRIPS-style planning): deterministic actions, fully observable environment, discrete time, actions are instantaneous and have only propositional effects. These are standard exam assumptions.
Three planning styles:
- Goal-stack (linear) planning: Also called backward chaining or means-ends analysis in a procedural form. The planner maintains a stack of goals and actions. The algorithm pops a goal; if it is satisfied in the current (simulated) state, continue; otherwise, choose an action that has the goal in its add list, push that action and its preconditions as new goals, and continue. This produces a totally ordered plan (a sequence). It is greedy and commits early to action order.
Precise algorithm outline (goal-stack planner):
- Input: Initial state S0, Goal set G.
- Initialize: Stack = [Goal(G)], Plan = empty, CurrentState = S0.
- Loop: If Stack empty -> return Plan (in order of actions added).
- Pop top X from Stack.
- If X is an action: if its preconditions all in CurrentState, apply the action (update CurrentState = Result(CurrentState, action)) and append action to Plan; else push the action back and push its preconditions (goals).
- If X is a literal goal: if it holds in CurrentState, continue; else choose an action A with literal in Add(A), push A, push preconditions(A).
- Nonlinear / Partial-order planning (POP): Keeps actions unordered until ordering is required. Key concepts:
- Partial-order plan: a tuple (A, O, L) where A is set of action instances (including fictitious Start and Finish actions), O is a set of ordering constraints (a < b), and L is a set of causal links of form a --p--> b meaning action a establishes literal p for b and should appear before b. The plan also maintains a set of open preconditions (goal literals that are not yet supported).
- Causal link: records that an action a provides a literal p (in its add list) which is required by action b (in b's precondition). It is written as a --p--> b and implicitly enforces ordering a < b.
- Threat: some action c threatens a causal link a --p--> b if p ∈ Del(c) and c can be ordered between a and b (i.e., no ordering currently prevents c from occurring after a and before b). Threats are resolved by promotion (order c < a) or demotion (order b < c), or by modifying the plan to avoid the threat.
- Least-commitment principle: defer decisions about ordering and variable bindings until they are forced by causal support or threat resolution, preserving maximal flexibility.
POP algorithm (sketch of iteration):
- Start with A = {Start, Finish} where Start has initial state's literals in its add list and Finish has goal literals in its preconditions; O = {Start < Finish}; L = empty; open preconditions = preconditions(Finish).
- While open preconditions exist:
- Select an open precondition p of some action b.
- If some existing action a has p in its add list, add causal link a --p--> b and add ordering a < b; else instantiate a new action a' whose add list contains p and add it to A, add ordering a' < b and Start < a' if needed.
- For any causal link added, check for threats from other actions c ∈ A; if any c threatens, resolve by adding ordering constraints (promotion/demotion) that prevent c from coming between a and b; if cannot resolve without creating cycles, backtrack.
- When no open preconditions remain, return the partial-order plan (can be linearized to a total order respecting O).
Properties and exact statements:
- Result function (semantics of actions):
Result(s, a) = (s - Del(a)) ∪ Add(a)where s is a set of literals. This assumes actions are deterministic and atomic. - Soundness of POP: Under the listed assumptions, if POP returns a plan, then any linearization that respects ordering constraints, applied from S0, will achieve the goals (soundness). The reason: causal links guarantee each precondition is provided and threats are resolved.
- Completeness of POP: POP is complete for finite domains under the STRIPS assumptions if the planner systematically explores choices (i.e., with backtracking and fair selection of goals and actions). Completeness depends on search strategy and representations; state-space completeness proofs typically require finite number of ground actions.
- Hierarchical Task Network (HTN) planning: Unlike STRIPS, an HTN planner has two kinds of tasks: primitive (executable) and compound (must be decomposed). The planner uses methods to decompose compound tasks into subtasks (ordered or partially ordered). An HTN plan is correct if all compound tasks are decomposed until only primitive tasks remain and their execution yields the goal (HTN does not always require explicit goal formulas; it encodes task requirements in methods).
Drawings to include on an exam (describe what to draw and label):
- For POP example: Draw Start and Finish nodes; intermediate action nodes. Draw directed ordering arrows (labeled with <) between actions to show ordering. Draw dashed arrows as causal links labeled with the literal they achieve (e.g., a --On(A,B)--> b). Show a threatening action c with its delete effect labeled ¬On(A,B) and indicate the two possible resolutions: promotion (arrow c < a) or demotion (arrow b < c).
- For goal-stack linear plan: Draw a vertical stack with top at the top; show pushing of goals and actions and the final linear sequence of actions produced.
Formulas
Result(s, a) = (s − Del(a)) ∪ Add(a) — s: state as set of literals (no unit); a: action; Del(a): delete list; Add(a): add list. Applies for deterministic STRIPS-style operators.
Action(name(params): Pre(a) -> Add(a), Del(a)) — Pre(a): precondition set; Add(a): add list; Del(a): delete list. Syntax to remember for STRIPS operators.
Plan = (A, O, L) — A: set of actions (including Start, Finish); O: ordering constraints (partial order); L: causal links. Used in POP representation.
There are no SI units in symbolic planning formulas.
Worked examples
Example 1 — Goal-stack planning (Blocks world) Problem statement (explicit): Three blocks A, B, C. Initial state S0 = {On(A,Table), On(B,Table), On(C,Table), Clear(A), Clear(B), Clear(C)}. Goal G = {On(A,B), On(B,C)} (i.e., A on B and B on C, producing A–B–C stack).
Operators (STRIPS-style):
MoveTableToBlock(x,z): Pre = {On(x,Table), Clear(x), Clear(z)} -> Add = {On(x,z)}, Del = {On(x,Table), Clear(z)}MoveBlockToTable(x,y): Pre = {On(x,y), Clear(x)} -> Add = {On(x,Table), Clear(y)}, Del = {On(x,y)}(Two operators avoid referring to Clear(Table); move block x from the table to block z, or from block y to the table.)
Goal-stack steps (numbered):
- Stack starts with [Goal({On(A,B), On(B,C)})].
- Pop goal set and treat one goal at a time; first take On(B,C). Since not in S0, choose action MoveTableToBlock(B,C) whose add list contains On(B,C). Push the action and its preconditions: Stack becomes [MoveTableToBlock(B,C), Pre(MoveTableToBlock(B,C)) = {On(B,Table), Clear(B), Clear(C)}, remaining goal On(A,B)].
- Pop top preconditions. All of On(B,Table), Clear(B), and Clear(C) hold in S0, so we can execute MoveTableToBlock(B,C). Applying it: Result(S0, MoveTableToBlock(B,C)) = S1 = {On(A,Table), On(B,C), On(C,Table), Clear(A), Clear(B)} (we removed On(B,Table) and Clear(C), and added On(B,C)).
- Append MoveTableToBlock(B,C) to Plan. Remaining goal On(A,B): choose MoveTableToBlock(A,B), push and check its preconditions {On(A,Table), Clear(A), Clear(B)} which all hold in S1; execute it to reach S2 with On(A,B) and On(B,C) true. Final linear sequence: MoveTableToBlock(B,C) — MoveTableToBlock(A,B).
Final linear sequence (one possible correct answer): Move(A,Table,Temp) — Move(B,Table,C) — Move(A,Temp,B). A concrete sequence using an extra temporary table location is required; the student must show each push/pop and the final state. (Explicit step-by-step push/pop expected in exam.)
Note: In many textbooks a temporary location is simply "Table"; in exams state the intermediate actions and check preconditions carefully. Verify the exact intermediate steps and variable naming.
Example 2 — Partial-order planning (same Blocks world simplified) Problem: Initial and goal same as Example 1. Use POP to show a partial-order plan that is not totally ordered.
Model answer steps (concise, as an exam long answer):
- Create Start (adds initial literals) and Finish (preconditions are goal literals On(A,B), On(B,C)). Order Start < Finish.
- Open preconditions: On(A,B) for Finish, On(B,C) for Finish.
- To satisfy On(A,B), pick action a1 = MoveTableToBlock(A,B). Add a1, add causal link a1 --On(A,B)--> Finish, add ordering a1 < Finish, and Start < a1.
- To satisfy On(B,C), pick action a2 = MoveTableToBlock(B,C). Add a2, causal link a2 --On(B,C)--> Finish, add ordering a2 < Finish, and Start < a2.
- Check threats: a1 deletes Clear(B), which threatens the causal link Start --Clear(B)--> a2 (supporting a2's precondition). Resolve by ordering a2 < a1 (demote the threat) so that a1 cannot occur between Start and a2 on that link. After adding this constraint, the plan remains partially ordered; valid linearizations must place a2 before a1.
Provide the diagram to draw: nodes Start, a2, a1, Finish, with causal links labeled On(B,C) and On(A,B) and an ordering arrow a2 < a1 (if chosen).
Example 3 — HTN (short model answer) Task: Prepare a sandwich. Compound task Make-Sandwich decomposed by method M1: [Get-Bread, Get-Filling, Assemble]. Each of these might further decompose: Get-Bread -> [Open-Box, Take-Slice], Assemble -> [Place-Bread, Put-Filling, Close-Bread]. The HTN planner chooses appropriate methods and produces a partially-ordered set of primitive actions. State that HTN methods can enforce ordering among subtasks and add constraints (e.g., Get-Filling must be done before Put-Filling). Show that HTN can encode procedural knowledge (recipes) and is less search-heavy when such knowledge exists.
Common mistakes
- Not checking delete lists: students often add an action because its add list supports a goal, but forget it deletes some other needed literal and thus creates a threat.
- Claiming POP always returns a totally ordered plan — wrong: POP returns a partial-order plan; it may be linearized but the algorithm does not commit to order unless forced.
- In goal-stack planning, forgetting to re-evaluate CurrentState after applying an action — leads to inconsistent precondition checks.
- Mixing HTN and STRIPS: HTN uses task decomposition (methods) and may not explicitly use a goal formula; mixing formalisms without clarification causes loss of marks.
For your exam
Typical question types:
- Definitions: define plan, operator, precondition, add/delete lists, causal link, threat, partial-order plan, HTN method. Full-marks: concise definition plus a short example.
- Short notes: compare goal-stack vs POP vs HTN; explain least-commitment principle. Full-marks: include pros/cons, complexity intuition, and when to use each.
- Derivations / algorithms: give the POP algorithm or goal-stack algorithm step-by-step. Full-marks: must include Start/Finish, open preconditions, causal links, threat resolution rules.
- Diagram question: draw a partial-order plan with causal links and show a threat and how to resolve it. Full-marks: draw nodes, order arrows, causal links labeled with literals, and label threat resolution.
- Long problem: perform planning on a blocks-world instance using goal-stack and then using POP; show each push/pop or each POP step. Full-marks: show explicit actions chosen, preconditions checked, causal links and threats identified and resolved, final plan linearization if required.
Exam strategy: always state assumptions (STRIPS, deterministic, fully observable), write Start/Finish explicitly in POP answers, and show state updates when using goal-stack.
Quick check
- What is a causal link in partial-order planning?
- Write the STRIPS successor function (Result) formula.
- Give one advantage of HTN over plain STRIPS planning.
Answers: 1) A causal link a --p--> b records that action a provides literal p needed by action b and enforces ordering a < b. 2) Result(s,a) = (s − Del(a)) ∪ Add(a). 3) HTN encodes domain knowledge as task decompositions, reducing search by using methods to guide planning.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?