Notation

An agent is anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.

The vacuum world

function Vacuum-Agent([location, status]) returns an action
  if status = Dirty then return Suck
  else if location = A then return Right
  else if location = B then return Left

State names

A state is named by the agent’s square, a space, and C (clean) or D (dirty) for each square from left to right: A DD has the agent in A and both squares dirty, as pictured on slide 3. The state-space graph of slide 9, in its order:

• A DD
• B DD
• A CD
• B CD
• A DC
• B DC
• A CC
• B CC

Performance measures

A performance measure (utility function) is an objective criterion for success of an agent’s behavior. Whether the reflex agent is rational depends on the performance measure and the environment. The vacuum tool scores the world after each time step with one of these:

A rational agent selects, for each possible percept sequence, an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and its built-in knowledge. The expected utility of an action:

EU(action) = Σ_outcomes P(outcome | action) U(outcome)

PEAS

Environment types

Seven dimensions, in the order of the slides. The table of slide 17, and the environments tool, write the short values.

Strategic and Semidynamic are the values the review slide adds in parentheses Lecture reference: Rational Agents · slide 20

A search problem has five components:

Heuristics

Complexity

Time is the number of nodes generated, space the largest number of nodes in memory, both in terms of b, d, m, and C*. Exponents are superscripts:

In plain text, such as the properties table below, the UCS bound is written O(b^(C*/ε)).

A strategy is defined by the order of node expansion, which is the order its frontier gives nodes back. Names and short forms as the tools write them:

DLS is the depth-limited DFS that IDS runs once per limit. Weighted A* orders the frontier by g(n) + α·h(n) with α = 2 unless set otherwise.

Properties

The time and space of UCS are also written O(b^C*/ε) Lecture reference: Uninformed Search · slide 44

The state-space graph draws each state once. The search tree draws a node for every path the search generates, so one state can appear many times. Both use the same status colors.

State-space graph

• State

  A circle with the state’s name.

• State on the Romania map

  A small square with the name beside it, as on the slide map.

• Start state

  An arrow in from nowhere, labelled start.

• Goal state

  A double outline.

• Action, both ways

  A line with the step cost (undirected graphs).

• Action, one way

  An arrow to the successor state, with the step cost.

• h(n) estimate

  The heuristic value of a state, written h=366.

• Being expanded

  The state of the node just taken off the frontier.

• On the frontier

  The state of a node waiting on the frontier: a colored outline.

• Expanded (explored)

  Expanded earlier; in graph search, the explored set.

• Not added (repeated state)

  A child generated at this step whose node was not added: a dashed ring.

• Solution path

  At the goal step: the states and actions of the solution.

Statuses are drawn on circles and on the map squares of Romania, where the small markers are filled solid.

Search tree

• Node

  Its state’s name. Children are drawn left to right in successor order.

• Priority

  Under the node: what the strategy orders the frontier by (see below).

• Being expanded

  The node just taken off the frontier, marked with a triangle.

• On the frontier

  Generated and not yet taken off: a colored outline.

• Expanded

  Taken off the frontier and expanded.

• Goal state

  The node that passed the goal test: a double outline.

• Solution path

  The nodes and edges from the root to the goal node.

• Not added (repeated state)

  A child that did not go on the frontier: dashed and crossed out, as the slides cross out repeated states.

• Cut off at the depth limit

  Goal-tested at the depth limit and not expanded.

• Replaced on the frontier

  A frontier node that a cheaper path to the same state replaced.

Under each node

The value the frontier is ordered by, as the slides write it. For Sibiu, reached from Arad at path cost g = 140 with straight-line distance h = 253:

In a tool

A* tree search on Romania, step 7 of 7: Take Bucharest off the frontier. It contains the goal state: return the solution Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest (cost 418).

The tools announce every step of a search in one sentence, in the words of the tree search outline. These sentences are produced by the same code, on the lecture graphs:

When the search ends, a summary gives the solution and the node counts:

Solution: Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest (cost 418). 6 nodes taken off the frontier, 5 expanded, 16 generated.

