The Missionaries and Cannibals Problem.

The Missionaries and Cannibals Problem Statement

Three missionaries and three cannibals find themselves on one side of a river. They have would like to get to the other side. But the missionaries are not sure what else the cannibals agreed to. So the missionaries managed the trip across the river in such a way that the number of missionaries on either side of the river is never less than the number of cannibals who are on the same side. The only boar available holds only two at a time. How can everyone get across the river without the missionaries risking being eaten?

Solution:-

The state for this problem can be defined as

{(i, j)/ i=0, 1, 2, 3, : j=0, 1, 2, 3}

where i represents the number missionaries in one side of a river . j represents the number of cannibals in the same side of river. The initial state is (3,3), that is three missionaries and three cannibals one side of a river , (Bank 1) and ( 0,0) on another side of the river (bank 2) . the goal state is to get (3,3) at bank 2 and (0,0) at bank 1.

To sole this problem we will make the following assumptions:

1. Number of cannibals should lesser than the missionaries on either side.

2. Only one boat is available to travel.

3. Only one or maximum of two people can go in the boat at a time.

4. All the six have to cross the river from bank.

5. There is no restriction on the number of trips that can be made to reach of the goal.

6. Both the missionaries and cannibals can row the boat.

This kind of problem is often solved by a graph search method. Represent the problem as a set of states which are snapshots of the world and operators which transform one state into another state are mapped to nodes of the graph and operators are the edges of the graph. The following procedure shows the graph search algorithm in PROLOG, for Missionaries and Cannibals Problem.

Path finding.

* Write a program to find path from one node to another.

* Must avoid cycles

* A template for the clause is

path(start, Finish, Visited, Path).
Start - the name of the starting node.
Finish - the name of the finishing node.
Visited - the list of nodes aready visited.
Path - the list of nodes on the path, including Start and Finish.

Program for finding a Path.

* The search for a path terminates when we have nowhere t0o go.

path {Node, Node,.., [Node]}

A path from start to Finish, starts with a node, X,connected to start followed by a path from X to Finish.

