Missionaries and Carnivals Problem in Artificial Intelligence

In Missionaries and Carnivals Problem, initially there are some missionaries and some carnivals will be at a side of a river. They want to cross the river. But there is only one boat available to cross the river.

The capacity of the boat is 2 and no one missionary or no Carnivals can cross the river together. So for solving the problem and to find out the solution on different states is called the Missionaries and Carnival Problem.

Procedure:

Let us take an example. Initially a boatman, Grass, Tiger and Goat is present at the left bank of the river and want to cross it. The only boat available is one capable of carrying 2 objects of portions at a time. The condition of safe crossing is that at no time the tiger present with goat, the goat present with the grass at the either side of the river. How they will cross the river?

The objective of the solution is to find the sequence of their transfer from one bank of the river to the other using the boat sailing through the river satisfying these constraints.

Let us use different representations for each of the missionaries and Carnivals as follows.

B: Boat

T: Tiger

G: Goat

Gr: Grass

Step 1:

According to the question, this step will be (B, T, G, Gr) as all the Missionaries and the Carnivals are at one side of the bank of the river. Different states from this state can be implemented as

The states (B, T, O, O) and (B, O, O, Gr) will not be countable because at a time the Boatman and the Tiger or the Boatman and grass cannot go. (According to the question).

Step 2:

 Now consider the current state of step-1 i.e. the state (B, O, G, O). The state is the right side of the river.

So on the left side the state may be (B, T,O, Gr)

i.e._B,O,G,O_ _ _B,T, O, Gr_

(Right)               (Left)

Step 3:

Now proceed according to the left and right sides of the river such that the condition of the problem must be satisfied.

Step 4:

First, consider the first current state on the right side of step 3 i.e.

Now consider the second current state on the right side of step-3 i.e.

Step 5:

Now first consider the first current state of step 4 i.e.

Hence the final state will be (B, T, G, Gr) which are on the right side of the river.

Comments:

This problem requires a lot of space for its state implementation. It takes a lot of time to search the goal node.

The production rules at each level of state are very strict.