Part 2: Rational Agents

Printed copy: all task answers are expanded below their tasks.

What this chapter assumes

• Acting rationally, defined precisely (part01.html). A rational agent selects the action that maximizes its expected utility, where the utility function is fixed in advance by the designer and the expectation is taken because the world is uncertain. Part 2 does not re-derive this; p.2 restates it in one line and then spends the rest of the deck on the consequences.
• The agent-environment loop (part01.html). Sensors deliver percepts, an internal decision process produces an action, actuators execute it, the environment changes, repeat. The same schematic (agent box with a "?" inside, sensors and actuators facing the environment) is reused on pp.2, 3 and 11 of this deck. The "?" is the agent program, and every later Part of the course is a candidate filling of that "?".
• Rationality is about decisions, not about thinking like a human (part01.html). The course sits in the "acting rationally" quadrant of the four-definitions matrix. That is why Part 2 measures an agent by an external performance measure rather than by the plausibility of its reasoning.

1. The claim that organises the Part

Slide p.2 is a recap rather than new material, and the lecturer opens the Part by presenting it as one. All three of its bullets already stand on p.63 of the Part 1 deck, and the only textual difference is the phrase "(or performance measure)" added to the second bullet (verified by comparing p.2 against Part 1 p.63 directly):

1. An agent is an entity that perceives and acts.
2. A rational agent selects actions that maximize its (expected) utility (or performance measure).
3. "Characteristics of the percepts, environment, and action space dictate techniques for selecting rational actions."

What changes between the two decks is which bullet does the work. In Part 1 the third bullet was a promise; here it is the thing being developed. Statement 3 is the thesis of the whole Part, and pp.6, 7 and 8 each repeat it as a banner line: "The environment largely determines the agent design!". The practical reading is a pipeline: you describe the task environment (Section 2), you classify it (Section 3), and the classification narrows the set of algorithms that can legally be applied (Section 11). Get the description wrong and you will apply a correct algorithm to the wrong problem.

Slide p.3 makes the pipeline concrete by putting Pacman in the agent box of the same diagram. Pacman perceives the grid (walls, dots, ghost positions) and acts by moving up, down, left or right. Nothing about the diagram changed: only the contents of percepts, actions and environment changed, and those contents are exactly what PEAS records.

2. PEAS: how to name a task environment

PEAS is the four-part specification of a task environment: Performance measure, Environment, Actuators, Sensors. On pp.4 and 5 the tables carry a leading "Agent Type" column, so the columns read Agent Type, then P, E, A, S from left to right.

The four slots are easy to recite and easy to fill in wrongly. The discipline that keeps them honest:

• P is measured on the environment, not inside the agent. It scores what actually happens in the world, over the whole run, and it is chosen by the designer. An agent that believes it is doing well scores zero for that belief. On p.4 the taxi's performance measure is deliberately multi-dimensional: safe, fast, legal, comfortable trip, maximize profits, minimize impact on other road users. Note that "maximize expected utility" needs one number, so a multi-dimensional P has to be aggregated (a weighted sum, or a hierarchy of hard constraints and then an objective). That aggregation is a design decision you own.
• E is everything outside the agent that P depends on. It includes other agents (p.4 lists other traffic, police, pedestrians, customers) and non-agent processes (weather). Listing E is where you first notice whether the task is multi-agent.
• A is what the agent can change: the flow of information goes from agent to world. p.4: steering, accelerator, brake, signal, horn, display, speech.
• S is what the agent can read: the flow goes from world to agent. p.4: cameras, radar, speedometer, GPS, engine sensors, accelerometer, microphones, touchscreen.

Slide p.5 supplies five further rows: medical diagnosis system, satellite image analysis system, part-picking robot, refinery controller, interactive English tutor. Read them as a range test on your intuitions. The satellite image analysis system has one sensor (a high-resolution digital camera) and one actuator (display of scene categorization); the refinery controller has valves, pumps, heaters, stirrers and displays as actuators, and temperature, pressure, flow and chemical sensors as sensors (note that displays appear as actuators here, for the reason given in Task 1). The English tutor's performance measure is the student's score on a test, which is a measure taken on the world, well after the agent has acted, and which the agent cannot directly observe. That last point is the seed of the "performance measure known or not known" axis on p.8.

3. The classification axes (pp.6, 7, 8)

Six axes on pp.6 and 7, plus two extra ones on p.8. For each, the deck gives a question to ask and, in most cases, the design consequence in a one-line arrow. Learn the consequences, because that is what turns the classification into an engineering decision.

3.1 Fully observable vs partially observable (p.6, called accessible vs inaccessible)

