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

The ordered Cartesian product has $n^4$ states, including $n^2$ goal states. Each robot has at most five commands, so the search tree has branching factor at most $25$, attained when both are interior for $n\ge 3$. Boundary states have fewer actions under the legal-move convention. For $n=2$ the maximum is $3^2=9$, and for $n=1$ it is one if waiting is retained.

The state space is finite, but the unrestricted search tree is infinite because both robots can wait repeatedly. $n^4$ counts physical states, not distinct action histories.