CS2910 2024 Past Paper solution

Question 1: Best-First Search

(a) Briefly discuss the idea of the evaluation function in best-first search and explain how it affects the selection of which node to explore next.

Answer:
In best-first search, the evaluation function, denoted as $f(n)$, is used to estimate the “desirability” of expanding a given node $n$. The node with the “best” (typically lowest) evaluation function value is chosen for expansion next.

(b) Define equations based on a heuristic function for (i) greedy search and (ii) $A^{*}$ search. Briefly explain all functions you use.

Answer:
Let $h(n)$ be the heuristic function, which estimates the cost from node $n$ to the goal state. Let $g(n)$ be the cost from the initial state to node $n$.

(i) Greedy Search:
The evaluation function for greedy search is:
$f(n) = h(n)$

$f(n)$: The evaluation function for node $n$. It represents the estimated cost from node $n$ to the goal.
$h(n)$: The heuristic function. It estimates the cost from the current node $n$ to the closest goal state. Greedy search prioritizes nodes that appear closest to the goal based solely on this estimate, without considering the cost already incurred to reach $n$.

(ii) $A^{*}$ Search:
The evaluation function for $A^{*}$ search is:
$f(n) = g(n) + h(n)$

$f(n)$: The evaluation function for node $n$. It estimates the total cost of the path from the initial state, through node $n$, to the goal state.
$g(n)$: The cost from the initial state to the current node $n$. This is the actual cost incurred to reach $n$ so far.
$h(n)$: The heuristic function. It estimates the cost from the current node $n$ to the closest goal state. $A^{*}$ search balances the cost incurred to reach the current node with the estimated cost to the goal, aiming to find the path with the lowest total cost.

(c) In both graphs of Fig. 1, A denotes the initial state, D denotes the goal and a number next to an edge denotes the cost of moving from a node to another. Compare the solutions’ cost found when applying the greedy search algorithm on the graphs to explain why greedy search is not optimal.

Answer:
Let’s apply greedy search to both graphs in Figure 1, with A as the initial state and D as the goal. Greedy search always expands the node that is estimated to be closest to the goal (i.e., has the lowest $h(n)$ value). Without an explicit heuristic table, we infer $h(n)$ values from the path costs to the goal for the purpose of demonstrating optimality.

Graph (a):
- From A, possible paths are A $\rightarrow$ B (cost 4) or A $\rightarrow$ C (cost 3) or A $\rightarrow$ D (cost 7).
- To apply greedy search, we need heuristic values for B and C. Let’s assume the heuristic is simply the remaining cost if we know the optimal path from B and C to D.
  - Path A $\rightarrow$ B $\rightarrow$ D: Cost = 4 + 1 = 5
  - Path A $\rightarrow$ C $\rightarrow$ D: Cost = 3 + 1 = 4
  - Path A $\rightarrow$ D: Cost = 7
- If we assume the heuristic function $h(n)$ gives the direct edge cost to D if available, or an estimate of the remaining path:
  - From A, $h(B)$ could be 1 (cost B to D), $h(C)$ could be 1 (cost C to D).
  - Greedy search would likely choose A $\rightarrow$ C first (cost 3), then C $\rightarrow$ D (cost 1). The path found would be A $\rightarrow$ C $\rightarrow$ D with a total cost of 3 + 1 = 4. This is the optimal path for graph (a).
Graph (b):
- From A, possible paths are A $\rightarrow$ B (cost 4) or A $\rightarrow$ C (cost 3) or A $\rightarrow$ D (cost 10).
- To apply greedy search, we assume $h(B)$ would be 1 (cost B to D) and $h(C)$ would be 5 (cost C to D).
- Greedy search from A would compare $h(B)=1$ and $h(C)=5$. It would choose A $\rightarrow$ B because $h(B)$ is smaller.
- Then, from B, it would go to D (cost 1).
- The path found by greedy search would be A $\rightarrow$ B $\rightarrow$ D with a total cost of 4 + 1 = 5.
- However, let’s look at the alternative path: A $\rightarrow$ C $\rightarrow$ D. The cost for this path is 3 + 5 = 8.
- The direct path A $\rightarrow$ D has a cost of 10.
- The optimal path for graph (b) is A $\rightarrow$ B $\rightarrow$ D with cost 5.

Explanation of why greedy search is not optimal:
In graph (a), greedy search finds the optimal path (A $\rightarrow$ C $\rightarrow$ D, cost 4).
In graph (b), greedy search finds A $\rightarrow$ B $\rightarrow$ D with a cost of 5. This is indeed the optimal path for graph (b).

