CSc 244

Project 1 -- Missionaries and Cannibals
Due: Tuesday, January 27, 2004

Objectives

To practice good problem formulation: appropriate states, actions, and state space
To implement, compare, and contrast uninformed search algorithms

Your Mission

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 useful?
Part (b) is the implementation itself, which should be a lot easier with the questions in Part (a) answered. Remember, you're building a problem-solving agent, 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 algorithm (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 response.

Notes

Remember, you can use any programming language you wish.
Be sure to include a README file or something similar that lets me know which 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 for repeated 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?

Grading

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 writeup

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.

Administrative statement

Programming assignments, like homework assignments, are individual projects. I encourage you to talk to others about the general nature of the project and ideas about how to pursue it. However, the technical work, the writing, and the inspiration behind these must be substantially your own. If any person besides you contributes in any way to the project, you must credit their work on your homework. Similarly, if you include information that you have gleaned from other published sources, you must cite them as references. Looking at, and/or copying, other people's programs or written work is inappropriate, and will be considered cheating.

Return to Project Index