Fundamentals of Artificial Intelligence, KU Leuven, Prof. dr. Mathias Verbeke, 2025-26
How a problem is turned into a state space, and why that choice decides how hard it is.
A planning or goal-based agent (p.3) makes decisions by evaluating future action sequences. The slide lists what that requires, and each item is a commitment you have to pay for:
Pages 5 and 6 contrast the two agents on the same Pac-Man maze. Example 1 (p.5) is "Move to the nearest dot and eat it": a reflex rule, no model, instant decisions, and it stalls once no dot is in view while the score keeps decaying. Example 2 (p.6) is "Precompute optimal plan and execute it": the agent stands still for a while, then executes and scores the maximum.
That pause is not a defect, it is the first quantity this Part names. The online and offline naming is printed on p.9, inside the fifth ingredient: "(search costs, offline costs and) the execution costs (path costs, online costs)". A text search of the deck finds the words online and offline on p.9 and nowhere else. Page 10 then adds the definition of search cost ("Time and storage requirements to find a solution (computational)") and the sum, total costs = search costs + path costs. So: path cost is what executing the solution costs, search cost is what finding it costs. The reflex agent has zero search cost and a terrible path cost. The planner inverts that. Every algorithm in Part 4 and Part 5 is a different position on that trade.
Page 8 states the frame: formulate the problem as a state space and the goal as a particular condition on states, then search for an action sequence that gets you from the initial state to a state satisfying that condition. Page 9 lists what you must supply. The lecturer restates the same list at the start of the second session, calling the fifth optional.
| Ingredient | What the slide says | What that commits you to |
|---|---|---|
| States | "represents the world in an unambiguous way (important: only the relevant aspects → abstraction)" | Two different world situations that your search must distinguish have to get different state descriptions; two that it need not distinguish should get the same one. This is the whole design problem. |
| Actions | "define the actions you can execute and change the world state, this can be a function of the states" | Which actions are available may depend on the state. In practice you write each action as a rule with a guard, not as a list of moves. |
| Initial state | "what is the initial state, the starting point" | One state, or in the sensorless case (p.27) a set of them. |
| Goal formulation | "define which world states have desired properties, which ones are the solutions" | A test, applicable to any state. It may accept many states, as with the water jugs (2,y) on p.21. |
| Search costs (OPTIONAL) | "(search costs, offline costs and) the execution costs (path costs, online costs)" | Only needed when you want an optimal solution rather than any solution. 8-queens (p.19) sets path costs to 0 for exactly this reason. |
Printed in the corner of p.9, next to the ingredient list: "Problem formulation has impact on the difficulty of the problem and solution method." That single line is what the rest of the deck exists to demonstrate.
"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)
He says it at the ingredient slide and again a week later when reintroducing the five concepts. Every example from p.13 onwards is a demonstration of it, and the 8-queens pair on p.20 is the demonstration with a number attached.
Exercise session 1 (Representing Search Problems), exercise 2: Towers of Hanoi, assignment sheet verbatim
The Towers of Hanoi is a famous problem for studying recursion in computer science and recurrence equations in discrete mathematics. We start with N discs of varying sizes on a pin (stacked in order according to size), and two empty pins. We are allowed to move a disc from one pin to another, but we are never allowed to move a larger disc on top of a smaller disc. The goal is to move all the discs to the rightmost pin (see figure).
This is archetype A1 in its purest form: the five bullets are the five ingredients of p.9, asked one at a time. Write your own answer before opening the model answer.
State representation. "We have three pins. Each pin is represented by a list with the discs that it contains", written (L1, L2, L3). Discs are named 1 to N by increasing size and each list is ordered smallest first, so the list is the stack.
Size of the state space. kn for n discs and k pins. The solution deck derives it as a tree in which every disc chooses one of the k pins. For the four-disc, three-pin figure on the sheet that is 34 = 81. Checked by enumeration here: all 81 disc-to-pin assignments give a legal configuration, because the no-larger-on-smaller rule forces the order inside each pin.
Start state. ([1,2,3,4], [ ], [ ]) for the four-disc instance, in general all N discs on the first pin and the other two empty.
Legal actions. "Discs can be moved from one pin to another. Lists need to be considered to be a stack, so you can only remove discs from the front of the list", that is pop and push, "BUT: pushed value must be smaller than head of stack". Written as one schema with a guard, in the p.22 style: move(i,j) takes (..., Li = d:R, ..., Lj, ...) to (..., R, ..., d:Lj, ...) if Lj is empty or d is smaller than the head of Lj.
Goal test. The state equals ([ ], [ ], [1,2,3,4]), in general all discs on the rightmost pin.
What earns the marks: five labelled items in the order the sheet asks them, the size given as a formula in n and k rather than a count, and the legality condition written as a guard on one move schema rather than as a paragraph of prose or a list of concrete moves. Note that the solution deck asks the same five in a different order (goal test before actions); answer in whatever order the sheet in front of you uses.
Constructed, in the sample paper's format (theory MC, true/false)
For the Towers of Hanoi with n discs and k pins, the size of the state space is kn, because a state is fixed by saying which pin each disc sits on.
Page 10 adds the terms the algorithm chapters will use without re-explaining them. Four of them are easy to blur together, so read them as a chain:
g over paths, "usually the sum of the costs of the actions along the path". A solution is an action sequence reaching a goal state; an optimal solution is one of least cost."Usually the sum" is worth pausing on. Additivity is an assumption, not a definition, and g being additive is what makes uniform-cost search and A* work at all in Part 4 and Part 5.
The heading on p.11 is the claim: a search problem is a model of the world, deliberately smaller than the world. Page 12 makes it concrete with travel in Romania: state space = cities; initial state = Arad; actions = go to adjacent city; transition model = reach adjacent city; goal test = s = Bucharest?; action cost = road distance from s to s'.
Notice what a Romanian road is not, in this model: it has no width, no traffic, no direction of travel, no fuel. The abstraction survives because none of those facts changes the answer to the question asked. Change the question (shortest time in rush hour) and the abstraction breaks, because the cost function would have to read facts the state does not carry. Abstraction is always relative to the query.
Constructed, in the sample paper's format (theory MC, true/false)
In the travel-in-Romania formulation on p.12, the action cost (the road distance from s to s') is part of the transition model.
Read the ingredient list on p.13 as a set of choices rather than facts:
The state-space size. There are 9 squares and 9 things to place (eight tiles plus the blank), so 9! = 362,880 configurations. The slide corrects itself in the same breath: "or actually 9!/2 because from any given state you can only reach half of the states", that is 181,440.
State the property that produces the halving. (a) Why is the reachable set 9!/2 = 181,440 rather than 9! = 362,880? (b) Does that change how you write the goal test?
(a) Sliding the blank one square does two things at once: it transposes the blank with one tile, which flips the parity of the permutation (whether the number of pairwise swaps needed to build the arrangement is even or odd), and it moves the blank to an adjacent square, which flips the parity of (row + column) of the blank. The sum of those two parities is therefore unchanged by every legal move, so it is an invariant. The 362,880 configurations split into two classes of 181,440 with no move between them. Reachability from the start state on p.13 was confirmed by breadth-first enumeration: exactly 181,440 states, all with the same invariant value.
(b) No. The goal test still compares the state description against the goal configuration. What the halving means is that for a randomly chosen pair of configurations there is a 50 percent chance that no solution exists at all, which is a fact about the problem instance, not about the test.
Why it matters: state-space size questions are graded on the reasoning, and "9!" is the answer that ignores the transition model. The size of a state space is a property of the states and the actions together.
This tree is drawn for a different starting configuration from the one on p.13: its root is 2 8 3 / 1 6 4 / 7 _ 5, with the blank in the bottom middle. Two things about it are structural rather than decorative.
First, the tree is implicit. Nobody stores it. The algorithm generates a node only when it expands its parent, using the transition model. This is why the branching factor (how many successors a node has) and the depth, not the drawing, are what cost you.
Second, one node is deliberately left empty: the highlighted circle at depth 2.
Complete the half-described diagram. Which configuration belongs in the circled node, and why has the slide left it blank?
It is the root itself, 2 8 3 / 1 6 4 / 7 _ 5. The circled node is the fourth child (blank moved down) of the middle depth-1 node (blank moved up). Up then down returns you to where you started. Verified by generating the successors: the four children of 2 8 3 / 1 _ 4 / 7 6 5 are the three drawn configurations plus the root.
It is left blank because it is a repeated state. Drawing it would be honest but useless: a tree search that expands it will regenerate the whole subtree it has already seen, and can do so forever.
Why it matters: this empty circle is the first appearance in the course of the tree-versus-graph problem, which p.24 makes unavoidable and Part 4 solves.
Pages 15 to 17 are the deck's cleanest demonstration that the search state is not the world state. Read them in two stages, because the maze changes between them.
Stage one, pp.15 and 16. One maze (a wide corridor layout with dots along the corridors), one set of actions (moving east, west, north, south), one cost model (each step costs 1 unit, printed on both slides), and two different questions. Path finding (p.15) takes the state to be "the possible (x,y) positions in the grid" and the goal test to be "is Pac-man on the desired position (x',y')". Eat all dots (p.16) takes the state to be "position {(x,y) of Pac-man + one boolean per possible dot position}" and the goal test to be "all booleans false". Nothing about the world changed. Only the question did, and the state description had to grow to answer it.
Stage two, p.17. The lecturer introduces this slide as a refinement of the previous problem, and it comes with its own, different maze: a single open room whose 30 dot positions sit in a 5 by 6 layout, plus a walled corridor down the right-hand side holding the two ghosts. That geometry is what makes the printed counts come out: 120 agent positions, food count 30, 12 ghost positions in the corridor, 4 facings. Note also that p.17 lists only those four components and the three counting questions; unlike pp.15 and 16 it prints no path-cost line, so do not carry the unit step cost over to it.
Each factor on p.17 comes from one component of that maze. 120 agent positions (the lecturer counts the grid as 12 by 10). Food at 30 positions, each present or absent independently, hence 230 = 1,073,741,824. Two ghosts on 12 corridor cells each, hence 122 = 144. Four facings. The slide then answers its own three questions:
| Question on p.17 | State that answers it | Count |
|---|---|---|
| World states? | agent position, dot booleans, two ghost positions, agent facing | 120 × 230 × 122 × 4 = 74,217,034,874,880 |
| Search states for pathing? | the agent position alone | 120 |
| Search states for eat-all-dots? | agent position plus the dot booleans | 120 × 230 = 128,849,018,880 |
The two search-state rows are the p.15 and p.16 formulations re-counted on the p.17 maze. That is the point of the refinement: the same two questions, now with numbers attached, against a world state that is bigger than either of them.
Predict before revealing. By what exact factor is the eat-all-dots search space smaller than the world-state count, and which components of the world state did that factor consist of? Then say what licensed dropping them.
Factor 122 × 4 = 576, that is the two ghost positions and Pac-Man's facing direction. (74,217,034,874,880 ÷ 128,849,018,880 = 576 exactly.)
They can be dropped because in the eat-all-dots problem as formulated on p.16 and counted on p.17, neither the goal test (all dot booleans false) nor the transition model (movement is constrained by walls only) reads them. A component of the world belongs in the state only if the transition model or the goal test consults it. In this particular maze the ghosts are behind a wall, so they cannot even interfere.
Why it matters: this is the test to apply in an exam. Do not ask "is this fact about the world true", ask "does any of my five ingredients read it". Page 18 is the same test run in reverse: once the goal becomes "eat all dots while keeping the ghosts perma-scared", the state space has to grow back to (agent position, dot booleans, power pellet booleans, remaining scared time), because now the goal test does read the scared timer.
Constructed, in the sample paper's format (theory MC, true/false)
In the eat-all-dots problem counted on p.17, the search state has to record Pac-Man's facing direction, because the facing determines which moves are available next.
Two smaller points that are easy to skim past. The environment footer on p.17 changes to dynamic and multi-agent, so this slide is formally outside the cell of the Part 2 table where classical search lives, while pp.15 and 16 are still inside it. And the pathing answer is 120, not 120 minus the dots: the position alone is the state, so the food on the screen is simply not in the model, even though it is plainly in the picture.
Page 19 gives the naive formulation: states are any arrangement of 0 to 8 queens on the board; the initial state is the empty board; the action is "add a queen to an empty field on the board"; the goal test is "8 queens on the board such that no queen attacks another"; path costs are 0, because only the final configuration matters.
Every ingredient there is defensible in isolation. Together they are a disaster, and p.20 says why.
Naive. "State space: 64 × 63 × ... ~ 1014 possible states." The lecturer derived that live in T2: 64 squares for the first queen, 63 for the second, and so on. The product 64 × 63 × ... × 57 is 178,462,987,637,760, that is 1.78 × 1014.
Worth seeing clearly: that product counts ordered placements. The number of distinct 8-queen boards is C(64,8) = 4,426,165,368, where C(64,8) is the binomial coefficient, the number of ways to choose 8 squares out of 64 without regard to order, and 4,426,165,368 × 8! = 178,462,987,637,760 exactly. So the naive successor function reaches each board 8! = 40,320 separate ways. Part of the 1014 is not information, it is the same board arrived at in a different order, which is the repeated-state problem of p.14 at industrial scale.
Better. "States: any arrangement of n queens, one per collumn in the leftmost collumn so that no queen attacks another one. Successor function: add a queen to a square in the leftmost empty collumn. State space: 2057."
Two separate changes are bundled in that sentence, and it is worth separating them because an exam answer that names only one is half an answer:
Predict the missing number. Suppose you apply only the first change: a state is a placement of one queen in each of the leftmost k columns, k = 0 to 8, with no requirement that they avoid attacking each other. How many states is that, and what does the comparison tell you about which change does the work?
Each of the k filled columns has 8 choices of row, so the count is 80 + 81 + ... + 88 = 19,173,961, about 1.9 × 107.
So the column restriction alone takes you from 1.78 × 1014 to 1.92 × 107, roughly seven orders of magnitude, and enforcing non-attacking on every intermediate state takes you the remaining four, from 1.92 × 107 to 2,057. Both changes carry weight, and the second is what turns a search into something a person can do by hand. The figure 2057 was reproduced here by direct enumeration of all non-attacking column-wise partial placements, counting the empty board.
Why it matters: the exam-usable formulation of the lesson is that a constraint checked at the goal costs you the whole space below the violation; the same constraint checked at generation time costs nothing. That is also the idea CSPs in Part 6 generalise.
Constructed, in the sample paper's format (theory MC, true/false)
In the improved 8-queens formulation on p.20, the drop from about 1014 states to 2057 is produced by the restriction to one queen per column, filled from the left.
The exercise session 1 sheet asks, in these words, "What is the size of the state space?" for the Towers of Hanoi, and answers it with a formula, kn for n discs and k pins, not with a count. The 8-queens pair here is the same skill with a comparison attached: quote the size, and say which modelling choice produced it.
Classic mistake: giving a raw count with no formula, or counting ordered constructions when the question asks for distinct states (or the reverse). Write the product, name what each factor ranges over, then evaluate.
Page 21 states the puzzle: a 4-gallon jug, a 3-gallon jug, an unlimited pump, the ground to pour on, no measuring marks. Get exactly 2 gallons into the 4-gallon jug. The formulation is three lines:
The goal is written (2,y) with y left free. That is the goal formulation doing its job: it accepts any of the four states whose first component is 2, because what is in the small jug is not part of what was asked. Writing a single fully ground goal state instead would be a modelling error.
Note also what the state does not record: how the water got there. The state is (x,y) and nothing else, which is exactly the atomic representation from Part 2.
This slide is the template for exam archetype A1. Every rule has the same three parts, and you should write yours the same way:
(x,y) → (4,y),if x < 4.There are 8 rules for a state space of 20 syntactic states (x from 0 to 4, y from 0 to 3). Two of them, the "fill A from B" pair, need arithmetic in the schema because the amount transferred depends on the state: Fill 4 from 3-gal jug (x,y) → (4, y - (4 - x)) if 0 < x+y ≥ 4 and y > 0. The quantity 4 - x is the headroom in the big jug, and y - (4 - x) is what is left in the small one after topping the big one up.
Name the trap in this setup. Four of the eight rules can fire in states where they change nothing, producing a transition from a state to itself. Find them, and say which conjunct is missing from each guard.
Checked exhaustively over all 20 states, there are 14 such (rule, state) pairs across exactly four rules:
0 < x+y ≤ 4 and y ≥ 0. The second conjunct is true in every state, so nothing forbids y = 0: at (1,0), (2,0), (3,0), (4,0) the rule returns the same state. Missing: y > 0.0 < x+y ≤ 3 and x ≥ 0. Same shape: at (0,1), (0,2), (0,3) it returns the same state. Missing: x > 0.0 < x+y ≥ 4 and y > 0. Nothing requires the big jug to have room, so at (4,1), (4,2), (4,3) it computes (4, y - 0) = (4,y). Missing: x < 4.0 < x+y ≥ 3 and x > 0. Nothing requires the small jug to have room, so at (1,3), (2,3), (3,3), (4,3) it computes (x - 0, 3) = (x,3). Missing: y < 3.Why it matters: a self-transition is the smallest possible loop, and a tree search will follow it forever. Guards are where a state representation is actually made correct, and they are where marks are lost. Note also the redundant 0 < in "0 < x+y ≥ 4": the effective guard is the second inequality.
Page 23 shows one path through the space: (0,0) → fill 3 → (0,3) → empty 3 in 4 → (3,0) → fill 3 → (3,3) → fill 4 from 3 → (4,2) → empty 4 → (0,2) → empty 3 in 4 → (2,0). Each of those six steps was re-derived here from the printed rules and matches exactly.
This is the result of a search, not the search. The extracted text of p.23 consists of the slide title alone, and the graphic carries seven state labels and six action labels: a path, with no algorithm attached. Filling that gap is what Part 4 does.
Fill the blank cell of the trace. The step (3,3) → (4,2) is labelled "fill 4 from 3". Instantiate the rule and say where the missing gallon went. Then: is this six-action path optimal?
Fill 4 from 3-gal jug: (x,y) → (4, y - (4 - x)) with x = 3, y = 3. Headroom in the big jug is 4 - 3 = 1, so the result is (4, 3 - 1) = (4,2). The gallon was not spilled: it moved from the small jug to the big one. Total water is conserved by this rule, 6 gallons before and after, which is a useful sanity check on any pouring rule you write.
Yes, six actions is optimal. Breadth-first search from (0,0) over the eight printed rules first reaches a state with x = 2 at depth 6 (it finds (2,3) via fill 4, fill 3 from 4, empty 3, empty 4 in 3, fill 4, fill 3 from 4). Since breadth-first search with uniform step costs reaches states in order of depth, no shorter solution exists.
Why it matters: the "0 < x+y" style guards look intimidating, but instantiating one rule with concrete numbers takes ten seconds and is the fastest way to check your own transition model in an exam.
Page 24 adds one green branch to the same picture and a heading in capitals: LOOPS! From (0,3) the rule "empty 3" returns you to (0,0), from which "fill 3" returns you to (0,3), and so on without limit. The slide then asks the question the whole deck has been building to: "Should we search a graph or a tree?"
Name the trap and the fix. Exactly what goes wrong if a search algorithm treats this space as a tree, and what does the repair cost?
A tree search never asks whether it has seen a state before, so the cycle (0,0) → (0,3) → (0,0) is re-expanded at every even depth. The frontier grows without bound while no new state is ever discovered. Depth-first search does not terminate at all; breadth-first search terminates only because a goal happens to sit at finite depth, and it wastes exponentially many nodes on repeats before getting there. Concretely, the water-jug space has only 14 states reachable from (0,0) out of the 20 syntactically writable pairs, and yet its search tree is infinite.
The fix is to search the graph: keep the set of states already visited (or already visited along the current path) and refuse to expand a repeat. The cost is bookkeeping, memory proportional to the number of visited states plus a lookup on every generated node.
Why it matters: this is the exact motivation for the distinction Part 4 formalises. In this course the loop-safe version is called generic search.
"in the project this is also referred to as graph search because it works on any graph while the algorithm that we saw previously uh only works on uh on trees."
Lecturer, T2 (slide-backed, Part 4 p.27)
Terminology warning that starts here and pays off in Part 4: what this course calls generic search is what the rest of the literature calls graph search. The loop on p.24 is why the distinction exists.
This is the one exercise archetype that belongs to Part 3, and it is the language every other exercise question is written in. The assignment sheet, Opgave Oefenzitting 1_ Representing Search Problems.pdf, asks verbatim: "Find a good representation for the states and the actions (= the transition rules to map states to the next possible states) of this problem, and also define the initial state and the goal formulation." The Towers of Hanoi exercise on the same sheet breaks that into five printed sub-questions: "Propose a state representation for Towers of Hanoi as a search problem"; "What is the size of the state space?"; "What is the start state?"; "From a given state, what actions are legal?"; "What is the goal test?"
Time it as 8 to 12 minutes. Deliver five labelled items, in that order, and give the state-space size as a formula.
Classic mistake: writing the transition rules at the wrong abstraction level, that is, enumerating ground moves instead of writing one symbolic rule. The sheet warns against exactly this, in print, in the worked pancake example that opens it: "When writing down transition rules, use an appropriate level of abstraction, e.g. a symbolic representation. E.g. do not write (1, 2, 3, 4) → (2, 1, 3, 4) [and] (1, 3, 2, 4) → (3, 1, 2, 4) [and] (1, 4, 3, 2) → (4, 1, 3, 2) ... As all transitions correspond to rule 3 above: flipping the top two pancakes." Three ground lines are shown and struck down in favour of one rule over variables (a, b, c, d) → (b, a, c, d). The second most common loss is forgetting the constraint clause that rules out illegal states.
Exercise session 1 (Representing Search Problems), exercise 1: Farmer, fox, goose and grain, assignment verbatim
A farmer has to cross a river with his fox, goose and grain. His boat can only carry himself and one of his possessions, though. Thus he needs to make several crossings in order for all the animals to reach the other bank. However, bear in mind that an unguarded fox will eat the goose and an unguarded goose the grain.
Find a good representation for the states and the actions (= the transition rules to map states to the next possible states) of this problem, and also define the initial state and the goal formulation.
Constraint worth imposing on yourself before you look: use at most four transition rules.
States of the form [L|R], where L holds the items on the left bank and R the items on the right bank, drawn from Fa (farmer), Fo (fox), Go (goose), Gr (grain).
Start: [Fa Fo Go Gr|] Goal: [|Fa Fo Go Gr]
Rules (X and Y stand for the rest of a bank, z for a single possession):
Additional constraint: no combination (Fo,Go) or (Go,Gr) on either bank without the farmer.
What earns the marks: four rules, not the dozens of concrete crossings. The variables X, Y and z are what make it four, and that is the abstraction level the pancake example on the same sheet demands in print. The constraint clause is a separate line, not folded into the rules, which is also how the water-jug guards are written on p.22. Nothing here asks for a solution path, so do not spend time producing one; the question asks for a formulation.
Constructed, in the sample paper's format (theory MC, true/false)
Repairing the four defective guards on p.22, so that no rule can map a state to itself, changes the set of states reachable from (0,0).
"not mandatory but it's something you should be able to do"
Exercise session, T10
Said in the MDP exercise session, about writing a transition function down formally for the grid world, using conditionals inside the schema to cover the cases a single unconditional expression would miss, with the water jug used as the worked analogy. Nothing is wrong with the rules printed on p.22: they conserve water, as the trace above shows, 6 gallons before and after. The point is the technique. The guard-plus-schema style of p.22 is the version you are expected to produce; a case split written inside the schema is the more compact alternative, and it is worth being able to write one.
Two rooms, dirt or no dirt in each, and the cleaner in one of them: 2 × 2 × 2 = 8 world states, numbered 1 to 8 on the slide. Actions are Left (L), Right (R) and Suck (S). The goal test is "no dirt in the rooms". Path cost is one unit per action, so this problem does have a cost model, unlike 8-queens.
Complete the description. Which of the eight numbered states pass the goal test, and what is the largest number of actions an optimal agent ever needs, over all eight possible starting states?
States 7 and 8 pass: both rooms clean, the cleaner on the left (7) or on the right (8). The goal test reads only the dirt, not the position, so it accepts two states, exactly like the free y in the water-jug goal (2,y).
The worst case is 3 actions, from state 1 (cleaner left, both rooms dirty) via S, R, S, or from state 2 (cleaner right, both dirty) via S, L, S. Verified by breadth-first search from each of the eight starts: the optimal lengths are 3, 3, 1, 2, 2, 1, 0, 0.
Why it matters: 8 states is small enough to reason about completely, which is the point of the example. It is also why the same world can carry the sensorless variant on p.27 without becoming unreadable.
Page 26 draws the transition model itself: eight nodes, arcs labelled L, R and S. The text on the slide states the consequence of full observability precisely: "If the environment is completely observable, the vacuum cleaner always knows where it is and where the dirt is. The solution then is reduced to searching for a path from the initial state to a goal state."
"And these are represented as a kind of finite state automaton"
Lecturer, T2 (on Part 3 p.26)
A finite state automaton is a graph of finitely many states with labelled arcs for the transitions, the object you meet in a formal languages course. The name is worth holding on to: it says that the state space plus the transition model together are just a labelled directed graph, and that every search algorithm from Part 4 onwards is a way of walking one. It also says loops are normal, because automata have them by design.
That reduction is the whole reason full observability makes life easy. The agent does not need a contingent plan (do this, then look, then decide). A fixed sequence of actions suffices, because there is no uncertainty for the sequence to hedge against.
Name the property this diagram makes visible. Several nodes carry an arc back to themselves labelled L, R or S. What do those self-loops encode, and what do they imply for a search algorithm?
They encode actions that are legal but have no effect: L while already in the left room, R while already in the right room, S in a room that is already clean. The transition model is a total function here, every action is applicable in every state, and "no effect" is represented as mapping the state to itself rather than by making the action inapplicable.
For a search algorithm this means the state space is a graph with cycles of length 1 before any longer cycle is even considered. A tree search would generate an infinite branch by repeating L in the leftmost state. It is the same failure as p.24, visible in a space of only eight states.
Why it matters: you have a genuine design choice when you write a transition model. Either restrict the guard so the useless action is not applicable (as the water-jug rules should have done) or allow it and rely on loop detection. Say which you chose.
Page 27 removes the sensors, and the slide text does something unusual: it redefines what a state is, mid-example. "Here, states are knowledge states. That is the state space becomes the power set of the world states 1-8."
Read that carefully. The five ingredients are unchanged as a frame, but every one of them is now instantiated over sets:
The slide's own summary line changes accordingly: Partially observable, deterministic, static, discrete and single-agent.
Trace it. Start from the belief containing all eight world states and apply the plan L, S, R, S. Write the belief after each action, using the numbering from p.25. Does the agent ever need to sense?
{1,2,3,4,5,6,7,8} →L→ {1,3,5,7} →S→ {5,7} →R→ {6,8} →S→ {8}
After L the agent is certainly in the left room, which removes the four states with the cleaner on the right. After S the left room is certainly clean, so only the two states with a clean left room survive. After R it is certainly on the right, after the second S the right room is certainly clean, and the belief has collapsed to the single world state 8, which passes the goal test.
No sensing at all, and this four-action plan is the shortest that is guaranteed: breadth-first search over belief states confirms no three-action sequence makes every member of the initial belief dirt-free.
Why it matters: the price of the guarantee is visible in the numbers. The observable version needs at most 3 actions and searches 8 states; the sensorless version needs 4 and lives in a space of up to 256. Removing an assumption about observability does not change the five ingredients, it changes what a state is, and the state space grows exponentially.
Constructed, in the sample paper's format (theory MC, true/false)
In the sensorless vacuum world of p.27, a knowledge state passes the goal test as soon as at least one of the world states it contains is free of dirt.
The closing slide is four questions, and each one is a pointer to a later Part. Treat it as the chapter's own summary of what it did not answer.
| Question on p.28 | Where it was raised | Where it is answered |
|---|---|---|
| "How to design the state space and the transition model? (cf. 8-queens, Pac-Man)" | pp.17, 20 | Answered here for classical search (archetype A1), then re-asked in every later formalism: MDP formulation in Part 9 (archetype A17, where the instruction is to minimise the number of states), and STRIPS operator design in Part 11 (archetype A21). The 2023 theory open question 3.2 is this skill in words: explain the input that determines a STRIPS problem, how a state is represented, and how valid successors are computed. |
| "Should we search an implicit graph or an implicit tree? (how to deal with loops)" | pp.14, 24, 26 | Part 4, loop breaking and generic search. |
| "Should we start to search from initial state or from goal state, should we search forward or backward?" | Raised here for the first time: a text search of all 29 pages finds "forward" and "backward" only on p.28 | Part 11, where progression (forward) planning is the taught method. |
| "Do we need an optimal solution or just any solution? (cf. Pac-Man)" | pp.9, 19 | Part 5, where greedy and hill-climbing trade optimality for speed. |
Constructed, in the sample paper's format (theory MC, true/false)
Because the 8-queens formulation on p.19 sets all path costs to 0, every solution that formulation admits is an optimal solution.
The August 2023 sample paper contains no question drawn from Part 3 (nor from Parts 1, 8 or 14). That is a fact about one paper, not a promise: the lecturer says the exam aims to be balanced across topics but also that "we cannot ask you everything", and that he will not ask the same questions as the sample. Part 3 is a live topic.
Where it certainly shows up is indirectly. The exercise exam's search traces (sample Q1) hand you a formulated problem and ask you to walk it; the MDP question (sample Q2) hands you states, actions and rewards. Every one of those questions is written in the vocabulary defined on pp.9 and 10. If "path cost", "goal test" and "transition model" are not automatic, you lose time decoding the question rather than answering it.
Also examinable from this Part: the counting arithmetic. "How many world states, how many search states" (p.17) is a question format, not a slide decoration.
| Term | Precise definition | Plain paraphrase | Exam phrasing |
|---|---|---|---|
| State | A description that represents the world unambiguously while retaining only the aspects relevant to the problem (p.9). | The smallest label that still tells the algorithm everything it needs. | "Propose a state representation for Towers of Hanoi as a search problem" (exercise session 1 sheet). |
| Abstraction | The deliberate omission of world detail that no ingredient of the search problem consults. | Leave out what nothing reads. | "only the relevant aspects → abstraction" (p.9). |
| State space | The set of all possible states (p.10). Defined implicitly by the states and the transition model, never built. | Everywhere you could in principle be. | "State space: 2057" (p.20). |
| State-space size | The cardinality of that set, normally given as a product over independent components, restricted to what is reachable. | How many states there are, as a formula. | "What is the size of the state space?" (exercise session 1 sheet); "How many states?" (p.13); "How many World states?" (p.17). |
| Initial state | The state the agent starts in (p.9). A set of states when the world is not observable (p.27). | Where you begin. | "What is the start state?" (exercise session 1 sheet); "Initial State: (0,0)" (p.21). |
| Actions | The operations available, possibly a function of the state (p.9). Written as named schemas with guards. | What you are allowed to do, and when. | "From a given state, what actions are legal?" (exercise session 1 sheet); "From a given state, which actions are allowed?" (session 1 solution deck). |
| Transition model | The successor function: what happens when you execute an action in a state (p.10). May be non-deterministic or stochastic. | The rule that turns a state plus an action into the next state. | "the actions (= the transition rules to map states to the next possible states)" (exercise session 1 sheet); "How to design the state space and the transition model?" (p.28). |
| Goal formulation | The specification of which world states have the desired properties and count as solutions (p.9). | What counts as done. | "also define the initial state and the goal formulation" (exercise session 1 sheet). |
| Goal test | The predicate that decides whether a state description matches a goal state (p.10). May accept many states. | The yes/no check you run on a state. | "What is the goal test?" (exercise session 1 sheet); "Goal Test: all booleans false" (p.16). |
| Path | A sequence of actions leading from one state to another (p.10). | A route, written as the moves rather than the places. | "Solution: an action sequence that reaches a goal state" (p.10). |
| Path cost | A cost function g over paths, usually the sum of the action costs along the path (p.10). Also called the online or execution cost. | What running the plan costs. | "Path Costs: Each step costs 1 unit (path costs corresponds to its length)" (p.13). |
| Search cost | The time and storage needed to find a solution (p.10). The offline, computational cost. Total cost = search cost + path cost. | What thinking costs. | "Specification of the search costs (OPTIONAL)" (p.9). |
| Optimal solution | A solution of least cost (p.10). Meaningless unless a cost model was specified. | The cheapest way that works. | "Optimal: achieve goal at least cost" (p.3); "Do we need an optimal solution or just any solution?" (p.28). |
| Implicit tree vs implicit graph | Two views of the same space. The tree view treats every generated path as new; the graph view records states already seen, so a state appears once. | Do you remember where you have been? | "LOOPS! Should we search a graph or a tree?" (p.24); "Should we search an implicit graph or an implicit tree? (how to deal with loops)" (p.28). |
| Belief state (knowledge state) | A set of world states the agent considers possible; the state space becomes the power set of the world states (p.27). | Everything the world could be, given what you know. | "Here, states are knowledge states. That is the state space becomes the power set of the world states 1-8" (p.27). |
Constructed, in the sample paper's format (theory MC, true/false)
A goal test must single out exactly one goal state; a search problem whose goal test accepts several states is incorrectly formulated.
Every number in this chapter (9!/2, 120 × 230, the factor 576, 1.78 × 1014, 80+...+88, 2057, the 14 reachable water-jug states, the six-action optimal jug path, the 14 self-transitions, the vacuum-world plan lengths and belief trace) was recomputed from the printed rules before being written down.