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.

 



Elementary Discussion About State Space Search (Part II)

Example problem: 8 puzzle

In the 8-puzzle problem we have a 3×3 square board and 8 numbered tiles. The board has one blank position. Bocks can be slid to adjacent blank positions. We can alternatively and equivalently look upon this as the movement of the blank position up, down, left or right. The objective of this puzzle is to move the tiles starting from an initial position and arrive at a given goal configuration.

The 15-puzzle problems is similar to the 8-puzzle. It has a 4×4 square board and 15 numbered tiles

The state space representation for this problem is summarized below:

States: A state is a description of each of the eight tiles in each location that it can occupy.

Operators/Action: The blank moves left, right, up or down

Goal Test: The current state matches a certain state (e.g. one of the ones shown on previous slide)

Path Cost: Each move of the blank costs 1

A small portion of the state space of 8-puzzle is shown below. Note that we do not need to generate all the states before the search begins. The states can be generated when required.

 



tic-tac-toe

Another example we will consider now is the game of tic-tac-toe. This is a game that involves two players who play alternately. Player one puts a X in an empty position. Player 2 places an O in an unoccupied position. The player who can first get three of his symbols in the same row, column or diagonal wins. A portion of the state space of tic-tac-toe is depicted below.

8 queens’ problem

The problem is to place 8 queens on a chessboard so that no two queens are in the same row, column or diagonal

The picture below on the left shows a solution of the 8-queens problem. The picture on the right is not a correct solution, because some of the queens are attacking each other.

How do we formulate this in terms of a state space search problem? The problem formulation involves deciding the representation of the states, selecting the initial state representation, the description of the operators, and the successor states. We will now show that we can formulate the search problem in several different ways for this problem.

N queens problem formulation 1

            • States: Any arrangement of 0 to 8 queens on the board

            • Initial state: 0 queens on the board

            • Successor function: Add a queen in any square

            • Goal test: 8 queens on the board, none are attacked

The initial state has 64 successors. Each of the states at the next level have 63 successors, and so on. We can restrict the search tree somewhat by considering only those successors where no queen is attacking each other. To do that we have to check the new queen against all existing queens on the board. The solutions are found at a depth of 8.

N queens problem formulation 2

            • States: Any arrangement of 8 queens on the board

            • Initial state: All queens are at column 1

            • Successor function: Change the position of any one queen

            • Goal test: 8 queens on the board, none are attacked

If we consider moving the queen at column 1, it may move to any of the seven remaining columns.

N queens problem formulation 3

            • States: Any arrangement of k queens in the first k rows such that none are attacked

            • Initial state: 0 queens on the board

            • Successor function: Add a queen to the (k+1)th row so that none are attacked.

            • Goal test : 8 queens on the board, none are attacked

Now here is the end of the discussion about State Space Search and some of its implementations. Feel free to query about the topic.

 

Source:http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT%20Kharagpur/Artificial%20intelligence/New_index1.html







Elementary Discussion About State Space Search (Part I)

State space search

            • Formulate a problem as a state space search by showing the legal problem states, the legal operators, and the initial and goal states.

            • A state is defined by the specification of the values of all attributes of interest in the world

            • An operator changes one state into the other; it has a precondition which is the value of certain attributes prior to the application of the operator, and a set of effects, which are the attributes altered by the operator

            • The initial state is where you start

            • The goal state is the partial description of the solution 

State Space Search Notations

Let us begin by introducing certain terms.

An initial state is the description of the starting configuration of the agent

An action or an operator takes the agent from one state to another state which is called a successor state. A state can have a number of successor states.

A plan is a sequence of actions. The cost of a plan is referred to as the path cost. The path cost is a positive number, and a common path cost may be the sum of the costs of the steps in the path.

Now let us look at the concept of a search problem.

Problem formulation means choosing a relevant set of states to consider, and a feasible set of operators for moving from one state to another.

Search is the process of considering various possible sequences of operators applied to the initial state, and finding out a sequence which culminates in a goal state.

Search Problem

We are now ready to formally describe a search problem.

A search problem consists of the following:

            • S: the full set of states

            • s₀ : the initial state

            • A:S→S is a set of operators

            • G is the set of final states. Note that G ⊆S

These are schematically depicted in Figure 1.

Figure 1

The search problem is to find a sequence of actions which transforms the agent from the initial state to a goal state g∈G. A search problem is represented by a 4-tuple {S, s₀, A, G}.

S: set of states

s₀ ∈ S: initial state

A: S -> S operators/ actions that transform one state to another state

G: goal, a set of states. G ⊆ S 

This sequence of actions is called a solution plan. It is a path from the initial state to a goal state. A plan P is a sequence of actions. 

Searching process

The generic searching process can be very simply described in terms of the following steps:

Do until a solution is found or the state space is exhausted.                         1. Check the current state                         2. Execute allowable actions to find the successor states.                         3. Pick one of the new states.                         4. Check if the new state is a solution state                         If it is not, the new state becomes the current state and the process is repeated

 

Illustration of a search process

We will now illustrate the searching process with the help of an example. Consider the problem depicted in Figure 2.

Figure 2

s₀ is the initial state.

The successor states are the adjacent states in the graph.

There are three goal states. 

Figure 3

The two successor states of the initial state are generated.

Figure 4

The successors of these states are picked and their successors are generated. Initial State Initial State

Figure 5

Successors of all these states are generated. 

Figure 6

The successors are generated. Initial State

Figure 7

A goal state has been found.

The above example illustrates how we can start from a given state and follow the successors, and be able to find solution paths that lead to a goal state. The grey nodes define the search tree. Usually the search tree is extended one node at a time. The order in which the search tree is extended depends on the search strategy.

We will now illustrate state space search with one more example – the pegs and disks problem. We will illustrate a solution sequence which when applied to the initial state takes us to a goal state. 

This topic will be continued in the next Part. Feel free to discuss about the topic.