Where the slides leave a choice open, every tool makes the same one. With these choices the tools reproduce the traces on the slides:

Successor order

Alphabetical by state name (“name order”): case-insensitive, with digit runs compared by value, so q2 comes before q10. Typed-in graphs can switch to “listed”, the order the edges are written in.

DFS order

Children are pushed so that the first successor is expanded first.

Goal test

When a node is taken off the frontier, as in the tree search outline. An option tests children when they are generated instead; the root is then tested when the frontier is initialized.

Expansion order

Lists every node taken off the frontier, including the goal node.

Ties

In a priority queue, the node added first comes off first.

Graph search

A node’s state enters the explored set when the node is expanded; a child whose state is explored is not added. A child whose state is already on the frontier replaces that frontier node only for UCS, greedy, A*, and weighted A*, and only when its path cost is lower; otherwise it is not added. The replacing node is a new frontier entry, so it takes its place among ties as a new node.

Path check

“Avoid repeated states along path”: a child whose state is already on the path from the root to it is not added. Available for every strategy; it makes DFS and IDS complete in finite state spaces. Lecture reference: Uninformed Search · slide 32

Depth limit

A node at depth = limit is goal-tested but not expanded: it is cut off, even when it has no children. DLS uses limit 3 unless set otherwise. IDS runs DLS with limits 0, 1, 2, … and stops at the first limit with a solution, when an iteration cuts nothing off (no solution), or at its largest limit (50 unless set otherwise).

Counts

Generated counts every node created, including the root and children that were not added. Expanded counts nodes whose successors were generated. The slides’ time is nodes generated; their space is the largest frontier, plus the explored set in graph search.

Missing h values

Greedy, A*, and weighted A* use h = 0 for states without a heuristic value.

Weighted A*

α = 2 unless set otherwise.

Run limits

A run stops at a limit on the nodes taken off the frontier (tools may set it; 10,000 unless set otherwise) or at 200,000 generated nodes; its last step says which limit stopped it.

Tools that take a typed graph read this format: one directive or edge per line. Directives are case-insensitive.

Costs are numbers ≥ 0, like 5 or 2.5; so are h values. A later line for the same edge replaces the earlier one. A graph has at most 300 states and 3,000 edges.

Examples

directed
node: S, a, b, c, d, e
node: f, G, h, p, q, r
start: S
goal: G
S -> d 3
S -> e 9
S -> p 1
b -> a 2
c -> a 2
d -> b 1
d -> c 8
d -> e 2
e -> h 8
e -> r 2
f -> c 3
f -> G 2
h -> p 4
h -> q 4
p -> q 15
r -> f 1

directed
node: S, A, B, C, G
start: S
goal: G
S -> A 1
S -> B 1
A -> C 1
B -> C 2
C -> G 3
h: S=2, A=4, B=1, C=1, G=0

Messages

Problems in the text are reported with the line they are on. For example:

Actions

Move the blank Left, Right, Up, Down (in successor order); each move costs 1.

States

181,440 states (9!/2) are reachable from any board. A board can be reached from the goal exactly when the parities of their inversions match.

h₁(n)

The number of misplaced tiles; the blank does not count.

h₂(n)

The total Manhattan distance: for each tile, the number of squares from its desired location, rows plus columns.

max(h₁(n), h₂(n))

The two combined by taking the larger value Lecture reference: Informed Search · slide 37

The terms of h₂ are tiles 1 to 8 in order, as on the slide. Open the slide boards in the 8-puzzle tool

A cell is written (column, row), counted from (0, 0) at the top left. Walls block; every other cell is a state. The successor function lists neighbors clockwise from Up:

Heuristics for a cell dx columns and dy rows from the goal, with values for dx = 3, dy = 2:

The default is the exact distance on a grid without walls: Manhattan for 4-connected moves, octile for 8-connected. Weighted A* multiplies h by α; the slides’ example uses 5 × the Euclidean distance.

Presets and sections cite a deck by its title and a slide number: Lecture reference: Uninformed Search · slide 4, or a range: Lecture reference: Rational Agents · slides 6–8.

The lectures page lists each deck with the tools that cite it.