Question on the slide: "Are the relevant aspects of the environment accessible to the sensors?" Consequence: partially observable means the agent requires memory, that is, an internal state. The load-bearing word is relevant. A chess player cannot see the opponent's intentions, yet chess is fully observable, because the board plus whose turn it is is all the state the transition model needs. Observability is about the state variables of your formulation, not about everything you might like to know.

3.2 Deterministic vs stochastic (p.6)

Question: "Is the next state of the environment completely determined by the current state and the selected action?" The slide adds a named special case: if only the actions of other agents are nondeterministic, the environment is called strategic. Consequence: stochastic means the agent may have to prepare for contingencies, that is, a plan that is a single action sequence is no longer enough.

Two traps. First, determinism is relative to how coarse your state is: a robot gripper that "sometimes" drops a slippery object is deterministic given a fine enough state (friction coefficient, grip force) and stochastic given the state you actually chose to represent. Second, stochastic is not the same as partially observable. Backgammon on p.10 is fully observable and stochastic (you see everything, the dice are random). Poker is partially observable and stochastic (hidden cards and shuffling). Keeping these apart is worth a mark.

3.3 Episodic vs sequential (p.6)

Question: "Can the quality of an action be evaluated within an episode (perception + action), or are future developments decisive for the evaluation of quality?" An episode is one percept plus the action taken on it. Episodic therefore means that credit assignment (deciding which earlier action deserves the credit or the blame for a later outcome) is local: classify this image, score this image, move on. Sequential means a present action can only be scored through its downstream consequences, which is exactly the condition that makes search, planning and MDPs necessary. Note that "episodic" is a statement about credit assignment, not about whether the task repeats: an image classifier run a million times is still episodic.

3.4 Static vs dynamic (p.7)

Question: "Can the environment change while the agent is deliberating?" The slide names the in-between case: if the environment does not change but the agent's performance score changes as time passes, the environment is semi-dynamic. Consequence: static means the agent has time to compute a rational decision, so an algorithm that takes as long as it needs (uninformed search, exhaustive CSP solving) is admissible engineering. Dynamic forces a time budget, which is where depth limits and evaluation functions come from in part07.html.

3.5 Discrete vs continuous (p.7)

Question: "Is the environment discrete (chess) or continuous (a robot moving in a room)?" Consequence on the slide: continuous time implies a continuously operating controller. The axis applies separately to time, to the state variables, to percepts and to actions, and a task can be mixed (a car has continuous position and a small discrete set of gear choices). Everything the course does algorithmically assumes a discrete state and action set.

3.6 Single agent vs multi-agent (p.7)

Question: "Which entities have to be regarded as agents?" The slide notes both competitive and cooperative scenarios, and gives the consequence: multi-agent means the agent may need to behave randomly. The reason given in the lecture is that randomness is what keeps a game interesting, so a multi-agent setting typically builds in a random effect. (Added note, not from the deck: in a competitive setting randomization is also a defence, because a rule that always answers the same way can be predicted and exploited by the opponent.) Note the phrasing of the question. Whether the pedestrian is an agent or part of the weather is a modelling choice: treat an entity as an agent when its behaviour is best predicted as maximizing an objective that depends on what you do.

3.7 The two extra axes (p.8)

• Environment known vs not known. Consequence: "Unknown physics" implies a need for exploration. This axis is about the agent's knowledge of the rules, and it is orthogonal to observability. A poker rulebook is fully known while the cards are hidden (known but partially observable); a new video game can show you the whole screen while you have no idea what the buttons do (fully observable but unknown).
• Performance measure known vs not known. Consequence on the slide: an unknown performance measure implies you must observe or interact with a human principal. This is the axis on which the value-alignment material of part14.html attaches: if P has to be inferred from a human, then a badly specified P is an engineering failure, not a philosophical quibble.

4. Pacman on the axes (p.9)

Slide p.9 puts the running example beside five of the axes. Count the bullets in the figure below and you get five: observability, deterministic vs stochastic, episodic vs sequential, discrete vs continuous, single vs multi-agent. The static/dynamic axis of p.7 and the two known/unknown axes of p.8 are not among them, which you can check against the reproduced slide. Pacman is useful here precisely because several of its answers flip between variants of the game, which makes the point of Section 3 unavoidable.

5. The reference table (p.10)

Slide p.10 is the compressed version of the entire Section 3: ten task environments (crossword puzzle, chess with a clock, poker, backgammon, taxi driving, medical diagnosis, image analysis, part-picking robot, refinery controller, English tutor) by six characteristics. Pack guidance: treat it as the densest slide in the Part and a likely source of true/false items, since every cell is a small, checkable judgement.

Three more cells from this table repay attention, because they are the ones students argue with:

• Medical diagnosis is marked Single agent, even though patients and doctors are obviously present, and they appear in E on p.5. That is the modelling choice from Section 3.6 in action: their behaviour is not being modelled as strategic response to the diagnostic system, so they are environment, not agents. The English tutor row, by contrast, is Multi, because the student adapts to the tutor.
• Poker is Partially observable and Stochastic; backgammon is Fully observable and Stochastic. Hidden information and randomness are separate axes, and the table proves it in adjacent rows.
• Part-picking robot is Episodic and Dynamic and Partially observable. Episodic because each part is picked and scored on its own; dynamic because the conveyor belt keeps moving while the robot deliberates; partially observable because the camera does not see what is under the top layer of parts.

6. Exam signal: the self-driving car item

7. Reflex agents (pp.11 to 15)

Slide p.11 reopens the agent diagram with the "?" still in it. Slides p.12 onwards fill it in, in increasing order of capability. Two families are worked through in detail here, the reflex agent (p.12) and the goal-based or planning agent (p.16). Two more are named without being developed: the lecturer names the utility-based agent at this point and defers it, and the summary slide p.20 lists learning agents, which improve their behavior over time.

The bullets on p.12: choose action based on current percept (and maybe memory); may have memory or a model of the world's current state; do not consider the future consequences of their actions; consider how the world is. The diagram is a straight line from Sensors to "What the world is like now" to a match against "Condition-action rules" to "What action I should do now" to Actuators. There is no branch that represents a hypothetical future.

The second bullet is the model-based case in Russell and Norvig's terminology, the textbook the deck draws on (p.1). The distinction that matters: the model here answers "what is the world like now, given what I have seen so far", which is what partial observability demands (p.6). It does not answer "what would the world be like if I did A", which is what p.16 adds. A model-based reflex agent is still reflex: it has memory, not foresight.

Slide p.13 gives the smallest possible instance, an agent program in Python for Pacman:

class GoWestAgent(Agent):
    def getAction(self, percept):
        if Directions.WEST in percept.getLegalPacmanActions():
            return Directions.WEST
        else:
            return Directions.STOP

This is the whole agent program: one condition-action rule, plus a default. It is also the cleanest illustration of what an agent program is, a function from a percept to an action.

Slides p.14 and p.15 show two reflex agents running (videos from UC Berkeley CS188). The first, in a simple layout, eats dots successfully. The second uses the rule "move towards the nearest visible food". It performs well while food is visible and then stalls when no food is in the percept, while the score keeps decreasing with each time step. The diagnosis is architectural, not a bug: the rule set is a lookup table over percepts, so when the percept contains no dot there is no rule that makes progress, and the agent has no mechanism for reasoning that moving away from where the food was could bring it back into view.

Worth noticing for later: this stall has exactly the shape of a local optimum in greedy local search (part05.html), where an algorithm that only looks at the immediate improvement has no move that looks good and therefore stops short of the goal.

8. Goal-based / planning agents (pp.16, 17)

The bullets on p.16: decisions based on evaluating future action sequences, so the agent asks "what if" questions and considers how the world would be; it must have a model of how the world evolves in response to actions; it must formulate a goal (test); optimal means achieving the goal at least cost; and the arrow at the bottom: this "Involves reasoning!".

Read the diagram as a data-flow graph and its boxes line up with the ingredients Part 3 will use to define a search problem, which is why this slide is the hinge of the Part:

• State: the internal state. The two arcs between it and "What the world is like now" run in opposite directions: the dashed arc goes from "What the world is like now" into State (the current picture updates what is remembered), and the solid arrow goes from State into "What the world is like now" (what is remembered feeds the next picture). Together they are the update loop that partial observability requires.
• How the world evolves plus What my actions do: the model of change, split into the part that happens without you and the part you cause. Part 3 p.10 gives this the name transition model.
• What it will be like if I do action A: the successor computation, applied to a hypothetical action rather than an executed one. This single box is the difference between the two agent families.
• Goals: what Part 3 p.9 calls goal formulation, that is, defining which world states count as solutions.
• "Optimal: achieve goal at least cost" on the bullet list: costs over paths.

part03.html turns this picture into its Five Ingredients, printed on Part 3 p.9: States (with the warning that only the relevant aspects go in, so a state is always an abstraction), Actions, Initial State, Goal Formulation, and Specification of the search costs, which that slide marks OPTIONAL. Note the shape of the list: the model of change is folded into Actions there, and cost is optional rather than mandatory. Part 3 then adds a further layer of concepts on its p.10, including state space, transition model, goal test, path, path cost, search cost, total cost, solution and optimal solution, so the mapping above is where the two chapters meet, not the whole of Part 3.

Slide p.17 shows the planning agent in Pacman: it pauses first, computing an action sequence that eats all the dots in the fewest moves, and then executes it to a maximum score. The pause is the visible cost of reasoning, and it is exactly what a dynamic environment (p.7) will not tolerate, which is the tension that later Parts manage with depth limits and heuristics.

