Search Under Uncertainty

Classical uninformed and informed search rests on two assumptions that are easy to forget precisely because they are never stated at run time: the environment is fully observable, so the agent always knows which state it is in, and it is deterministic, so each action produces a known successor. Then a solution is a sequence of actions computed once, in advance, and executed blindly — percepts received during execution carry no new information because everything was already predictable.¹

Drop either assumption and the sequence breaks. If an action has several possible outcomes, the agent cannot know which one occurred, so it cannot know which action to take next. If the agent cannot observe the full state, it may not know where it started. In both cases future percepts become informative, and later choices must depend on them. A solution is no longer a straight line but a contingency plan (a strategy): a branching object prescribing what to do as a function of what is perceived.

Assumption dropped	State known?	Solution form	Tool
none	yes	action sequence	classical search
determinism	yes	contingency plan (tree)	AND-OR search
observability	belief state (set)	plan over belief states	belief-state search
both (unknown map)	learned online	interleaved plan/execution	online search

This lesson takes the first row below the classical case: the agent knows its state, but its actions are nondeterministic — one action, several possible results — and the tool is AND-OR search. The two deeper settings, where the state is only partially observable and where the environment is entirely unknown, are the subject of the companion lesson, belief-state and online search. Together the two lessons are the bridge from classical search to planning under uncertainty, probabilistic state estimation, and reinforcement learning.

Nondeterministic actions: the erratic vacuum world

A sequence fails as soon as one action can land in more than one state. Recall the two-square vacuum world from intelligent agents: two squares, each clean or dirty, the robot in one of them — $2^{2} \cdot 2 = 8$ states, three actions (Left, Right, Suck), goal a clean world (states 7 and 8). Deterministically it is trivial: from state 1 the sequence [Suck, Right, Suck] reaches the goal.

The eight states of the vacuum world. A dot marks the robot's square; a shaded square is dirty, blank is clean. States 7 and 8 (both squares clean) are the goals, marked in the accent colour.

Now make the cleaner erratic. Applied to a dirty square, Suck cleans it and sometimes cleans the adjacent square too; applied to a clean square, it sometimes deposits dirt.² A single action now has several possible results, so the transition model can no longer be a function returning one state. Generalize $Result (s, a)$ to $Results (s, a)$ returning the set of possible outcome states.

In the erratic world $Results (1, Suck) = {5, 7}$ — the dirt in the right square may or may not get vacuumed. The agent cannot control which outcome occurs, so no fixed sequence solves the problem; from state 1 the plan must react:

[Suck, if State = 5 then [Right, Suck] else []] .

Suck from state 1 lands in 5 or 7. If it landed in 7, the world is already clean and we stop. If it landed in 5 (the left square clean, the right dirty), we go Right and Suck again. The plan is a tree.

AND-OR search trees

The search tree alternates two kinds of branching, as in a game between the agent and nature. At an OR node the branching is the agent's choice: in state 1 it may pick Left, Right, or Suck — one action suffices. At an AND node the branching is nature's choice of outcome: after Suck in state 1 the result may be 5 or 7, and the plan must handle both. The agent controls OR nodes; nature controls AND nodes.³

An AND-OR search tree for the erratic vacuum world. Square OR nodes are states where the agent chooses one action; round AND nodes are outcome sets where every branch must be handled (the arc links them). Bold edges mark one solution subtree; a leaf may repeat an ancestor state (a loop).

Reading the bold subtree above recovers the earlier plan: at OR node 1 choose Suck; both AND outcomes 5 and 7 are covered; from 5 choose Right, then Suck, reaching goal 8.

The recursion mirrors the two node types. Or-Search tries each action and hands the resulting outcome set to And-Search, which demands a subplan for every outcome and joins them with an if–then–else. A cycle check handles the loops nondeterminism creates: if the current state already lies on the path from the root, the branch returns failure — any acyclic solution is reachable without revisiting the state.³

Algorithm:

\textsc{And-Or-Graph-Search}

— return a contingency plan, or failure

1
function AND-OR-GRAPH-SEARCH( $problem$ ):
2
return OR-SEARCH( $problem.\text{INITIAL}$ , $problem$ , $[\,]$ )
3
4
function OR-SEARCH( $state$ , $problem$ , $path$ ):
5
if $problem.\textsc{Goal-Test}(state)$ then return the empty plan
6
if $state$ is on $path$ then return failure
cycle: prune
7
for each $action$ in $problem.\textsc{Actions}(state)$ do
8
$plan \gets$ AND-SEARCH( $\textsc{Results}(state, action)$ , $problem$ , $[state \mid path]$ )
9
if $plan \neq$ failure then return $[action \mid plan]$
10
return failure
11
12
function AND-SEARCH( $states$ , $problem$ , $path$ ):
13
for each $s_i$ in $states$ do
14
$plan_i \gets$ OR-SEARCH( $s_i$ , $problem$ , $path$ )
15
if $plan_i =$ failure then return failure
16
return $[\textbf{if } s_1 \textbf{ then } plan_1 \textbf{ else if } s_2 \textbf{ then } plan_2 \ldots \textbf{ else } plan_n]$

