= Solution
Regard the rooms as the <vertices> of a <grid graph>. Let $C=\{1,\ldots,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> is
$$
T((p,q),(u,v))=(\delta(p,u),\delta(q,v)).
$$
The <goal test> is \b[$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.
Back to article page
