The Missionaries and Cannibals: A classic AI problem

On one bank of a river are three missionaries and three cannibals. There is one boat available that can hold up to two people and that they would like to use to cross the river. If the cannibals ever outnumber the missionaries on either of the river’s banks, the missionaries will get eaten.
How can the boat be used to safely carry all the missionaries and cannibals across the river?

The initial state is shown to the right here, where black triangles represent missionaries and red circles represent cannibals.

A state could be

·           (CanLeft, MissLeft, BoatPos, CanRight, MissRight)

·           (2, 2, RIGHT, 1, 1)

ie. 2 cannibals and 2 missionaries on the left bank of the river, the boat is on the right side, together with 1 cannibal and 1 missionary.  A legal move is one which involves moving up to two people to the opposite bank, (such that cannibals don't outnumber missionaries on either bank).

State Space Example

An initial state is:

·           (3, 3, LEFT, 0, 0)

·         Possible moves are:

·           from (3, 3, LEFT, 0, 0) to (2, 2, RIGHT, 1, 1) 

·      from (2, 2, RIGHT, 1, 1) to (2, 3, LEFT, 1, 0)

A goal state is:

·           (0, 0, RIGHT, 3, 3)

 Note this is one of many possible representations of a state.    

Operators For M&C

Assume the current state is:

  (cLeft, mLeft, boatPos, cRight, mRight)

Move-1m1c-lr : move 1 missionary and 1 cannibal from the left bank to the right bank.

Preconditions:

1.   boatPos = LEFT

2.    cLeft >= 1 AND mLeft >= 1

3.    (mLeft-1 >= cLeft-1) OR mLeft = 0

4.    (mRight+1 >= cRight+1) OR mRight = 0

New State would become:

  (cLeft-1, mLeft-1, RIGHT, cRight+1, mRight+1)

This operator could be applied to the state:

  (3, 3, LEFT, 0, 0)

and would give the new state:

  (2, 2, RIGHT, 1, 1)

This operator could not be applied to the state:

  (2, 2, RIGHT, 1, 1)

Another Operator Example for M&C

Assume the current state is:

  (cLeft, mLeft, boatPos, cRight, mRight)

Move-2m-rl : move 2 missionaries from the right bank to the left bank.

Preconditions:

5.   boatPos = RIGHT

6.    mRight >= 2

7.    cLeft <= mLeft + 2

8.    (cRight <= mRight - 2) OR mRight = 2

New State would become:

  (cLeft, mLeft+2, LEFT, cRight, mRight-2)

This operator could be applied to the state:

  (1, 1, RIGHT, 2, 2)

and would give the new state:

  (1, 3, LEFT, 2, 0)

This operator could not be applied to the state:

  (2, 2, RIGHT, 1, 1)

Complete List of Operators for M&C

Move-1m1c-lr
Move-1m1c-rl
Move-2c-lr
Move-2c-rl
Move-2m-lr
Move-2m-rl
Move-1c-lr
Move-1c-rl
Move-1m-lr
Move-1m-rl

Searching for a Solution

This problem can be solved by searching for a solution, which is a sequence of actions that leads from the initial state to the goal state. The goal state is effectively a mirror image of the initial state. The complete search space is shown in figure 1.

Figure 1: Search-space for the Missionaries and Cannibals problem

Arrows in figure 1 represent state transitions and are labelled with actions, e.g. 2c represents the action of two cannibals crossing the river. The initial state is shown again on the left, whereas the goal state is all the way to the right.

 



Heuristic Search Techniques in AI: Generate & Test, Hill Climbing and Best-first search (Part I)

What is Heuristic Search technique?

Heuristic search is an AI search technique that employs heuristic for its moves. Heuristic is a rule of thumb that probably leads to a solution. Heuristics play a major role in search strategies because of exponential nature of the most problems. Heuristics help to reduce the number of alternatives from an exponential number to a polynomial number. In Artificial Intelligence, heuristic search has a general meaning, and a more specialized technical meaning. In a general sense, the term heuristic is used for any advice that is often effective, but is not guaranteed to work in every case. Within the heuristic search architecture, however, the term heuristic usually refers to the special case of a heuristic evaluation function.

•         Generate-and-test

•         Hill climbing

•         Best-first search

Generate-and-test

Algorithm:

1. Generate a possible solution.
2. Test to see if this is actually a solution.
3. Quit if a solution has been found. Otherwise, return to step 1.

Advantages & Disadvantages:

•         Acceptable for simple problems.

•         Inefficient for problems with large space.

Hill Climbing

•         Searching for a goal state = Climbing to the top of a hill

•         Generate-and-test + direction to move.

•         Heuristic function to estimate how close a given state is to a goal state.

Algorithm:

1. Evaluate the initial state.
2. Loop until a solution is found or there are no new operators left to be applied:

                        - Select and apply a new operator

                        - Evaluate the new state:

                                    goal-> quit

                                    better than current state-> new current state

Steepest-Ascent Hill Climbing (Gradient Search)

•         Considers all the moves from the current state.

•         Selects the best one as the next state.

Algorithm:

1. Evaluate the initial state.
2. Loop until a solution is found or a complete iteration produces no change to current state:

                        - SUCC = a state such that any possible successor of the

                           current state will be better than SUCC (the worst state).

                        - For each operator that applies to the current state, evaluate

                           the new state:

                                    goal-> quit

                                    better than SUCC-> set SUCC to this state

                         - SUCC is better than the current state-> set the current

                            state to SUCC.

Hill Climbing: Disadvantages

Local maximum

A state that is better than all of its neighbors, but not better than some other states far away.

Plateau

It is a flat area of the search space in which all neighboring states have the same value.

Ridge

The orientation of the high region, compared to the set of available moves, makes it impossible to climb up. However, two moves executed serially may increase the height.

Ways Out:

•         Backtrack to some earlier node and try going in a different direction.

•         Make a big jump to try to get in a new section.

•         Moving in several directions at once.

Conclusion

•   Hill climbing is a local method: Decides what to do next by looking only at the “immediate” consequences of its choices.

•         Global information might be encoded in heuristic functions.

•         Can be very inefficient in a large, rough problem space.

•     Global heuristic may have to pay for computational complexity. Often useful when combined with other methods, getting it started right in the right general neighborhood.