Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence / 2 / f / Solution

Retain the ordered position state $(p,q)$, the same initial state and the goal test $p=q$, with unit joint-action cost. Replace the deterministic search transition model by a set-valued outcome relation. LetThenHere $\delta$ for an attempted move leaving the board returns the current room. This explicit boundary convention keeps every outcome inside the state space; alternatively disable a horizontal command unless both possible destinations are legal. Mrs Robot’s commands can still be restricted to legal moves as before.

The result is a fully observable nondeterministic planning problem, assuming that actual positions are observed after every step. Both possible horizontal outcomes must be represented, even though they may coincide at a boundary or when $n=1$. No outcome probabilities are supplied, so attaching equal probabilities would add an assumption. Its solution is a position-dependent plan or policy.