CS4341 ARTIFICIAL INTELLIGENCE. A97 FINAL EXAM Prof. Carolina Ruiz Oct. 14, 1997 Department of Computer Science Worcester Polytechnic Institute

Name: ————————————————————————————————-

Instructions

• Show your work

• Justify your answers

• Use the space provided to write your answers

• Write your name on each page

• Ask if you have any questions

Problem 1. Constraints and Constraint Propagation (20 points)

Consider the problem of seating 6 people at a round table in such a way that the following constraints are satisfied:

(C1) Spouses (if any) sit next to each other.

(C2) People who hate each other don’t sit next to each other.

Construct a constraint net to represent this problem, assuming that spouses don’t hate each other.

Name: ————————————————————————————————-

Problem 2. Logic Systems (20 points)

Consider the following set of axioms:

(1) ∀x[reads(x) ⇒ literate(x)]

(2) ∀y[dolphin(y) ⇒ ¬literate(y)]

(3) ∃z[dolphin(z) ∧ intelligent(z)] Construct a proof by refutation (using resolution) of the sentence:

(4) ∃w[intelligent(w) ∧ ¬reads(w)] (Hint: Remember to negate (4) before translating it into clausal form.)

Name: ————————————————————————————————-

Problem 3. Planning (20 points)

Consider the towers-of-Hanoi puzzle. In this puzzle there are three disks A, B, and C no two of which are of the same size, and three pegs 1, 2, and 3. Each disk has a hole in its center and can be placed over any peg. Each disk must be placed on one peg, and several disks can be piled up on any peg as long as no disk is placed on top of a smaller disk.

There is just one operator to move disks:

Operator: Move disk x to z:

IF on(x,y)

clear(x) clear(z) smaller(x,z)

ADD LIST on(x,z)

clear(y)

DELETE LIST on(x,y)

clear(z)

Using backward chaining, construct a plan to go from the initial situation to the goal situation described below. Show establishes, threatens, and before links.

Initial Situation  Goal Situation
clear(1) on(B,2) on(A,C) on(C,3) on(A,B)
smaller(A,B) smaller(B,C) smaller(A,C)  on(B,C)
smaller(A,1) smaller(A,2) smaller(A,3)  on(C,3)
smaller(B,1) smaller(B,2) smaller(B,3)
smaller(C,1) smaller(C,2) smaller(C,3)
clear(A)  clear(B)

Name: ————————————————————————————————- 4

Problem 4. Learning (20 points)

Run Operator Machine Overtime Output
1  Patrick a  no  high
2  Patrick b  yes  low
3  Thomas b  yes  low
4  Patrick b  no  high
5  Sally  c  no  high
6  Thomas c  no  low
7  Thomas c  no  low
8  Patrick a  yes  low

Construct the smallest identification tree possible for predicting the output in a factory setting using the data recorded in the table above. Use the average disorder formula to select which attribute to use at each step of the construction. Show your work.

Average Disorder Formula: ∑_{b}(\frac{n_{b}}{n_{t}}) ∗ (∑_{c} −\frac{n_{bc}}{n_{b}} log_{2} \frac{n_{bc}}{n_{b}})

\begin{matrix}x & 1 & 1/2 & 1/3 & 2/3 & 2/5 & 3/5 \\ log_{2}(x) & 0 & −1 & −1.6 & −0.6 & −1.33 & −0.74 \end{matrix}

Name: ————————————————————————————————- 6

Problem 5. Machine Vision (20 points)

Consider the thin rectangle I_{1} shown in the figure. Let I_{2} be the same thin rectangle rotated by a certain angle around the y–axis. Using I_{1} and I_{2} as templates, determine whether or not the unknown object I_{0} is the same as the template rectangles (up to a rotation around the y–axis). In other words, determine if I_{0} “fits” the templates. Explain your answer.

The values of the x coordinates for the four corresponding vertices A, B, C, and D of the objects are given below. Remember that, for any given point P of the rectangle, the x coordinates of the corresponding points P I_{0} (of the unknown object), P I_{1} (of the template I_{1}), and P I_{2} (of the template I_{2}), are related by the following linear equation:

x_{P I_{0}} = α x_{P I_{1}} + β x_{P I_{2}}
Object  x coordinate x coordinate x coordinate x coordinate
of point A of point B of point C of point D
Template: I_{1}  0  1  1  0
Template: I_{2}  1  1  -2  -2
Unknown: I_{0}  0.8  1.4  -1  -1.8

Name: ————————————————————————————————- 8