Missionaries & Canibal Problem in AI using Pro Log

Introduction:

Missionaries and Cannibals is a notable problem in Artificial Intelligence in which three Missionaries and three Cannibals attempt to cross a river to the other side using a boat.  However, there are constraints on the problem, most notably that there can never be more Cannibals than Missionaries on either side of the river (as they will be eaten!), the boat must always take across at least one person, and the goal state is when all Missionaries and all Cannibals have successfully reached the right side of the river from the left.  Thus, with these constraints in mind, they can be programmed into Prolog fairly simply, and a solution can be searched for.

Problem Discussion:

With the ability to construct a knowledge base in Prolog, the list of available moves must be put into the program.  This is the longest section of code, and also the simplest.  A legal move as a bound must also be defined as well, to prevent the wrong moves from being executed and thus violating the rules of the game.  Furthermore, as this problem is to be solved recursively, it is essential that there is a base case so that the recursive call that will solve the problem will actually succeed.

Commented Program Listing/Analysis:

% Main control block and printing

find :-
path([3,3,left],[0,0,right],[[3,3,left]],_).
output([]) :- nl, nl.
output([[A,B,String]|T]) :-
output(T),
write(B), write(' ~~ '), write(A), write(': '), write(String), nl.

This section of code is by far the simplest.  The main control block is what happens upon the execution of the find command when the Prolog is queried.  In this case, it has the parameters of 3 missionaries and 3 cannibals on the left side, with the goal of 0 cannibals and 0 missionaries on the right side.  The output and write sections are what actually print out the results of the query on the screen, as shown in the testing documentation below.  Because Prolog indicates Horn Clauses with :-, we can say that if the path command here is true that find will also return true.

% Base case

path([A,B,C],[A,B,C],_,MoveList):-
nl,nl,output(MoveList).

Here, we find the base case for the recursion.  Thus, when find. is called, it will traverse the code below until this absolute Base Case is found.  The _ found in the path statement indicates a wildcard, which would make sense as at this absolute point, the list of nodes traversed (which is important below) would be irrelevant as the base case would be the only case remaining.  Thus, the MoveList from the bottom code is passed over and then output to the screen once this step is reached.

% Recursive call to solve the problem

path([A,B,C],[D,E,F],Traversed,Moves) :-
move([A,B,C],[I,J,K],Out),
legal([I,J,K]), % Don't use this move unless it's safe.
not(member([I,J,K],Traversed)),
path([I,J,K],[D,E,F],[[I,J,K]|Traversed],[ [[I,J,K],[A,B,C],Out] | Moves ]).

Here we are able to see the actual tree being traversed to find the valid moves.  Line 3 in this block only allows the move to be used if it is legal, line 4 makes sure that it is not attempting the same node as before.  All references to Out just are taking the output described in the below section of all the possible types of moves.

% Move commands and descriptions of the move

move([A,B,left],[C,B,right],'One missionary crosses the river') :-
A > 0, C is A - 1.
move([A,B,left],[C,B,right],'Two missionaries cross the river') :-
A > 1, C is A - 2.
move([A,B,left],[C,D,right],'One missionary and One cannibal cross the river') :-
A > 0, B > 0, C is A - 1, D is B - 1.
move([A,B,left],[A,D,right],'One cannibal crosses the river') :-
B > 0, D is B - 1.
move([A,B,left],[A,D,right],'Two cannibals cross the river') :-
B > 1, D is B - 2.
move([A,B,right],[C,B,left],'One missionary returns from the other side') :-
A < 3, C is A + 1.
move([A,B,right],[C,B,left],'Two missionaries return from the other side') :-
A < 2, C is A + 2.
move([A,B,right],[C,D,left],'One missionary and One cannibal return from the other side') :-
A < 3, B < 3, C is A + 1, D is B + 1.
move([A,B,right],[A,D,left],'One cannibal returns from the other side') :-
B < 3, D is B + 1.
move([A,B,right],[A,D,left],'Two cannibals return from the other side') :-
B < 2, D is B + 2.

Here we find the constraints on every type of move.  In this format, A are cannibals on the left side, B are missionaries on the left side, while C are cannibals on the right side and D are missionaries on the right side.  The statements such as A <2, C is A+2 are indicative of what move to be used based off the amount of missionaries or cannibals on either side of the river.  The move commands correspond to what is being moved, and what direction they are moving in, and what output to provide to the user when queried.

% Legal move definition where B is missionaries and A is cannibals:

legal([B,A,_]) :-
(A =< B ; B = 0),
C is 3-A, D is 3-B,
(C =< D; D = 0).

This is a simple check to make sure that any move being taken is legal at the given point.  It will return true if the missionaries outnumber the cannibals on the left side of the river (A =< B; B= 0) and the right side of the river (number of each determined by C is 3-A, D is 3-B).

Testing Plan:

In the simplest case, we will attempt to solve for path([3,3,left],[0,0,right],[3,3,left]],_) as given by default.  Since this will indicate that the starting state is 3 missionaries and 3 cannibals on the left and none on the right, and the goal state will be that there are 3 of each on the right and none on the left.

We will then modify the goal states, to see if this algorithm is able to search for more missionaries and cannibals on the left side for the starting state (4,4,left).

Another test would be to see if the test still works if there are less than three missionaries and cannibals on the left side to start (2,2,left).

Finally, let’s modify the goal parameter.  Is the program able to determine a tree where there only needs to be 2 of each person on the right side as a goal (1,1,right).  Note that the right side is calculated by subtracting from 3, so 3 indicates 0 on the right and 0 indicates 3 of a type on the right side.

Download Complete Code here.

Testing Documentation:

Source : http://code.bretonstyle.net/