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

Use 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: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.

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.