Missionaries and Cannibals problem in AI

Introduction

Missionaries and Cannibals problem is very famous in Artificial Intelligence because it was the subject of the first paper that approached problem formulation from an analytical viewpoint. The problem can be stated as follow. Three missionaries and three cannibals are on one side of a river, along with a boat that can hold one or two people. Now we have to 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 other side. The above problem can be solved by a graph search method. Here I represent the problem as a set of states and operators. States are snapshots of the world and operators are those which transform one state into another state. States can be mapped to nodes of a graph and operators are the edges of the graph.

Explanation

Missionaries and Cannibals cab be solved by using different search algorithms like Breadth first and Depth first search algorithm to find the solution. The node of the graph to be searched is represented by a state space. Each state space can be represent by

State(no_of_missionaries, no_of_cannibals, side_of_the_boat)

Where no_of_missonaries are the number of missionaries at left side of river, no_of_cannibals are the number of cannibals at the left side of river and side_of_the_boat is the side of the boat at particular state. For our case

                                 Initial State => State(3, 3, 0) and

                Final State => State(0, 0, 1).

Where 0 represents left side and 1 represents right side of river. We should make a graph search which traverse the graph from initial state and find out the final state in fewest moves. There are many AI searches that search the graphs like Breadth first search, Depth first search, or iterative deepening search. Each of these different search methods has different properties such as whether a result is guaranteed, and how much time and space is needed to carry out the search. This project uses Breadth first and Depth first search.

Production rules for Missionaries and Cannibals problem

 
Possible Moves

A move is characterized by the number of missionaries and the number of cannibals taken in the boat at one time. Since the boat can carry no more than two people at once, the only feasible combinations are:
                  Carry (2, 0).

         Carry (1, 0).
         Carry (1, 1).
         Carry (0, 1).
         Carry(0, 2). 

Where Carry (M, C) means the boat will carry M missionaries and C cannibals on one trip.

Feasible Moves

Once we have found a possible move, we have to confirm that it is feasible. It is not a 
feasible to move more missionaries or more cannibals than that are present on one bank. 
When the state is state(M1, C1, left) and we try carry (M,C) then 
                 M <= M1 and C <= C1 
must be true. 
When the state is state(M1, C1, right) and we try carry(M, C) then 
                 M + M1 <= 3 and C + C1 <= 3 
must be true.

Legal Moves

Once we have found a feasible move, we must check that  is legal i.e. no missionaries must be eaten. 
                 Legal(X, X). 
                 Legal(3, X). 
                 Legal(0, X). 
The only safe combinations are when there are equal numbers of missionaries and cannibals or all the missionaries are on one side. Generating the next state Above figure only shows valid states. 

Generating the next state 




Sources :

Code Project 

Problem Solving in Prolog 

Missionaries and cannibals problem