The cycle check guarantees termination in any finite state space: every path ends at a goal, a dead end, or a repeated state. AND-OR graphs also admit breadth-first or best-first exploration; the admissible-heuristic notion carries over, now estimating the cost of a contingent solution (a tree) rather than a sequence, with an $A^{*}$ analog for finding optimal ones.

A worked AND-OR trace

Follow the recursion on the erratic world from state 1, trying actions in the order Suck, Left, Right. Each indented line is a recursive call returning a plan or failure.

Or-Search(1, []). Not a goal. Try Suck first.
- And-Search({5, 7}, [1]) — Suck from 1 yields the outcome set ${5, 7}$ ; both must be solved.
  - Or-Search(5, [1]). Not a goal. Left from 5 loops back toward the left square configurations; Suck on 5 (right square dirty, robot left) does nothing useful; Right from 5 yields ${6}$ .
    - And-Search({6}, [5, 1]).
      - Or-Search(6, [5, 1]). Not a goal. Suck from 6 yields ${8}$ .
        And-Search({8}, [6, 5, 1]).
        Or-Search(8, [6, 5, 1]). State 8 is a goal — return the empty plan.
        returns [], so And-Search returns [].
      - Suck succeeds: Or-Search(6, ...) returns [Suck].
    - returns [Suck], so And-Search returns [if 6 then [Suck]].
  - Right succeeds: Or-Search(5, ...) returns [Right, if 6 then [Suck]].
  - Or-Search(7, [1]). State 7 is a goal — return [].
- both outcomes solved, so And-Search({5,7}) returns [if 5 then [Right, Suck] else if 7 then []].
Suck succeeds at the root: the returned plan is $[Suck, if 5 then [Right, Suck] else []]$ .

This is the contingency plan stated earlier; the bold subtree in the figure traces the same calls. The structural point: And-Search on ${5, 7}$ returned only once both branches had plans — a contingency plan solves the problem exactly when every outcome nature can force is covered.

Cyclic solutions: try, try again

Sometimes no acyclic solution exists, and the plan must loop back on itself. In the slippery vacuum world, movement actions sometimes fail and leave the agent in place: $Results (1, Right) = {1, 2}$ . Every move may bounce back, so And-Or-Graph-Search as written returns failure — no finite subtree has a goal at every leaf, since stay put is always a possible outcome.

In the slippery world, moving Right from state 1 may fail and return to state 1. No acyclic plan exists; the cyclic plan keeps retrying Right (the loop edge) until it succeeds.

The fix is a cyclic solution: keep trying Right until it works. We express it by labelling a portion of the plan and re-invoking the label instead of copying the plan:

[Suck, L_{1} : Right, if State = 5 then L_{1} else Suck] .

read as while State = 5 do Right. A cyclic plan is a solution provided every leaf is a goal and a goal is reachable from every point in the plan. Whether reachability suffices for the agent to succeed depends on the source of nondeterminism: if each outcome occurs eventually under repetition — as a die eventually yields a six — the retrying agent reaches the goal. If failures are correlated (the wrong hotel key never opens the door), no cyclic plan helps, and the persistent failure should be reattributed to an unobservable property.

That reattribution leads to the next lesson. A failure that is not random but follows from a fact the agent cannot see — the key is the wrong key — is not nondeterminism but partial observability, and it needs a different tool. This continues in Belief-State and Online Search, which reasons over sets of possible states and then over environments the agent does not even have a map of.

AIMA, Ch. 4 — Beyond Classical Search; §4.3 Searching with Nondeterministic Actions: when the environment is partially observable or nondeterministic, percepts become informative and a solution must be a contingency plan (strategy) specifying actions as a function of future percepts, using nested if–then–else branches rather than a fixed action sequence. ↩
AIMA, §4.3.1 — The erratic vacuum world: generalizing the transition model from a Result function returning one state to a Results function returning a set of possible outcome states, illustrated by $Results (1, Suck) = {5, 7}$ and the contingent plan of Equation (4.3). ↩
AIMA, §4.3.2 — AND-OR search trees: OR nodes (the agent's action choices) alternating with AND nodes (the environment's outcome choices); a solution as a subtree with a goal at every leaf, one action per OR node, and every branch at each AND node; And-Or-Graph-Search (Figure 4.11) with its cycle check; and §4.3.3 cyclic solutions for the slippery world. ↩ ↩²