morris_AIMA [#8]: Problem 3.9 - Missionaries and Cannibals

 Working through AIMA chapter 3, here is the first implementation problem. This post will outline the problem, my solution, and contrasting where I could have made my solution better. I have yet to look at any solution key for this problem, everything has been done by myself alone, aside from a couple definitions I had to review.

Problem Statement 

"Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the other side without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place." 

Problem Formulation 

Part a) Formulate the problem precisely, making only those distinctions necessary to ensure a valid solution.  Draw a diagram of the complete state space. 

Here is my formulation of the problem with the 5 components outlined in chapter 3 of the text. 
States: A state will feature the number of cannibals on left and right, number of missionaries on left and right, and whether or not the boat has crossed the river. 

Initial State: 3 cannibals and 3 missionaries on left bank, the boat has not crossed the river. 

Actions: SHIP(# Cannibals, #Missionaries): sends people from side the boat is currently on, to the other side. 

Transition Model: SHIP: This will move the boat to whatever side of the river it isn't on. SHIP action only works if there are enough people on the side travelling, and of the given type, that are being shipped. Also the shipping may not cause missionaries to die on the other side (avoid invalid state). 

NOTE A ship can't be sent across the river when empty. This is the big catch. 

Goal Test: 3 cannibals and 3 missionaries are on the right bank of river. Path Cost: The number of actions needed to do this correctly. 

Each action has a positive constant cost. It took me about 3 formulation attempts before I reached this conclusion. The key point is abstraction: ensuring we only describe the relevant information. 

Designing for Morris_AIMA Software 

I've followed my framework structure used in past for problems such as this. The design wasn't too difficult, I created a new project layout and various classes to handle nodes/states. 
One issue I'm finding more noticeable is unit testing. It's really essential now. Typing out code alone won't give you a precise solution, and the bugs aren't trivial as with problems such as simple searches. I'll begin with unit testing for the next problem I implement. 

You can find the project code for yourself here. I created a StateNode that contains the path cost, parent, action, and state for generating a graph. 

The search I used was Breadth First Search, which is optimal for this problem considering all step costs are equal. 

Program demo 

The program runs the main act() loop and performs breadth first search. After 11 cycles the solution is generated. The series of actions to reach the goal state are as follows. 

distance to goal: 11 (INITIAL STATE) 
    state: {LEFT=(3 cannibals, 3 missionaries RIGHT=(0 cannibals, 0 missionaries) river=left side} 
    ACTION: Ship(1 cannibal, 1 missionary) from left to right of river 

distance to goal: 10
    state: {LEFT=(2 cannibals, 2 missionaries RIGHT=(1 cannibals, 1 missionaries) river=right side} 
    ACTION: Ship(0 cannibals, 1 missionary) from right to left of river 

distance to goal: 9 
    state: {LEFT=(2 cannibals, 3 missionaries RIGHT=(1 cannibals, 0 missionaries) river=left side} 
    ACTION: Ship(2 cannibals, 0 missionary) from left to right of river 

distance to goal: 8
    state: {LEFT=(0 cannibals, 3 missionaries RIGHT=(3 cannibals, 0 missionaries) river=right side} 
    ACTION: Ship(1 cannibals, 0 missionary) from right to left of river 

distance to goal: 7
    state: {LEFT=(1 cannibals, 3 missionaries RIGHT=(2 cannibals, 0 missionaries) river=left side} 
    ACTION: Ship(0 cannibals, 2 missionary) from left to right of river 

distance to goal: 6 
    state: {LEFT=(1 cannibals, 1 missionaries RIGHT=(2 cannibals, 2 missionaries) river=right side} 
    ACTION: Ship(1 cannibals, 1 missionary) from right to left of river 

distance to goal: 5 
    state: {LEFT=(2 cannibals, 2 missionaries RIGHT=(1 cannibals, 1 missionaries) river=left side} 
    ACTION: Ship(0 cannibals, 2 missionary) from left to right of river 

distance to goal: 4 
    state: {LEFT=(2 cannibals, 0 missionaries RIGHT=(1 cannibals, 3 missionaries) river=right side} 
    ACTION: Ship(1 cannibals, 0 missionary) from right to left of river 

distance to goal: 3 
    state: {LEFT=(3 cannibals, 0 missionaries RIGHT=(0 cannibals, 3 missionaries) river=left side} 
    ACTION: Ship(2 cannibals, 0 missionary) from left to right of river 

distance to goal: 2
    state: {LEFT=(1 cannibals, 0 missionaries RIGHT=(2 cannibals, 3 missionaries) river=right side} 
    ACTION: Ship(1 cannibals, 0 missionary) from right to left of river 

distance to goal: 1 
    state: {LEFT=(2 cannibals, 0 missionaries RIGHT=(1 cannibals, 3 missionaries) river=left side} 
    ACTION: Ship(2 cannibals, 0 missionary) from left to right of river 

GOAL STATE: 
    state: {LEFT=(0 cannibals, 0 missionaries RIGHT=(3 cannibals, 3 missionaries) river=right side} 

Part b) Is it a good idea to check for repeated states? 

Yes, as there are many of them in this problem. Every action can be repeated. 

Part c) Why do you think people have a hard time solving this puzzle, given that the state space is so simple? 

Since there are so many cycles in the state space graph, it's very simple to end up in either a repeated state, or a dead end. There are very few clean cut paths to the end-point and we as humans don't look all the way to the solution immediately. We don't use any clean cut algorithm, so it's hard for us to know if we're repeating behaviour or not. 

Conclusions/Future Plans 

This problem took me about 6 days to solve and implement, seeing as I originally took the wrong approach a couple times. I've also hit some roadblocks in my own framework, so I wish to address things that need to be added/changed. 

Need for Unit testing

 As I mentioned above this is crucial now. For future problems involving more complex states, I will have to start with unit testing to save a lot of time down the road. 

Callbacks for visualizer 

This simulation runs in the cyclical fashion that the vacuum world does. I ran it for 11 cycles because that's how many it takes to finish the search. What I should have implemented is some sort of callback system, that will send and shut-down message when a (found goal) interrupt is found 

Transition to ROS 

With regards to callback issues and other difficulties I'm foreseeing in the future with my framework, I'm considering migrating portions of it to the ROS environment. It is very modular in design and with a wide variety of 2000+ packages it may help with some of the more advanced exercises coming up in the book. I don't want to be spending a month or more on each little exercise, when libraries exist. I do believe however I've obtained a lot of experience developing what I have thus far, so I'll keep building on it, just not reinventing the wheel.