Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems (A12075W1)

Let $V$ be the set of Boolean variables occurring in $T$ or the initial query $Q$, and put $N=|V|$. Represent a current query by a subset $R\subseteq \{\neg p:p\in V\}$: the Boolean literals in this set are the outstanding obligations. The initial state is $R=Q$, and the goal test is $R=\varnothing$.

An action chooses a Horn clause $C\in T$ with positive Boolean literal $p$, provided $\neg p\in R$. Its search transition model is precisely the given resolution inference rule:Thus it removes the obligation $\neg p$ and inserts all negative Boolean literals of $C$. Repeated Boolean literals merge because queries are sets. A Horn clause without a positive Boolean literal supplies no action under the rule specified in this paper; it must not be treated as an additional way of finishing the query.

Give every action unit cost. A graph path with $\ell$ actions gives a proof containing $\ell +1$ queries, so minimizing either quantity gives the same shortest proof. Uniform-cost search orders the search frontier by the number of actions already taken and applies the goal test when removing a search node for expansion. Recording parent actions reconstructs the proof.

There are at most two choices, present or absent, for each of the $N$ negative Boolean literals. ThereforeThis bounds the state space, including the empty query, rather than the possibly infinite search tree of action histories.^[ref]

A-star search is best-first search with priorityHere $u$ is a search node, $s(u)$ is its state, $g(u)$ is its accumulated path cost, and $h^{\ast }(s)$ is the minimum remaining cost to any goal state, interpreted as $\infty$ if no goal is reachable. The inequality defines an admissible heuristic. Thus $f(u)$ is a lower bound on the cost of any solution extending that particular action history.

Initialize the search frontier with the root. Repeatedly remove a search node of least $f$, apply the goal test, and, if it is not a goal, insert its applicable-action children with their updated $g$ and $f$. In tree search, different action histories remain distinct search nodes even when they reach the same state; there is no global visited-state set.

For the finite branching factor and unit costs here, an admissible heuristic ensures that any first goal removed is optimal. If a cheaper solution existed, the search frontier would contain an unexpanded prefix of it with $f$ at most that cheaper cost, contradicting selection of the more expensive goal. Nonnegative $h$ also means only finitely many search nodes can have $f$ below any fixed finite cost, so a finite solution will eventually be reached. This does not guarantee termination when no proof exists.

Termination is not guaranteed. TakeBoth members of $T$ are valid Horn clauses with distinct underlying Boolean variables. The only possible continuation alternatesThe empty query is unreachable. With the admissible heuristic $h=0$, ordinary A-star search keeps generating the next search node forever, despite there being only two reachable states.

A modification requiring no additional stored state collection is to impose the known search depth boundThe unit-cost $g$ already stored by A-star search is also its search depth; the bound is a scalar computed from the input, not a closed set. Apply the goal test before refusing expansion at the bound.

To prove completeness of this modification, remove any segment between two equal states in a successful proof. The successor choices after the later occurrence are available at the earlier occurrence because the search transition model depends only on the current query. Repeating this removal gives a proof with no repeated states, hence at most $2^N-1$ actions. In particular, a shortest proof never needs a repeated state, since every removed segment has positive cost. The depth restriction therefore preserves a shortest proof whenever one exists.

The restricted search tree has finite depth and finite branching factor, so it is finite. A-star search must then either remove a goal or exhaust the search frontier and report failure. Its existing search frontier may still be large; the modification saves a separate visited-state collection, not all storage used by tree search.

Yes: $h_1(R)=|R|$ is an admissible heuristic. One application of the resolution inference rule removes just one current negative Boolean literal. It may add other negative Boolean literals, and some of those may already occur, but it cannot remove any other current obligation. ConsequentlyIf $\ell$ actions lead from $R$ to $\varnothing$, applying this inequality at every step gives $0\ge |R|-\ell$. ThusIt is also a consistent heuristic, since $h_1(R)\le 1+h_1(R^{\prime })$ and $h_1(\varnothing )=0$. In particular, merging duplicate obligations cannot invalidate the lower bound: removing several duplicates from the representation never counts as removing several distinct members of a set.

Use the shortest path distances in the directed dependency graph to defineThe additional $1$ counts the final use of a positive unit Horn clause, which corresponds to a fact rather than an edge of $G$.

