Updated 27 February 2007

This section of the Midterm exam is open-book, open-notes, approximately one hour in length, with six questions. This follows the earlier separate closed-book, closed-notes section, also about one hour in length.

Question 1: Depth-first search including path lengths: In the figure below, draw the search tree for enough of a depth-first search that the goal 'I' is reached by two distinct paths, starting at node 'A'. In constructing your search tree never include any nodes that are identical to a previous nodes in that path, "no loops" - ABEF... is OK, but ABEB... is not.

Next to each node in your drawing of the search tree place the total path length to that node reached so far by that path. When you are done, state what the path lengths are that you found from 'A' to the goal node 'I'.

To make your search systematic, whenever your node expands to more than one additional one, visit those nodes in alphabetical order, e.g., From 'E', you might choose 'D', 'F', and 'H', in that order (assuming none of the three violated the loop constraint).

You will also find it useful to make copies of the lattice (omitting the node labels for simplicity) and then draw arrows along the paths you found.

Question 2: Resolution proof for propositional logic: Given the following statements and the conclusion to prove, do the standard conversion to conjunctive normal form and carry through a resolution proof.

• Sunny or warm implies no ice:      Sun ∨ Warm ⇒ ¬Ice
• No ice implies OK driving:      ¬Ice ⇒ OK
• It is sunny:      Sun
• The conclusion to be proved - there is OK driving:      OK

Question 3: Constraint satisfaction: The diagram to the right represents the following constraints.: Any letter assigned to a variable at a node variable at the tail of an arrow must alphabetically precede the letter assigned at the head of the same arrow. For example, if k was assigned to the variable UL, only x could be assigned as the value of MD. Notation for the five variables: UL = upper left, UR = upper right, MD = middle, LL = lower left, LR = lower right. The multiple letters for each variable represent the domain of the corresponding variable. By examining the diagram, draw at least two diagrams with assignments that satisfy the constraints. For your convenience, here is the alphabet:   abcdefghijklmnopqrstuvwxyz EXTRA CREDIT 10 points - SEARCH AND ARC-CONSISTENCY (Sec. 5.2 of AIMA): Repeatedly apply arc-consistency to the constraints to reduce the domains as much as possible. When that is complete, do a depth-first search to find one solution. Search the variables in the order UL, UR, MD, LL, and LR. For each variable, search the domain values in alphabetical order. Some branches of the search may fail, but continuing the search will eventually find a solution, since the problem does have a solution - more than one, actually.

Question 4: Checking validity by using equivalences: You are to prove that the statement below is valid by applying a series of equivalences until you reach the value True. Since your result is independent of the values of the three variables involved, you will have proved that the statement is valid.

(P ⇒ Q) ⇒ ((P ∧ R) ⇒ Q)

Question 5: Horn database and AND-OR graphs: Given the clauses below, prove S by drawing an AND-OR graph corresponding to the premises and conclusions of the clauses.

A
B
C
O
P
A ∧ B ⇒ M
B ∧ C ⇒ N
M ∧ O ⇒ Q
N ∧ P ⇒ R
Q ∧ R ⇒ S

Question 6: Task environments: Specify and describe the characteristics of the task environment for an automated filling station attendant (filling gas tank, checking and adding oil, and windshield washer fluid, and checking tire pressures). For each characteristic (the six on page 43) give an approximately two-sentence description of why you chose the characteristic you did.