My initial analysis for graph (b) to demonstrate sub-optimality using the provided graph might have been flawed. Let’s re-evaluate the classic reason greedy search is not optimal, which is that it only considers the heuristic estimate (estimated cost to goal) and ignores the path cost incurred so far ($g(n)$). This can lead it to choose a path that looks promising initially but ends up being more expensive overall.

Consider if graph (b) had different costs:
Let A $\rightarrow$ B cost = 1, B $\rightarrow$ D cost = 10. (Path A $\rightarrow$ B $\rightarrow$ D = 11)
Let A $\rightarrow$ C cost = 10, C $\rightarrow$ D cost = 1. (Path A $\rightarrow$ C $\rightarrow$ D = 11)
Let A $\rightarrow$ D cost = 12.
Assume $h(B)=10$ and $h(C)=1$.
Greedy search would pick A $\rightarrow$ C (cost 10), then C $\rightarrow$ D (cost 1), for a total cost of 11.
If the actual optimal path was A $\rightarrow$ B (cost 1) and then B $\rightarrow$ D (cost 10) for total 11.

Let’s use the given graph (b) to show it’s not guaranteed optimal.
Greedy search prioritizes low $h(n)$. Suppose we are at A.
If $h(B)=1$ (cost from B to D) and $h(C)=5$ (cost from C to D).
Greedy chooses A $\rightarrow$ B (cost 4) because $h(B)=1$ is less than $h(C)=5$. Path found: A $\rightarrow$ B $\rightarrow$ D with cost 4+1 = 5. This is the optimal path in graph (b).

The provided graph (b) does not clearly demonstrate sub-optimality for greedy search, as greedy search finds the optimal path here. A typical example to show greedy search is not optimal involves a scenario where a locally good choice (low $h(n)$) leads to a much higher overall path cost compared to another path with a higher initial $h(n)$ but a lower total cost.

Let’s construct a scenario that clearly shows non-optimality of greedy search:
Initial State: S, Goal State: G
Edges: S $\rightarrow$ A (cost 1), S $\rightarrow$ B (cost 10)
A $\rightarrow$ G (cost 100)
B $\rightarrow$ G (cost 2)
Heuristics: $h(A) = 5$, $h(B) = 1$

Greedy search from S:

Evaluate A: $h(A) = 5$.
Evaluate B: $h(B) = 1$.
Greedy chooses B because $h(B)$ is lower. Path: S $\rightarrow$ B (cost 10).
From B, go to G (cost 2).
Total cost for greedy path: S $\rightarrow$ B $\rightarrow$ G = 10 + 2 = 12.

Optimal path:

Path S $\rightarrow$ A $\rightarrow$ G = 1 + 100 = 101.
Path S $\rightarrow$ B $\rightarrow$ G = 10 + 2 = 12.
In this constructed example, greedy finds the optimal path.

Let’s try again with the provided graphs, assuming what “greedy” would do.
For graph (a): A (start), D (goal)
Paths:

A $\rightarrow$ B $\rightarrow$ D: cost 4+1 = 5
A $\rightarrow$ C $\rightarrow$ D: cost 3+1 = 4
A $\rightarrow$ D: cost 7
Assume $h(B)=1$ and $h(C)=1$ (the cost to D).
Greedy from A:
It needs to decide between paths A $\rightarrow$ B and A $\rightarrow$ C.
If it expands A:
Successors are B, C, D.
Suppose the heuristic is the direct edge cost to D if available, or the estimated cost from the node to the goal.
If we consider the states B and C:
Path to D from B is 1. So $h(B) = 1$.
Path to D from C is 1. So $h(C) = 1$.
Greedy chooses A $\rightarrow$ C (cost 3) if it picks lowest path cost from A.
If it expands based on $h(n)$ of children:
$f(B) = h(B) = 1$
$f(C) = h(C) = 1$
It might expand B first or C first.
If C is chosen (e.g., tie-breaking): A $\rightarrow$ C (cost 3), then C $\rightarrow$ D (cost 1). Total cost = 4. This is optimal for (a).

For graph (b): A (start), D (goal)
Paths:

A $\rightarrow$ B $\rightarrow$ D: cost 4+1 = 5
A $\rightarrow$ C $\rightarrow$ D: cost 3+5 = 8
A $\rightarrow$ D: cost 10
Assume $h(B)=1$ and $h(C)=5$.
Greedy from A:
$f(B) = h(B) = 1$
$f(C) = h(C) = 5$
Greedy will choose to expand B (because $h(B)=1$ is smaller).
Path chosen: A $\rightarrow$ B (cost 4). Then from B, goes to D (cost 1). Total cost = 4+1 = 5. This is also optimal for (b).