To justify the new lower bound, consider any complete proof from $R$ and fix $\neg p\in R$. At some step this obligation must be removed using a Horn clause with head $p$. If that Horn clause is the fact $\{p\}$, we have already found a dependency graph path of length zero ending at a fact. Otherwise select one negative body Boolean literal $\neg q$. Immediately after the step it belongs to the query, whether newly inserted or merged with an existing obligation. It must subsequently be removed. Record the edge $p\to q$ and repeat this argument at its later removal.

The selected removal times strictly increase. Since the proof is finite and ends with no obligations, this chain eventually uses a fact. A proof of $\ell$ actions therefore produces a dependency walk of at most $\ell -1$ edges from $p$ to a fact. Removing any cycles from that walk gives $d_G(p)\le \ell -1$. Hence $1+d_G(p)\le \ell$ for every initial obligation. If $d_G(p)=\infty$, no such proof exists. Combining this bound with the admissible heuristic $|R|$ by taking their maximum preserves admissibility.

For a strict improvement, useHere $d_G(p)=2$, so $h_1(R)=1$ while $h_2(R)=3$. The three successive obligations are $\neg p,\neg q,\neg r$, followed by the empty query, so the improved bound is exact.

Do not sum all the values $1+d_G(p)$ without an additional argument: different obligations may share work. For example, with $T=\{\{p,\neg r\},\{q,\neg r\},\{r\}\}$, the query $\{\neg p,\neg q\}$ takes three actions, while that sum would be four.

When the values of several admissible heuristics are already available, choose their maximum:Every $h_i(R)\le h^{\ast }(R)$, so their maximum is still an admissible heuristic. It has heuristic dominance over their minimum and their arithmetic average, which are also admissible heuristics but give no larger lower bound. Thus the maximum supplies the most informative generally valid choice among these alternatives.

Their sum can overestimate by counting the same remaining action repeatedly. If two heuristic functions both give the exact value $1$ at a state one action from the goal, their sum gives $2$. A valid sum requires extra structure such as dividing each action's cost between the component estimates; admissibility of the components alone does not provide that structure.

Larger admissible values reduce the region $g+h<C^{\ast }$ that A-star search must expand before an optimal solution of cost $C^{\ast }$ can be removed. This is a statement about heuristic dominance, not a strict claim about running time under every tie-breaking rule or evaluation cost.

Index the coins so that $c_1$ is smallest and $c_n$ largest. Choose $s_1$ as the initial stack and $s_2$ as the destination, assuming $k\ge 2$. The static predicate facts describing size areNo size comparison with $g$ is needed: moving onto empty ground will have a separate action schema. The initial STRIPS state isUnder the closed-world assumption, all other ground ground atoms are false. In particular, the initial state contains just one predicate fact naming the top of each stack. The predicate $\mathrm{OnTop}$ names the immediate support, not every coin farther below.

An explicit positive conjunctive goal is the following set of required ground atoms:A state succeeds when it contains $G_{\mathrm{goal}}$. The static predicate facts in $S_{\mathrm{size}}$ persist automatically. Starting from $I$, the planning state invariants proved below make this goal exactly the desired completed stack on $s_2$ with all other stacks empty. If any new stack is acceptable, the choice of $s_2$ loses no generality because the initially empty stacks are interchangeable.

Use two STRIPS action schemas, for a destination topped by a coin and for an empty destination. In both, $x$ is a coin, $s,t$ are distinct stack constants, and $y$ is either a different coin or $g$. In the first, $z$ is a coin distinct from $x$ and, when $y$ is a coin, also distinct from $y$. These are restrictions on action grounding, so no new type or inequality predicates are needed.

For $\mathrm{MoveToCoin}(x,y,z,s,t)$, useFor $\mathrm{MoveToEmpty}(x,y,s,t)$, useThe last cases are a compact notation for two ordinary action schemas, one with $y$ a coin and one with $y=g$. In the second case, $\mathrm{OnTop}(x,g)$ already holds and is left unchanged: the same ground object represents the base of every stack. Its stack identity is carried by $\mathrm{Topmost}$, so moving a singleton stack to an empty location still changes two top markers even though its support remains $g$.

