Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Planning and the blocks world

Concise study notes on classical planning and the blocks world: STRIPS formalism, state-transition equations, forward/backward search, Graphplan and partial-order planning, with worked blocks-world examples 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 the AI task of computing a sequence of actions (a plan) to reach a goal from a known start. Engineers use planning in automated control, robotics (motion and manipulation), automated testing, and any system that must schedule or sequence actions under constraints — for example, a robot arm stacking blocks or a factory scheduling jobs.

Key ideas

  • Action / Operator (a): An action (or operator) has three parts in STRIPS-style representation: Preconditions Pre(a) (a set of atoms that must be true to apply a), Add-list Add(a) (atoms made true by a), and Delete-list Del(a) (atoms made false by a). Assumption: actions are instantaneous, deterministic, and their effects are fully captured by add and delete lists.

  • Applicability: An action a is applicable in state s iff Pre(a) ⊆ s. (You must check every atom of Pre(a) is present in s.)

  • Result / successor function: The result of applying a to s (written Result(s,a)) is the new state obtained by removing Del(a) from s and adding Add(a). This is the standard STRIPS state-transition function.

    Exact statement: For propositional STRIPS, Result(s,a) = (s − Del(a)) ∪ Add(a), provided Pre(a) ⊆ s; otherwise a is not applicable.

    Universities often ask a step-by-step derivation: start from s as a set of atoms, remove each atom in Del(a), then add each atom in Add(a). Show closure under set union; do not re-add deleted atoms unless they appear in Add(a).

  • Plan: A plan Π is a (finite) sequence of actions [a1, a2, …, an] such that Result(...Result(Result(s0,a1),a2)…,an) satisfies G (i.e., all atoms of G are in the final state). If actions can be parallelised, a plan can be a partially ordered set of actions with ordering constraints.

  • Classical search view: Planning can be viewed as state-space search: start at s0, use Result(s,a) to generate successor states until you reach a state satisfying G. Alternatively search can be done backward from goals (goal regression), or in plan-space (search over partially specified plans).

  • Complexity (exact statements students should remember): In propositional STRIPS with unbounded plan length, the decision problem "Does there exist a plan that reaches G from s0?" (plan-existence) is PSPACE-complete. If plan length is given as a bound that is polynomial in the input size, the bounded plan-existence problem is NP-complete. These statements assume classical deterministic, propositional STRIPS operators.

  • Graphplan: Graphplan builds a layered planning graph with alternating proposition layers P0, P1, P2, … and action layers A0, A1, A2, …

    • P0 is the set of atoms true in s0.
    • Ai contains all actions whose preconditions are satisfied in Pi (considering persistence / no-op actions for each proposition).
    • Pi+1 contains all atoms that are added by actions in Ai; with no-ops, Pi ⊆ Pi+1 and delete effects do not remove atoms from Pi+1 (their impact appears as mutexes).
    • Mutex (mutual exclusion): Two actions at the same action layer are mutex if they have inconsistent effects (one deletes an effect of the other), interfere (one deletes a precondition of the other), or have competing needs (their preconditions are pairwise mutex). Two propositions at the same proposition layer are mutex if every pair of actions that could achieve them are pairwise mutex; additionally, a proposition and its negation are always mutex if explicit negative literals are represented. Graphplan alternates growth and mutex propagation until the goal atoms all appear in some Pi without pairwise mutex; then it performs a backward search (plan extraction) to pick non-conflicting achievers and produces a plan. Extraction is a constraint search and may backtrack.
  • Partial-Order Planning (POP): A partial-order plan is a tuple (A, O, CL) where A is a set of actions, O is a set of ordering constraints (ai ≺ aj), and CL is a set of causal links (ai —p→ aj) indicating action ai establishes precondition p of aj. POP algorithms search in plan-space, adding actions, causal links and orderings, and resolving threats (an action that could delete a causal link) by adding order constraints or promoting/demoting the threatening action.

  • Blocks world specifics: Typical blocks-world atoms: on(X,Y), ontable(X) (or equivalently represent ontable(X) as on(X,table)), clear(X). Typical operator move(X,Y,Z) moves block X from Y to Z (Y and Z may be block names or table), with preconditions on(X,Y) and clear(X) and clear(Z) (for Z=table include clear(table) as a proposition if you use the same scheme), add on(X,Z) and clear(Y), delete on(X,Y) and clear(Z).

Diagram students should be able to draw when asked: a planning graph to level k — draw alternating horizontal layers: P0 (propositions), below it A0 (action nodes), below that P1, etc. Draw action-to-proposition directed edges for effects, proposition-to-action edges for preconditions, and dashed lines between mutex nodes (label as mutex). For POP draw actions as boxes with arrows for causal links and dotted arrows for ordering constraints.

Formulas

Applicable(a,s) ⇔ Pre(a) ⊆ s — Pre(a): precondition set, s: state (set of atoms). Applies when actions are STRIPS-style.

Result(s,a) = (s − Del(a)) ∪ Add(a) — Result is the successor state after action a; symbols are sets of atoms; no SI units (propositional).

Result(s0, [a1,...,an]) = Result(...Result(Result(s0,a1),a2)..., an) — result of a plan is repeated application of Result.

Regression(G, a) = (G − Add(a)) ∪ Pre(a), defined only if Del(a) ∩ G = ∅ — goal-regression step used in backward search.

