If you are new to Python, read the beginning of the Tutorial, and team up with someone in the class who either has complementary skills and interests or is just willing to work together with you on the code-understanding aspects of this assignment.
In this project, you will implement three separate components of technology for problem-space exploration: a search algorithm, a heuristic, and a visualization. An optional fourth component is a second search algorithm that uses the heuristic.
For the first component of this project, you'll examine the problem formulation for the Missionaries and Cannibals problem, as well as the Text_SOLUZION_Client.py program. This program allows you to manually and interactively solve the puzzle, with the computer keeping track of your progress. It does not solve the problem itself. The code does illustrate, however, how operators can be applied to states in Python. Your job is to write a program that solves the problem automatically. You will use an algorithm known as Breadth-First Search. Your search program should be able to work with any SOLUZION-compliant problem formulation, and not just Missionaries and Cannibals. However, Missionaries and Cannibals has a nice, compact problem space and will be a good test case.
Call your program MyBFSSolver.py. It should import Missionaries.py, and then it should solve the problem by starting a breadth-first search from the initial state, building a hash table of states as keys and their provenance information as values. The provenance information should be a (parent_state, operator_index) pair, where the first piece is the parent of the state that is the key, and the operator_index tells which operator was applied to the parent state to get the state that is the key. When the goal is reached, the solution path can be obtained by backtracing through the predecessor links. Your search method should return the solution path (in the initial state to goal state order), and then your testing should print this out.
There is a starter-code tar file provided for you for this project. If you copy it to your working folder, either on Nicto.cs.washington.edu, or on your home computer, and you have a Linux, Unix or Cygwin environment, then you will be able to untar it by typing
tar -xf P1-starter.tar
Among the other files is one called depthFirst.py. This is very similar to what you are asked to produce, and you can start with this file and simply make some small modifications to get your breadth-first-search program working.
The concept of a heuristic was covered in the lecture on Classic Puzzles. Make up your own heuristic for the Missionaries and Cannibals problem. Explain how it works (and put this in the Description file mentioned near the end of this page). Implement it in Python, adding it to your own copy of Missionaries.py. Here is a template for this code:
#<HEURISTICS> def h1(state): # My heuristic, an optimistic estimate of the # distance from state to the closest goal state. # Figure out a good mapping from the state to an int. h = 0 # h = ??? return h HEURISTICS = [h1] #</HEURISTICS>
This part of the project involves the use of the Flask_SOLUZION_Client_Server.py program. This program probably will run best on your own computer, if you get all the proper component libraries installed. It can also be run on Nicto.cs.washington.edu, but you can only see the results in a browser if you then use the "localtunnel" program, and then interaction is somewhat unstable and "bursty."
The Missionaries and Cannibals program has an optional visualization component that requires the use of a browser and the Flask_SOLUZION_Client_Server.py program. Your job is to modify the visualization (which is in its own Python file, separate from Missionaries.py), so that the visualization includes, somewhere on the screen, near the river, but not blocking any existing part of the visualization, the following: a rounded rectangle, with a blue boundary and light-gray background fill, and some text inside the box that explains the heuristic value and then gives the value. For example it might say: "Optimistic estimate of minimum remaining moves to goal: 3".
In addition to changing the visualization file, you'll need to make a small modification to Missionaries.py. It will need to compute the heuristic value for the current state, and it will need to make this value part of the state, so that it can be rendered by visualization method.
Copy and modify your code from Components 1 and 2, so that you get a program HeuristicSearch.py that implements the A* algorithm using your heuristic method. Then demonstrate the solution of the Missionaries and Cannibals problem with that algorithm. Finally, "instrument" your code for Components 1 and 4 with counters to determine the number of state "expansions" performed by each algorithm, so you can compare them. A state is expanded when it is removed from the OPEN list and its successors are generated. We plan to give extra credit if you attempt or complete this component. A working implementation will be worth an extra fifteen percent of the points for this project.
Create a file Description.pdf that answers the following questions. (1) What is the solution path (operator sequence) found by your Component 1 program? (2) What is the intuition behind your heuristic? Is this heuristic admissible? Why or why not? (3) Which computer did you use for performing Component 3 of the project? What problems, if any, did you run into when setting up the tools or running them? (4) If you did optional Component 4, what were the numbers of expansions for each of the two search algorithms? Why didn't they differ more than they did?
Submit your code files and description file via Catalyst CollectIt.
Files needed:
MyBFSSolver.py Missionaries.py Missionaries_SVG_VIS_FOR_BRIFL.py HeuristicSearch.py (optional) Description.pdf