Assignment 4: Logic, Image Understanding
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2008
The reading for this assignment consists of the material on state-space search and on logical reasoning from the "textbook information" label on the home page.
Due Friday, February 15. Turn in your answers to problem 1 on paper at lab, and turn in your answers to problems 2, 3, and 4 through Catalyst Collect-It before 12:00 noon. Turn in three text files: a4.txt that contains your answers to problems 2 and 3, and then two files for your Prolog expert: expert.pl that contains the code for your Prolog expert, and transcript.txt that gives a sample session with the expert.
  1. Consider the following version (MC3) of the "Missionaries and Cannibals" puzzle: There are three missionaries and three cannibals on the left bank of a river. There is a canoe that can hold up to three people at a time. When crossing the river, there must be at least one missionary in the boat to steer it. The cannibals must never ever outnumber the missionaries on either bank or in the boat, because the outnumbered missionaries would be eaten. What sequence of crossings would get all the people safely to the other side? (a) Develop a representation for each state of this puzzle using a list of numbers or numbers and strings. (b) Draw the complete state space for this puzzle. Do not repeat identical states in the diagram. (c) Highlight a shortest path between the start state and the goal.
  2. How many different states can there be in a Painted Squares puzzle state space if the first piece is always required to be in the upper left position of the 2x2 square (but can still be rotated to any of 4 different orientations)? Assume all pieces are painted with asymmetrical arrangements. Give a justification for your answer, with a formula and a brief description of each term in the formula.
  3. Consider the following problem. In a corn maze, 13 flags have been set up in different parts of the maze, each next to a bucket of miniature pumpkins. Each flag has one of the letters A through M on it, and all the pumpkins in the bucket by that flag have the same letter painted on them. A contest has been set up in which each contestant will run through the maze carrying a sack and collect a set of 13 pumpkins with labels A through M and return to the starting point. One of the flags is right at the starting point, making it easy to get started collecting pumpkins. In order to avoid people getting lost in the maze, each contestant is given an aerial photo of the maze, in which the walls of the maze and the flags (but not their letters) are distinctly visible.

    There is no prohibition against androids entering the contest, and let's say you can loan out a programmable android to represent you at the event. However, you have to program into it a route to follow through the maze. You will need to determine the best route, and to prove to your financial backers that is the best route. The photos are to be available only one day (24 hours) before the event. So you would need to prepare any program you are going to use in advance of that.

    (a) How would you represent the problem?

    (b) Give a strategy you might use to solve it. (200 words or less = 1200 characters or less).

  4. Work with a partner on creating a Prolog program to serve as an expert consultant on a subject. Use the techniques introduced in Lab 5. Here are some suggested topic areas. HIKING TRAIL RECOMMMENDER. MUSIC PLAYER SELECTION (iPOD, etc). VACATION PLANNER. Your team should select or pose your own PROBLEM. The problem should be written as a passage of English text. It should contain the information that will be soon rewritten as rules and facts using logic programming. You should also give two or three sample questions that you want the system to be able to answer. This problem is similar to the Lab 5 exercise on restaurant selection, except that you should make up your own topic, unrelated to restaurants.
(Updated with a modification to problem 4 on Sunday, 10 Feb.)