9. Atomic, factored, structured (p.18)

A goal-based agent has to represent states in order to predict them. Slide p.18 gives the three levels of representation the course uses, drawn as the transition from one state B to a successor C at each level.

• Atomic (panel a): a state is a black box with a name and no visible internals. The only operations the algorithm needs are "are these two states the same" and "is this the goal". Everything in part04.html and part05.html works at this level, and so do MDPs in part09.html, where a state is just an index into a table of values.
• Factored (panel b): a state is a fixed set of variables, each with a value (the dots and bars in the panel are the variables). This buys you reasoning inside a state: partial assignments, constraints between variables, propagation, independence. That is exactly what part06.html needs, and what SAT in part10.html needs.
• Structured (panel c): a state contains objects and relations between them, so it can express things whose number is not fixed in advance. This is what STRIPS operators with preconditions and effects need in part11.html, and what first-order logic gives you in part10.html.

The trade-off runs one way: expressiveness increases left to right, and so does the leverage you can get from a single state description, but reasoning becomes harder and the algorithms become more specialised.

10. The course grid (p.19)

Slide p.19 crosses the representation spectrum of p.18 with the deterministic/stochastic axis of p.6 and drops the course's algorithm families into the resulting cells. It is titled "Outline of the course" and it means it.

Reading the grid: the green arrow runs deterministic to stochastic, the blue arrow runs atomic to factored to structured, and four families are placed on it.

• Search: atomic, deterministic (part03.html, part04.html, part05.html).
• MDPs: atomic, stochastic (part09.html).
• CSPs: factored, deterministic (part06.html).
• Planning: structured, deterministic (part11.html).

Why this slide repays memorising rather than merely reading: it comes back, and that is checkable. The same grid is slide p.9 of the Part 6 deck (identical, same title "Outline of the course"), and it reappears twice in the Part 10 deck (pp.2 and 29) retitled "Environments in this course", with the factored cell expanded to "CSPs/SAT, Propositional Logic" and the structured cell carrying "First-Order Logic" above "Planning" on two lines, and with the p.18 representation icons drawn beside the axes. The lecturer is using one picture as the spine of the whole course.

11. The bridge: what search silently assumes

This is the connection the theory exam actually tests, because it is where Part 2 stops being vocabulary and becomes a precondition check on everything that follows.

Then the rest of the course is the systematic relaxation of that list, one assumption at a time:

Notice what the grid on p.19 does not have: an axis for observability. Check the reproduced figure in Section 10 and you will find two arrows, deterministic to stochastic and atomic to factored to structured, and nothing on the picture that refers to what the agent can see. So observability is not what selects a family on this map. The design consequence p.6 attaches to partial observability is a different kind of answer: give the agent memory, an internal state, which is a change to the agent rather than a change of algorithm family.

12. The summary slide (p.20)

p.20 compresses the Part into five statements. Three of them are worth re-reading before an exam:

• "An agent is something that perceives and acts. It consists of an architecture and an agent program." The architecture is the physical or computational platform; the agent program is the function from percept to action, and p.13's GoWestAgent is one, written out in full.
• "An agent program maps from a percept to an action. There are a variety of designs": reflex agents respond immediately to percepts, goal-based agents work towards goals, learning agents improve their behavior over time. The learning family is named here and developed in the machine-learning Parts of the course (part12.html, part13.html).
• "Environments that are partially observable, non-deterministic, dynamic, and continuous and multi-agent are the most challenging." That list is the taxi of p.4, which is why the sample-exam item picked it.

What this sets up

• Search (part03.html, part04.html, part05.html). Part 3 recasts the p.16 diagram as its Five Ingredients on p.9 (States, Actions, Initial State, Goal Formulation, and an OPTIONAL specification of the search costs), then adds state space, transition model, path and solution on p.10; Parts 4 and 5 give the algorithms. Carry forward the bridge in Section 11: those algorithms assume fully observable, deterministic, known, discrete, static, single-agent, atomic. The theory exam tests exactly this dependency.
• CSPs (part06.html). The factored level of p.18. Part 6 reopens with the same grid on its p.9, so the vocabulary of this chapter is the vocabulary of that first slide.
• Stochastic environments (part08.html, part09.html). Dropping determinism replaces "a plan" with "a policy" and replaces max with expectation. Part 9 fills the one stochastic cell drawn on the p.19 grid, and Part 8 puts chance nodes into game trees.
• Logic and planning (part10.html, part11.html). The structured level of p.18, where a state is objects and relations. Part 10 redraws this chapter's grid on its pp.2 and 29 with logic added to the factored and structured cells.

Term box