CSE 415: Introduction to Artificial Intelligence Spring 2014

Hw Assignment 1 (Program): 20 pts

Turn In Here

Download the skeleton code here:

Part A Due Thursday, April 10 at 11:59pm

Part B Due Monday, April 14 at 11:59 pm

Part C Due Sunday, April 20 at 11:59pm, 10% off per day until Tuesday, April 22 at 11:59pm

Problem Definition: The missionaries and cannibals problem is usually stated as follows. Three missionaries and three cannibals are on one side (left) of a river, along with a boat that can hold one or two people. If there are ever more cannibals than missionaries on one side of the river, the cannibals will eat the missionaries. (We call this a "dead" state.) Find a way to get everyone to the other side (right), without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place, ie. without anyone getting eaten. This problem is famous in AI, because it was the subject of the first paper that approached problem formulation from an analytical viewpoint (Amarel, 1968).

Tanvir has pointed us to this flash version that lets you play with the problem. Note that here the cannibals gobble up the missionaries as soon as they arrive on the other side without getting out of the boat, not like our assignment. It's equivalent, since as soon as they get out of the boat, which we require, they would be eaten. flash version

Solve the Missionary-Cannibal Problem (with 3 missionaries and 3 cannibals) by writing blind search methods as follows:

• A state must be in the form (M, C, S), where M and C represents number of missionaries and cannibals on the left bank, repectively, and S represents the bank the boat is at.
• Use recursive depth-first search. No other method will be accepted.
• No repeated states. When you reach a state for which there is an identical ancestor on the same path, the search backs up.
• There is no state when the boat is moving, this is a transition. When the boat arrives everyone gets out.
• You MUST use the skeleton code and fill in the parts saying "#WRITE SOME CODE HERE". The skeleton code is written in Python.
• Each method has a comment describing its purpose.
• Please comment important sections of your code; 'This is the main loop', 'This checks for repeated states', etc.
• Your program should print out all paths it finds to the goal state in the following format: [(3, 3, L), (2, 2, R), (3, 2, L), (3, 0, R), (3, 1, L), (1, 1, R), (2, 2, L), (0, 2, R), (0, 3, L), (0, 1, R), (1, 1, L), (0, 0, R)]. This is a correct example path.

Part A

• Define a state and complete the init, describe, goal and illegal methods.
• Describe should return the string form of the state, ie. '(3, 3, L)', goal should return false for all states other than (0, 0, R), and illegal returns true for states in which there are more cannibals than missionaries on either the left or right bank, like (1, 3, R) and (2, 1, R), but NOT like (0, 3, R), since if there are no missionaries to eat, the cannibals won't eat them.

Part B

• Complete the 10 operators. Each operator first checks if it can be applied (see example). If it cannot be applied, it just returns the "bad" state (-1, -1, M).
• For example, MCR sends the boat from left to right with one missionary and one cannibal. Therefore if there are both cannibals and missionaries on the left bank, it decreases the number of missionaries and the number of cannibals on the left side by one and sets the boat to the right bank, returning (currentStatesMissionaryCount-1, currentStatesCannibalCount-1, R). If either the number of missionaries or cannibals on the left bank is zero, then MCR cannot be applied.

Part C

• Complete the rest of the methods that are needed for the search.

• your well-commented code
• the solutions your program finds, each solution being an ordered list of states from initial state to goal state. Format is given above.

Evaluation:

• PART A (3 pts)
• PART B (5 pts)
• PART C (12 pts) [Readable code (1 pts), clear comments (1 pts), working program (10 pts)].