path (Start, Finish, Visited, {Start [ Path]} :-
edge (Start,X),
not (member( X,Visited)),
path(x,Finish, {X [vISITED],Path)
member (X,[X I_ I).
member (X,I_ IYI):- member(X,Y).

Representing the state.

Now we returen to the peoblem or rrepresenting tyhe missionaries and cannibals problem;
*A State is one "snapshot" in time.

*For this problem the only infoemation we need to fully characterize the state is :
*the number of missionaries on the left bank,
*the number of cannibals on the left bank,
*the side the boat is on.

All other information can be deduced from these thres items.

In PROLOG, the state can be representted by a 3-arity term, state (Missionaries,Cannibals, State).

Representing the solution.

*The solution consists of a list of moves, e.g.
[move( I.I. right), move 2.0, lift)].
*We take this to mean that I missionary and i cannibal moved to the right bank, then 2
missionaries moved to hte left bank.
*Like the graph search problem, we must avoid returing to state we have visited before.
The visited list will have the form:
[Most Recent State I list of previousstates]

Overview of solution.

We follow a simple graph search procedure:

*Start from an initial state
*Find a neighbouring state
*Check that the now stae has not been visited before
*Find a path from the neighbour to the goal.

The search terminates when we have found the state:

state(0, 0, right).

PROLOG Code.

% mandc(CurrentState, Visited, Path)

mandc(start(0, 0, right), -,[]).
mande(Currentstate, visited,[Move I Rest O fMoves]):-
newstate (Current state, NestState, Move).
not (member(NestState,Visited)0,
make., move(Current state, NestState, Move),
mande((Nextstate I visited,[Move I Rest O fMoves])

make_move (state(M1,C1,left) state (M2,C2,right) move(M,C,right)) :-
M is M1 - M2.
C is C1 - C2.

make_move(state(M1,C1,right),state(M2,C2,right),move M,C,left)) :-
M is M2 -M1
C is C2 - C1.

A move is characterized by the nummber of missionar5ies and the number of canniblls taken in the boal at6 one time.

Since the boat can carry no more than two peopel at once, the only possible 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 hafe found a possible move, we have to confirm that it is feasible It is not feasible to move more missionaries or more cannibals than that are present on one bank.
When the stae is stae(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, left) and we try carry (M,C) then

M + M1 ≤ AND C + C1 ≤ 3

must be true.

Legal Moves.

* Once we have found a feasible move, we must check that it is legal, i.e no Missionaries must be eaten.

legal(X,X).

legal(3,X).

legal(O,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.

newstate(state(M1,C1,left), state(M2,C2,right)):-

carry(M,C),

M ≤ M1

C ≤ C1

M2 is M1 - M2,

C2 is C1 - C,

legal(M2,C2)

newstate(M1, C1, right), state(M2, C2, left)):-

carry(M,C),

M2 is M1 + M,

C2 is C1 + C,

M2 ≤ 3,

C2 ≤ 3,

legal(M2, C2)

What is Production System .? Types., Characterstics.

Artificial Intelligence is the study of how to make computers do things at which at the movement people are better. - Its main aim is depend upon the situation to take the decisions automatically. - AI is the scientific research, this research will begin from past 30 years , its origin is JAPAN. - AI is the part of the Computer Science Concerned with designing, intelligent computer systems, that is systems that exhibits the characteristics we associate with intelligence in Human Behavior. Once again this definition will raise the following question. “Intelligent Behavior “, in view of the difficulty in defining the Intelligence, Let us try to characteristics that is a list of number of characteristics by which we can identify the Human Intelligence . - In AI problems that appear very little common, there are appropriate Techniques to solve these problems are called AI Techniques. A Production System is best suited AI Technique to solve the State Space Problems like Water Jug, and Missionaries and Cannibals. these problems consists of State, State Space and Goal State. State = Initial state of the Problem. State space = Intermediate States between Initial State and Goal State. Goal State = Final state of the problem. - to solve state space problems Production System is best suited AI Technique. A production system consists of rules and factors. Knowledge is encoded in a declarative from which comprises of a set of rules of the form and Control strategy. PRODUCTION SYSTEM SITUATION that implies ACTION. Example:- IF the initial state is a goal state THEN quit. The major components of an AI production system are i. A global database ii. A set of production rules and iii. A control system The goal database is the central data structure used by an AI production system. The production system. The production rules operate on the global database. Each rule has a precondition that is either satisfied or not by the database. If the precondition is satisfied, the rule can be applied. Application of the rule changes the database. The control system chooses which applicable rule should be applied and ceases computation when a termination condition on the database is satisfied. If several rules are to fire at the same time, the control system resolves the conflicts. Four classes of production systems:- 1. A monotonic production system 2. A non monotonic production system 3. A partially commutative production system 4. A commutative production system. Advantages of production systems:- 1. Production systems provide an excellent tool for structuring AI programs. 2. Production Systems are highly modular because the individual rules can be added, removed or modified independently. 3. The production rules are expressed in a natural form, so the statements contained in the knowledge base should the a recording of an expert thinking out loud. Disadvantages of Production Systems:-One important disadvantage is the fact that it may be very difficult analyse the flow of control within a production system because the individual rules don’t call each other. Production systems describe the operations that can be performed in a search for a solution to the problem. They can be classified as follows. Monotonic production system :- A system in which the application of a rule never prevents the later application of another rule, that could have also been applied at the time the first rule was selected. Partially commutative production system:- A production system in which the application of a particular sequence of rules transforms state X into state Y, then any permutation of those rules that is allowable also transforms state x into state Y. Theorem proving falls under monotonic partially communicative system. Blocks world and 8 puzzle problems like chemical analysis and synthesis come under monotonic, not partially commutative systems. Playing the game of bridge comes under non monotonic , not partially commutative system. For any problem, several production systems exist. Some will be efficient than others. Though it may seem that there is no relationship between kinds of problems and kinds of production systems, in practice there is a definite relationship. Partially commutative , monotonic production systems are useful for solving ignorable problems. These systems are important for man implementation standpoint because they can be implemented without the ability to backtrack to previous states, when it is discovered that an incorrect path was followed. Such systems increase the efficiency since it is not necessary to keep track of the changes made in the search process. Monotonic partially commutative systems are useful for problems in which changes occur but can be reversed and in which the order of operation is not critical (ex: 8 puzzle problem). Production systems that are not partially commutative are useful for many problems in which irreversible changes occur, such as chemical analysis. When dealing with such systems, the order in which operations are performed is very important and hence correct decisions have to be made at the first time itself.