Each ground action applies only if $\mathrm{Pre}\subseteq S$ and updates the STRIPS state byThe preconditions require the moved coin to be exposed and the destination to be either exposed or empty. A coin destination additionally requires the moved coin to be smaller. The delete list removes its old support relation when that support changes, removes its old source-top marker, and removes the destination's old top marker. The add list exposes its former support and installs it as the destination top.

To prove that no incorrect plans arise, induct on the action history. Initially every coin has exactly one support; the stacks are disjoint decreasing chains ending at $g$; and each stack has exactly one correct top marker. An applicable action removes just the top coin from one such chain and attaches it to a different chain, or creates a singleton chain. The size precondition preserves decreasing order; distinct stack parameters prevent moving onto one's own stack; and updating both top markers preserves their accuracy. The unchanged chain segments retain their support relations. These planning state invariants therefore hold after every action. Only the $k$ named stacks can be used, enforcing the stack limit.

Conversely, every legal physical move has a source top $x$, a uniquely determined former support $y$, and either an empty target or a target top $z$ larger than $x$. The corresponding ground action has exactly these preconditions and effects. Thus the encoding permits all legal moves and preserves physical legality from the initial state.^[ref]

Move the three coins as follows, with $c_1$ smallest:

Every moved coin is exposed, and the last two moves put a smaller coin on a larger one. ThusFive is also optimal here: before the first move of $c_3$, both smaller coins must leave $s_1$. Neither can make its only move directly to the final destination and remain there, because it would obstruct the eventual arrival of $c_3$. Each smaller coin therefore needs at least two moves. Those four small-coin moves and at least one move of $c_3$ give the matching lower bound.

In terms of minimum plan length, allowing more stacks can only help:Every legal plan using at most $k$ stacks remains legal with $k+1$ available: simply ignore the new stack. The inequality need not be strict. For $n=1$, one move suffices for every $k\ge 2$.

With $k\ge n+1$, put each of the $n-1$ smaller coins on its own spare stack, move the largest coin to the destination, and then place the smaller coins on it in decreasing size order. This uses $2n-1$ moves. Every smaller coin must leave the initial stack before the largest coin's first move. It cannot move just once directly to the final stack and stay there, since that would block the largest coin's eventual arrival. Thus each smaller coin requires at least two moves, while the largest coin requires at least one. HenceCompared with the three-stack value $2^n-1$, the physical task can therefore become substantially easier.

The difficulty of finding an optimal plan is a different issue. Each legal state is determined by assigning every coin to one of the $k$ labelled stacks, whose size order is then forced. There are $k^n$ such assignments, so the state space and possible branching factor grow with $k$. An uninformed search algorithm can therefore face more alternatives even when the optimal plan becomes shorter. Likewise, a simple recursive strategy for three stacks need not immediately supply the best strategy with more stacks. The defensible answer is that the required number of moves never increases, while computational search effort need not decrease.

Two general constructions are delete-relaxation heuristics and abstraction heuristics. Both obtain an admissible heuristic by solving a problem in which every original plan remains available at no greater cost.

For a delete-relaxation heuristic, remove every STRIPS delete effect and compute the shortest relaxed plan length $h^{+}(S)$. A relaxed action never makes a true fact false. Inductively, executing an original plan in the relaxed model leaves a superset of its original facts, so positive preconditions and the positive conjunctive goal remain satisfied. ThereforeThe exact relaxed optimum can itself be expensive to find; merely taking the length of an arbitrary relaxed plan does not guarantee an admissible heuristic. One can instead use a proven lower bound on the relaxed optimum.

For this coin encoding, removing delete effects loses the requirement to free an occupied stack and the requirement to destroy and later rebuild support relations. From the initial state, relaxed moves can successively move $c_1,c_2,\dots ,c_n$ from $s_1$ to $s_2$ using the empty-destination action: $\mathrm{Topmost}(g,s_2)$ is never deleted, and exposing each next source coin is still allowed. The original support-chain goal facts are never deleted either. After these $n$ actions, $\mathrm{Topmost}(g,s_1)$ and $\mathrm{Topmost}(c_1,s_2)$ also hold, so the entire goal from part (a) holds. Thus $h^{+}(I)\le n$, showing why this relaxation misses much of the exponential work needed with three stacks.

