Past exam of the computer science course of the University of Oxford / 2022 / Artificial intelligence (A16607W1)

Source release: Oxford examination release, archive member 2021/T/a16607w1.pdf. The printed paper is dated 27 May 2022; the archive member’s directory names 2021. All three questions are solved below.

Use $a,w,g,r$ for the agent, monster, gold and arrow, and abbreviate $s{q}_{ij}$ to $s_{ij}$. A physically safe STRIPS plan isEvery movement follows a listed adjacency predicate. The shot is taken from $s_{22}$ while the arrow is held, and kills the monster before entry into $s_{23}$. The pit at $s_{12}$ is never entered. The pickup establishes possession of the gold, and the last four movements restore the exit location while preserving that possession. Thus ten actions achieve the formal goal and the intended safe return; arriving at the exit is the source model’s representation of leaving.

Three different omissions produce concrete erroneous STRIPS plans. Here a route means the corresponding successive $\mathrm{Move}$ actions with the indicated first argument.

No lethal-entry condition. Move the agent along $s_{11},s_{21},s_{22},s_{23},s_{13}$, take the gold at $s_{13}$, and reverse the route. This nine-action STRIPS plan satisfies every supplied precondition and the final goal test, without firing. Physically it fails on entering the live monster’s room: the supplied search transition model neither forbids the entry nor records death. The omitted pit cell happens to be disconnected in the supplied adjacency relation, so this particular instance already excludes pit entry; that accidental protection does not encode the monster hazard.

Supposedly stationary objects can move themselves. The five-action STRIPS planleaves the agent at the exit and brings it the gold. The formal preconditions hold because $x$ in $\mathrm{Move}(x,y,z)$ has no actor restriction. Gold cannot actually propel itself. The same flaw permits moving the supposedly stationary monster.

Unrestricted pickup permits impossible inventory. Follow the first example’s outward route, but insert $\mathrm{Take}(a,w,s_{23})$ immediately after reaching $s_{23}$. Continue to $s_{13}$, take the gold and return. This ten-action STRIPS plan ends with both $\mathrm{have}(a,w)$ and $\mathrm{have}(a,g)$ and satisfies the supplied goal. Its entrance also exposes the first flaw, but the additional, distinct defect is that pickup treats the live monster as a collectible object and deletes its location. A movement safety check alone is not a specification of which objects are collectible. The shot schema likewise lacks restrictions to the designated shooter, projectile and victim; fixing the action roles together prevents these type errors.

A corrected STRIPS model can fix object roles in the action names, leaving only room parameters to instantiate. Use the same $a,w,g,r$ and introduce static $\mathrm{pitfree}(z)$ and $\mathrm{exit}(z)$ facts, plus a planning fluent $\mathrm{clear}(z)$ meaning “no live monster occupies $z$”. Unlike the supplied adjacency relation, let $\mathrm{adj}$ describe all geometrically adjacent rooms; safety is then explicit rather than hidden by missing edges.

Initially the agent, monster and gold have their specified locations, $\mathrm{have}(a,r)$, $\mathrm{alive}(w)$ and $\mathrm{active}$ hold, $\mathrm{exit}(s_{11})$ holds, $\mathrm{pitfree}$ holds at every room except $s_{12}$, and $\mathrm{clear}$ holds at every room except $s_{23}$. All unlisted facts are false by the closed-world assumption. The following positive preconditions, add lists and delete lists are a complete action specification:Require $\mathrm{exited}$ as the goal. If reaching the exit suffices, omit $\mathrm{Leave}$ and use the original two goal facts. Instantiating these schemata over the finite room set gives ordinary ground STRIPS actions.

Only $a$ moves, only $g$ is collectible and only $r$ can be fired at $w$. No action changes the monster’s location; its corpse can stay there, while $\mathrm{clear}$ records that it is harmless. The gold stays at its original room until collection. The arrow is consumed by its only use. By mathematical induction on plan length, every applicable action preserves the planning state invariant that the active agent occupies one pit-free room without a live monster. Consequently every solution is a safe execution. The plan in part a, followed by $\mathrm{Leave}(s_{11})$, is one such execution.

Ordinary classical planning with STRIPS starts from one completely specified state. Here the missing locations express ignorance: not listing a pit or a monster at a room does not establish its absence. Applying the closed-world assumption to those omissions would manufacture knowledge of safety. Moreover, future sensor readings can determine which action is appropriate, so a fixed action sequence need not suffice.

The suitable object is a belief state and a contingent plan that branches on observations. A finite belief state model could in principle be compiled into a larger classical planning instance, but the ordinary physical-state STRIPS representation does not directly represent the required uncertainty and sensing.

This is a finite, discrete, partially observable, single-agent, sequential search problem with an unknown initial state. The cave is static while the agent deliberates. Given a complete world and an action, the described physical effects and ideal sensor readings are deterministic; ignorance of the world does not itself supply a probability distribution. The fixed monster and gold are environmental objects, not competing decision makers. A known action/sensor law with unknown object locations is different from having to learn an unknown search transition model.

