Exam 1

810:161

Artificial Intelligence

Fall Semester 2001

Instructions

• The exam consists of ten questions, one algorithm, and one figure, on three pages. Be sure that you have all of these items and that they are all legible.

• Read all questions and their instructions thoroughly before you begin. It is almost always worth your time to plan ahead!

• You have also been given three blank pages. Use these sheets for your exam answers. Be sure to write your name on each sheet.

• The exam is worth 100 points. Each problem is worth 10 points.

• Keep the exam questions when you are done, for future reference.

• Points will be awarded based on your explicit answers. Partial credit will be given where possible, so show all of your work.

• The exam lasts seventy-five (75) minutes. It is due at 3:15 PM.

Problems

1. Suppose that you have been exchanging letters with a pen pal for a number of years. You've exchanged letters on a variety of subjects, some in depth, and you feel like you know this person pretty well--at least as well as you can not ever having met the person. Suddenly, you are informed that your pen pal is, in fact, a computer system. Compare and contrast your experience with Turing's "imitation game". Would your opinion of your pen pal's intelligence change as a result of the revelation? Why, or why not?

2. Describe some of the advantages that an agent which deliberates in choosing its next action has over an agent that simply responds to its environment. What are some of the disadvantages of deliberation?

3. The "missionaries and cannibals" problem is as follows:

   On one bank of a river are three missionaries, three cannibals, and a boat. They would all like to cross to the other side of the river. The boat will hold up to two people. But if the cannibals ever outnumber the missionaries on one side of the river, the missionaries will be eaten. The missionaries would like to avoid this fate, and the cannibals are a kind-hearted bunch (if lacking in self-control), so they agree to develop a plan to get all six men across the river safely.

   Using a simple "iconic" representation of states in this problem, show how our generic search algorithm would explore this search space. For this problem, assume that the algorithm favors new states in its exploration. Be sure to go far enough that the algorithm considers at least one state three moves away from the initial state.

4. Before an agent can formulate a solution through search, it must first formulate the problem. What are the steps of problem formulation? What are the components of the resulting problem definition?

5. Describe at least three ways in which an agent can use knowledge to improve how--or how well--it does search.

6. Discuss the similarities and differences between uniform cost search and greedy search. Why do we consider these methods "informed" techniques?

7. Consider the game tree below, in which a static evaluation function has been applied to the leaf nodes.

   • What value will the minimax algorithm assign to the initial position? (Be sure to show your intermediate steps!)

   • Why could agent not consider states G, H, K, and L and still the best move?

8. What are the four components of a knowledge representation scheme? Give examples from the domain of predicate logic.

9. Translate the following sentences into predicate logic. You may use either Horn clause form (with implications) or disjunctive form (with only ors and nots).
   • Bill eats peanuts and is alive.
   • Sue eats everything that Bill eats.
   • Apples are food.
   • Chicken is, too.
   • John likes all kinds of food.
   • Anything anyone eats and isn't killed by is food.

10. Given the database from Problem 6, use modus ponens or resolution to infer that John likes peanuts.

Appendices

A generic algorithm for systematic search

• INPUT:
  • the starting situation (the start state)
  • a goal to achieve
  • a search strategy

• OUTPUT:
  • a sequence of actions (called operators)
    that transforms the problem's start state into a goal state
    OR
  • an announcement that no such sequence can be found

• STEPS
  1. Initialize the set of states to be considered to include the start state.
  2. Repeat the following:
     • If the set of unconsidered states is empty, then announce failure.
     • Choose a state to consider, based on the search strategy.
     • If the state chosen is the goal state, then return the sequence of actions that leads to this state.
     • Add to the set of unconsidered states all of the states that can be reached from the current state by doing one action.

Figure for Problem 7