CM3112
CARDIFF UNIVERSITY
EXAMINATION PAPER
Academic Year: 2015-2016
Examination Period: Autumn
Examination Paper Number: CM3112
Examination Paper Title: Artificial Intelligence
Duration: 2 hours
Do not turn this page over until instructed to do so by the Senior Invigilator.
Structure of Examination Paper:
There are 8 pages.
There are 5 questions in total.
The following appendices are attached to this examination paper: Formula sheet
The maximum mark for the examination paper is 100 and the mark obtainable for a question
or part of a question is shown in brackets alongside the question.
Students to be provided with:
The following items of stationery are to be provided:
ONE answer book.
Instructions to Students:
Answer four questions.
The use of calculators is permitted in this examination.
Important note: if you answer more than the number of questions instructed, then answers
will be marked in the order they appear only until the above instruction is met. Extra
answers will be ignored. Clearly cancel any answers not intended for marking. Write
clearly on the front of the answer book the numbers of the answers to be marked.
The use of translation dictionaries between English or Welsh and a foreign language bearing
an appropriate departmental stamp is permitted in this examination.
1 PLEASE TURN OVER
CM3112
Q1. Search
(a) Explain how the minimax algorithm can be extended to deal with chance ele-
ments (e.g. in games such as backgammon). [6]
(b) i. When do we say that a heuristic function is admissible? [2]
ii. When do we say that a heuristic function is consistent? [2]
iii. Consider a pathfinding problem with the following state space:
where a is the initial state, f is the only goal state, and the edges are labelled
with the costs of the corresponding actions. Give an example of a heuristic
function which is admissible but not consistent. Explain why the function is
not consistent. [6]
(c) Consider the following implementation of breadth-first search with multiple-path
pruning:
i. How would you modify this code to obtain an implementation of depth-first
search? [3]
ii. Suggest two ways in which the implementation of multiple-path pruning can
be improved. [6]
Total: [25]
2
CM3112
Q2. Propositional logic
(a) i. What is the definition of a possible world? [3]
ii. What is the definition of a tautology? [3]
iii. Explain why a SAT solver can be used to check whether α |= β holds for
formulas α and β. [3]
(b) Which of the following formulas are entailed by a ∨ b [6]
i. a
ii. a ∨ b ∨ c
iii. c→ a ∨ b
iv. c ∨ ¬c
v. a ∨ (b→ (c ∧ a))
vi. ¬a→ ((c ∨ ¬e) ∧ (¬a ∨ d ∨ e)→ b)
(c) Prove the following entailment relation using the properties of propositional logic
that have been provided in the appendix: [10]
e ∨ f → (a→ b) ∧ (b→ c ∨ d) |= e ∧ a→ c ∨ d
Total: [25]
3 PLEASE TURN OVER
CM3112
Q3. Planning
(a) i. When is it useful to search for partially ordered plans instead of totally or-
dered plans? [4]
ii. What is the advantage of searching partially-ordered plans instead of totally
ordered plans? [3]
(b) Explain how causal links and ordering constraints are used when searching for
partially ordered plans. [6]
(c) Formalise the 8-puzzle as a STRIPS planning problem. Provide a full specifi-
cation of all actions, as well as the initial and final states which are illustrated
below: [12]
Recall that the 8-puzzle is a puzzle in which numbered tiles on a 3× 3 grid need
to be rearranged such that the numbers appear in increasing order (as in the figure
on the right). To this end, the player can slide one of the tiles which is adjacent
(horizontally or vertically) to the empty grid cell onto that empty grid cell. For
example, in the figure on the left, the player can slide the 5-tile to the right, the
6-tile to the left, the 2-tile down or the 3-tile up.
Hint: arithmetic operations are not supported in STRIPS, so you cannot use
expressions such as row + 1. Instead you could assign labels to the rows
and columns (e.g. a, b, c, d, e, f ) and explicitly encode in the initial state which
rows/columns are adjacent to each other.
Total: [25]
4
CM3112
Q4. Bayesian networks
(a) i. What does it mean for random variables to be conditionally independent?
[5]
ii. What assumptions about conditional independence are encoded by the struc-
ture of a Bayesian network? [5]
(b) Give an example of a Bayesian network with random variables A,B,C,D,E
such that the Markov blanket of A is given by {B,C}, the Markov blanket of C
is given by {A,B,D,E} and the Markov blanket of E is given by {B,C,D}.
You only need to provide the network structure, not the conditional probability
tables. [6]
(c) Calculate the value of P (a,¬c|b) for P the probability measure defined by the
following Bayesian network: [9]
Total: [25]
5 PLEASE TURN OVER
CM3112
Q5. Fuzzy logic
(a) i. What is the definition of a t-conorm? [5]
ii. What is the definition of the residual implicator induced by a continuous
t-norm T ? [5]
(b) Let the fuzzy set A and the fuzzy relation R be defined as follows:
A = {a/0.7, b/0.3, c/0.8}
R = {(a, x)/0.9, (a, y)/0.5, (b, x)/0.7, (b, y)/1, (c, x)/0.8, (c, y)/0.6}
Evaluate the direct product of A and R w.r.t. the Łukasiewicz t-norm TW (see
appendix for the definition). [8]
(c) Let A be a set in the universe X and let R be a relation from X to X . The lower
approximation of A w.r.t. R is defined as follows:
A↓R = {x | for every y in X it holds that if (x, y) ∈ R then y ∈ A}
Suggest a way to define the lower approximation of a fuzzy set A w.r.t. a fuzzy
relation R which generalises the above definition. [7]
Total: [25]
6
CM3112
Appendix I: Formula sheet
Propositional logic
Law of De Morgan ¬(a ∨ b) ≡ ¬a ∧ ¬b
¬(a ∧ b) ≡ ¬a ∨ ¬b
Distributivity a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c)
a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)
Implication law a→ b ≡ ¬a ∨ b
Double negation ¬¬a ≡ a
Absorption a ∧ (a ∨ b) ≡ a
a ∨ (a ∧ b) ≡ a
Excluded middle a ∨ ¬a ≡ true
Contradiction a ∧ ¬a ≡ false
Symmetry a ∨ b ≡ b ∨ a
a ∧ b ≡ b ∧ a
Contraposition a→ b ≡ ¬b→ ¬a
Idempotency a ∨ a ≡ a
a ∧ a ≡ a
Truth constants a ∨ true ≡ true
a ∨ false ≡ a
a ∧ true ≡ a
a ∧ false ≡ false
¬false ≡ true
Equivalence if α ≡ β then α |= β
Deduction theorem α |= β iff true |= α→ β
Weakening a ∧ b |= a
a |= a ∨ b
a→ c |= a ∧ b→ c
a ∨ b→ c |= a→ c
a→ b |= a→ b ∨ c
a→ b ∧ c |= a→ b
Resolution (a ∨ b) ∧ (¬a ∨ c) |= b ∨ c
7 PLEASE TURN OVER
CM3112
Fuzzy logic
Popular choices for t-norms and t-conorms are:
t–norm t–conorm
TM(a, b) = min(a, b) SM(a, b) = max(a, b)
TP (a, b) = ab SP (a, b) = a+ b− ab
TW (a, b) = max(0, a+ b− 1) SW (a, b) = min(1, a+ b)
The corresponding S-implicators and residual implicators are given by:
S–implicator Residual implicator
ISM (a, b) = max(1− a, b) ITM (a, b) =
{
1 if a ≤ b
b otherwise
ISP (a, b) = 1− a+ ab ITP (a, b) =
{
1 if a ≤ b
b
a
otherwise
ISW (a, b) = min(1, 1− a+ b) ITW (a, b) = min(1, 1− a+ b)
Some properties of a continuous t-norm T and its corresponding residual implicator IT are:
IT (1, a) = a
a ≤ b⇔ IT (a, b) = 1
T (IT (a, b), c) ≤ IT (a, T (b, c))
IT (T (a, b), c) = IT (a, IT (b, c))
IT (a, IT (b, c)) = IT (b, IT (a, c))
T (IT (a, b), IT (b, c)) ≤ IT (a, c)
T (IT (a, b), IT (c, d)) ≤ IT (T (a, c), T (b, d))
T (a, IT (b, c)) ≤ IT (IT (a, b), c)
T (a, IT (a, b)) = min(a, b)
8X END OF EXAMINATION