Past exam of the computer science course of the University of Oxford / 2015 / Intelligent systems / 1

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.