ECE457 S'98
University of Waterloo
Department of Electrical and Computer Engineering
ECE 457 Final Exam
August 12, 1998
Instructor: P. Dasiewicz
Instructions: Time allowed: 3.0 hours. No aids allowed. Answer all questions. Show all work. Questions not of equal marks. Cross out all work not to be marked.
Question One [22] Search
Consider the following maze in which the successors of a cell include any adjacent cell in the directions North, South, East and West of the current cell, except at the boundary of the maze or when a barrier (thick line) exists. For example. successors(M) = {D, G, N}. Assume each type of move (N, S, E, W) has cost 1.
A / BC / D / E
F / S / H / K / M / N
P / Q / R / T / G
The problem is to find a path from cell S to cell G. Assume that children are always expanded in the order East, South, West, North. If a search method needs to break ties, expand first the node corresponding to the letter closest to the front of the alphabet.
For the parts (i) to (iv) of this question, what is the order of nodes expanded (plus the goal node if it is found) by each of the following search methods? You need not show the search tree, just give the order of expansion.
i. Breadth-First Search
ii. Depth-First Search. Assume that cycles are detected and eliminated by never expanding a node containing a state that is repeated on the path back to the root.
iii. Greedy Search. Use as the heuristic function h(state) = Manhattan distance from state to G assuming there were no barriers. Remove redundant states.
iv. A* algorithm. Use the same heuristic function as in (iii). Remove redundant states.
v. Is h2(n) = min(2, h(n)) an admissible heuristic? Why?
vi. Is h3(n) = max(2, h(n)) an admissible heuristic? Why?
Question Two [20] Neural Nets
Part A:
a) Consider a three-input, one-output Perceptron that we want to compute the function “two or more.” That is, if the number of “1” inputs is at least two, the output is “1”; otherwise, the output is “0”. Can this Perceptron learn this function? If not, briefly explain why not. If so, draw a network (including weights and threshold) that implements this function.
b) Draw a three-input Perceptron that implements the Boolean function ( A /\ ØC), where the inputs correspond to A, B, and C.
Part B:
Consider a 2-layer, feed forward neural network with two input units, one hidden unit, and one output unit, as shown in the following figure. Units a and b are the input units, and units c and d are sigmoid units. Assume all the weights are initially equal to 0.1, and the learning rate is a = 0.9. For your information, e0 » 1, e-.1 » 0.90, e-.2 » 0.82, e-.3 » 0.74, e-.4 » 0.67, e-.5 » 0.61 and e-.6 » 0.55.
a) Given one training example with input (a=1, b=0) and desired output 1, what is the output of the feedforward phase of the back propagation algorithm?
b) What is the updated weight computed by the back propagation phase for w1? Show your answer as an arithmetic expression involving only constants, and optionally, as a real value.
c) What is the updated weight computed by the back propagation phase for w3? Show your answer as an arithmetic expression involving only constants, and optionally, as a real value.
Question Three [33] FOL
Part A:
Convert the following sentences into CNF (Clausal Normal Form): [do not just state the CNF form, but show all the intermediate steps]
i. ("x) (P(x) Þ (("y) (P(y) Þ P( F(x,y))) /\ Ø("y) (Q(x,y) Þ P(y) ) ) )
ii. $x D(x) /\ O(J,x)
iii. "x ($y D(y) /\ O(x,y)) Þ A(x)
iv. "x A(x) Þ "y AM(y) Þ ØK(x,y)
Part B:
Consider the following FOL sentences:
1. "x S(x) \/ M(x)
2. Ø$x (M(x) /\ L(x, Rain)
3. "x ( S(x) Þ L(x, Snow) )
4. "y ( L(Ellen, y) Û ØL(Tony, y) )
5. L(Tony, Rain)
6. L(Tony, Snow)
7. Query: $x (M(x) /\ ØS(x) )
Sentences 1 to 6 define the knowledge base while sentence 7 defines a query of the knowledge base. Use an appropriate form of resolution with proof by refutation to determine the validity of the query.
Proceed in a structured manner: first convert the sentences into some appropriate normal form, then using the respective version of resolution perform the proof by refutation. At each step of the proof, keep track of the most general unifier (MGU) and determine the final binding to variable x in the query (if there is one).
Question Four [25] Planning
Consider the following operators:
OP( ACTION: Pickup(x),
PRECOND: Ontable(x) Ù Clear(x) Ù Handempty,
EFFECTS: Holding(x) Ù ØOntable(x) Ù ØClear(x) Ù ØHandempty )
OP( ACTION: Putdown(x),
PRECOND: Holding(x)
EFFECTS: Ontable(x) Ù Clear(x) Ù Handempty Ù ØHolding(x) )
OP( ACTION: Stack(x,y),
PRECOND: Holding(x) Ù Clear(y)
EFFECTS: On(x,y) Ù Clear(x) Ù Handempty Ù ØHolding(x) Ù ØClear(y) )
OP( ACTION: Unstack(x,y),
PRECOND: Clear(x) Ù On(x,y) Ù Handempty,
EFFECTS: Holding(x) Ù Clear(y) Ù ØClear(x) Ù ØOn(x,y) Ù ØHandempty )
The start state is defined as:
Clear(B) Ù Clear(C) Ù On(C,A) Ù Ontable(A) Ù Ontable(B) Ù Handempty
The goal state is defined as:
On(A,C) Ù On(C,B)
Derive the plan (ordered set of steps) to achieve the goal state using the Partial-Order-Planner (POP) algorithm. Do not just state the plan. Illustrate how the plan is constructed step by step. In all cases, identity all possible threats and indicate how each threat is handled.
Start your planner by achieving the goal’s On(A,C) precondition first, then achieve the On(C,B) goal precondition second.
Question Five [10] Semantic Nets
a) Convert the following FOL sentences into a single equivalent semantic network: (draw the network)
"x Housecat(x) Þ Cat(x)
Housecat( Ziggy )
Color( Ziggy, Gray )
"x Housecat(x) Þ Eats(x, Birds)
"x $y Housecat(x) Þ Birds(y) /\ Eats(x,y)
b) Draw a single semantic network representing all of the following sentences:
Both people and cats are mammals.
Animal-lovers are people.
John is an animal lover.
John owns Garfield who is a cat
Every animal-lover owns a cat.
3 of 4