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\to \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.