The question asks to compare solutions to explain why greedy search is not optimal. The provided graphs (a) and (b) both show scenarios where greedy search does find the optimal path. This makes it difficult to use these specific graphs to demonstrate non-optimality.

To answer this question as intended, one must use a general example or slightly modify the interpretation of the graphs to illustrate the point. The core reason greedy search is not optimal is that it is purely guided by the heuristic function $h(n)$ and does not take into account the path cost $g(n)$ already incurred to reach the current node. This means it can choose a path that looks promising (low $h(n)$) but has a high initial cost ($g(n)$), leading to a suboptimal total cost.

Revised Answer for (c) focusing on the general principle:
Greedy search is not optimal because it only considers the estimated cost from the current node to the goal ($h(n)$) and completely ignores the actual cost incurred to reach the current node from the start state ($g(n)$). This “myopic” approach can lead it down a path that appears good locally but ultimately results in a higher total path cost compared to other paths.

Let’s illustrate with a hypothetical scenario similar in structure to what the exam question implies, even if Figure 1 doesn’t perfectly demonstrate it:
Imagine a situation where:

Path 1: Start $\rightarrow$ Node X (cost = 100). From Node X, $h(X) = 5$. Total apparent cost for greedy: 5.
Path 2: Start $\rightarrow$ Node Y (cost = 1). From Node Y, $h(Y) = 10$. Total apparent cost for greedy: 10.

Greedy search would expand Node X first because $h(X)$ (5) is lower than $h(Y)$ (10). If the actual path cost from X to the goal is 5, the total cost for Path 1 would be 100 + 5 = 105.
If the actual path cost from Y to the goal is 10, the total cost for Path 2 would be 1 + 10 = 11.
In this case, greedy search would choose Path 1 (total cost 105) over Path 2 (total cost 11), leading to a suboptimal solution. This demonstrates that by only looking at the heuristic $h(n)$, greedy search can miss the true optimal path that has a higher $h(n)$ value but a significantly lower $g(n)$ value.

(d) In the context of the $A^{*}$ algorithm explain what an admissible heuristic function is.

Answer:
In the context of the $A^{}$ algorithm, an admissible heuristic function $h(n)$ is one that never overestimates the cost to reach the goal from node $n$. That is, for every node $n$ in the search space, the estimated cost $h(n)$ must be less than or equal to the true cost $h^(n)$ of the optimal path from $n$ to the goal.
Formally: $h(n) \le h^(n)$ for all nodes $n$.
Admissibility is a crucial property for $A^{}$ search because it guarantees that if a solution exists, $A^{*}$ will find an optimal one (i.e., it is complete and optimal).

(e) In order to apply $A^{*}$ search on the graph of Fig. 2, using A as the initial state and E as the goal, we need an admissible heuristic function. Is the function specified by the table below admissible? Justify your answer.

Answer:
To check if the heuristic function $H$ is admissible, we need to verify if $H(n) \le h^(n)$ for all nodes $n$, where $h^(n)$ is the true cost from node $n$ to the goal (E in this case).

Let’s calculate the true cost $h^*(n)$ for each node to the goal E from Figure 2:

$h^*(E) = 0$ (Already at goal)
$h^(D)$: Path D $\rightarrow$ E, cost = 3. So, $h^(D) = 3$.
$h^(C)$: Path C $\rightarrow$ D $\rightarrow$ E, cost = 2 + 3 = 5. So, $h^(C) = 5$.
$h^*(B)$:
- Path B $\rightarrow$ D $\rightarrow$ E: cost = 5 + 3 = 8.
- Path B $\rightarrow$ E: cost = 12.
- So, $h^*(B) = \min(8, 12) = 8$.
$h^*(A)$:
- Path A $\rightarrow$ B $\rightarrow$ D $\rightarrow$ E: cost = 1 + 5 + 3 = 9.
- Path A $\rightarrow$ B $\rightarrow$ E: cost = 1 + 12 = 13.
- Path A $\rightarrow$ C $\rightarrow$ D $\rightarrow$ E: cost = 4 + 2 + 3 = 9.
- So, $h^*(A) = \min(9, 13, 9) = 9$.

Now, let’s compare these true costs ($h^*(n)$) with the given heuristic values ($H(n)$) from the table:

State	Given H	True $h^*$	Admissible? ($H \le h^*$)
A	7	9	Yes ($7 \le 9$)
B	6	8	Yes ($6 \le 8$)
C	2	5	Yes ($2 \le 5$)
D	1	3	Yes ($1 \le 3$)
E	0	0	Yes ($0 \le 0$)