For an abstraction heuristic, project states onto selected information and project each action onto its effect on that information. Forgetting a selected collection of planning fluents, and their preconditions and goals, gives one general construction for STRIPS. Define the abstract transition relation to include every projected original transition, with cost at most the original cost. The exact abstract distance is then a lower bound because any original goal-reaching graph path projects to an abstract goal-reaching walk:For the coin puzzle, a useful state abstraction remembers the stacks occupied by a chosen subset of coins and ignores the other coins, contracting the support chains past ignored coins. Moving an ignored coin leaves the abstract state unchanged; moving a retained coin is a legal move in the smaller Tower of Hanoi instance. Precomputing exact abstract goal distances gives a pattern database. This can retain stacking and spare-stack restrictions that the delete-relaxation heuristic loses. Larger retained subsets give potentially stronger information but require more storage and preprocessing. Maxima of these admissible heuristics remain safe; unqualified sums can double-count moves.

Use one variable $X_{r,c}$ for each cell, with $1\le r,c\le 9$. An empty cell has constraint domain $\{1,\dots ,9\}$; a clue containing $d$ has singleton constraint domain $\{d\}$. Thus all clues are retained automatically.

For every row $r$ impose $\mathrm{AllDifferent}(X_{r,1},\dots ,X_{r,9})$, and for every column $c$ impose $\mathrm{AllDifferent}(X_{1,c},\dots ,X_{9,c})$. For each $a,b\in \{0,1,2\}$ impose an all-different constraint onThese are the nine prescribed boxes. There are 27 all-different constraints altogether. Nine pairwise distinct values chosen from a set of nine values must use every value exactly once, so these restrictions are precisely the Sudoku requirements. Equivalently, expand each all-different constraint into pairwise binary constraints $X_{r,c}\ne X_{r^{\prime },c^{\prime }}$ for cells sharing a row, column, or box.

Choose the distinct values of $(X_1,X_2,X_4)$ and call them $(a,b,c)$. There are $3!=6$ choices. Constraint (5), on $(X_1,X_4,X_9)$, immediately forces $X_9=b$.

Constraints (2) and (3) require $X_5\ne X_2=b$ and $X_5\ne X_4=c$, respectively. Since the constraint domain has exactly three values, $X_5=a$. Constraint (2) now forces $X_3=c$, and constraint (3) forces $X_6=b$. Finally, constraint (4) permits $(X_7,X_8)=(a,c)$ or $(c,a)$.

Every choice just described satisfies all five all-different constraints, and the forced-value argument shows there are no other possibilities. HenceIn the order $(X_1,\dots ,X_9)$, the two forms arewhere $(a,b,c)$ ranges over the six permutations of $(0,1,2)$.

The constraint hypergraph has one vertex for each of $X_1,\dots ,X_9$ and one hypergraph edge for each constraint scope:Here $i$ abbreviates $X_i$. These five scopes follow the corrected source.^[ref] The diagram uses the incidence representation: round nodes are the original variables, square nodes represent hypergraph edges, and a joining line means that the variable belongs to that constraint scope. The square nodes are not extra variables of $P$.

In particular, the central pattern involving $X_2,X_4,X_5$ forms a cycle through three constraint scopes; the scopes cannot themselves simply be joined into a valid tree decomposition without an additional bag.

Use the ordinary treewidth of the primal graph of the constraint hypergraph: two variables are adjacent whenever they occur together in an all-different constraint. Equivalently, a tree decomposition of this constraint hypergraph has a bag containing every constraint scope, together with the running-intersection requirement for each variable. This is distinct from taking the treewidth of its incidence drawing.

Introduce a central bag $B_0=\{2,4,5\}$ and the five scope bagsJoin $B_0$ to each of $B_1,B_2,B_3$, join $B_3$ to $B_4$, and join $B_1$ to $B_5$:

Every constraint scope is contained in its own bag, and every variable occurs. The nontrivial running-intersection checks are: $2$ occurs along $B_1-B_0-B_2$; $4$ along the connected branches $B_5-B_1-B_0-B_3$; $5$ along $B_2-B_0-B_3$; $1$ along $B_1-B_5$; and $6$ along $B_3-B_4$. Each of the other variables occurs in just one bag. This is therefore a valid tree decomposition of width $3-1=2$.

