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

Regard the rooms as the vertices of a grid graph. Let $C=\{1,\dots ,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 isThe goal test is $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.

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.

Let $D(p,q)=|p_x-q_x|+|p_y-q_y|$ be their Manhattan distance. Each joint action can reduce $D$ by at most two, so use the simultaneous rendezvous distanceThis heuristic function is nonzero whenever the robots are apart. For a transition $(p,q)\to (p^{\prime },q^{\prime })$, the triangle inequality givesApplying the ceiling function yields $h(p,q)\le 1+h(p^{\prime },q^{\prime })$, and $h(p,p)=0$. Thus $h$ is a consistent heuristic, hence an admissible heuristic.

In the unobstructed grid this estimate is exact. Along a shortest route of length $D$, both robots approach a middle room, taking at most $\lceil D/2\rceil$ steps each; when $D$ is an odd integer, the robot with the shorter route waits once. That final wait prevents a crossing from being mistaken for a meeting. With obstacles the same formula remains a relaxation heuristic, though it need not be exact.

Write $h^{\ast }(s)$ for the optimal remaining cost and suppose $h_i(s)\le h^{\ast }(s)$ for $i=1,2$. The conclusions hold pointwise:

These are admissible heuristic combinations. An unweighted sum needs an extra condition, such as distributing action costs between the component estimates, to prevent counting the same required work twice.

Use $H=\max (h_1,h_2)$ if each estimate is available at comparable cost. For every $\alpha \in [0,1]$,Thus $H$ has heuristic dominance over all the other combinations guaranteed to remain admissible heuristics. A-star search orders nodes by $f=g+h$, where $g$ is the accumulated path cost. A larger admissible heuristic excludes more nodes from the compulsory $f<C^{\ast }$ region, where $C^{\ast }$ is the optimal solution cost. Under the usual nonnegative-cost and goal-normalization assumptions, this gives at least as informative a search guide while preserving the optimality guarantee of A-star search with tree search.

The unweighted sum loses that guarantee. The dominance statement does not promise smaller wall-clock time in every implementation: evaluating estimates costs time, and nodes with $f=C^{\ast }$ depend on tie handling. Nor does admissibility of the inputs alone imply consistent heuristics. If both inputs are consistent heuristics, however, their pointwise maximum is also a consistent heuristic.

Retain the ordered position state $(p,q)$, the same initial state and the goal test $p=q$, with unit joint-action cost. Replace the deterministic search transition model by a set-valued outcome relation. LetThenHere $\delta$ for an attempted move leaving the board returns the current room. This explicit boundary convention keeps every outcome inside the state space; alternatively disable a horizontal command unless both possible destinations are legal. Mrs Robot’s commands can still be restricted to legal moves as before.

The result is a fully observable nondeterministic planning problem, assuming that actual positions are observed after every step. Both possible horizontal outcomes must be represented, even though they may coincide at a boundary or when $n=1$. No outcome probabilities are supplied, so attaching equal probabilities would add an assumption. Its solution is a position-dependent plan or policy.

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.

Include all four positions and a turn marker:The initial marker is $\mathrm{R}$. There are at most $2n^8$ such states before terminal compression. The two robots form one maximizing team in the adversarial search representation. At an R state their actions are joint legal moves, including waiting, with deterministic successor positions and marker M. At an M state the monster outcome is a pair of legal cardinal moves, producing marker R.

Check termination initially and after each simultaneous pair of moves. A state is a failure if $\{p,q\}\cap \{z_1,z_2\}\ne \varnothing$. Otherwise it is a success if $p=q$. Collision takes priority over meeting, so meeting on an occupied room fails. A safe meeting ends immediately, before a further monster response. Room swaps without a shared position at a checked boundary are neither capture nor meeting.

The monsters move randomly, so their nodes are chance nodes, not minimizing decisions. Under independent uniform legal moves, if monster $j$ currently has $d_j$ available destinations, each joint outcome has probability $1/(d_1{d}_2)$. If several commands produce the same state, add their probabilities. This specifies a stochastic game tree, equivalently a Markov decision process for the robot team. Uniform legal moves and independent monsters are explicit boundary/joint-law conventions; uniform attempted directions with blocked moves staying put is another convention, with different boundary transition probabilities but the same search method. For the one-cell grid, a monster with no legal move stays; all four initial positions then coincide and the instance immediately fails.

The game tree alternates MAX nodes for joint robot choices and CHANCE nodes for joint monster outcomes. An interior MAX node has at most $25$ children; an interior CHANCE node at most $4^2=16$. A terminal safe meeting has utility one and capture has utility zero. With no specified preference for speed, the objective is to maximize the probability of eventual safe meeting.

Use expectimax: maximize at MAX nodes and take the expected value at CHANCE nodes. For nonterminal states, its finite-horizon backup isHere the horizon counts half-turns, terminal values stay fixed at zero or one, and $V_0$ is zero at nonterminal states. This computes the best chance of success within the horizon. Maximizing the worst monster outcome would solve a different problem from the stipulated random movement.

Because waiting and movement cycles can repeat states, the infinite game tree need not terminate. For the unbounded objective, use value iteration on the finite state graph, starting from terminal-success indicators as above: $V_t$ increases to the optimal eventual-success probability. A reachability-policy method or sufficiently long finite-horizon policies can extract the actions; arbitrary tie choices in the limiting equations must not select a policy that waits forever instead of realizing the value. Alternatively impose an explicit finite horizon and use depth-limited expectimax, stating that changed objective. No method guarantees success with probability one from every initial configuration.