Suppose the agent could see the whole cave: pits, wumpus, gold. What's left is planning, a pure search problem. Most of the work is choosing the state, and each choice gives a different search.
World & search progress hover a square
expanded (number = how many nodes in that square)frontiercurrent node / solutionpath to current node
Pseudocode
Now
Search tree hover a node for its state · click it to see its path
expandedfrontier (hollow)current / solutionpopped, not expanded (cutoff/cycle)generated, rejected (already reached)
Counters
Frontier
Compare all algorithms on this problem
Same world, problem and heuristic. d = solution length, b* = effective branching factor (§3.6.1).
Heuristic lab
Computes the true cost-to-go h*(s) for every reachable state (Dijkstra backward from the goals), then checks each heuristic. Admissible: h(s) ≤ h*(s). Consistent: h(s) ≤ c(s,a,s′) + h(s′) on every edge.
Chapter notes & questions
Two formulations of the same world
Route: state = (x, y), actions N/E/S/W. At most n² states. Easy to read, but it drops orientation, the gold and the return trip.
Full mission: state = (x, y, facing, hasGold, hasArrow, wumpusAlive), with the real actuators. At most n²·4·2·2·2 states. Shooting costs 11 (−1 action, −10 arrow). If the wumpus blocks the only corridor, the optimal plan shoots it.
Questions to try
On the mission problem, BFS returns a plan with the fewest actions. When is that not the cheapest plan? hintMake a world where the wumpus blocks the short corridor: BFS may shoot (1 action, cost 11) while UCS walks around.
Run IDS and watch the heat map. How many times is [1,1] expanded in total? Why is that still acceptable (§3.4.4)?
Depth-first tree-like search on the mission problem can blow up even with a cycle check. Why doesn’t IS-CYCLE stop “TurnLeft, Forward, TurnLeft, TurnLeft, Forward…” loops? hintIS-CYCLE only checks the current path. Paths that differ in facing are different states.
Compare A* with “Manhattan tour” and with “+ minimum turns”. Which expands fewer nodes? Is the second one still admissible? Check in the heuristic lab.
Use the inadmissible 3× heuristic with A*. Does it still find the optimal cost? Try several seeds.
Greedy best-first with Manhattan distance: build a world with a pit wall that makes it take a long detour.