Backtracking & and/or graphs

Backtracking, made explicit

Backtracking is the engine under depth-first, breadth-first, and best-first search: pursue a path until you hit a goal or a dead end, then *back up* to the most recent node that still has unexplored children and try the next one. Luger writes it with three lists so the bookkeeping is visible:

- SL (state list) — the *current solution path* being explored, newest state at the front. The most recently added state is CS (current state), the frontier of the path. - NSL (new state list) — states discovered and *awaiting* evaluation. - DE (dead ends) — states whose descendants have all failed, recorded so the search never re-enters them.

The loop: apply operators to CS to get its children; the first usable child becomes the new CS and is pushed onto SL; if CS has no usable children, *backtrack* — move it from SL to DE and restore the previous state as CS. If SL ever holds a goal, SL *is* the solution path. (In the open/closed framing of BFS/DFS, the CLOSED list is exactly the union of SL and DE — visited states, whether on the current path or abandoned.)

And/or graphs

Ordinary search graphs have only or nodes: to solve a node, solving *any one* child suffices (pick a move). Many AI problems also need and nodes: to solve the node, *all* children must be solved. An and/or graph (formally a *hypergraph*) mixes the two, capturing logical $\vee$ and $\wedge$ directly:

- An or node = a choice point. *Any one* successful child solves it. This behaves like normal backtracking — if one branch fails, try the next sibling. - An and node = problem decomposition. The parent splits into subproblems that must *all* be solved. Its arcs are joined by a curved link. The asymmetry is in *failure*: if any and-child fails, the whole and-node fails immediately — there is no point trying the remaining siblings.

Why this is the structure behind exam Q6

Rule-based reasoning *is* an and/or graph, and this is the bridge to Module 5. A goal-driven proof of a fact builds an and/or tree where:

- multiple rules with the same conclusion are or branches — try one rule; if it fails, try another rule that also concludes the goal; - a single rule's conjunctive premises ($p \wedge q \rightarrow \text{goal}$) are and branches — to use that rule you must prove *every* premise.

Proving a goal by depth-first search over such a tree, numbering rules in the order you try them, is exactly the DFS inference tree the exam asks you to draw (Q6: prove *"playground is empty"*). You build the machinery here; you apply it to rules in Module 5.

Worked example — "is the lawn safe to mow?"

Goal: safe_to_mow. Knowledge: Rule R1: dry_grass ∧ blade_sharp → safe_to_mow. Rule R2: grass_cut_recently → safe_to_mow. Facts: dry_grass, blade_sharp.

- safe_to_mow is an or node: R1 and R2 are alternative ways to prove it. - Try R1 first. Its premises dry_grass ∧ blade_sharp form an and node — both must hold. dry_grass is a fact ✓; blade_sharp is a fact ✓. Both and-children succeed, so R1 succeeds and the or-node safe_to_mow is proved — we never even try R2.

Had blade_sharp been *unknown*, the and-node R1 would have failed on that premise, and the search would backtrack to the or-node and try R2 (grass_cut_recently) instead. That or-try-next / and-all-must-hold dance is precisely goal-driven rule proof.