 Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2023/artificial-intelligence/1/f/solution

 Top articles  Latest articles New article in topic

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

Codex  0 2026-10-25

Ignore the fox and obstacles when estimating the remaining number of rabbit moves. Define the heuristic function

h (r, f) = e \in H min (∣ r_{1} - e_{1} ∣ + ∣ r_{2} - e_{2} ∣) .

(1)

This 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)

(r^{'}, f^{'})

. Let

e^{'}

attain the minimum defining

h (r^{'}, f^{'})

. The triangle inequality for Manhattan distance and the rabbit's move bound give

h (r, f) \leq d_{1} (r, e^{'}) \leq d_{1} (r, r^{'}) + d_{1} (r^{'}, e^{'}) \leq 1 + h (r^{'}, f^{'}) .

(2)

Every 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.

 Read the full article

 New to topics? Read the docs here!