--- title: Search Under Uncertainty module: Search moduleNumber: 2 lessonNumber: 11 order: 211 summary: > Classical search assumes the agent knows the state it is in and exactly what each action does. Drop the second assumption and a plan can no longer be a fixed sequence of actions. This lesson develops the first response: AND-OR search over nondeterministic actions, which returns a branching contingency plan rather than a straight line. We build it on the erratic vacuum world, show how OR nodes (the agent's choices) alternate with AND nodes (nature's outcomes), trace the recursion that finds a plan, and handle the case where the only solution is a cyclic "try, try again." topics: [Search] sources: - book: AIMA ref: "Ch. 4 — Beyond Classical Search; §4.3 Searching with Nondeterministic Actions" --- Classical [uninformed](/artificial-intelligence/search/uninformed-search) and [informed](/artificial-intelligence/search/informed-search) 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.[^aima-nondet] 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 | > **Definition (Contingency plan).** A solution to a search problem that specifies > the action to take as a function of the percepts received during execution, > rather than a fixed sequence fixed in advance. It contains nested > `if`–`then`–`else` branches (or a `case` construct) and reads as a tree, not a > list. 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](/artificial-intelligence/search/belief-state-and-online-search). Together the two lessons are the bridge from classical search to [planning under uncertainty](/artificial-intelligence/logic-and-planning/planning-in-the-real-world), [probabilistic state estimation](/artificial-intelligence/uncertainty/reasoning-over-time), 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](/artificial-intelligence/foundations/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. $$ % caption: 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. \begin{tikzpicture}[>=stealth, font=\footnotesize, cell/.style={draw, minimum width=7mm, minimum height=6mm, inner sep=1pt}, dirt/.style={cell, fill=black!22}, robot/.style={circle, fill=black, inner sep=1.1pt}, lbl/.style={font=\scriptsize, anchor=east}] \definecolor{acc}{HTML}{2348F2} % top row: states 1,2 (both dirty), robot left / right \node[lbl] at (-0.55,1.9) {1}; \node[dirt] (c1a) at (0,1.9) {}; \node[dirt] (c1b) at (0.72,1.9) {}; \node[robot] at (0,1.9) {}; \node[lbl] at (3.25,1.9) {2}; \node[dirt] (c2a) at (3.8,1.9) {}; \node[dirt] (c2b) at (4.52,1.9) {}; \node[robot] at (4.52,1.9) {}; % row: states 3 (left dirty, robot left), 4 (left dirty, robot right) \node[lbl] at (-0.55,0.95) {3}; \node[dirt] (c3a) at (0,0.95) {}; \node[cell] (c3b) at (0.72,0.95) {}; \node[robot] at (0,0.95) {}; \node[lbl] at (3.25,0.95) {4}; \node[dirt] (c4a) at (3.8,0.95) {}; \node[cell] (c4b) at (4.52,0.95) {}; \node[robot] at (4.52,0.95) {}; % row: states 5 (right dirty, robot left), 6 (right dirty, robot right) \node[lbl] at (-0.55,0) {5}; \node[cell] (c5a) at (0,0) {}; \node[dirt] (c5b) at (0.72,0) {}; \node[robot] at (0,0) {}; \node[lbl] at (3.25,0) {6}; \node[cell] (c6a) at (3.8,0) {}; \node[dirt] (c6b) at (4.52,0) {}; \node[robot] at (4.52,0) {}; % goal row: states 7 (both clean, robot left), 8 (both clean, robot right) \node[lbl, text=acc] at (-0.55,-0.95) {7}; \node[cell, draw=acc] (c7a) at (0,-0.95) {}; \node[cell, draw=acc] (c7b) at (0.72,-0.95) {}; \node[robot] at (0,-0.95) {}; \node[acc, font=\scriptsize, anchor=west] at (1.0,-0.95) {goal}; \node[lbl, text=acc] at (3.25,-0.95) {8}; \node[cell, draw=acc] (c8a) at (3.8,-0.95) {}; \node[cell, draw=acc] (c8b) at (4.52,-0.95) {}; \node[robot] at (4.52,-0.95) {}; \node[acc, font=\scriptsize, anchor=west] at (4.8,-0.95) {goal}; \end{tikzpicture} $$ 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.[^aima-erratic] A single action now has several possible results, so the transition model can no longer be a function returning one state. Generalize $\textsc{Result}(s, a)$ to $\textsc{Results}(s, a)$ returning the _set_ of possible outcome states. > **Definition (Nondeterministic transition model).** A function > $\textsc{Results}(s, a)$ returning the **set** of physical states that may > result from taking action $a$ in state $s$. Classical (deterministic) search is > the special case where every such set is a singleton. In the erratic world $\textsc{Results}(1, \textit{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_: $$ [\,\textit{Suck},\ \textbf{if } \textit{State}=5 \textbf{ then } [\textit{Right}, \textit{Suck}] \textbf{ 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.[^aima-andor] $$ % caption: 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). \begin{tikzpicture}[>=stealth, font=\footnotesize, ornode/.style={draw, minimum width=7mm, minimum height=6mm}, andnode/.style={draw, circle, minimum size=5mm, inner sep=0pt}, goal/.style={acc, font=\scriptsize}, sel/.style={acc, very thick}] \definecolor{acc}{HTML}{2348F2} % root OR node (state 1) \node[ornode] (s1) at (0,4.5) {1}; % two AND nodes under it \node[andnode] (a1) at (-3,3.3) {}; \node[andnode] (a2) at (3,3.3) {}; \draw[->, sel] (s1) -- (a1) node[midway, above left, black, font=\scriptsize] {Suck}; \draw[->] (s1) -- (a2) node[midway, above right, black, font=\footnotesize] {Right}; % arc marking the AND at a1 \draw[sel] (-3.6,2.95) to[bend left=55] (-2.4,2.95); % outcomes of Suck: {7 goal} and {5} \node[ornode] (s7) at (-4.4,2.0) {7}; \node[ornode] (s5) at (-1.6,2.0) {5}; \node[goal, anchor=north] at (-4.4,1.65) {goal}; \draw[->, sel] (a1) -- (s7); \draw[->, sel] (a1) -- (s5); % from state 5: Right leads to AND {6} \node[andnode] (a5) at (-1.6,0.6) {}; \draw[->, sel] (s5) -- (a5) node[midway, right, black, font=\footnotesize] {Right}; \node[ornode] (s6) at (-1.6,-0.7) {6}; \draw[->, sel] (a5) -- (s6); % from state 6: Suck leads to AND {8 goal} \node[andnode] (a6) at (-1.6,-2.0) {}; \draw[->, sel] (s6) -- (a6) node[midway, right, black, font=\scriptsize] {Suck}; \node[ornode] (s8) at (-1.6,-3.3) {8}; \node[goal, anchor=north] at (-1.6,-3.65) {goal}; \draw[->, sel] (a6) -- (s8); % right branch (Right from 1): state 2, unexplored \node[ornode] (s2) at (3,2.0) {2}; \draw[->] (a2) -- (s2); \node[font=\scriptsize] at (3,0.9) {(other subtree)}; \end{tikzpicture} $$ > **Definition (AND-OR solution).** A solution is not a path but a _subtree_ of the > AND-OR graph that (1) has a goal at every leaf, (2) selects exactly one action at > each OR node it contains, and (3) includes _every_ outcome branch at each AND node > it contains. Equivalently, a plan $\pi$ solves state $s$ iff either $s$ is a goal, > or $\pi$ chooses an action $a$ such that $\pi$ solves every $s' \in \textsc{Results}(s, a)$. 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.[^aima-andor] ```algorithm caption: $\textsc{And-Or-Graph-Search}$ — return a contingency plan, or failure function AND-OR-GRAPH-SEARCH($problem$): return OR-SEARCH($problem.\text{INITIAL}$, $problem$, $[\,]$) function OR-SEARCH($state$, $problem$, $path$): if $problem.\textsc{Goal-Test}(state)$ then return the empty plan if $state$ is on $path$ then return failure // cycle: prune for each $action$ in $problem.\textsc{Actions}(state)$ do $plan \gets$ AND-SEARCH($\textsc{Results}(state, action)$, $problem$, $[state \mid path]$) if $plan \neq$ failure then return $[action \mid plan]$ return failure function AND-SEARCH($states$, $problem$, $path$): for each $s_i$ in $states$ do $plan_i \gets$ OR-SEARCH($s_i$, $problem$, $path$) if $plan_i =$ failure then return failure 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^\ast$ 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 $[\textit{Suck},\ \textbf{if } 5 \textbf{ then } [\textit{Right}, \textit{Suck}] \textbf{ 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: $\textsc{Results}(1, \textit{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. $$ % caption: 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. \begin{tikzpicture}[>=stealth, font=\footnotesize, ornode/.style={draw, minimum width=7mm, minimum height=6mm}, andnode/.style={draw, circle, minimum size=5mm, inner sep=0pt}] \definecolor{acc}{HTML}{2348F2} \node[ornode] (s1) at (0,2.6) {1}; \node[andnode] (a1) at (0,1.3) {}; \draw[->, acc, thick] (s1) -- (a1) node[midway, right, black, font=\footnotesize] {Right}; % outcome set {1,2}: back to 1 (loop) or on to 2 \node[ornode] (s2) at (2.6,0) {2}; \draw[->, acc, thick] (a1) -- (s2); % loop edge back to state 1 \draw[->, acc, thick] (a1) to[out=170, in=250] (s1); \node[acc, font=\footnotesize, anchor=east] at (-0.9,1.9) {retry}; \node[font=\footnotesize] at (2.6,-0.9) {(goal reachable)}; \end{tikzpicture} $$ 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: $$ [\,\textit{Suck},\ L_1:\ \textit{Right},\ \textbf{if } \textit{State}=5 \textbf{ then } L_1 \textbf{ else } \textit{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](/artificial-intelligence/search/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-nondet]: **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-erratic]: **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 $\textsc{Results}(1, \textit{Suck}) = \{5,7\}$ and the contingent plan of Equation (4.3). [^aima-andor]: **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.