The Missionaries and Cannibals: A classic AI problem

On one bank of a river are three missionaries and three cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.
How can the boat be used to safely carry all the missionaries and cannibals across the river?

The initial state is shown to the right here, where black triangles represent missionaries and red circles represent cannibals.

A state could be

·           (CanLeft, MissLeft, BoatPos, CanRight, MissRight)

·           (2, 2, RIGHT, 1, 1)

ie. 2 cannibals and 2 missionaries on the left bank of the river, the boat is on the right side, together with 1 cannibal and 1 missionary.  A legal move is one which involves moving up to two people to the opposite bank, (such that cannibals don't outnumber missionaries on either bank).

State Space Example

An initial state is:

·           (3, 3, LEFT, 0, 0)

·         Possible moves are:

·           from (3, 3, LEFT, 0, 0) to (2, 2, RIGHT, 1, 1) 

·      from (2, 2, RIGHT, 1, 1) to (2, 3, LEFT, 1, 0)

A goal state is:

·           (0, 0, RIGHT, 3, 3)

 Note this is one of many possible representations of a state.    

Operators For M&C

Assume the current state is:

  (cLeft, mLeft, boatPos, cRight, mRight)

Move-1m1c-lr : move 1 missionary and 1 cannibal from the left bank to the right bank.

Preconditions:

1.   boatPos = LEFT

2.    cLeft >= 1 AND mLeft >= 1

3.    (mLeft-1 >= cLeft-1) OR mLeft = 0

4.    (mRight+1 >= cRight+1) OR mRight = 0

New State would become:

  (cLeft-1, mLeft-1, RIGHT, cRight+1, mRight+1)

This operator could be applied to the state:

  (3, 3, LEFT, 0, 0)

and would give the new state:

  (2, 2, RIGHT, 1, 1)

This operator could not be applied to the state:

  (2, 2, RIGHT, 1, 1)

Another Operator Example for M&C

Assume the current state is:

  (cLeft, mLeft, boatPos, cRight, mRight)

Move-2m-rl : move 2 missionaries from the right bank to the left bank.

Preconditions:

5.   boatPos = RIGHT

6.    mRight >= 2

7.    cLeft <= mLeft + 2

8.    (cRight <= mRight - 2) OR mRight = 2

New State would become:

  (cLeft, mLeft+2, LEFT, cRight, mRight-2)

This operator could be applied to the state:

  (1, 1, RIGHT, 2, 2)

and would give the new state:

  (1, 3, LEFT, 2, 0)

This operator could not be applied to the state:

  (2, 2, RIGHT, 1, 1)

Complete List of Operators for M&C

Move-1m1c-lr
Move-1m1c-rl
Move-2c-lr
Move-2c-rl
Move-2m-lr
Move-2m-rl
Move-1c-lr
Move-1c-rl
Move-1m-lr
Move-1m-rl

Searching for a Solution

This problem can be solved by searching for a solution, which is a sequence of actions that leads from the initial state to the goal state. The goal state is effectively a mirror image of the initial state. The complete search space is shown in figure 1.

Figure 1: Search-space for the Missionaries and Cannibals problem

Arrows in figure 1 represent state transitions and are labelled with actions, e.g. 2c represents the action of two cannibals crossing the river. The initial state is shown again on the left, whereas the goal state is all the way to the right.