Thursday, October 4, 2012

Missionaries and Cannibals problem in AI

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.
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
production Rule
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
S. Russel and P. Norvig, Artif icial Intelligence –A Modern App roach, Second Edition

No comments:

Post a Comment