Assignment 4: Logic, Image Understanding
|
CSE 415: Introduction to Artificial Intelligence
The University of Washington, Seattle, Winter 2008
|
![](../bar.gif) |
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.
|
-
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.
-
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.
-
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).
-
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.)
|