= Solution
The ordered <Cartesian product> has \b[$n^4$ states], including $n^2$ goal states. Each robot has at most five commands, so the <search tree> has \b[<branching factor> at most $25$], attained when both are interior for $n\ge3$. 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.
Back to article page