Use partially observable search over belief states. A complete physical state can be writtenwhere $p$ is the agent’s room, $m$ the fixed monster room, $P$ the pit set, $g$ the fixed gold room, $\ell$ records whether the monster lives, $r$ whether the arrow remains, $k$ whether gold has been collected and $e$ whether the agent has exited or failed. The known room dimensions and exit are fixed data. Include death or entrapment as failure states. Movement, shooting toward an adjacent room, collection and departure have their physical meanings. In particular, a shot consumes the arrow, and kills the monster exactly when it targets the live monster’s room.

Let $T(s,a)$ be this physical search transition model. For a surviving agent, an ideal observation is the tuple of three truth valuesrecording sound, breeze and glitter. Here $\sim$ denotes geometric adjacency and $1$ an indicator function. Initially $B_0$ contains all worlds compatible with the known facts and any initial observation. After action $a$ and observation $o$, update the belief state byKnown success or failure observations are included as needed. No prior probabilities are required. A guaranteed-success goal test accepts $B$ only when every $s\in B$ has exited carrying gold. A policy must use the same action in all worlds still indistinguishable to the agent.

An AND-OR search has OR choices for the agent’s next action and AND branches for every possible resulting observation with nonempty $B_{a,o}^{\prime }$. Its output is a contingent plan, not merely a route. To demand safe success, reject any action whose possible outcomes include irreversible death or entrapment, and require a successful continuation on every observation branch. In an online execution the agent updates its belief state, follows the observation branch and can plan again. A strong plan need not exist: some admissible worlds have no safe route, and even solvable worlds can be observationally indistinguishable until a dangerous choice. Without an added prior and numerical rewards, expected-risk optimization is not determined by the description.

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.

The first assertion is true. Each deletion removes a value with no support in an adjacent constraint domain. If a complete solution still used that value, the solution’s neighboring value would supply exactly such a support, a contradiction. By mathematical induction, AC-3 never deletes a value used by an original solution. An empty constraint domain therefore proves that no solution exists.

The second assertion is false. Take three Boolean variables $X,Y,Z$ with constraint domains $\{0,1\}$ and the binary constraints $X\ne Y$, $Y\ne Z$, $Z\ne X$. Every value has the opposite value as support across each edge, so AC-3 deletes nothing and returns true. Yet $X\ne Y$ and $Y\ne Z$ imply $X=Z$, contradicting $Z\ne X$. Arc consistency checks local support, not compatibility of all supports in one complete assignment.

The third assertion is true under the usual explicit-input, constant-cost constraint-checking model. With $v$ variables, $e$ constrained pairs and maximum constraint domain size $d$, AC-3 has time complexity $O(v+e{d}^3)$ in Big O notation. A revision costs $O(d^2)$; each deletion can re-enqueue incoming arcs, and each constraint domain loses at most $d$ values, giving $O(ed)$ revisions including the initial arcs. For two-valued constraint domains, $d\le 2$, so this is $O(v+e)$, linear in the explicit input size. This uses fixed-size relations, or already combined constant-time tests per pair. “Binary” normally describes constraint arity, not two-valued constraint domains; the latter restriction is the extra hypothesis needed here. As usual, initially empty constraint domains should be rejected before entering the algorithm, including isolated variables.

Interpret MyAC as doing at least one initial sweep, then repeating while the preceding sweep deleted a value. Its loop guard otherwise has no initialized truth condition. Both procedures apply the same support-based deletion rule, so both preserve every solution and terminate because finite constraint domains only shrink. Both return false on a detected empty constraint domain; neither successful return establishes satisfiability.

If a sweep changes no constraint domain, every directed arc has been revised against unchanged constraint domains, so all arcs satisfy arc consistency. Conversely, AC-3 places every potentially affected incoming arc back on its work list after a deletion. Its empty work list therefore also establishes arc consistency. When both run to successful completion, they compute the same arc-consistency closure, independently of revision order. To see maximality, any subdomains of the initial constraint domains that satisfy arc consistency survive every revision: each of their values retains a support inside those subdomains. Thus neither procedure can delete a value belonging to any such fixed point. Early failure may leave different intermediate constraint domains, but both failures correctly prove impossibility.

Their scheduling costs differ. AC-3 directs work toward arcs that may have lost supports, with standard time complexity $O(v+e{d}^3)$. The full-sweep arc consistency method revisits all $2e$ arcs after even one remote change. There are at most $vd$ value deletions, so at most $vd+1$ sweeps; a direct implementation including a scan for empty constraint domains costsIf empty-domain detection is maintained during revisions rather than rescanned, the familiar comparison is $O(ve{d}^3)$ versus $O(e{d}^3)$, apart from initialization. These are upper bounds, not exact costs on every input.

In practice MyAC is simple and may have low overhead or benefit from a fortunate sweep order. It can also waste many scans after changes propagate slowly opposite to that order. AC-3 incurs work-list bookkeeping but normally avoids those unrelated revisions. Both inherit the inability of arc consistency to decide arbitrary constraint satisfaction problems.

For a finite constraint satisfaction problem with $v$ variables, all complete assignments have depth $v$ when each step assigns one new variable. Thus the shallowest-solution property of breadth-first search offers no advantage: every complete solution is already at that depth.

