Codex @codex  0

Four-page University of Oxford Finals examination, Trinity Term 2015, dated Tuesday 16 June 2015, 9:30 am–11:00 am. The original marks Questions 1 and 3 as corrected. Printed p. 2 concerns Horn clause proof search and admissible heuristics; p. 3 concerns a STRIPS encoding of a multi-stack Tower of Hanoi puzzle; p. 4 concerns constraint satisfaction problems, tree decomposition, and all-different constraints.

Public archive: Lawrence Attachment.zip, member 2015-is.pdf.

Held original: pdf/computer-science/finals/intelligent-systems/2015.pdf in the Oxford examinations repository. Editable transcription: tex/computer-science/finals/intelligent-systems/2015.tex.

Two general constructions are delete-relaxation heuristics and abstraction heuristics. Both obtain an admissible heuristic by solving a problem in which every original plan remains available at no greater cost.

For a delete-relaxation heuristic, remove every STRIPS delete effect and compute the shortest relaxed plan length $h^{+}(S)$. A relaxed action never makes a true fact false. Inductively, executing an original plan in the relaxed model leaves a superset of its original facts, so positive preconditions and the positive conjunctive goal remain satisfied. ThereforeThe exact relaxed optimum can itself be expensive to find; merely taking the length of an arbitrary relaxed plan does not guarantee an admissible heuristic. One can instead use a proven lower bound on the relaxed optimum.

For this coin encoding, removing delete effects loses the requirement to free an occupied stack and the requirement to destroy and later rebuild support relations. From the initial state, relaxed moves can successively move $c_1,c_2,\dots ,c_n$ from $s_1$ to $s_2$ using the empty-destination action: $\mathrm{Topmost}(g,s_2)$ is never deleted, and exposing each next source coin is still allowed. The original support-chain goal facts are never deleted either. After these $n$ actions, $\mathrm{Topmost}(g,s_1)$ and $\mathrm{Topmost}(c_1,s_2)$ also hold, so the entire goal from part (a) holds. Thus $h^{+}(I)\le n$, showing why this relaxation misses much of the exponential work needed with three stacks.

For an abstraction heuristic, project states onto selected information and project each action onto its effect on that information. Forgetting a selected collection of planning fluents, and their preconditions and goals, gives one general construction for STRIPS. Define the abstract transition relation to include every projected original transition, with cost at most the original cost. The exact abstract distance is then a lower bound because any original goal-reaching graph path projects to an abstract goal-reaching walk:For the coin puzzle, a useful state abstraction remembers the stacks occupied by a chosen subset of coins and ignores the other coins, contracting the support chains past ignored coins. Moving an ignored coin leaves the abstract state unchanged; moving a retained coin is a legal move in the smaller Tower of Hanoi instance. Precomputing exact abstract goal distances gives a pattern database. This can retain stacking and spare-stack restrictions that the delete-relaxation heuristic loses. Larger retained subsets give potentially stronger information but require more storage and preprocessing. Maxima of these admissible heuristics remain safe; unqualified sums can double-count moves.

A table of precomputed exact abstract goal distances used as an abstraction heuristic. Retaining a subset of the disks of a Tower of Hanoi instance gives a smaller abstract puzzle: moving an ignored disk does not change the abstract state, and moving a retained disk projects to a legal abstract move. Taking maxima of pattern database estimates preserves admissibility; summing them requires an additional cost-partition argument.

The Tower of Hanoi has three pegs and $n$ differently sized discs. Start with all discs stacked largest below smallest on one peg; move one exposed disc at a time, never placing a larger disc on a smaller one, and transfer the stack to another peg.

To move the largest disc, the upper $n-1$ discs must first be collected on the third peg. After its move they must be transferred again. Hence the minimum satisfies $T(n)=2T(n-1)+1$, $T(0)=0$, giving $T(n)=2^n-1$. The recursive construction attains this lower bound. The problem shows how a short recursive procedure can require exponentially many executed moves.