Since for every state $n$, the given heuristic value $H(n)$ is less than or equal to the true optimal cost $h^*(n)$ to the goal, the function specified by the table is admissible.

Question 2: Logical Learning and the Role of Knowledge

(a) Using a generic logical schema, briefly explain the aim of inductive learning.

Answer:
The aim of inductive learning is to infer a general rule or hypothesis (H) from a set of observed examples (E). This hypothesis should ideally explain the given examples and generalize well to unseen examples. In a generic logical schema, this can be represented as finding a hypothesis H such that:
$KB \land H \models E$
where:

$KB$ (Knowledge Base): Represents any existing background knowledge or prior beliefs.
$H$ (Hypothesis): The general logical rule or theory being learned.
$E$ (Examples): A set of positive and/or negative training examples.
$\models$ (Entailment): Means that $KB \land H$ logically entails (implies) $E$.
The goal is to find an $H$ that is consistent with the examples and potentially provides new knowledge.

(b) Specialise the inductive learning schema you used in part 2(a) to define logically the decision tree shown in Fig. 3. This tree shows how an AI program should advise a user whether to go hiking.

Answer:
The decision tree in Figure 3 determines whether to “GoHiking” based on “Outlook”, “Temperature”, and “Wind”. We can translate this into a set of logical implications (rules) as our hypothesis H.

Let:

GoHiking be the proposition indicating whether to go hiking (T for True, F for False).
Outlook(X) be the proposition for the outlook, where X can be Sunny, Partly_Cloudy, Cloudy.
Temperature(Y) be the proposition for temperature, where Y can be High, Normal.
Wind(Z) be the proposition for wind, where Z can be Strong, Weak.

Based on the decision tree:

If Outlook is “Partly cloudy”, then GoHiking is True.
Outlook(Partly_Cloudy) $\rightarrow$ GoHiking
If Outlook is “Sunny”:
- If Temperature is “High”, then GoHiking is False.
  Outlook(Sunny) $\land$ Temperature(High) $\rightarrow$ $\neg$GoHiking
- If Temperature is “Normal”, then GoHiking is True.
  Outlook(Sunny) $\land$ Temperature(Normal) $\rightarrow$ GoHiking
If Outlook is “Cloudy”:
- If Wind is “Strong”, then GoHiking is False.
  Outlook(Cloudy) $\land$ Wind(Strong) $\rightarrow$ $\neg$GoHiking
- If Wind is “Weak”, then GoHiking is True.
  Outlook(Cloudy) $\land$ Wind(Weak) $\rightarrow$ GoHiking

This set of logical rules represents the hypothesis H learned from the decision tree. Given a set of examples E (e.g., Outlook(Sunny) $\land$ Temperature(Normal) as an example where GoHiking is true), our background knowledge (KB) might include facts like Outlook(Sunny) and Temperature(Normal), and the hypothesis H (the rules above) would then logically entail GoHiking.

(c) Briefly explain the entailment constraint for knowledge learning and state how you would change it to support knowledge-based inductive learning.

Answer:
The entailment constraint for knowledge learning typically states that the learned hypothesis $H$ and any existing background knowledge $KB$ must logically entail the observed examples $E$. Formally: $KB \land H \models E$. This means that the hypothesis, in conjunction with what is already known, must be sufficient to explain or predict all the given training examples.

To support knowledge-based inductive learning, the entailment constraint can be broadened to incorporate a notion of learnability or refinement of the knowledge base itself, rather than just learning new rules from scratch that entail observations. This often involves relaxing the strict requirement for $H$ to explain all examples perfectly or allowing for the revision of $KB$.

One common way to change it is to adopt a noisy or uncertain entailment model, where $KB \land H$ should entail $E$ with a high probability or within a certain error margin, rather than strict logical truth. This acknowledges that real-world data might be imperfect or contain noise.

Alternatively, in the context of Inductive Logic Programming (ILP), the constraint might be refined to:
$KB \land H \models E_{positive}$ (Positive examples must be covered)
$KB \land H \not\models E_{negative}$ (Negative examples must not be covered)
where $E_{positive}$ are examples known to be true, and $E_{negative}$ are examples known to be false. The goal is to find an $H$ that covers all positive examples and none of the negative ones, given the $KB$. This still relies on strict entailment but separates positive and negative examples.

Another change could involve mechanisms for theory revision, where the learning process doesn’t just add to $KB$ but also modifies existing knowledge in $KB$ if it contradicts new examples. This moves beyond simply finding an $H$ that entails $E$ to a dynamic process of updating $KB$ itself based on new observations.

