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.

 



PROLOG: Intelligent Logic Programming in AI (Part I)

What is PROLOG?

Prolog was invented in the early seventies at the University of Marseille. Prolog stands for PROgramming in LOGic. It is a logic language that is particularly used by programs that use non-numeric objects. For this reason it is a frequently used language in Artificial Intelligence where manipulation of symbols is a common task. Prolog differs from the most common programmings languages because it is declarativre language. Traditional programming languages are said to be procedural. This means that the programmer specify how to solve a problem. In declarative languages the programmers only give the problem and the language find himself how to solve the problem.

What is the difference between PROLOG and the languages you have studied ever?

You will see that Prolog is quite different from other programming languages you have studied. First, Prolog has no types. In fact, the basic logic programming environment has no literal values as such. Identifiers starting with lower-case letters denote data values (almost like values in an enumerated type) while all other identifiers denote variables. Though the basic elements of Prolog are typeless, most implementations have been enhanced to include character and integer values and operations. Also, Prolog has mechanisms built in for describing tuples and lists.

             Remember that all programming languages have both declarative (definitional) and imperative (computational) components. Prolog is referred to as a declarative language because all program statements are definitional. In particular, a Prolog program consists of facts and rules which serve to define relations (in the mathematical sense) on sets of values. The imperative component of Prolog is its execution engine based on unification and resolution, a mechanism for recursively extracting sets of data values implicit in the facts and rules of a program. In this section you will be briefly introduced to each of these terms.

What are Facts, Rules and Predicates?

Facts and Rules

Everything in Prolog is defined in terms of two constructs: the fact and the rule. A fact is a Prolog statement consisting simply of an identifier followed by an n-tuple of constants. The identifier is interpreted as the name of a (mathematical) relation and the fact states that the specified n-tuple is in the relation. In Prolog a relation identifier is referred to as a predicate; when a tuple of values is in a relation we say the tuple satisfies the predicate.

More complicated facts consist of a relation and the items that this refers to. These items are called arguments. Facts can have arbitrary number of arguments from zero upwards. A general model is shown below:

   

 relation(<argument1>,<argument2>,....,<argumentN> ).

The arguments can be any legal Prolog term. The basic Prolog terms are an integer, an atom, a variable or a structure. Various Prolog implementations enhance this basic list with other data types, such as floating point numbers, or strings. Exemple:

    

likes(john,mary).

In the above fact john and mary are two atomes. Atoms are usally made from letters and digits with lowercase characters. The underscore (_) can also be used to separe 2 words but is not allowed as the first charactere. Atoms can also be legally made from symbols.

Consider the following sentence: 'All men are mortal'.  We can express this thing in Prolog by:

     mortal(X) :- human(X)

The clause can be read as 'X is mortal if X is human'.
To continue with this example, let us define the fact that Socrate is a human. Our program will be:

    

mortal(X) :- human(X).

    

human(socrate).

Now if we ask to prolog :

    

?- mortal(socrate).

Prolog will respond :

   

 Yes

SWI PROLOG Environment:

The version of Prolog that we will use is called SWI-Prolog, developed at the Swedish Institute of Computer Science. The SWI-Prolog environment is an interactive system, much like the Hugs functional programming environment.

After SWI-Prolog has been installed on a Windows system, the following important new things are available to the user:

• A folder (called directory in the remainder of this document) called pl containing the executables, libraries, etc. of the system. No files are installed outside this directory.
• A program swipl-win.exe, providing a window for interaction with Prolog. The program swipl.exe is a version of SWI-Prolog that runs in a DOS-box.
• The file-extension .pl is associated with the program swipl-win.exe. Opening a .pl file will cause swipl-win.exe to start, change directory to the directory in which the file-to-open resides and load this file.

How to write and run programs in SWI-Prolog:

1. Go to \program files\pl\bin

2. Open a new Notepad file

3. Write the prolog code there

4. Save the file using .pl extension

5. The file will be saved as a prolog file

6. By double clicking execute the file