Midterm Exam Solution

This is an open book exam. Pen and paper preferred. Scan answers to PDF. Duration: 150 min.

Answer all questions, with brief but complete explanations. Keep your answers concise and to the point. Please write legibly. Write your name on Page 1. Hint: Try the larger credit questions =irst. Answer on separate papers.

1.  This has 2 parts, 4 points for each part:    [8 points]



















2.  Agents Worlds    [12 points]

LILBANK is a bank with four rooms, every adjacent room is connected with the door. All rooms also have an external door.
There is a security agent (Guard G) in the bottom leftmost corner. There is a thief T somewhere in the bank. Guard’s job is to move from one room to the next, check if the external door is locked are not, and relay a message for the police as follows: (OK if the door is locked and there is no thief; NAK if it orders phone unlocked and HELP if there is a thief found in the same room as the agent).


a)  Draw a diagram to fully represent the above as an agent based AI world problem.

b)    Provide an agent program (pseudocode) for a simple reWlex agent Wirst. Then modify this program to represent a model based agent.

3.
What is AND-OR search? Give an example where and AND-OR Search tree function would be useful in solving

the Missionaries and Cannibals problem from Question 1 above. Show with a Wigure.
[7 points]
4.
CSP: There are a total of 6 songs in a musical event and each song will use a solo instrument, played by one

specialist musician. Here is the format of the concert:
[13 points]
    1. S1. Flute
    2. S2. Vocal
    3. S3. Guitar
    4. S4. Violin
    5. S5. Ukulele
    6. S6. Clarinet
There are 7 musicians on the staff: Brad, Donahue, Ferguson, Judy, Kyle, Michael, and Nick. Each of them is responsible to play one song as the solo player. (But a song could end up having more than one musician, or
1
2

potentially zero staff assigned to it.) However, the musicians are pretty quirky and want the following constraints to be satisWied:
    a. Donahue (D) will not play a song together with Judy (J).
    b. Kyle (K) must playeither Flute, Vocal or guitar song.
    c. Michael (M) is very odd, so he can only contribute to an odd-numbered song.
    d. Nick (N) must playa song that’s before Michael (M)’s song.
    e. Kyle (K) must playa song that’s before Donahue (D)’s song
    f. Brad (B) does not like instruments, so he must sing only Vocal.
    g. Judy (J) must playa song that’s after Nick (N)’s song.
    h. If Brad (B) is to work with someone, it cannot be with Nick (N).
    i. Nick (N) cannot playsong 6.
    j. Ferguson (F) cannot play songs 4, 5, or 6
    k. Donahue (D) cannot play song 5.
    l. Donahue (D) must play a song before Ferguson (F)’s song.

Model this as a Constraint Satisfaction Problem (CSP) (describe how, using a suitable visual diagram – Hint: a grid or table). What are the Variables and Domains involved? After applying the unary constraints, what are the resulting domains of each variable?

5.    MINI-MAX SEARCH IN GAME TREES:

The game tree below illustrates a position reached in the game. Process the tree left-to-right. It is Max's turn to move.

At each leaf node is the estimated score returned by the heuristic static evaluator.    [20 points]

    a) Fill in each blank square with the proper mini-max search value.

    b) What is the best move for Max? (write A, B, or C)

    c) What score does Max expect to achieve?

































2
3

    6. ALPHA-BETA PRUNING: Process the tree left-toright. This is the same tree as above. You do not need to

indicate the branch node values again.    [25 points]

























7.    For each English sentence below, write the letter corresponding to its best or closest FOPC (FOL) sentence (wff, or

well-formed formula). The first one is done for you, as an example.    [15 points]

“Every butterfly likes some flower.”

A. ∀x ∀y Butterfly(x) ∧ Flower(y) ∧ Likes(x, y)
B. ∀x ∃y Butterfly(x) ∧ Flower(y) ∧ Likes(x, y)

C. ∀x ∀y Butterfly(x) ⇒ ( Flower(y) ∧ Likes(x, y) )

D. ∀x ∃y Butterfly(x) ⇒ ( Flower(y) ∧ Likes(x, y) )

“All butterflies are insects.”

A. ∀x Butterfly(x) ∧ Insect(x)
B. ∀x Butterfly(x) ⇒ Insect(x)

C. ∃x Butterfly(x) ∧ Insect(x)

D. ∃x Butterfly(x) ⇒ Insect(x)

“For every flower, there is a butterfly that likes that flower.” A. ∀x ∃y Flower(x) ∧ Butterfly(y) ∧ Likes(y, x)

B. ∀x ∃y [ Flower(x) ∧ Butterfly(y) ] ⇒ Likes(y, x)

C. ∀x ∃y Flower(x) ⇒ [ Butterfly(y) ∧ Likes(y, x) ]

D. ∀x ∀y Flower(x) ∧ Butterfly(y) ∧ Likes(y, x)

“Every butterfly likes every flower.”

A. ∀x ∀y [ Butterfly(x) ∧ Flower(y) ] ⇒ Likes(x, y)
B. ∀x ∀y Butterfly(x) ⇒ [ Flower(y) ∧ Likes(x, y) ]

C. ∀x ∀y Butterfly(x) ∧ Flower(y) ∧ Likes(x, y)

D. ∀x ∃y [ Butterfly(x) ∧ Flower(y) ] ⇒ Likes(x, y)


3
4

“There is some butterfly in Irvine that is pretty.”

A. ∀x Butterfly(x) ∧ In(x, Irvine) ∧ Pretty(x)
B. ∃x Butterfly(x) ∧ In(x, Irvine) ∧ Pretty(x)

C. ∀x [ Butterfly(x) ∧ In(x, Irvine) ] ⇒ Pretty(x)

D. ∃x Butterfly(x) ⇒ [ In(x, Irvine) ∧ Pretty(x)]




























































4