= Solution
Use \b[<AND-OR search> for a <strong plan>]. At an OR node choose a joint action; at its AND node require successful continuations for every possible outcome. A repeated state on the current branch cannot by itself establish progress. On a finite <state space>, the equivalent <strong planning winning-set iteration> starts with $W_0=\{(p,p):p\in C\}$ and repeatedly adds states with an action whose nonempty outcome <set> is contained in the current winning <set>:
$$
W_{t+1}=W_t\cup\{s:\exists a,\ \varnothing\ne\operatorname{Results}(s,a)\subseteq W_t\}.
$$
A newly admitted state has a plan with at most $t+1$ remaining steps in the worst case. This <algorithm> terminates on the finite <state space> and is complete for finite guaranteed-success plans. In a general <nondeterministic planning> problem it cannot guarantee that a <strong plan> exists: an uncontrollable self-loop can prevent inevitable progress.
\b[For this particular unobstructed grid, a <strong plan> does exist.] Command Mr Robot to wait throughout and move Mrs Robot along a shortest route to his initial room. Her movement is deterministic and his waiting is unaffected by the horizontal uncertainty. This meets in $D(p_0,q_0)$ steps, regardless of every uncertain outcome, because no uncertain command is used. Thus a complete finite <AND-OR search> will find a solution here. With an unspecified disconnected maze, existence would instead require both robots to lie in the same reachable <graph component>.
Back to article page
