Updated 28 February 2007

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

Question 1: A constraint satisfaction problem, CSP: There are three actions (variables): Open car door (O), Get in (G), and Start car (S). They are each to be assigned one of three time values: 1, 2, or 3 (the domains). For example, the assignments: [3, 1, 2] produces the (faulty) sequence SOG. The binary constraints are the following:

• No two actions can have equal values (same times).
• G > O (where '>' means later than)
• S > G

From these constraints it is easy to see that the result must be the sequence OGS.

First, draw the constraint graph, indicating all the binary constraints. Draw two more such graphs, each with a single value at the nodes (variables). One should show the correct solution and the other should show an incorrect solution. Discuss the constraints that are met and violated in your two examples.

EXTRA CREDIT - 5 POINTS: Draw the depth-first search tree, examining the action variables in alphabetical order G, O, S and the time values in the order 1, 2, 3. Draw the tree and list the order of nodes visited in a depth-first search up to the state, OGS in which all the constraints are satisfied. HINT: Each level in such a constraint search tree examines the various values for a single variable.

Question 2: Order of search: For the tree below, list the order of the nodes expanded by:

• Breadth-first search
• Depth-first search
• Each of the three stages of interative-deepening depth-first search.

(Don't bother putting a circle around each node you list - that's a waste of time.)

Question 3: Write out a PEAS description for a grocery store shelf stocking robot. (PEAS = Performance Measure, Environment, Actuators, Sensors). Write reasonably brief descriptions for each of the four items. In addition, you can comment on how your descriptions could vary depending on whether or not there are multiple robots working at the same time and/or if (human) customers are shopping while the stocking is going on.

Question 4: Using truth tables, prove the following two equivalences:

• ¬(α ∧ β) ≡ (¬α ∨ ¬β)
• ¬(α ∨ β) ≡ (¬α ∧ ¬β)

Question 5: Give an explanation as to which one of the following expressions has a reasonable and useful meaning and which does not:
∀x Bus(x) ⇒ Vehicle(x)
∀x Bus(x) ∧ Vehicle(x)

Question 6: As in question 5, give an explanation as to which one of the following expressions has a reasonable and useful meaning and which does not:
∃x Toothpaste(x) ⇒ InDrugStore(x,CVS)
∃x Toothpaste(x) ∧ InDrugStore(x,Walgreens)