Conversely, any of the original three-variable constraint scopes forms a clique of size three in the primal graph. Such a clique must be contained in one bag of every tree decomposition, forcing width at least two. The upper and lower bounds agree:

Always true. An all-different constraint of arity $k$ requires $k$ distinct values. If $|D|<k$, the pigeonhole principle makes even one such constraint impossible. Since $m>0$, at least one is present, and consequently

True in some cases and false in others: the two numerical inequalities do not guarantee a solution.

For an unsatisfiable example satisfying both inequalities, take six variables, a constraint domain with five values, and $k=4$, $m=3$, with all-different constraints onAny pair of the six variables occurs together in at least one of these scopes: view the variables as the three pairs $\{1,2\},\{3,4\},\{5,6\}$, and each scope as the union of two pairs. All six values must therefore be distinct. This is impossible with five available values, even though $5>4$ and $5>3$.

For a satisfiable example with the same $k,m,|D|$, take three disjoint groups of four variables and impose one all-different constraint on each group. Assign values $1,2,3,4$ separately in every group. All three constraints hold with $D=\{1,2,3,4,5\}$.These examples concern the intended cases in which the antecedent holds; they do not rely on vacuous truth of an implication.

True in some cases and false in others. Equality of the constraint domain size and treewidth does not decide satisfiability.

For an unsatisfiable example, let $D=\{0,1\}$ and impose the three binary all-different constraints $X_1\ne X_2$, $X_2\ne X_3$, and $X_3\ne X_1$. The primal graph is a triangle, with treewidth two. It needs three different values, so no solution exists despite $|D|=\mathrm{tw}(P)=2$.

For a satisfiable example, take four variables with the same constraint domain and constraintsIts primal graph is a four-cycle of treewidth two: bags $\{1,2,3\}$ and $\{1,3,4\}$ give width two, while width one would require a forest. The assignment $(0,1,0,1)$ satisfies all constraints.

Always true. Replace every all-different constraint by the pairwise inequalities on its scope. Then solutions are precisely the proper graph colourings of the primal graph using values from $D$ as colours. Put $t=\mathrm{tw}(P)$.

A graph of treewidth $t$ has a proper graph colouring with at most $t+1$ colours. Here is a constructive proof. In a width-$t$ tree decomposition, remove any leaf bag contained in its neighbor. If more than one bag remains, a leaf bag has a vertex absent from its neighbor. The running-intersection property means that vertex occurs only in the leaf bag, so every neighbor of the vertex belongs to that bag. It has at most $t$ neighbors. If only one bag remains, it has at most $t+1$ vertices and the same degree bound holds.

Remove the chosen vertex and repeat; deleting vertices cannot increase the width of the restricted tree decomposition. Now colour in reverse removal order. At most $t$ already coloured neighbors forbid colours, so one of $t+1$ colours is always available. Since the integer inequality $|D|>t$ gives $|D|\ge t+1$, this produces a satisfying assignment:The common unrestricted constraint domain and the exclusively all-different constraints are essential: arbitrary constraint relations do not reduce to graph colouring in this way.

Always true for a nonempty finite constraint domain, as conventionally assumed. Write $q=|D|$ and identify its values with $\{0,\dots ,q-1\}$. For each satisfying assignment $(x_1,\dots ,x_n)$, simultaneously replace every value byThis permutation of the common constraint domain preserves every equality and inequality, hence every all-different constraint. The resulting $q$ assignments are distinct: equality of even one coordinate before and after a shift forces $a=0(\mathrm{mod}q)$. There is at least one variable, since $m>0$ and $k\ge 2$.

The cyclic group of shifts therefore partitions the solution set into disjoint orbits of size $q$. It follows thatThe conclusion includes an unsatisfiable instance, whose solution count is zero. Full permutation group orbits need not have size $q!$, because unused values can be permuted without changing an assignment; the cyclic-shift argument avoids that mistake.

If an empty constraint domain is permitted, there are zero assignments here, but the wording “divisible by $|D|$” then asks about divisibility by zero, which is ordinarily left undefined. The asserted divisibility uses the standard nonempty-domain convention, and the no-solution conclusion still holds for that degenerate input.