Held on Thursday, February 24th 2005

This is an open book, open notes exam. Please put all your answers in the blue answer book. You may keep your copy of this question sheet.

Question 1. Discuss the differences in agent architecture (PEAS) between two designs of a robot vacuum cleaner for a large apartment, e.g., having 5 rooms. Please describe the architecture using the proper technical concepts and terminology. Though this question is primarily related to Chapter 2, you may find that concepts from later chapters are applicable too. Use diagrams wherever they're helpful.

1. A robot that stores no map of the apartment, simply continuing to move in some regular or random pattern to do its work.


2. A robot that builds and occasionally alters its internal map of the apartment, as well as a history of how much it has collected at various spots. It can also be instructed to go to a certain area and vacuum that. Assume that the robot has quite rudimentary visual location abilities, e.g., via small colored reflectors or IR lights at various places.

Question 2. Give the initial state, goal test, successor function, and cost function for the following problem. Describe a formulation precise enough to be implemented.

A 3-foot-tall monkey is in a room where some bananas are suspended near an 8-foot ceiling. He would like to get the bananas. The room contains two stackable, movable, climbable 3-foot-high crates.

Question 3. The Missionaries and Cannibals problem is: Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get to the other side of the river without ever leaving a group of missionaries in one place outnumbered by the cannibals at that place. (Please accept my apologies for the political incorrectness of this problem in the current era.)

Hints: This problem can be difficult and confusing until you hit on a simple and efficient representation of the states. I suggest that you use a representation in which the initial state is MMMCCCBr, which means that the three missionaries, M, cannibals, C, and the one boat, B, are on the left side of the river, r. The goal state in this notation is rMMMCCCB. Omit any illegal states and label the transitions by which are in the boat. You should find only about fifteen legal and accessible states. Omit useless cycles that return to an earlier state and don't write down the same state twice in your diagram.

1. Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution. Draw a diagram of the complete state space.


2. Describe a solution of the problem that you can develop by visually inspecting your drawing of the state space.


3. Why do you think people have a hard time solving this puzzle, given that the state space is so simple?

Question 4. Decide whether each of the following sentences is valid, unsatisfiable, or neither. Verify your decisions using truth tables or the equivalence rules of Figure 7.11 in your textbook or even using Resolution.

1. Smoke ⇒ Smoke
2. Smoke ⇒ Fire
3. (Smoke ⇒ Fire) ⇒ (¬Smoke ⇒ ¬Fire)
4. Smoke ∨ Fire ∨ ¬Fire

Question 5. Simple resolution problems in Propositional Logic.

1. Using refutation in resolution show that the goal A∨B can be proven from A. You will need to use a simple identity to transform this into CNF.


2. Now do the same, proving C from the following clauses. Draw a diagram to show the resolution steps.
   
   
   1. A ∨ B ∨ ¬D
   2. A ∨ B ∨ C ∨ D
   3. ¬B ∨ C
   4. ¬A

Question 6. Resolution problems in FOL. Below, the problem is set up for you. Your task is to convert the statements to CNF and use Resolution (refutation) to prove the consequent. The English language statements are the following:

1. If a course is easy, there are some students that are enrolled in it who are happy.


2. If a course has a final exam, no students that are enrolled in it are happy.


3. The consequent to be proved is: If a course has a final exam, the course is not easy.

These are then represented using the relations:

1. Course has a final: F(x)
2. Course is easy: E(x)
3. Student is happy: H(x)
4. Student enrolled in: S(x,y)

Here are the two assertions and the negated conclusion. The steps for converting these to the full conjunctive normal form needed for resolution can be found in Sec. 9.5 of your textbook, with additional information on logical equivalences on page 210 (Fig. 7.11).

1. ∀x[E(x) → ∃y(S(y,x) ∧ H(y))]


2. ∀x[F(x) → ∀y(S(y,x) → ¬H(y))]


3. ¬∀x[F(x) → ¬E(x)]

Go to CSG120 home page. or RPF's Teaching Gateway or homepage