Answers Q1. Search
(a) i.
True. Multiple-path pruning is used to avoid the same node being expanded more than once. However, this can only occur if there is more than one path to a given node, which is never the case if the search space is a tree. [3]
(b)
ii. True. Cycle checking is used to avoid analysing paths that contains cycles, as such paths can never be optimal. However, if the search space is a tree, such cycles cannot occur. [3]
iii. True. Iterative deepening only needs to store (i) the nodes on the path from the root to the first solution (in terms of depth in the tree) and (ii) the siblings of these nodes. Breadth-first search needs to store all nodes of all levels up to the level where the solution is found, which always includes the nodes stored by iterative deepening. [3]
Given that the state space is a tree, there is exactly one path from the initial node to a goal node. Suppose n1 and n2 are two goal nodes, but that the true cost g(n1) to reach n1 is higher than the true cost g(n2) to reach n2, i.e. n1 is a sub-optimal goal. [2]
Let n be any node on the path from the initial node to n2 We show that the node n1 can never be expanded by A∗ before the node n, i.e. that f(n1) > f(n), from which the proposition readily follows. [2]
We find [4]
f(n) = g(n) + h(n) ≤ g(n2) < g(n1) = g(n1) + h(n1) = f(n1)
where we have respectively used the definition of f , the fact that h is admissible, the fact that n1 is less optimal than n2, the fact that h(n1) = 0 for a goal node n1 and the definition of f.
i. The heuristic is indeed admissible, since for each node it holds that the heuristic value assigned by h is less than the true cost of the shortest path to I. [2]
ii. The heuristic is not consistent, since e.g. h(B) = 9 > h(E) + c(B, E) =
(c)
5 + 3 = 8.
iii. The sequence of steps is as follows:
[2] [4]
Total: [25] PLEASE TURN OVER
CM3112
node expanded frontier
A B/9,C/5,D/4 D B/9,C/5,F/4
F B/9,C/5,G/1
G B/9,C/5,I/0
I B/9,C/5
1
CM3112
Q2. Minimax and planning
(a)
i.
ii.
Suppose there is a node s that would trigger an α − β cutoff, i.e. getMaxS- core(s, alpha, beta) ≤ alpha in the case of getMinScore, or getMinScore(s, alpha, beta) ≥ beta in the case of getMaxScore. The sooner this node is anal- ysed, the sooner the cut-off can happen, and the larger the part of the tree that is pruned. If we have a way of estimating which moves are most promising, i.e. which moves are most likely to trigger such a cut-off, analysing these moves first would result in larger parts of the game tree being pruned. [5]
Transposition tables may be used to store results from earlier analyses of the game tree, e.g. from the analyses of previous moves, or from previous iterations if iterative deepening is used. [3]
utilities of the different nodes in the game tree are as follows:
a
bcd
352 efghij
3 12 5 10 15 2
(b) The
(c)
i. ii.
i.
ii.
mnopqrstuv 3 2 12 6 5 1 9 10 15 4 1 2
The move to c is the preferred move as the utility of c is highest. [3] The nodes n and r are pruned. [4]
The advantage is that the state space can be drastically reduced, as we do not need to specify how the actions in the plans for these sub-goals are in- terleaved. [5]
Whilesearchingforaplan,asetofcausallinksismaintainedtokeeptrackof which actions have been added to achieve which preconditions. In this way, if an action a1 was previously added to achieve the precondition p of action a2, the planner can ensure that any actions added to the plan afterwards which have ¬p as an effect will either take place before a1 or after a2. [5]
Total: [25]
kl
2
Q3. Propositional logic
(a) i. We say that α entails β if β is satisfied by every interpretation that satisfies
α. [4] ii. A clause is a disjunction of literals (which are atoms or negations of atoms).
[4] (b) We find: [9]
(c)
(a∧b∧¬c)∨¬(x∨¬y)
≡ (a ∧ b ∧ ¬c) ∨ (¬x ∧ ¬¬y)
≡ (a ∧ b ∧ ¬c) ∨ (¬x ∧ y)
≡ (a ∨ (¬x ∧ y)) ∧ (b ∨ (¬x ∧ y)) ∧ (¬c ∨ (¬x ∧ y))
≡ (a ∨ ¬x) ∧ (a ∨ y) ∧ (b ∨ ¬x) ∧ (b ∨ y) ∧ (¬c ∨ ¬x) ∧ (¬c ∨ y)
i. We obtain the following truth table: [4]
Since the rightmost column has T on every row, it holds that the formula is true in every possible world, which means that it is indeed a tautology.
ii. We obtain the following truth table: [4]
On the last two rows, we have T for a → (b → a) but F for a, hence it does not hold that a is satisfied in every possible world satisfying a → (b → a), which means that the entailment does not hold.
CM3112
a
b
a∧b
¬a∨b
a ∧ b → ¬a ∨ b
T T F F
T F T F
T F F F
T F T T
T T T T
a
b
b→a
a → (b → a)
T T F F
T F T F
T T F T
T T T T
Total: [25] 3 PLEASE TURN OVER
CM3112
Q4. Bayesian networks
(a) i. {C,D,E,G} [4]
ii. B and C [4]
(b) Given a set of random variables, the construction algorithm consists of two steps
i. Define an ordering X1, …, Xn of the random variables. [2]
ii. For each i ∈ {1, …, n}, find a minimal subset parents(Xi) of {X1, …, Xi−1}
such that
(c) i.Wefind:
P(Xi = xi |X1 = x1,…,Xi−1 = xi−1)
= P(Xi = xi |{Xj = xj |Xj ∈ parents(Xi)})
P (a, ¬b, ¬c, d) = P (a) · P (¬c) · P (¬b|a, ¬c) · P (d|¬b) = 0.4·0.8·0.4·0.4
[6]
[4]
= 0.0512
ii. We have that: [2]
P(d|a,¬b,¬c) = P(a,¬b,¬c,d) = P(a,¬b,¬c,d) P(a,¬b,¬c) P(a,¬b,¬c,d)+P(a,¬b,¬c,¬d)
We find: [1]
This gives us:
[2]
P (a, ¬b, ¬c, ¬d) = P (a) · P (¬c) · P (¬b|a, ¬c) · P (¬d|¬b) = 0.4·0.8·0.4·0.6
= 0.0768
P (d|a, ¬b, ¬c) =
0.0512 0.0512 + 0.0768
= 0.4
4
Total: [25]
Q5. Fuzzy logic
(a) i.
Let A be a fuzzy set in the universe X and let R be a fuzzy relation from X toY.ThedirectproductA◦T RisthenafuzzysetinY,definedforb∈Y
(b)
(c)
ii. Let A and B be fuzzy sets in some universe X and T a t-norm. The inter- sectionA∩T BisthenthefuzzysetinX,definedforeachx∈Xas:
[5]
(A∩T B)(x)=T(A(x),B(x))
One possible answer, for fuzzy sets A and B over a finite universe X, is as
follows: [7]
x∈X T(A(x),B(x)) Jacc(A, B) = x∈X S(A(x), B(x))
where T is a t-norm and S is a t-conorm.
The activation level of the first rule is given by: [2]
min(Large(1), High(2)) = min(0.3, 1) = 0.3
The activation level of the second rule is given by: [2]
min(Small(1), Low(2)) = min(0.7, 0.5) = 0.5
This means that we can derive the fuzzy restriction A on the price of the televi- sion, defined by: [4]
A(x) = max(min(0.3, Expensive(x)), min(0.5, Cheap(x))
as:
[5]
where T is a t-norm.
(A◦T R)(b)=maxT(A(x),R(x,b)) x∈X
CM3112
5X END OF EXAMINATION
Total: [25]