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

Regard the rooms as the vertices of a grid graph. Let $C=\{1,\dots ,n{\}}^2$ and let the two robot positions be $p,q\in C$. A single controller chooses both commands, so the state space is the ordered Cartesian product $S=C\times C$, with initial state $(p_0,q_0)$. Distinguishing the robots matters because their later action laws need not be identical.

For a room $x$, let $A(x)$ consist of wait and all cardinal moves remaining in $C$; write $\delta (x,u)$ for the resulting room. At $(p,q)$ an action is the ordered pair $(u,v)\in A(p)\times A(q)$, and the deterministic search transition model isThe goal test is $p=q$, checked at integer time boundaries, and every joint action costs one. Swapping two distinct rooms does not satisfy the goal test. No internal walls are supplied; if walls were specified, they would simply restrict the move relation.