Project 1 -- Missionaries and Cannibals
Due: Tuesday, January 27, 2004
- To practice good problem formulation: appropriate states,
actions, and state space
- To implement, compare, and contrast uninformed search
Your assignment is to complete Problem 3.9, p. 90, in your text, which
is part written exercise and part
programming project. Once you've read and understood the problem as
stated in the text, read the
following for help on how to approach each part. I'm also modifying the
assignment a little, so be sure
to read carefully so you don't miss anything.
- Part (a) should be completed before you write any code. You
need to think about
the problem the right way first. When it asks you to formulate
precisely, be sure to include
answers to the following in your writeup: what is an appropriate state
here? What are appropriate
actions? What are the initial state(s) and the goal state(s)? What is
the goal test? What is the
path cost? (hint: you're trying to get everybody across the river in as
few "moves" as possible.)
Then diagram the complete state space. Remember, you're trying to
abstract away everything
in the "real world" that does not contribute to the solving of the
problem given the actors in the
problem itself. Is your abstraction both valid and
- Part (b) is the implementation itself, which should be a lot
easier with the
questions in Part (a) answered. Remember, you're building a
so the solution (the output) is going to be a sequence of actions
leading from the
initial state to a goal state. For this assignment, your output could
also take the form of a
sequence of states starting with the initial state and ending with a
goal state since it should be
relatively easy to determine what action occurred based on the previous
state and the next state.
I want you to implement this twice using two different
uninformed search algorithms.
You must pick two optimal algorithms, as "optimal" is defined in
the text, but otherwise,
the choice is up to you. Then compare and contrast the two search
methods by displaying
- the number of fringe nodes expanded by each algorithm
- the time it takes for your agent to find a solution under each
(most programming languages provide a way for
you to calculate execution time)
Discuss the results in your writeup.
- Part (c) should be answered after your implementation is
finished and working.
That way, you can look at actual solutions to help you formulate a
- Remember, you can use any programming language you wish.
- Be sure to include a README file or something similar that lets me
search algorithms you implemented and how to run
your agent with each algorithm.
- Be sure to tell me if your agent checks for repeated states or not.
(It's not mandatory
that you do.)
- Extra Credit: make your agent modular enough so that checking
states can be toggled on and off. Then run the experiments above to
find the number of expanded
nodes and the agent running time with the toggle on and then off. Is
there a big difference? Why
or why not?
This project is worth 50 points. I'm looking for:
- correct implementations of your search algorithms
- an optimal correct solution
- understanding of problem-formation and uninformed search as
displayed in your
I'm not looking for:
- mistakes or inefficiencies in the design of your code. This
isn't a programming class,
after all. However, if an error is so egregious that I catch it anyway
without even looking for it,
points may still be deducted.
Please hand in both an electronic copy of your project on
BlackBoard and a paper copy.
Programming assignments, like homework
assignments, are individual projects. I encourage you to
others about the general nature of the project and ideas about how to
However, the technical work, the writing, and the inspiration behind
be substantially your own. If any person besides you contributes in any
the project, you must credit their work on your homework. Similarly, if
include information that you have gleaned from other published sources,
cite them as references. Looking at, and/or copying, other people's
written work is inappropriate, and will be considered cheating.