Planning problem = (S, A, s0, G) — S: set of states, A: set of actions, s0: initial state, G: goal condition (set of atoms).

Planning graph layers: PG = P0, A0, P1, A1, ..., Pk — Pi: propositions true at level i, Ai: actions applicable at level i (including no-ops).

Worked examples

Example 1 — STRIPS blocks world, step-by-step (exam style model answer). Problem: Blocks A, B, C. Initial state s0 = {on(A,B), on(B,table), on(C,table), clear(A), clear(C), clear(table)}. Goal G = {on(A,table), on(B,A)}. Operator (schema) move(x,y,z): Pre(move(x,y,z)) = {on(x,y), clear(x), clear(z)} Add(move(x,y,z)) = {on(x,z), clear(y)} Del(move(x,y,z)) = {on(x,y), clear(z)} Find a plan. Solution (steps):

  1. Check an applicable action in s0: move(A,B,table) is applicable because Pre = {on(A,B), clear(A), clear(table)} ⊆ s0. Apply Result(s0, move(A,B,table)) By formula: s1 = (s0 − Del) ∪ Add Del = {on(A,B), clear(table)}; Add = {on(A,table), clear(B)} s1 = {on(B,table), on(C,table), on(A,table), clear(A), clear(C), clear(B)}
  2. Now check move(B,table,A) in s1: Pre = {on(B,table), clear(B), clear(A)} ⊆ s1, so applicable. Apply Result(s1, move(B,table,A)) Del = {on(B,table), clear(A)}; Add = {on(B,A), clear(table)} s2 = {on(A,table), on(B,A), on(C,table), clear(B), clear(C), clear(table)}
  3. Check goal G = {on(A,table), on(B,A)} ⊆ s2. Both goal atoms present, so plan [move(A,B,table), move(B,table,A)] succeeds. Answer (final): The plan is [move(A,B,table), move(B,table,A)]. Bold final state achievement: Goal reached: on(A,table) and on(B,A).

Example 2 — Sketch of Graphplan for the same instance (model-answer style).

  1. P0 = s0 = {on(A,B), on(B,table), on(C,table), clear(A), clear(C), clear(table)}.
  2. A0: include all actions whose preconditions are in P0 (plus no-op actions for each proposition). In this instance, include move(A,B,table); move(B,table,A) is not included because clear(B) ∉ P0.
  3. Compute P1 from A0 effects: P1 contains all propositions added by actions in A0 (including persistence via no-ops). Here, P1 includes on(A,table) and clear(B) (effects of move(A,B,table)), and also on(A,B), on(B,table), on(C,table), clear(A), clear(C), clear(table) via no-ops; it does not include on(B,A) at this level. For mutexes: action-level mutex is checked only between actions in A0; “competing needs” depends on preconditions being mutex at P0 (not on their truth values). Since P0 has no proposition mutexes and only one real action is present (besides no-ops), there is no competing-needs mutex between real actions at A0. Due to interference, the no-op for on(A,B) is mutex with move(A,B,table), so in P1 the pair on(A,table) and on(A,B) are proposition-mutex by inconsistent support.
  4. Grow graph until both goal atoms appear together in some Pi without pairwise mutex. At that level perform backward search to choose achievers that are not mutex, producing the same sequence as the STRIPS forward plan above (possibly with different ordering if parallel actions are allowed). (Exam advice: draw P0, A0, P1, label action and proposition nodes, show mutex edges and show the two chosen actions during extraction.)

Common mistakes

  • Assuming table needs no clear(table) unless your encoding explicitly treats table as a proposition; be consistent in encoding and state the assumption.
  • Mixing up goal satisfaction (all goal atoms must be present) with having at least one goal atom present.
  • Drawing planning graphs without marking no-op actions or without propagating mutex relations correctly (especially competing needs).
  • For POP, failing to identify and correctly resolve threats to causal links.

For your exam

Question types you will get and what full-marks answers include:

  • Definitions and short notes: define STRIPS operator, state, plan, planning graph, mutex; give concise examples.
  • Derivations: show Result(s,a) step-by-step for a given action and state; show successor-state expansion in search.
  • Diagram question: draw 3 levels of a planning graph for a small problem and mark mutex links; label P0, A0, P1 etc.; explain why a pair is mutex.
  • Long answer / model problem: formalize a small blocks-world problem with STRIPS operators, show a valid plan by forward or backward search with each step justified, and show state after each action.
  • Algorithm explanation: explain Graphplan steps (graph growth, mutex propagation, extraction) or POP steps (add causal link, check threats, add ordering) and discuss complexity informally. Full-marks answers always state assumptions (e.g., whether table is modelled as a proposition, whether actions are instantaneous/deterministic), show all intermediate states or graph levels, and explain why preconditions are satisfied and why goals are achieved.

Quick check

  1. In STRIPS, an action is applicable in state s when which relation holds?
  2. Write the formula for the successor state after applying action a in state s (the Result formula).
  3. What is a causal link in partial-order planning? Answers: 1) Pre(a) ⊆ s. 2) Result(s,a) = (s − Del(a)) ∪ Add(a). 3) A causal link ai —p→ aj asserts that action ai achieves proposition p which is a precondition of aj and protects that condition from being deleted by intervening actions (until aj).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?