Past exam of the computer science course of the University of Oxford / 2023 / Artificial intelligence / 1 / f

Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the heuristic functionThis is Manhattan distance to the nearest exit, a relaxation heuristic. Assume at least one exit; with none the instance is immediately unsolvable. The estimate is generally nonconstant and is not the perfect escape cost: obstacles can force detours, while pursuit can make an apparently nearby exit unreachable.

To prove it is a consistent heuristic, consider a surviving one-round transition from $(r,f)$ to $(r^{\prime },f^{\prime })$. Let $e^{\prime }$ attain the minimum defining $h(r^{\prime },f^{\prime })$. The triangle inequality for Manhattan distance and the rabbit's move bound giveEvery successful terminal state has $h=0$. This proves consistency with unit round costs; summing the inequality along any successful route also proves that it is an admissible heuristic. Failed transitions need no successor estimate because they are discarded.