In summary, for knowledge-based inductive learning, the entailment constraint often moves from a strict, perfect entailment of all examples to a more flexible approach that accounts for noise, distinguishes between positive and negative examples, or allows for the modification of the background knowledge itself to achieve better predictive power.

Question 3: Logical Inference and their Formulation

(a) Briefly explain when a substitution unifies two atomic sentences p and q;

Answer:
A substitution $\theta$ unifies two atomic sentences $p$ and $q$ if and only if applying the substitution to both sentences makes them identical.

(b) Find the most general unifiers of the following terms, if they exist:

i. admires(molly, X) and admires(beatrice, lilly).

Answer:
These two atomic sentences cannot be unified.
To unify admires(molly, X) and admires(beatrice, lilly):

The predicate names match: admires.
The first arguments are molly and beatrice. Since molly $\ne$ beatrice and neither is a variable, they cannot be unified.
Therefore, no unifier exists, and consequently, no most general unifier (MGU) exists.

ii. f(g(Y), h(c,d)) and f(X, h(W,d)).

Answer:
Let’s find the most general unifier (MGU) step-by-step:
Terms: $f(g(Y), h(c,d))$ and $f(X, h(W,d))$

Match the main function symbol: Both are f.
Match the first arguments: g(Y) and X.
To unify these, we can substitute X with g(Y).
Substitution: $\theta_1 = {X/g(Y)}$
Applying $\theta_1$ to the second term gives: $f(g(Y), h(W,d))$
Now the terms are: $f(g(Y), h(c,d))$ and $f(g(Y), h(W,d))$.
Match the second arguments: h(c,d) and h(W,d).
- Match the main function symbol: Both are h.
- Match the first arguments of h: c and W.
  To unify these, substitute W with c.
  Substitution: $\theta_2 = {W/c}$
  Applying $\theta_2$ to the second argument gives: h(c,d)
- Match the second arguments of h: d and d. These already match.

Combining the substitutions:
$\theta = {X/g(Y), W/c}$

The most general unifier (MGU) is ${X/g(Y), W/c}$.
Applying this MGU to both original terms:
$f(g(Y), h(c,d)) {X/g(Y), W/c} = f(g(Y), h(c,d))$
$f(X, h(W,d)) {X/g(Y), W/c} = f(g(Y), h(c,d))$
The terms become identical.

(c) Given the modus ponens rule below
$\frac{\alpha,\alpha\rightarrow\beta}{\beta}$
write it in clausal form in order to explain how the basic resolution inference rule works for first order logic.

Answer:
The Modus Ponens rule states that if we have a premise $\alpha$ and an implication $\alpha \rightarrow \beta$, then we can infer $\beta$.

To write Modus Ponens in clausal form (conjunctive normal form, CNF), we convert each part into a disjunction of literals:

$\alpha$: This is already a literal, so its clausal form is simply $\alpha$.
$\alpha \rightarrow \beta$: This implication is equivalent to $\neg \alpha \lor \beta$. This is a disjunction of literals, so it’s in clausal form.
$\beta$: This is the conclusion. In resolution, we try to prove a conclusion by refutation, meaning we negate the conclusion and add it to our knowledge base. If we derive a contradiction (the empty clause), then the original conclusion is proven. So, for the purpose of demonstrating resolution, the conclusion $\beta$ would be negated to $\neg \beta$.

Now, let’s explain how the basic resolution inference rule works using these clauses. Resolution is a refutation complete inference procedure for first-order logic. It operates on clauses.

Given two clauses, $C_1$ and $C_2$, if $C_1$ contains a literal $L_1$ and $C_2$ contains a literal $L_2$ such that $L_1$ is complementary to $L_2$ (i.e., $L_1 = \neg L_2\theta$ for some substitution $\theta$ where $\theta$ unifies them), then a new clause, called the resolvent, can be inferred. The resolvent is formed by taking the disjunction of all literals in $C_1$ and $C_2$, excluding $L_1$ and $L_2$, and applying the unifier $\theta$.

Let’s apply this to Modus Ponens:
Clauses:

$C_1$: $\alpha$ (from the premise $\alpha$)
$C_2$: $\neg \alpha \lor \beta$ (from the premise $\alpha \rightarrow \beta$)
For refutation, we add the negation of the conclusion: $C_3$: $\neg \beta$

Resolution Process:

Resolve $C_1$ ($\alpha$) and $C_2$ ($\neg \alpha \lor \beta$):
- Literal in $C_1$: $\alpha$
- Complementary literal in $C_2$: $\neg \alpha$
- These unify (with empty substitution if $\alpha$ is ground, or appropriate substitution if variables are involved).
- The resolvent is formed by combining the remaining literals: $\beta$.
  So, we get a new clause: $\beta$.
