The University of Manitoba In-Class Test
March 4, 2020 PAGE NUMBER: 1 OF 4
COURSE: Comp 3190 Artificial Intelligence (Anderson) TIME: 50 Minutes
Instructions
Calculators and electronic devices are not permitted. This is a closed-book test.
Read questions carefully and answer all questions on this test paper. For multiple choice
questions, circle the correct answer. Each question has only one correct answer - if there
appears to be more than one, choose the best or most appropriate of those available.
There is a total of 24 marks in the test. 14 of these are for question 5.
Name:
Student Number:
1. [6 marks] Suppose you are performing state-space search using the algorithms mentioned
below. Assume your initial state is node A in the tree, and the rest of the tree below A
represents the alternatives that would be generated as you applied operators (i.e. as in class,
the tree does not exist to start with - we must generate nodes by visiting them). The
heuristic function d represents the estimated distance to the goal (lower d is better). The d
value that will be obtained for a node once it is visited is marked for each non-goal node.
Assume we are starting at A and are beginning to generate this tree, where we expand (visit)
child nodes in order by letter where the algorithm has a choice, and we are looking for any goal
state (i.e. we stop at the first goal we find). States that have no children but are not labeled as
goal states are dead ends.
For each of the following algorithms, state the order in which nodes are visited given the above
conditions (just give me a list of letters in the appropriate order). [3 marks each x 2(a,b) = 6]
a) A Beam search, with N=2 [Beam = expand children to plug into H, choose best M=2 at each
level]
ABCDEFGHIJM (or N)
b) A Best-First search:
ABCFGJDEHIM (or N)
2. [1 mark] What is the meaning of ∀X: bird(X) ^ fly(X)?
a) All birds can fly.
b) There are flying birds in our logical system.
c) Many birds exist, and all of them can fly.
d) Everything that exists is a flying bird.
e) None of the above.
A
B
D
C
E F
M N O P Q
d=10
d=4
d=5
d=8 d=6
d=3
Goal States
G
R S T
d=7
I H K J L d=4
d=9
d=8 d=1 d=2
The University of Manitoba In-Class Test
March 4, 2020 PAGE NUMBER: 2 OF 4
COURSE: Comp 3190 Artificial Intelligence (Anderson) TIME: 50 Minutes
3. [1 mark ] A wff is:
a) A true clause form statement.
b) A statement that must be true in some logical system.
c) Any statement that uses a Skolem constant.
d) A low-budget TV Wrestling Federation.
e) None of the above.
4. [2 marks] Why would you want to choose an iterative deepening search over (as these
are very different searches it goes without saying your reasons should be different for each):
a) a breadth-first search?
BFS requires storing all nodes, while IDS does not.
b) a depth-limited depth-first search?
DLDFS is not complete, while IDS is complete.
5. [14 marks] It would likely be helpful to read all parts of this question before starting (i.e.
look at how you are going to use the system). Consider the logical system described by the
following English sentences:
1) Pooh, Piglet, and Tigger are all animals.
2) Pooh is fat and likes honey.
3) Tigger is not fat and not happy.
4) Some animals are mean.
5) If a mean animal likes something, he steals it.
6) All animals who are not fat like honey.
7) Anything that is not happy is mean.
a) [5 marks] Convert the above statements to first order logic.
1) animal(pooh) ^ animal(piglet) ^ animal(tigger)
2) fat(pooh) ^likes(pooh,honey)
3) ~fat(tigger) ^ ~happy(tigger)
4) Exists(Q): animal(Q) ^ mean(Q)
5) Forall(X,Y): animal(X) ^ mean(X) ^ likes(X,Y) -> steals(X,Y)
6) Forall(K): animal(K) ^ ~fat(K) -> likes(K,honey)
7) Forall(F): ~happy(F) -> mean(F)
The University of Manitoba In-Class Test
March 4, 2020 PAGE NUMBER: 3 OF 4
COURSE: Comp 3190 Artificial Intelligence (Anderson) TIME: 50 Minutes
b) [5 marks] Translate your system from part a) to clause form, renumbering statements in order and
indicating which came from what statement in part a) above (show your work for part marks).
All the initial sentences are just splitting on the ands…
1) animal(pooh) (from 1)
2) animal(piglet) (from 1)
3) animal(tigger) (from 1)
4) fat(pooh) (from 2)
5) likes(pooh,honey) (from 2)
6) ~fat(tigger) (from 3)
7) ~happy(tigger) (from 3)
4 needs you to get rid of an existential and then split
8) animal(eeyore) (from 4 – eeyore is a skolem)
9) mean(eeyore) (from 4- eeyore is a skolem)
and the rest are more complicated
animal(X) ^ mean(X) ^ likes(X,Y) -> steals(X,Y)
~(animal(X) ^ mean(X) ^ likes(X,Y)) v steals(X,Y)
10) ~animal(X) v ~mean(X) v ~likes(X,Y) v steals(X,Y) (from 5)
animal(K) ^ ~fat(K) -> likes(K,honey)
~(animal(K) ^ ~fat(K)) v likes(K,honey)
11) ~animal(K) v fat(K) v likes(K,honey) (from 6)
~happy(F) -> mean(F)
12) happy(F) v mean(F) (from 7)
c) [4 marks] Prove, using resolution refutation in conjunction with the clause form statements
above, that Tigger steals honey. For each resolution, indicate the parent clauses (stating numbers
that match those of your clause form statements in b) above is fine). Show any variable
substitutions that are necessary at each step. No marks will be awarded for proofs that are not
purely resolution refutation based.
Note that this is not the only sequence that could have gotten you to the goal. You MUST
introduce a ~H in clause form or you are not using resolution refutation
13 (~H): ~steals(tigger,honey)
14 (1310, tigger/X,honey/Y): ~animal(tigger) v ~mean(tigger) v ~likes(tigger,honey)
15 (1214, tigger/F): ~animal(tigger) v happy(tigger) v ~likes(tigger,honey)
16 (157): ~animal(tigger) v ~likes(tigger,honey)
17 (163): ~likes(tigger,honey)
18 (1711, tigger/K): ~animal(tigger) v fat(tigger)
19 (183): fat(tigger)
20 (196): nil
We have a contradiction generated from ~H. ~H is false, and therefore H (tigger steals honey) is true.
The University of Manitoba In-Class Test
March 4, 2020 PAGE NUMBER: 4 OF 4
COURSE: Comp 3190 Artificial Intelligence (Anderson) TIME: 50 Minutes
You likely won’t need to use this page but if you require more space for any question where you have
run out of room, continue your answer here.