STRIPS: a world described by literals, actions described by preconditions and by two lists of effects, and a plan found by ordinary search over that description. This is the Part where logic stops being a language for asking questions and starts being a language for changing the world.
Printed copy: all hidden answers below are revealed. On screen they are behind a click, which is how you should use them first.
the theory exam... tests both for factual knowledge as well as for synthetic knowledge... we also want to see that you can uh bring things across different chapters uh together because as you know by now uh the course is largely incremental.(Lecturer, T9). Planning is the most incremental Part in the course: it borrows the representation from Part 10 and the search from Parts 4 and 5, and adds only the action schema. Expect a question that needs two chapters at once.
The lecture starts where Part 10 ended. You have a problem, you encode it into a formalism, you hand the encoding to a highly optimised solver, and you decode the answer back. Deck pp.2 to 8 are that recap in five slides, ending on p.8 with a list of what first-order logic can express: "circuits, software, planning, law, taxes, network and security protocols, product descriptions, ecommerce transactions, geographical information systems, Google Knowledge Graph, Semantic Web". Planning is the item that gets its own lecture.
The difference from every search Part so far is on p.9, the motivating example. You are outside a room and want to be inside it. Four actions are listed with their preconditions and effects: Move to door (preconditions: none, effects: At door), Unlock door (preconditions: Hold key, effects: Door open), Kick door (preconditions: none, effects: Door open), Move into room (preconditions: Door open, effects: In room). The plan is not just a path through positions. Each step carries an action that changes what is true about the world, and later actions are legal only because earlier ones made them legal.
The lecturer frames the whole Part against Part 9: there we searched for a policy in a stochastic environment, here we search for a plan in a deterministic one. Same pair of axes from the Part 2 taxonomy, opposite corner. See Part 9 for the other half of that contrast.
Deck p.10 names the formalism: STRIPS (Stanford Research Institute Problem Solver), proposed by Fikes and Nilsson in 1971 (deck p.40), originally the planner inside Shakey the robot, and now the name of the input language rather than the program. Deck p.11 gives the shape of every planning problem in one slide:
Five slides build the definition on a Sokoban level (a warehouse puzzle where a figure pushes crates onto marked squares). They add one line at a time, and the order of the lines is the definition.
The slide gives one of the three inputs of a planning problem. Name the other two, in the order the deck introduces them, before scrolling.
The goal (frame 2, p.13) and the available actions (frame 3, p.14). Deck p.11 already listed all three: initial state, goal, available actions. Why it matters: the sample exam's open question 3.2 asks you to "explain the relevant parts of the input that determines a STRIPS planning problem". Those three, with the right qualifiers on each, are the marks.
The goal is drawn as three X marks. Is this goal a complete description of the desired final state? Say what it does not fix.
No. It fixes only where the crates must end up. It says nothing about where the figure stands at the end, and nothing about which crate goes on which X. That is the partial specification of goals which deck p.24 makes formal: the goal is a set of literals that must be present, and the final state may contain many more. Why it matters: this asymmetry between the initial state and the goal is the single most quotable fact in the Part, and section 5 gives the lecturer's own words for it.
Four arrows are drawn. How many actions are actually applicable in the position shown, and what would you have to know to answer that without looking at the picture?
You cannot tell from the arrow picture alone: an arrow is a schema, and whether an instance of it is applicable depends on the preconditions holding in the current state (a wall or an unpushable crate blocks the move). The arrows show four action types, not four legal moves. Why it matters: the same distinction, schema versus applicable ground instance, is what sections 6 and 7 are entirely about. In the blocks world the schema Move(b,x,y) has 48 ground instantiations over three blocks plus the table, and only six of them are applicable in the initial state (both numbers computed and checked; see section 12).
The deck writes the solution as "a sequence of actions that achieves the goal", for example [Left, Down, Left, Up, ...]. Complete the formal version from p.11: a sequence of actions that, executed in the initial state, results in a state that ______.
"satisfies the goal condition" (deck p.11, verbatim). Note the word satisfies, not equals: p.24 defines satisfaction as containment, g ⊆ s. Why it matters: writing "results in the goal state" instead of "results in a state that satisfies the goal" is exactly the error that the closed-world asymmetry punishes.
The final frame blanks out the puzzle with two plain rectangles and adds a second bullet under "Find": a method capable of finding a solution for every application domain. Why blank the level out?
Because the method must not look at the level. Everything the planner is allowed to use is the formal description (initial state, goal, action schemas); the picture is for you, not for the algorithm. Blanking it is the visual statement of domain independence, which returns on p.64 as the reason planning heuristics are different from the Manhattan distance you used in Part 5. Why it matters: quote 36 in section 14 is the lecturer making exactly this point, and it is prime multiple-choice material.
Three slides, no procedure. Deck p.17: scheduling in general, and the Hubble Space Telescope in particular. The lecturer's reason for Hubble is worth one line because it shows what "resource" means in a planning problem: the telescope has limited memory and limited computing power, so an observation is only legal if there is memory free to store the result, and the memory is only freed after a communication window sends the image to Earth. Take an observation too early and the plan is infeasible for a reason that has nothing to do with pointing the mirror.
Deck p.18: KIVA warehouse robots, which drive under a shelf, lift it, and carry the shelf to the picker instead of the picker walking to the shelf; the planning content is collision-free routing for many agents at once. Deck p.19: unmanned aerial vehicles, the DARPA Grand and Urban Challenge cars, and Honda ASIMO, where the point is replanning under conditions you did not foresee, such as a gust of wind. Deck p.76 repeats the same list in the conclusion: space, flight, robotics.
Deck p.20 introduces the running example: the blocks world. Three blocks on a table, an initial state s0 with all three side by side, a goal g with A on B on C, and three shapes of legal move (table to block, block to table, block to block).
You are about to be given two predicates that describe every state of this domain. Guess them, then say how many ground atoms they generate over the constants A, B, C and Table.
On(b,x) and Clear(x) (p.21). Over the four constants that is 4 × 4 = 16 ground On atoms and 4 ground Clear atoms, 20 in total, so at most 220 literal sets, though almost none of them describe a physically possible arrangement. Why it matters: the exercise session asks precisely this counting question for n blocks (section 12), and the gap between "sets of literals" and "physically sensible states" is what makes planning hard.
The deck defines Clear(x) as "a block can be placed on top of x", not as "nothing is on x". The exercise session sheet gives both readings: "there is no object on x OR an object can be placed on x". Which reading do you need for the Table, and why does the deck's s0 on this slide not contain Clear(Table)?
For the Table the two readings come apart: the table always has room for another block (so "a block can be placed on it" is permanently true), but it is never "empty" once anything sits on it. The deck's s0 here lists only On(A,Table), On(B,Table), On(C,Table), Clear(A), Clear(B), Clear(C), so Clear(Table) is absent, which under the closed-world assumption means it is false. Why it matters: this one absent literal is the whole content of section 8. Note also that the exercise-session sheet makes the opposite choice and puts Clear(Table) into its s0. Both are defensible; you must say which you are using.
Write one literal that violates "ground" and one that violates "function-free", using this vocabulary.
Not ground: On(b,Table), because b is a variable (lower case), so the literal does not say anything definite about the world. Not function-free: Clear(topOf(A)), because topOf is a function symbol whose value would have to be computed. The lecturer's phrasing is that the arguments of the predicates must always be constants. Why it matters: "ground and function-free" is the qualifier the open question 3.2 wants when it asks how a state is represented, and it is also the precondition for the state space being finite (deck p.57).
The beige panel lists the negative literals that the closed-world assumption supplies for free. Sixteen of them are harmless bookkeeping about blocks not being on each other. One of them is going to cause a bug 12 slides later. Which one, and what will go wrong?
¬Clear(Table), the last line. Because Clear(Table) is not asserted in s0, the closed world makes it false, so any action whose preconditions include Clear(Table) is blocked from the start; and once some action adds Clear(Table), a later move can delete it again and lock the table permanently. That is the flawed representation of deck pp.35 to 38, worked in section 8. Also worth noticing: the printed panel repeats ¬On(A,A), ¬On(A,B) and ¬On(A,C) a second time, so read it as an illustration of the principle rather than as an exact enumeration.
anything that is not mentioned in the original state is also assumed to be false
and, on the very next slide,
the target state... is only partially specified without a closed world assumption.(Lecturer, T10). This is the asymmetry, in his own words, said twice within a minute. The initial state is closed and complete; the goal is open and partial. Everything that follows, the applicability test and the goal test, is built on it.
The goal panel contains exactly two literals: On(A,B) and On(B,C). The picture shows A on B on C on the table. Write the goal test as a set expression, and say what happens to On(C,Table) and Clear(A).
The test is g ⊆ s. A state satisfies the goal if it contains all the literals of g; it may contain many more. On(C,Table) and Clear(A) are true in the picture but are simply not required, so they are neither in g nor forbidden. Under a closed-world reading of the goal you would be demanding that they be false, which would make the goal unsatisfiable. Why it matters: the goal test g ⊆ s and the applicability test PRE ⊆ s are the same operation on the same data structure. That is the observation the "why we like this formalism" slide is built on (section 10).
This slide adds a third word to "ground" and "function-free": positive. Both s0 and g are lists of positive literals. What does that rule out, and what does the note about a logical conjunction let you write instead of a set?
It rules out writing a negative literal inside a state or a goal: you may not put ¬On(A,B) in s0 or in g. Negation appears only in the effects of an action, where it means "delete this literal". The conjunction note means the set {On(A,B), On(B,C)} may equally be written On(A,B) ∧ On(B,C), which is how deck p.38 prints it. Why it matters: this is why a STRIPS state is representable as a plain set and why the successor computation is two set operations rather than logical inference.
Constructed, in the sample paper's format (2023 theory Part 1, true or false)
In STRIPS, both the initial state and the goal are completely specified descriptions under a closed-world assumption.
Whenever this Part asks "how is a state represented", the marks are in the adjectives, not the noun. The full stack, in the deck's own order: a state is a set of first-order logic literals that are ground, function-free and positive, completely specified under the closed-world assumption, so that anything not listed is false. The goal takes the same first four adjectives but is partially specified with no closed-world assumption. Say all of it; it is one sentence and it is a chunk of open question 3.2.
Deck p.26 states the three moves in English. Deck p.27 gives the two halves every action has, and p.28 fills them in. This is the slide to be able to reproduce from memory.
The slide defines preconditions and effects in words. In one line each, say what kind of object each list contains and what the system does with it.
Preconditions: a list of literals that must be in the state for the action to be applicable. The system tests them by set containment. Effects: a list of literals, some positive and some negated, saying how the state is transformed. The system applies them by adding the positive ones and removing the negated ones. Why it matters: the exam answer needs the two lists and the split of the effects into positive and negative, because the successor computation treats the two halves differently.
Cover the slide. Write the three preconditions and the four effects of Move(b,x,y) and give the physical reason for each. Then check.
Preconditions. On(b,x): you can only move b off x if it is on x. Clear(b): the gripper takes b from above, so nothing may be on top of b. Clear(y): there must be room on the destination.
Effects. Positive: On(b,y) (b is now on y) and Clear(x) (whatever b was standing on is now free). Negative: ¬On(b,x) (it is no longer on x) and ¬Clear(y) (the destination is now occupied).
Two symmetries worth memorising: the arguments of the two positive effects are (b,y) and (x), and the arguments of the two negative effects are (b,x) and (y). Positive and negative swap x and y. Why it matters: this is the figure the 2023 open question 3.2 is really asking about, and a schema written with Clear(x) in the preconditions instead of the effects is the classic slip.
Constructed, in the sample paper's format (2023 theory Part 1, true or false)
In the blocks-world schema Move(b,x,y), Clear(x) is one of the preconditions.
Deck pp.29 to 32 then instantiate the schema three times against a concrete state, which is exactly the pen-and-paper skill the exercise session drills.
Write the substitution that turns the schema into this ground action, then list the four ground effects.
Substitution: b to B, x to Table, y to C. Preconditions become On(B,Table), Clear(B), Clear(C), all three present in s0, so the action is applicable (the three "OK!" marks). Effects become positive On(B,C) and Clear(Table), negative ¬On(B,Table) and ¬Clear(C). Note that Clear(x) with x bound to Table produces Clear(Table): the schema has just injected the literal whose absence defined the closed world on p.23. Why it matters: this is the exact instantiation the deck reuses on p.52, and it is where Clear(Table) enters the state space.
Two of the three preconditions hold and the third fails. Which one, why does the picture agree, and what does the algorithm do next?
Clear(C) fails: in this state B is sitting on C, so the state contains On(B,C) and not Clear(C). The picture agrees because you can see B on top of C. The algorithm does nothing special: applicability is a single containment test on the whole precondition list, so one missing literal makes the whole ground action unavailable, and it never appears in the successor set. Why it matters: on paper, students check the preconditions that the picture makes obvious and forget the one that the closed-world assumption is quietly making false. Check all of them, every time, in writing.
Deck pp.29 and 32 together are a complete plan for the toy problem. Write the plan, then perform the goal test formally.
Plan: <Move(B,Table,C), Move(A,Table,B)>, cost 2. Executing it from s0 gives s2 = {On(A,B), On(B,C), On(C,Table), Clear(A), Clear(Table)}. Goal test: g = {On(A,B), On(B,C)}, and both are in s2, so g ⊆ s2 and the plan is a solution, even though s2 contains three literals the goal never mentions. This plan and this cost were verified by executing the schema in code; it is also the plan A* finds in section 13. Why it matters: this is the shortest possible worked example of "satisfies" meaning "contains".
Exercise session 8, question 2, bullets 1 and 2 (verbatim)
There are 4 cities, A, B, C, D as shown in the figure below. Two cities are connected with a road if there is an edge between them. There is a 'gift' at D which must be delivered by a truck (loaded and then unloaded) to B. The truck is initially at A.
The figure is a four-city cycle: A to B, B to C, C to D, D to A, each road usable in both directions.
Initial state. {road(A,B), road(B,A), road(B,C), road(C,B), road(C,D), road(D,C), road(D,A), road(A,D), truck(A), gift(D)}. Both directions of every road appear as separate ground literals, because road is not symmetric by magic; nothing outside the state description is true.
Goal. {gift(B)}. One literal. Nothing about where the truck ends up, and nothing about loaded().
Actions.
What earns the marks. Three things. (1) The road literals are in the state, not hard-wired into the action, which is why road(x,y) is a precondition of move: that is what stops the truck teleporting. (2) The truck's position is a single literal that is deleted and re-added, not a set of literals; forgetting ¬truck(x) lets the truck be in two places at once, and section 15 shows that this is precisely the relaxation h+ makes on purpose. (3) loaded() is a zero-argument predicate: the gift disappears from the world while it is on the truck, which is why load deletes gift(x) and unload re-creates it somewhere else.
dependent on how you defined each of these aspects, how you formulated the problem, the problem will be easier or will be harder to solve. And that's something very important to realize.(Lecturer, T1, restated in T2). Said originally about search-problem formulation in Part 3, and this Part is the strongest evidence for it in the whole course: section 8 is a formulation that is only slightly wrong and that makes the problem unsolvable.
Deck p.41 states both operations on one slide, in the middle of a list of reasons the formalism is convenient. They are the whole computational content of STRIPS.
Deck p.41 writes the middle line in the other order: "Add the list of positive effects to the state description and remove the list of negative effects: S' = (S / NEGATIVE-EFFECTS) ⋃ POSITIVE-EFFECTS". The exercise-session sheet writes it as s' = (s ∪ PositiveEffects) \ NegativeEffects. Use the exercise-session order, add first and then delete, because that is the version the exercise archetype is built on and the version the session solutions apply.
Does the order matter? Only when a literal appears in both the add list and the delete list, and for these schemas that happens only for degenerate instantiations. Checked exhaustively in code over the deck's two schemas and all four constants: the add and delete lists overlap exactly for Move(b,x,y) with x = y (for example Move(A,B,B), where Clear(B) is both added and deleted) and for MoveToTable(b,Table) (where On(b,Table) is both added and deleted). For every instantiation with b, x and y distinct the two lists are disjoint, so the two orders give identical successors. Those degenerate instantiations are the ones the deck discards on p.51 anyway.
s0 = {On(A,Table), On(B,Table), On(C,Table), Clear(A), Clear(B), Clear(C)}. Apply Move(B,Table,C) with the formula above and write s1 as a set, then compare with the right-hand panel of the slide.
ADD = {On(B,C), Clear(Table)}, DEL = {On(B,Table), Clear(C)}.
s1 = (s0 ∪ {On(B,C), Clear(Table)}) \ {On(B,Table), Clear(C)}
s1 = {On(A,Table), On(B,C), On(C,Table), Clear(A), Clear(B), Clear(Table)}
Six literals in, six literals out: two added, two removed. This matches the slide's right-hand panel line for line, and was reproduced by executing the schema in code. Why it matters: the state did not "become" the picture, it was edited. Everything untouched by the two lists is carried over unchanged, which is what makes the operation cheap and is also what makes an incomplete delete list so dangerous.
2023 sample theory exam, open question 3.2 (2 points), verbatim
In progression planning algorithms for STRIPS, how do you compute the (valid) successor states of a state? First explain (the relevant parts of) the input that determines a STRIPS planning problem, then explain how a state is represented, and finally how to compute the valid successor states using this information.
Part 1: the input. A STRIPS planning problem is given by three things (deck pp.11 and 43).
Part 2: how a state is represented. A state is the set of ground positive literals that are true in it, nothing more. There is no separate list of false facts: by the closed-world assumption, a literal is false in s exactly when it is not an element of s. Because the literals are ground and function-free and the number of constants is finite, the number of ground atoms is finite, so the state space is finite (deck p.57). A state s satisfies the goal g exactly when g ⊆ s; s may contain any number of extra literals.
Part 3: how to compute the valid successors. Three steps.
The set of valid successors of s is then { (s ∪ ADD(a)) \ DEL(a) | a is a ground action with PRECONDITIONS(a) ⊆ s }, one successor per applicable ground action. Progression planning repeats this from Init until it reaches a state s with g ⊆ s, and it keeps a set of visited states so that no state is expanded twice.
What earns the marks. The three input components with their qualifiers (ground, function-free, positive, closed-world for Init, partial and non-closed-world for the goal); the sentence "a state is the set of literals that are true, everything else is false"; the two set operations written explicitly, one for the applicability test and one for the successor; and the statement that there is one successor per applicable ground instantiation, not per schema. The answer box on the paper is one page for 2 points, so this is roughly the right length: a compact worked instantiation such as the one on p.29 fits and is worth including.
The 2023 paper asked this as open question 3.2 and structured it for you in three parts. Answer in those three parts, with those headings. The classic mistakes catalogued for A21 are: applying the effects in the wrong order (add the positive effects first, then delete the negative ones); testing only the preconditions the picture makes obvious instead of the whole list; and answering about schemas when the question is about ground instantiations. The lecturer also expects the pen-and-paper version of this: "It's also important that you can execute and simulate these algorithms in a pen and paper uh version on a small scale" (Lecturer, T4).
This is the best story in the Part and the one most likely to be turned into a question, because it is a formulation error rather than an algorithm error.
The state is s2 = {On(A,B), On(B,C), On(C,Table), Clear(A), Clear(Table)} and the plan is to move A and then B back to the table. Apply Move(A,B,Table) and write s3, then decide whether Move(B,C,Table) is applicable.
Move(A,B,Table) has preconditions {On(A,B), Clear(A), Clear(Table)}, all present, so it fires. ADD = {On(A,Table), Clear(B)}, DEL = {On(A,B), Clear(Table)}. So
s3 = {On(A,Table), On(B,C), On(C,Table), Clear(A), Clear(B)}
and Clear(Table) is gone. Move(B,C,Table) needs {On(B,C), Clear(B), Clear(Table)} and the last one is now missing, so it is not applicable. Verified by execution: in s3, with only the Move schema available, no ground action at all can put a block on the table. Why it matters: the table has become permanently full after a single block was placed on it, which is not what anybody intended, and nothing in the algorithm is wrong.
The slide shows s4 as a question mark. In one sentence, name the false assumption the representation encodes.
That the table has room for exactly one block. Clear(y) means "y has room for a block", and for a block that is a genuine one-slot property, but the table has unlimited room, so treating Clear(Table) like Clear(B) makes the table behave like a block. The lecture makes the point this way: the representation assumes a table large enough for all three blocks, yet allows each block to be put on it only once. Why it matters: the exercise-session sheet leads with exactly this ("A flawed (see Exercise 1) formalization"), so the fix is examinable material, not a curiosity.
The deck's fix is to split the schema into Move(b,x,y) and MoveToTable(b,x). Write the preconditions and effects of MoveToTable(b,x) yourself before looking at p.38.
MoveToTable(b,x): PRECONDITIONS On(b,x) ∧ Clear(b); EFFECTS On(b,Table) ∧ Clear(x) ∧ ¬On(b,x). Two things changed against Move(b,x,Table): the precondition Clear(Table) is dropped (the table always has room), and the negative effect ¬Clear(Table) is dropped (putting a block down never fills the table). Why it matters: the repair is "make the special constant a special case", and that is the transferable lesson. If a predicate means something different for one constant than for all the others, give that constant its own action.
Compare this Init with the exercise-session s0, which is {Clear(Table), On(A,Table), Clear(A), On(C,Table), On(B,C), Clear(B)}. One literal is present there and absent here. Which, and is the deck's Init now safe?
Clear(Table). The deck's Init omits it, so no Move(b,x,Table) can fire at the start, and MoveToTable is used instead. But the fix is not airtight: Move(b,Table,y) still has Clear(x) as a positive effect with x bound to Table, so the very first move off the table re-introduces Clear(Table) into the state. The session solutions say this in as many words ("But Move(b,Table,y) will reintroduce it. (Using OnTable(x) instead of On(x,Table) would help.)") and mark one successor in their A* trace with "(Reintroduces Clear(Table)!)". Verified by execution: from the deck's Init, all six first-level successors contain Clear(Table). Why it matters: this is a genuinely subtle point, and it is the kind of "here is a representation, what breaks" question the open format likes.
Exercise session 8, question 1, bullets 1 and 2 (verbatim)
The formulation above is flawed because moving a block onto the table removes Clear(Table), preventing further blocks being moved to the table. This can be fixed by introducing two new actions MoveToTable(b,x) and MoveFromTable(b,y) corresponding to moving b from x to the table, and moving b from the table to y respectively.
The two new actions.
Compare each with the instantiation of the old schema it replaces. Move(b,x,Table) had the extra precondition Clear(Table) and the extra negative effect ¬Clear(Table); MoveToTable drops both. Move(b,Table,y) had the extra positive effect Clear(Table); MoveFromTable drops it. In each case exactly one literal about the Table is removed, and that is the whole repair.
The revised initial state. Yes, revise it: drop Clear(Table). For the session's picture (C on the table, B on A, A on the table) the revised s0 is {On(A,Table), On(B,A), Clear(B), On(C,Table), Clear(C)}.
Why. The solutions give the reason in one line: "clear(Table) was removed since no longer needed. Prevents Move(b,x,Table) from having preconditions satisfied. But Move(b,Table,y) will reintroduce it. (Using OnTable(x) instead of On(x,Table) would help.)" So the deletion does two jobs: it makes the old table-filling instantiation of Move unusable, and it stops the literal being a lie about the world. The residual leak, Move(b,Table,y) re-adding it, is what a cleaner vocabulary with a separate OnTable predicate would remove for good.
What earns the marks. Writing both new schemas with their full precondition and effect lists; saying explicitly which literal each one drops relative to the old schema; and answering the second bullet with a yes plus the reason, not just a yes.
The gripper version of the blocks world replaces one Move with four actions and adds one new predicate. What is the predicate, and why does one move become two actions?
The new predicate is Grip-Empty, a zero-argument literal saying the hand is free. One move becomes two because the gripper makes the intermediate state, "block in hand", explicit: Unstack or Pick-up takes a block into the hand and deletes Grip-Empty, and Stack or Put-down releases it and restores Grip-Empty. Note also that this deck writes On-Table(A) as its own predicate rather than On(A,Table), which is exactly the vocabulary change the exercise-session solutions recommend as a cure for the Clear(Table) bug. Why it matters: the deck prints the four actions with "..." instead of their effects, and the lecturer talks the domain through without working it, so you will not be asked to execute it. You could be asked what changes when you add a gripper: the answer is "one more predicate and a finer decomposition of the same physical move".
Deck p.40 places STRIPS historically. It was proposed in 1971 by R. E. Fikes and N. J. Nilsson; since then the formalisms built on it have become both faster and more expressive. Named on the slide: ADL (Action Description Language, Pednault 1988), which allows open worlds, conditional effects and quantifiers; situation calculus (McCarthy and Hayes 1969, Reiter 2001), based on first-order logic and allowing rich representations; and action languages A, the fluent calculus and the event calculus.
we will not go into that. But be aware that this exists.(Lecturer, T10, on situation calculus). This is an explicit scope limit from the reference file's list of safe absence claims: situation calculus is mentioned and not taught. Know the name and the one-line description on p.40; do not try to learn the calculus.
Deck p.41 gives three reasons, and all three are the same reason: every question you need to ask about a state is a set-containment question on a set of literals.
| Question | Operation | Cost |
|---|---|---|
| Which actions can I take here? | PRECONDITIONS ⊆ S, once per ground action | Linear in the size of the precondition list |
| Where do I end up? | S' = (S ∪ POSITIVE-EFFECTS) \ NEGATIVE-EFFECTS | Linear in the size of the two effect lists |
| Am I done? | G ⊆ S | Linear in the size of the goal |
Deck p.42 adds the second reason, that despite the toy example the formalism "can already describe difficult and complex problems", and hands over to the search half of the lecture. The lecturer's summary is that STRIPS is nice because it is easy to represent planning problems, easy to calculate the applicable actions, easy to calculate the successor states, and easy to check the goal.
Constructed, in the sample paper's format (2023 theory Part 1, true or false)
In STRIPS, deciding whether an action is applicable in a state requires logical inference over the state description.
The slide annotates Init, Goal and Action with three phrases. Before reading them, say which component plays the role of the start node, which of the goal test, and which of the successor function in an ordinary search problem.
Init is "where to start from", Goal is "when to stop searching", Action is "how to generate the graph". In other words the planning problem is already a search problem, and the only new thing is that the successor function is given as data (schemas with preconditions and effects) rather than as code. Why it matters: this is the hinge on which every property from Parts 4 and 5 carries over unchanged. Note also the direction of the arrows in the diagram: they fan downward from the orange start node to the orange goal node, which is the picture p.73 will reverse.
Two directions are named: progression planning, forward state-based search from Init towards the goal, and regression planning, backward state-based search from the goal towards Init. The lecture is about progression, on the grounds that this is what most modern planning systems do. Regression gets one slide, p.73, and section 16 below.
Six bullets. Five of them are mechanical. One of them is where every design decision in the rest of this Part lives. Which, and what changes about it on p.66?
"Pick one of the successor states as the current state." That is the only free choice in the loop, and it is what a heuristic is for. Deck p.66 repeats this whole box with one word changed: "Pick one the most promising of the successor states as the current state". Everything from p.62 to p.72 is about how to compute "most promising". Why it matters: this is the same observation as in Part 4, where the frontier's ordering discipline is the only difference between breadth-first, depth-first and uniform-cost search.
Deck pp.45 to 56 walk the loop once on the toy problem. Start from s0 (p.45). Test the goal: g = {On(A,B), On(B,C)} is not a subset of s0, so no (p.46). Then compute the applicable actions.
With three blocks and the constant Table, how many ground instantiations does Move(b,x,y) have if b ranges over the blocks and x and y range over blocks plus Table? How many survive the filter b, x and y all distinct? And how many of those are applicable in s0?
3 × 4 × 4 = 48 raw instantiations; 18 survive the distinctness filter; 6 are applicable in s0, namely Move(b,Table,y) for the six ordered pairs of distinct blocks. All three numbers were computed by enumerating the instantiations in code. MoveToTable(b,x) similarly has 12 raw instantiations, 6 after dropping b = x and x = Table, and none of them is applicable in s0 because every block is already on the table. Why it matters: the number of ground actions grows polynomially in the number of constants and the arity, and this is the arithmetic the exercise session's counting sub-question is about.
Deck p.48 lists the six applicable actions and says "All these are applicable actions!". Deck pp.49 to 51 then raise the degenerate instantiations: Move(B,Table,B) passes its precondition test, and so does MoveTT(B,Table), the deck's abbreviation for MoveToTable. Deck p.51 prints all six of them, Move(A,Table,A), Move(B,Table,B), Move(C,Table,C), MoveTT(A,Table), MoveTT(B,Table), MoveTT(C,Table), under the line "These are the actions we will continue with". Read that slide as the discard list: the lecturer is explicit in the lecture that these instantiations are filtered out and removed from the search, and p.53 shows exactly six successors, all from the sensible list on p.48. Verified: each of those six degenerate ground actions really is applicable in s0, and none of them leaves the state unchanged, so filtering them is a deliberate modelling decision and not an automatic consequence of the definitions.
The picture changes from three blocks in a row to B on C with A beside them. Which literals of the state actually changed, and which of the six did not?
Changed: On(B,Table) and Clear(C) left, On(B,C) and Clear(Table) arrived. Unchanged and carried over: On(A,Table), On(C,Table), Clear(A), Clear(B). Why it matters: STRIPS actions are local edits. Everything not named in the two effect lists persists automatically, which is the representational trick that makes the formalism cheap. Naming that explicitly in an open answer is worth a mark.
Six successors are drawn. Explain the number 6 from the schema and the state, without counting the pictures.
Only Move(b,Table,y) can fire, because every block is on the table and every block is clear. Choose the block to move (3 ways) and the destination block (2 remaining ways), giving 3 × 2 = 6. MoveToTable cannot fire on a non-degenerate instantiation because no block is on another block. Why it matters: being able to derive the branching factor from the schema rather than from the drawing is what lets you do the same on an exam problem with no picture.
The deck picks the top right successor. It happens to be the one on an optimal plan. How many more expansions before the goal test succeeds, and what would you have to add to the algorithm to make that outcome reliable?
One. From that state, Move(A,Table,B) gives {On(A,B), On(B,C), On(C,Table), Clear(A), Clear(Table)}, which contains g, so the plan is <Move(B,Table,C), Move(A,Table,B)> of cost 2. Verified by executing the algorithm: 2 really is the optimal cost from s0. To make it reliable rather than lucky you need an ordering on the successors, which is A* with a heuristic (section 13). Why it matters: the lecture makes the same point, describing this run as the most optimistic case, in which the goal was reached by coincidence because the lucky successor happened to be picked.
Deck pp.57 and 59 answer the completeness question. "Is it guaranteed that progression planning will find a solution if one exists? Given that the state-space is finite (ground atoms, no function symbols, finite number of constants).. Yes! As long as we visit each state only once." And then p.59 adds the sting: "But it may have to explore the whole state-space!"
this is equivalent to the loop breaking that we added to the algorithms that we have seen before.(Lecturer, T10, on the requirement to visit each state only once). The visited-state set here is the same device as the redundant-path elimination of Part 4. Nothing new is being introduced, and saying so is exactly the cross-chapter synthesis the theory exam is looking for.
Count the boxes in the picture. Then count the reachable literal sets. The two numbers are not the same. Say why.
13 pictures. That is the number of physical configurations of three blocks (one three-tower in each of 6 orders, one two-tower plus a loose block in 6 ways, and all three flat), and it is what the slide draws.
20 literal sets. Computed by exhaustive forward search from the deck's Init with the filtered action set: Clear(Table) is itself a literal, and 7 of the 13 configurations are reachable both with it and without it, so 13 + 7 = 20.
Why it matters twice over. First, the algorithm's visited set works on literal sets, not on pictures, so a "repeat" that your eye sees is not necessarily a repeat the algorithm sees, and the search can be larger than the drawing suggests. Second, this is the Clear(Table) leak of section 8 showing up as a measurable cost: a redundant literal doubles part of your state space.
Deck p.61 draws the moral: "Even this simple example becomes challenging if we consider 100 boxes and 1000s of applicable actions of the form Move(b,x,y) in each state. Similar to search problems we can make use of heuristics that help progression planning pick the most promising states to investigate first."
Exercise session 8, question 2, bullet 3 (verbatim)
Trace the states when executing the plan (ignore road(x,y)): <move(A,D), load(D), move(D,C), move(C,B), unload(B)>
Each step was checked for applicability (preconditions ⊆ state) before applying s' = (s ∪ ADD) \ DEL. The road literals are carried unchanged through every state and are omitted here, as the question allows.
Goal test: g = {gift(B)} ⊆ s5, so the plan is a solution. Note what happens at load(D): gift(D) is deleted and loaded() is added, so between loading and unloading the gift is nowhere in the state, which is exactly how a STRIPS domain models "in transit" without adding a predicate for it. Note also that move both adds and deletes a truck literal, so the truck's position is always exactly one literal.
What earns the marks. Writing the full state after every action (not just the changed literal), saying explicitly that the road literals persist, and checking applicability before each step rather than assuming the given plan is legal.
Exercise session 8, question 1, bullet 4 (verbatim)
How many instantiations of each action exist for a world with n blocks? Estimate (bounds for) the number of states.
Instantiations (counting only the n blocks, abstracting away the special constant Table, as the solutions do):
These counts include the non-sensible instantiations; filtering them out is a separate step, as on deck p.51.
Number of states. The predicates give n2 ground On atoms and n ground Clear atoms, so every subset of those n2 + n atoms is a syntactically possible state: 2n2+n in total, which is 212 = 4096 for n = 3. That is a wild over-count, because almost no subset is a physically valid arrangement. The solutions bound the valid states by O(nn): assign each block to one of n groups (nn), multiply by at most n! for the order within a group, divide by exactly n! because the groups must be distinct, so the final count is below O(nn).
The take-away the solutions print in bold: the state space grows rapidly, the planning problem becomes increasingly complex to solve, and that is the motivation for heuristics. That sentence is the link from this section to the next one.
Budget 15 to 20 minutes. What the marker is looking for: applicability justified by naming the preconditions and pointing at the state, the successor written as a full set (not a picture and not a delta), the add-then-delete order used consistently, and degenerate instantiations either filtered with a stated reason or shown and discarded. The classic mistakes for this archetype are exactly those four, in reverse order of frequency.
In Part 5, g was a path cost in kilometres or euros. What is it here, and what does that imply about the step cost of an action?
g(s) is the number of actions needed to reach s from the initial state, which is accurate because you have actually taken them; h(s) is the estimated number of actions from s to a goal state. So the step cost of every action is 1 by default, and plan cost equals plan length. The exercise sheet states the assumption explicitly ("Assume cost=1 for each action"). Why it matters: if a question gives actions different costs, g becomes a sum of costs and "number of actions" stops being the right phrase; say which convention you are using.
The heuristic the deck uses in the trace is the last bullet of p.65: h(s) = the number of literals in the goal that are missing from s, written h(s) = |g \ s| in the exercise session. It costs one set difference to evaluate.
The goal is g = {On(A,B), On(B,C)}. Compute h = |g \ s| for all six successors yourself, then compare with the slide. Also compute h(s0).
All six values were computed by executing the set difference:
| Action | Resulting configuration | h = |g \ s| | f = g + h |
|---|---|---|---|
| Move(A,Table,B) | A on B, C loose | 1 | 2 |
| Move(B,Table,C) | B on C, A loose | 1 | 2 |
| Move(A,Table,C) | A on C, B loose | 2 | 3 |
| Move(B,Table,A) | B on A, C loose | 2 | 3 |
| Move(C,Table,A) | C on A, B loose | 2 | 3 |
| Move(C,Table,B) | C on B, A loose | 2 | 3 |
h(s0) = 2, because neither goal literal is present. The two h = 1 states are the two that already contain one of On(A,B) or On(B,C). Why it matters: h counts missing goal literals, not the size of the symmetric difference and not the number of blocks in the wrong place. Counting all differences between s and g is the classic A22 mistake.
Two states are tied on f = 2. The deck picks the left one. Which rule decides that, and what will happen to the other one?
No rule decides it: in the lecture the tie is broken arbitrarily, one of the two equal states simply being chosen. The other one stays on the frontier with f = 2 and will be picked next, because expanding the left one produces nothing cheaper than f = 3. In an exam answer, state your tie-break rule (the sample exercise exam asks for left-to-right or lexicographic order elsewhere) and then follow it consistently. Why it matters: an arbitrary tie-break is fine, an undeclared one is not, and a trace that silently swaps rules mid-way loses marks.
Deck pp.69 to 72 finish the run. Here is the same run reproduced by executing A* with a closed set, printing the frontier before every expansion. Ties are broken in favour of the smaller g and then by plan text, which reproduces the deck's choices.
Two remarks on reading the deck's version of this against the frontier above. The deck draws each state once, keeping the cheaper g when a state is reached again by a longer route: on p.69 the A-on-C state keeps g = 1 even though the expansion of the A-on-B state also reaches it at g = 2. And the deck stops as soon as the goal state is picked, not when it is generated, which is the correct A* stopping rule from Part 5.
Exercise session 8, question 1, bullet 3 (verbatim)
Perform A* for the initial and final state below. Assume cost=1 for each action. Use the heuristic h(s) = |g \ s| (number of literals in the goal which are missing from s). At each step, show the state chosen to expand, actions applied and resulting states with heuristic value.
Initial state: A on the table, B on A, C on the table. Goal = {On(C,Table), On(B,C), On(A,B), Clear(A)}. Actions: the revised set with Move, MoveToTable and MoveFromTable from bullet 1.
s0 = {On(A,Table), On(B,A), Clear(B), On(C,Table), Clear(C)}, and g \ s0 = {On(B,C), On(A,B), Clear(A)}, so h(s0) = 3 (On(C,Table) is already there). f(s0) = 0 + 3 = 3.
Expansion 1: expand s0. Five ground actions are applicable. Each successor with its h and f:
| Action | Resulting state | h | f |
|---|---|---|---|
| Move(B,A,C) | {On(A,Table), Clear(A), On(C,Table), On(B,C), Clear(B)} | 1 | 2 |
| MoveToTable(B,A) | {On(A,Table), Clear(A), On(B,Table), Clear(B), On(C,Table), Clear(C)} | 2 | 3 |
| MoveToTable(C,Table) | the initial state again (degenerate instantiation) | 3 | 4 |
| MoveFromTable(C,B) | {On(A,Table), On(B,A), On(C,B), Clear(C)} | 4 | 5 |
| Move(C,Table,B) | {On(A,Table), On(B,A), On(C,B), Clear(C), Clear(Table)} | 4 | 5 |
The last row is the one the solutions annotate "(Reintroduces Clear(Table)!)", because Move(b,Table,y) has Clear(x) as a positive effect with x bound to Table. The MoveToTable(C,Table) row is a degenerate instantiation (C is already on the table): the answer key shows it as the initial state again with h = 3, whereas applying (s ∪ ADD) \ DEL literally would delete On(C,Table), since that literal is in both lists. Either way it is not progress and the visited check throws it away. Filter such instantiations, and say that you are doing so.
Expansion 2: expand the f = 2 node, <Move(B,A,C)>. Its state is {On(A,Table), Clear(A), On(C,Table), On(B,C), Clear(B)}, g = 1, h = 1. Its successors:
| Action | Resulting state | h | f |
|---|---|---|---|
| MoveFromTable(A,B) | {On(C,Table), On(B,C), On(A,B), Clear(A)} | 0 | 2 |
| Move(A,Table,B) | {On(C,Table), On(B,C), On(A,B), Clear(A), Clear(Table)} | 0 | 2 |
| MoveToTable(A,Table) | degenerate, no progress | 1 | 3 |
| MoveToTable(B,C) | {On(A,Table), Clear(A), On(B,Table), Clear(B), On(C,Table), Clear(C)} | 2 | 4 |
| Move(B,C,A) | back to the initial state | 3 | 5 |
Expansion 3. The frontier minimum is f = 2, reached by <Move(B,A,C), MoveFromTable(A,B)> with h = 0. Popping it satisfies the goal test.
Solution. <Move(B,A,C), MoveFromTable(A,B)>, cost 2. (The variant <Move(B,A,C), Move(A,Table,B)> also has cost 2 and also satisfies the goal; it merely leaves the extra literal Clear(Table) in the final state, which the goal does not forbid.)
What earns the marks. The h value beside every generated state, the f value used to choose, the state chosen at each step written out, and the tie between the two cost-2 solutions handled explicitly rather than silently.
Budget 20 to 25 minutes. The named classic mistake is computing h as the total difference between s and g rather than "the number of goal literals missing from s". Two further habits that cost marks: not showing the frontier at each expansion (the sample exercise exam's search question says "write down their frontier at every step" in so many words), and forgetting that the step cost is 1 per action so that g is just the plan length. Drill the trace at viz-planning.html.
Deck p.64 asks the question directly: "So why is it different than the usual search problems?" In a grid you could define h with a relaxed distance metric such as the Manhattan distance, because the problem has a grid. A planning problem has no grid. It has a list of literals and a set of action schemas, and nothing else. So the heuristic has to be built out of the schemas themselves, and the slide's conclusion is the important sentence: "The action schemas provide valuable information that can be used to specify domain independent heuristic functions!"
each of these is specified irrespective of the domain, in contrast to the heuristics that we saw in informed search before.(Lecturer, T10, and the point is also printed on deck p.64). In Part 5 a heuristic had to be invented per problem (straight-line distance for maps, Manhattan for grids, misplaced tiles for the 8-puzzle). Here one definition works for every STRIPS domain, because it is defined on the schema syntax rather than on the domain's meaning.
An action has three parts: preconditions, positive effects, negative effects. Two of the four heuristics on this slide are relaxations that delete one of those parts. Which part does each delete, and why can you not also delete the positive effects?
Empty list of preconditions deletes the preconditions: h(s) is the number of actions needed to reach the goal if every action is always applicable. Empty list of negative effects deletes the delete lists: h(s) is the number of actions needed if literals are only ever added and never removed. You cannot delete the positive effects too, because then no action would achieve anything and nothing could ever reach the goal. The lecture states the constraint this way: a heuristic that uses all three parts is not a relaxation at all, because computing it would repeat the work the search does anyway, so it would not be a cheap estimate.
The other two items: planning graphs, described in the lecture as the most effective of the three and explicitly not covered, on the grounds that it would lead too far, and the simple example h(s) = the number of goal literals missing from s, which is the one used in the deck's own trace and in the exercise session. Why it matters: "which part of the action does this relaxation ignore" is a one-line question with a one-line answer, and it is exactly the kind of thing a fill-in box asks for.
Constructed, in the sample paper's format (2023 theory Part 1, true or false)
Unlike the heuristics used in informed search, the heuristics used for STRIPS progression planning are specified without reference to the particular domain.
Deck p.65 names the relaxation in one line ("Empty list of negative effects"). Exercise session 8 turns it into a full question with a proof, so this section follows the session, which is where the examinable detail lives.
the slides and the material for the exercise sessions uh are the main source of reference. So that's the basis of what you need to know uh for the evaluation.(Lecturer, T1, and the same claim is printed on the slides). Everything in this section beyond one bullet on p.65 comes from the exercise session. It counts.
The construction. Let Π be a planning problem with goal g. Let Π+ be the relaxed problem obtained by deleting every negative effect from every action. For a state s, h+(s) is the cost of an optimal plan for Π+ from s. For the blocks world, Move(b,x,y) keeps effects {On(b,y), Clear(x)} and loses {¬On(b,x), ¬Clear(y)}. For the logistics problem:
In the relaxed world nothing is ever taken away, so the truck accumulates positions: after move(D,C) the state contains both truck(D) and truck(C). That sounds absurd and it is the point. Because preconditions once established are never destroyed, the relaxed problem is much easier to solve, and the session sheet says exactly that: "Since preconditions once established are never deleted, it should be much less expensive to solve the relaxed problem."
Exercise session 8, question 3 (verbatim)
Let Π be a planning problem with goal g; Let Π+ be the relaxed problem obtained by neglecting all delete effects in Π; And, for a state s, let h+(s) denote the heuristic value obtained by optimally solving Π+.
(a) |g \ s| for the initial state is 1. The goal is the single literal {gift(B)}, and it is not present, so exactly one goal literal is missing.
(b) Why it is unsuitable here. Because the goal has only one literal, |g \ s| can only take the values 1 and 0. It is 1 for every non-goal state and 0 for a goal state. Verified by exhaustive forward search: the problem has 20 reachable states and the heuristic takes exactly the values {0, 1} over all of them. A heuristic with the same value everywhere gives A* no information at all, so the search degenerates to uniform-cost search. The solutions put it as: "The heuristic will thus have value 1 for all non-goal states, rendering it useless." The general lesson: |g \ s| is only informative when the goal is a conjunction of many literals that get achieved gradually, as in the blocks world.
(c) The relaxed actions are the three shown above: keep Truck(y), Loaded(), Gift(x), drop all three negations.
(d) h+({truck(D), gift(D)}) = 4. Computed by optimal breadth-first search in the relaxed problem: the cheapest relaxed plan is 4 actions, for instance <move(D,C), move(C,B), load(D), unload(B)>, and no 3-action relaxed plan exists. The reason is easy to see and worth writing down: unload(B) needs both truck(B) and loaded(). Getting truck(B) from D takes two moves whichever way round the cycle you go, loaded() takes one load(D), and then the unload(B) itself makes 4. The session's tree draws the relaxed states growing by one literal per layer with cost 1, 2, 3, 4 and h+(s) = 4 at the bottom.
A detail the session does not spell out but which shows what the relaxation buys: from this state the true optimal cost is also 4, so h+ is exact here. From the real initial state {truck(A), gift(D)} it is not: h+ = 4 while the true optimum is 5, because the relaxed truck can be at A and at D at the same time and so never has to drive back. Both numbers were computed. That gap, always in the same direction, is admissibility.
(e) h+ is admissible. Proof from the solutions. Let π(s) be an optimal plan from s in the original problem Π. Any plan that solves Π also solves Π+, because removing delete effects can only make preconditions easier to satisfy, never harder. So π(s) is a solution of Π+, and the optimal solution π+(s) of Π+ is at least as good: h+(s) = cost(π+(s,g)) ≤ cost(π(s,g)) = h*(s). And h+ ≥ 0. So 0 ≤ h+(n) ≤ h*(n) for every n, which is the Part 5 definition of admissible.
h+ is consistent. Proof from the solutions. In Π, applying an action a with cost c at state n takes you to p. Let π+(p) be an optimal relaxed plan from p. Then the concatenation <a, π+(p)> is a solution of Π+ from n, so the optimal one is at least as good: cost(π+(n,g)) ≤ c + cost(π+(p,g)), that is h+(n) ≤ c + h+(p). Together with h+(goal) = 0 that is the Part 5 definition of consistency. Note the shape of both proofs: they never look inside the domain, they only use "any plan for the hard problem is a plan for the easy one".
(f) h(s) = |g \ s| is not admissible, hence not consistent. The solutions give the counterexample from the blocks-world question. Take s = {On(A,Table), On(B,A), On(C,B), Clear(C)}, the tower C on B on A, with g = {On(C,Table), On(B,C), On(A,B), Clear(A)}. All four goal literals are missing, so h(s) = 4. But three moves suffice: <MoveToTable(C,B), Move(B,A,C), MoveFromTable(A,B)>. Verified: that plan reaches the goal, and breadth-first search confirms the true optimal cost from this state is exactly 3. So h(s) = 4 > 3 = h*(s) and the heuristic overestimates. The reason in one line, as the solutions put it: "A single action may satisfy more than one goal fact", and h counts facts, not actions. Since consistency implies admissibility (Part 5), failing admissibility rules out consistency automatically.
(g) The trade-off. h+ is admissible and consistent, so A* with it returns optimal plans, but computing it means solving an optimisation problem at every node, which is expensive (in general still NP-hard, which is why real planners use approximations such as hmax or hadd or the planning graph, the item deck p.65 lists and does not teach). h = |g \ s| costs a single set difference, "is quick to evaluate and will still lead to less paths being explored", but "the plan found may not be optimal", and in practice a less-than-optimal plan is often an acceptable price for making the problem solvable at all.
What earns the marks. For the admissibility and consistency parts, the two-line argument, not the verdict: "any plan for Π is a plan for Π+, so the optimal relaxed plan is no more expensive" and "<a, π+(p)> is a relaxed plan from n". For the |g \ s| part, an explicit counterexample state with its h and its h*, since a claim of non-admissibility without a witness is worth little.
The catalogued classic mistake is stating the properties the wrong way round: h+ is admissible and consistent but expensive; |g \ s| is cheap but can be badly uninformative, and is not admissible at all. The second catalogued point is the "why is |g \ s| unsuitable here" sub-question: the answer is about the shape of the goal (a single literal, so the heuristic is constant), not about the domain being hard. Remember the one-way implication from Part 5: "And consistency implies admissibility." (Lecturer, T4). So if you have shown a heuristic is not admissible, you have shown it is not consistent, and you should say that rather than argue it again.
Put the six bullets of p.73 next to the six bullets of p.44 and name, for each, the progression step it mirrors. Which one is not a simple mirror?
Start from the goal mirrors start from the initial state; check whether the initial state satisfies the current goal mirrors check whether the current state satisfies the goal; compute predecessor states mirrors compute successor states; pick one predecessor as the current goal mirrors pick one successor as the current state; repeat mirrors repeat. The step that is not a simple mirror is "compute the relevant and consistent actions": going forwards, an action qualifies if its preconditions are present, one test; going backwards it must both contribute something the current goal needs (relevant) and not destroy something else the goal needs (consistent), two tests. Why it matters: that extra condition is the whole reason regression is fiddlier, and it is the one-line answer if you are asked how the two directions differ.
we won't move uh into detail here because um it's not that frequently used.(Lecturer, T10, on regression planning, deck p.73). This is a licensed absence claim from the reference file. Know the six bullets and the direction; do not expect to trace it. Deck p.76 repeats the limit in the conclusion, listing regression as "backward, not discussed".
Deck p.74 introduces PDDL, the Planning Domain Definition Language: a formal language for specifying planning problems, with a syntax similar to a programming language, that includes STRIPS and ADL and many more features. The reason it exists is on the same slide and is the reason worth remembering: it "provides the ground for performing a direct comparison between planning techniques and evaluating against classes of problems". A shared input language turns planning into a benchmark discipline.
Deck p.75 is the consequence: the International Planning Competition, running from 1998 to today, with the systems SAT Plan, TL Plan, FF, BlackBox, SHOP2 and TALPlanner. The lecturer singles out FF (Fast Forward) as the system that made the largest jump in what progression planning could solve and says it is still good and still shipped inside planning toolkits. Deck p.76 closes the Part: STRIPS planning is a generic formalism for representing planning problems plus generic search procedures for finding a plan, progression forward and regression backward, with applications in space, flight and robotics.
The fill-in format asks for a term or a short answer, and the answer-box size tells you the expected length ("the boxes also give an indication of the expected length given a regular written font size", Lecturer, T9). The obvious candidates from these two slides are the expansions of the acronyms and one clause of purpose: PDDL is the Planning Domain Definition Language, ADL is the Action Description Language and generalises STRIPS with open worlds, conditional effects and quantifiers, and STRIPS is the Stanford Research Institute Problem Solver, Fikes and Nilsson, 1971. Learn the four expansions; they cost nothing and each is a whole fill-in blank.
| Term | Precise definition | Plain paraphrase | Exam phrasing |
|---|---|---|---|
| STRIPS | Stanford Research Institute Problem Solver (Fikes and Nilsson, 1971). Originally a planner, now the name of the formal language for describing planning problems: Init, Goal and a set of action schemas. | The standard way of writing a planning problem down. | "In progression planning algorithms for STRIPS..." (2023 open 3.2) |
| Ground, function-free, positive literal | A predicate applied to constants only: no variables (ground), no function symbols in the arguments (function-free), and not negated (positive). Example On(B,Table). | A definite fact about named things, with no formulas inside it. | "described using first-order logic literals: ground, function-free, positive" (deck p.25) |
| Closed-world assumption (CWA) | Any literal not listed in the description of a state is assumed to be false. Applies to states, not to goals. | If it is not written down, it is not true. | "Any literal not mentioned in the description of the state are assumed to be false!" (deck p.23) |
| State | The set of ground, function-free, positive literals true at that moment. Completely specified, under the CWA. Finitely many exist because there are finitely many constants and no function symbols. | A list of everything currently true. | "explain how a state is represented" (2023 open 3.2) |
| Goal, and goal satisfaction | A set of ground, function-free, positive literals, partially specified with no CWA. A state s satisfies goal g exactly when g ⊆ s; s may contain further literals. | A checklist, not a photograph. Extra facts are allowed. | "A state s satisfies goal g if it contains all literals in g (more literals may be in s)" (deck p.24) |
| Action schema, and its ground instantiations | A named template with variables, carrying a precondition list and an effect list, for example Move(b,x,y). A ground instantiation replaces every variable by a constant, for example Move(B,Table,C). Search operates on the instantiations. | One rule, many concrete moves. | "Action( Move(b,x,y), PRECONDITIONS: ... EFFECTS: ... )" (deck p.38) |
| Preconditions | The literals that must be in the state for the action to be applicable. For Move(b,x,y): On(b,x), Clear(b), Clear(y). | What has to be true before you can do it. | "literals denoting what needs to be in the state for the action to be applicable" (deck p.27) |
| Positive effects (add list) and negative effects (delete list) | The effect literals, split by sign. Positive effects are added to the state; negated effect literals name the literals to be removed. For Move(b,x,y): add On(b,y), Clear(x); delete On(b,x), Clear(y). | What appears and what disappears. | "the list of positive effects... the list of negative effects" (deck p.41) |
| Applicable action | A ground action a is applicable in s exactly when PRECONDITIONS(a) ⊆ s. One subset test; no inference. | You can do it here because everything it needs is already true. | "Check whether the list of preconditions is a subset of the state description: PRECONDITIONS ⊆ S" (deck p.41) |
| Successor state | s' = (s ∪ ADD(a)) \ DEL(a), for an applicable ground action a. Everything not named in the two lists is carried over unchanged. Deck p.41 writes the same operation in the other order; the two agree whenever ADD and DEL are disjoint, which holds for every non-degenerate instantiation. | Copy the state, add the new facts, cross out the dead ones. | "how to compute the valid successor states using this information" (2023 open 3.2) |
| Progression planning, regression planning | Progression: forward state-based search from Init, generating successors until a state satisfies g. Regression: backward state-based search from g, generating predecessors using the relevant and consistent actions until Init satisfies the current goal. | Forwards from the start, or backwards from the finish. | "Progression planning: forward state-based search. Regression planning: backward state-based search" (deck p.43) |
| Domain-independent heuristic | A heuristic defined on the action schemas themselves rather than on the meaning of the domain, so that one definition works for every STRIPS problem. Deck p.65 lists four: ignore preconditions, ignore negative effects, planning graphs, and missing goal literals. | A rule for guessing the distance that never looks at what the problem is about. | "specify domain independent heuristic functions" (deck p.64) |
| Delete relaxation, h+ | Π+ is Π with every negative effect deleted; h+(s) is the cost of an optimal plan for Π+ from s. Admissible and consistent, and expensive to compute. | Pretend nothing ever becomes false, solve that, and use the answer as your estimate. | "What can be said about the admissibility and consistency of h+?" (exercise session 8, question 3) |
| h(s) = |g \ s| | The number of goal literals missing from s. One set difference to evaluate. Not admissible, because one action can achieve several goal literals at once, and therefore not consistent. | Count the ticks still missing from the checklist. | "the heuristic h(s) = |g \ s| (number of literals in the goal which are missing from s)" (exercise session 8, question 1) |
| PDDL | Planning Domain Definition Language: a formal input language including STRIPS and ADL, with a programming-language-like syntax, which makes direct comparison of planning techniques on shared benchmarks possible. Used by the International Planning Competition since 1998. | The standard file format that lets everyone's planner read everyone's problem. | "Planning Domain Definition Language (PDDL)" (deck pp.74 and 75) |
Constructed, in the sample paper's format (2023 theory Part 2, fill-in)
In STRIPS, an action is applicable in a state s when its list of ____________ is a ____________ of s, and the successor state is then obtained by adding the ____________ to s and removing the ____________ from s. The initial state is completely specified under a ____________ assumption, whereas the goal is only ____________ specified.
preconditions / subset / positive effects (add list) / negative effects (delete list) / closed-world / partially.
Full-credit variants: "contained in s" for the second blank; "effects that are not negated" for the third; "literals that appear negated in the effects" for the fourth. What would not score: writing "effects" for the third and fourth blanks without the sign, since the whole point of the pair is that the two halves are treated differently. Remember the format note: fill-in questions "can also be short answers that you need to provide" (Lecturer, T9), and the size of the printed box tells you how much is expected.
Index: index.html · Previous: Part 10, SAT Solving and Beyond · Next: Part 12, Version Spaces · Drill: viz-planning.html · Search by question: question-index.html