Resolve the new clause ($\beta$) with $C_3$ ($\neg \beta$):
- Literal in the new clause: $\beta$
- Complementary literal in $C_3$: $\neg \beta$
- These unify.
- The resolvent is the empty clause, [] (also denoted as $\bot$ or False).

Deriving the empty clause signifies a contradiction. Since we added $\neg \beta$ to a consistent set of premises ($\alpha$ and $\alpha \rightarrow \beta$) and derived a contradiction, it proves that $\neg \beta$ must be false, meaning $\beta$ must be true. This demonstrates how resolution can perform inference akin to Modus Ponens in a clausal logic framework.

(d) Explain how we would apply resolution to prove the goal connected(a, X) using the following KB.
$edge(a,b).$
$edge(a,c).$
$edge(a,f(a)).$
$connected(a,X)\leftarrow edge(a,X).$

Answer:
To prove the goal connected(a, X) using resolution, we follow the refutation procedure:

Convert KB and the negation of the goal into clausal form.
Apply the resolution rule repeatedly until the empty clause is derived.

Step 1: Convert to Clausal Form

$edge(a,b).$ $\rightarrow$ Clause 1: edge(a,b)
$edge(a,c).$ $\rightarrow$ Clause 2: edge(a,c)
$edge(a,f(a)).$ $\rightarrow$ Clause 3: edge(a,f(a))
$connected(a,X)\leftarrow edge(a,X).$ (This is an implication: $edge(a,X) \rightarrow connected(a,X)$)
$\rightarrow$ Equivalent to $\neg edge(a,X) \lor connected(a,X)$
$\rightarrow$ Clause 4: $\neg$edge(a,X) $\lor$ connected(a,X) (Note: X here is a universally quantified variable)
Negate the Goal: The goal is connected(a, X). The negation is $\neg$connected(a, X') (using a new variable X’ to avoid clashes).
$\rightarrow$ Clause 5: $\neg$connected(a, X')

Step 2: Apply Resolution

We aim to derive the empty clause. We’ll resolve Clause 5 with Clause 4, and then the resulting resolvent with the edge facts (Clauses 1, 2, or 3).

Resolve Clause 5 ($\neg$connected(a, X')) with Clause 4 ($\neg$edge(a,X) $\lor$ connected(a,X)):
- Literal in Clause 5: $\neg$connected(a, X')
- Literal in Clause 4: connected(a,X)
- Unification: connected(a, X') unifies with connected(a, X) with substitution $\theta = {X/X’}$ (or ${X’/X}$).
- Resolvent: Remove the connected literals and apply the substitution to the remaining literal from Clause 4.
- Resulting Clause: $\neg$edge(a, X') (This means: “For connected(a,X') to be false, edge(a,X') must be false.”)
- Let’s call this Clause 6: $\neg$edge(a, X')
Resolve Clause 6 ($\neg$edge(a, X')) with Clause 1 (edge(a,b)):
- Literal in Clause 6: $\neg$edge(a, X')
- Literal in Clause 1: edge(a,b)
- Unification: edge(a, X') unifies with edge(a,b) with substitution $\theta = {X’/b}$.
- Resolvent: The literals are complementary. When they are removed, there are no remaining literals.
- Resulting Clause: [] (the empty clause).

Conclusion:
Since we derived the empty clause, the initial assumption (negation of the goal) must be false. Therefore, the goal connected(a, X) is true. The unification in the last step ($X’/b$) tells us one specific instance for which it is true: connected(a, b). We could also have used Clause 2 or Clause 3 to get connected(a, c) or connected(a, f(a)). The variable $X$ in the goal connected(a, X) is existentially quantified (meaning “is there any X such that connected(a,X) is true?”), and resolution finds specific instantiations that satisfy the query. In this case, X=b, X=c, or X=f(a) are solutions.

(e) Formally define what we mean when we say that an inference procedure $i$ (like resolution), deriving a specific sentence $\alpha$ from a knowledge base $KB$, is sound and complete. Briefly explain any formal symbols that you use in your definitions.

Answer:
Let $KB$ be a knowledge base (a set of sentences), $\alpha$ be a sentence, and $i$ be an inference procedure.

Soundness:
An inference procedure $i$ is sound if and only if every sentence $\alpha$ that can be derived (inferred) from $KB$ using $i$ is logically entailed by $KB$.
Formally: If $KB \vdash_i \alpha$, then $KB \models \alpha$.

$KB \vdash_i \alpha$: This means that the inference procedure $i$ can derive the sentence $\alpha$ from the knowledge base $KB$. The symbol ‘$\vdash$’ denotes derivability.
$KB \models \alpha$: This means that the knowledge base $KB$ logically entails the sentence $\alpha$. In other words, in all models (interpretations) where $KB$ is true, $\alpha$ is also true. The symbol ‘$\models$’ denotes logical entailment.
Soundness ensures that an inference procedure does not derive false conclusions from true premises. It guarantees that whatever the procedure proves is actually true given the knowledge base.

Completeness:
An inference procedure $i$ is complete if and only if every sentence $\alpha$ that is logically entailed by $KB$ can be derived from $KB$ using $i$.
Formally: If $KB \models \alpha$, then $KB \vdash_i \alpha$.

$KB \models \alpha$: As defined above, $KB$ logically entails $\alpha$.
$KB \vdash_i \alpha$: As defined above, $\alpha$ can be derived from $KB$ using procedure $i$.
Completeness ensures that an inference procedure can prove everything that is logically true given the knowledge base. For resolution specifically, it is refutation complete, meaning if a set of clauses is unsatisfiable (contradictory), resolution can derive the empty clause. This implies that if $KB \models \alpha$, then $KB \cup {\neg \alpha}$ is unsatisfiable, and resolution can prove this unsatisfiability by deriving the empty clause from $KB \cup {\neg \alpha}$.

In essence, soundness means “nothing false is proven,” and completeness means “everything true can be proven” (within the scope of the logical system).

Question 4: AI Planning

(a) Define the planning problem.

Answer:
The planning problem in AI involves finding a sequence of actions that transforms an initial state of the world into a desired goal state. More formally, a planning problem typically consists of:

Initial State ($S_0$): A description of the world at the beginning, specifying the truth values of all relevant propositions.
Goal State (G): A (partial) description of a desired state of the world, usually specified as a set of propositions that must be true.
Actions (A): A set of possible actions, each defined by:
- Preconditions: A set of propositions that must be true for the action to be executable.
- Effects (or Postconditions): A set of propositions that become true (add list) or false (delete list) after the action is executed.
  The solution to a planning problem is a plan, which is a sequence of actions $[a_1, a_2, \dots, a_k]$ such that executing this sequence from the initial state leads to a state where all propositions in the goal state are true.

(b) Briefly explain what are the conditions that define the classical planning problem. Is the observability of the environment relevant for the classical planning problem? Justify your answer.

Answer:
The classical planning problem is defined by a set of specific conditions, often referred to as “STRIPS assumptions” (although broader than just STRIPS language):

Static: The world does not change on its own while the agent is planning or executing actions. Changes only occur as a result of the agent’s actions.
Deterministic: The outcome of each action is perfectly predictable and certain. There is no uncertainty about the effects of an action.
Fully Observable: The agent has complete and accurate knowledge of the current state of the world at all times. There are no hidden states or unknown facts.
Discrete: The state space and actions are typically represented in a discrete, symbolic manner (e.g., propositions are either true or false).
Finite: The state space and the number of actions are finite.
Implicit Time/Instantaneous Actions: Actions are considered to take no time or have negligible duration, and sequences of actions are modeled without explicit temporal reasoning.
Single Agent: Typically, there is only one agent performing actions.
Goal-directed: The problem is defined by a specific goal state to be achieved.

Is the observability of the environment relevant for the classical planning problem? Justify your answer.

Yes, the observability of the environment is highly relevant for the classical planning problem.

Justification:
The assumption of full observability means that the agent always knows the complete and accurate state of the world. This is crucial for classical planning because:

Precondition Checking: The planner can always precisely determine if an action’s preconditions are met, as it knows the truth value of every relevant proposition in the current state.
State Transitions: The planner can accurately predict the exact resulting state after executing an action because its effects are deterministic and all relevant information about the world is known.
Plan Validity: Without full observability, the agent might execute a plan based on an incomplete or incorrect understanding of the world, leading to unexpected outcomes or plan failures. The entire concept of generating a fixed sequence of actions that guarantees goal achievement relies on this certainty.

If the environment were partially observable, the agent would need to maintain beliefs about the state, and planning would involve finding a sequence of actions that works across all possible consistent states, or incorporates sensing actions to gain more information. This falls under the domain of contingent planning or replanning, which are extensions beyond classical planning.

(c) Consider the state space of Vacuum World in Fig. 4 where a cleaning robot transitions between states by moving left (L), right (R) or sucking dirt (S). Formulate this problem as a classical planning problem with PDDL-like action schemas, stating any assumptions you make in your formulation. Exemplify your answer by showing how your formulation may generate a concrete plan between two states in the diagram of Fig. 4.

Answer:

Assumptions:

The Vacuum World consists of two locations, let’s call them LocA (left) and LocB (right).
Each location can either be Dirty or Clean.
The robot is in one of the two locations (AtLocA or AtLocB).
The goal is to clean both locations.
Actions are MoveLeft, MoveRight, Suck.
The diagram shows 6 states, representing combinations of robot location and dirt presence in each location. For example, the top-left state has the robot in LocA, LocA is dirty, and LocB is dirty. The bottom-right state has the robot in LocB, LocA is clean, and LocB is clean.
The problem is deterministic and fully observable, as required by classical planning.

PDDL-like Formulation:

Predicates:

(robot-at ?loc): The robot is at location ?loc.
(dirty ?loc): Location ?loc is dirty.
(clean ?loc): Location ?loc is clean (implicitly, clean is the negation of dirty).

Actions:

Action: MoveRight
- Parameters: ?from - location, ?to - location
- Preconditions:
  - (robot-at ?from)
  - (Implicit: ?from is LocA, ?to is LocB)
- Effects:
  - (del (robot-at ?from))
  - (add (robot-at ?to))
    (Note: This generic schema assumes ?from and ?to define a valid right move. For this 2-location world, it would be MoveRight LocA LocB)
Action: MoveLeft
- Parameters: ?from - location, ?to - location
- Preconditions:
  - (robot-at ?from)
  - (Implicit: ?from is LocB, ?to is LocA)
- Effects:
  - (del (robot-at ?from))
  - (add (robot-at ?to))
    (Note: For this 2-location world, it would be MoveLeft LocB LocA)
Action: Suck
- Parameters: ?loc - location
- Preconditions:
  - (robot-at ?loc)
  - (dirty ?loc)
- Effects:
  - (del (dirty ?loc))
  - (add (clean ?loc))

Constants (Objects):

LocA (left location)
LocB (right location)

Exemplifying a Plan Generation:

Let’s generate a plan from an initial state to a goal state shown in Figure 4.

Initial State: Robot in LocA, LocA is Dirty, LocB is Dirty. (Top-left state in Fig. 4)

(robot-at LocA)
(dirty LocA)
(dirty LocB)
(implicitly (not (robot-at LocB)), (not (clean LocA)), (not (clean LocB)))

Goal State: Both LocA and LocB are Clean. (Any state where both are clean, e.g., bottom-left or bottom-right in Fig. 4)

(clean LocA)
(clean LocB)

Plan Generation Steps (using a simplified forward search approach):

Initial State ($S_0$): {(robot-at LocA), (dirty LocA), (dirty LocB)}
Possible Actions from $S_0$:
- MoveRight LocA LocB: Preconditions (robot-at LocA) met.
- Suck LocA: Preconditions (robot-at LocA) and (dirty LocA) met.
Choose Suck LocA:
- State after Suck LocA ($S_1$): {(robot-at LocA), (clean LocA), (dirty LocB)}
- Check Goal: Goal (clean LocB) is not met.
Possible Actions from $S_1$:
- MoveRight LocA LocB: Preconditions (robot-at LocA) met.
- Suck LocA: Preconditions (robot-at LocA) met, but (dirty LocA) is not met (as LocA is now clean). So, Suck LocA is not applicable.
Choose MoveRight LocA LocB:
- State after MoveRight LocA LocB ($S_2$): {(robot-at LocB), (clean LocA), (dirty LocB)}
- Check Goal: Goal (clean LocB) is not met.
Possible Actions from $S_2$:
- MoveLeft LocB LocA: Preconditions (robot-at LocB) met.
- Suck LocB: Preconditions (robot-at LocB) and (dirty LocB) met.
Choose Suck LocB:
- State after Suck LocB ($S_3$): {(robot-at LocB), (clean LocA), (clean LocB)}
- Check Goal: Goal (clean LocA) and (clean LocB) are both met. Goal Reached!

Concrete Plan:
The generated plan is the sequence of actions:

Suck LocA
MoveRight LocA LocB
Suck LocB

This plan transforms the initial state (robot at A, A dirty, B dirty) into a goal state (A clean, B clean).

Revision

#CS2910

CS2910 2024 Past Paper solution

https://blog.pandayuyu.zone/2025/05/20/CS2910-2024-Past-Paper-Solution/

Author

Panda

Posted on

May 20, 2025

Licensed under

CS2910 Exam topics with example questions and solutions Previous

CS2910 Symbolic AI Comprehensive Revision Guide Next