Exam 1


Artificial Intelligence

Fall Semester 2001



  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.

  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).

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


A generic algorithm for systematic search

Figure for Problem 7

Eugene Wallingford ==== wallingf@cs.uni.edu ==== October 12, 2001