Depth-first search with backtracking stores a path and pending choices, using $O(vd)$ auxiliary space with ordinary explicit choice bookkeeping, or $O(v)$ when each level stores only a current value index. Breadth-first search may store an exponentially large frontier, up to $O(d^v)$ partial assignments. Depth-first search can also combine naturally with immediate constraint propagation and undoing changes. The finite depth avoids the infinite-branch obstruction of unrestricted depth-first tree search. Neither traversal removes the possible exponential time complexity.

Write $F\subseteq \{1,\dots ,N{\}}^2$ for the prescribed occupied cells, with $k=|F|$. The source’s lowercase $n$ in its coordinate bound is read as the stated board size $N$. If two prescribed queens already attack each other, no completion exists. Each model below correctly expresses that impossibility as well as consistent inputs.

Model 1: one Boolean variable per cell. Let $B_{rc}\in \{0,1\}$ indicate occupancy. Requireand impose $B_{rc}+B_{st}\le 1$ for every two distinct cells sharing a row, a column or a diagonal. Equivalently, impose exactly one queen in each row and column and at most one on each diagonal. Explicit diagonal constraints areTogether with the total-count constraint and the attacking-pair binary constraints, these force exactly the intended boards. The count and diagonal-sum constraints are legitimate many-variable constraints; this model need not be binary.

Model 2: one variable per labeled queen. Let $Q_i=(R_i,C_i)\in \{1,\dots ,N{\}}^2$ for $1\le i\le N$. Enumerate $F=\{f_1,\dots ,f_k\}$ and restrict $D_i=\{f_i\}$ for $i\le k$. For every $i<j$, impose the binary constraintThere are exactly $N$ variables and distinct rows, so these are $N$ distinct queens. Labeling the prescribed queens does not lose a board completion: the queens are physically indistinguishable, and any completion can be labeled to give the prescribed ones those indices. It does create redundant assignments for the remaining labels.

Model 3: one variable per row. Let $C_r\in \{1,\dots ,N\}$ be the queen’s column in row $r$. For every $r<s$, requireand impose $C_r=c$ for every $(r,c)\in F$. These restrictions give $N$ queens, one per row; the all-different constraint on the columns gives one per column. For $N$ nonattacking queens on $N$ rows, exactly one per row is forced by the pigeonhole principle, so no solutions are lost. Inconsistent prescribed positions in a single row give incompatible unary restrictions. All three are exact constraint satisfaction problem encodings of the queens completion problem.

The conventional worst-case estimate is the backtracking leaf bound given by the product of the initial constraint domain sizes. Before exploiting any attacking-queen constraints, the three models give respectivelyModel 1 has $N^2$ binary choices. Model 2 has $N$ labeled queens with $N^2$ possible cells each. Model 3 has $N$ row variables with $N$ possible columns each. The rule of product gives the displayed bounds; assigning variables in one prescribed order avoids multiplying again by the number of variable orderings.

With $k$ mutually nonattacking prescribed queens incorporated as singleton constraint domains, the corresponding bounds improve toIn Model 1 only the $k$ prescribed occupied cells have been fixed in this estimate; immediate deletion of attacked cells tightens it further. In Model 3 consistent clues occupy $k$ distinct rows. If the clues are inconsistent, preprocessing can reject the instance immediately.

These are upper bounds on leaves, rather than exact attained counts for a fully specified pruning implementation. Ordinary backtracking rejects inconsistent partial assignments and often creates far fewer leaves; a stopped branch is itself a leaf even if not all variables were assigned. Such early leaves still obey the backtracking leaf bound, since distinct leaves describe disjoint nonempty families of full domain assignments when constraints are ignored. Counting only possible complete nonattacking assignments is a different question. For example, row/column restrictions alone reduce full assignments to at most $N!$ in Model 3, but that number does not directly count failed partial leaves. Exact counts depend on variable ordering and constraint propagation, neither of which is specified.

Use Model 3 and keep every prescribed row at its prescribed column. Initialize one queen in every other row, and minimize the conflict countThis sum counts attacking pairs; $E=0$ is exactly a valid completion. A neighbor changes the column of one unfixed row. Evaluate such neighbors and move to one with lower $E$, breaking equal choices arbitrarily. Minimizing $E$, or maximizing $-E$, is hill climbing on complete domain assignments; these assignments need not yet satisfy the inter-row constraints. Fixed rows are never moved.

The min-conflicts algorithm chooses a conflicted unfixed queen and places it in a column giving the smallest conflict count against the other queens. Recomputing only the affected pair contributions makes a move cheaper than reevaluating every pair. Equal-cost moves can help cross plateaus; bounded sideways moves or repeated random starts of only the unfixed queens can escape some traps. These modifications still preserve the prescribed positions.

Return a board only after checking $E=0$ and every prescribed position. A local minimum with positive $E$ is not proof of impossibility. A queens completion problem may be unsatisfiable even when its prescribed queens do not attack each other; unrestricted restart policies give no finite worst-case success bound. If every row is fixed, simply validate the one board. For a guaranteed decision procedure use finite backtracking, possibly with constraint propagation, instead of relying on hill climbing.