How to solve Monkey and Banana Problem Using Prolog

Here i demonstrated how we can solve the monkey and banana problem(Famous problem Artificial Intelligence files).

Reference : Bratko,Ivan Prolog Programming for Artificial Intelligence

There is a monkey at the door in to a room. Inside the room at the middle a banana is hanging from the ceiling and there is box at the window which can be used by monkey to grasp the banana. Monkey is allowed following actions.

1. Walk on the floor

2. Climb the box

3. Push the box around( if it is already at the box)

4. Grasp the banana if standing on the box directly under the banana.

In order to bring this scenario in to computer language we model this problem as Monkey world. There is a particular state that the monkey can take. The current state is determined by the current position of the objects.

Eg: The initial state of the world

1. Monkey is at door

2. Monkey is on floor

3. Box is at window

4. Monkey Does not have banana

It is convenient to combine all of these four pieces of information into one structured object.Let us choose the word 'state' as the functor to hold the four components together.

Our problem can be viewed as a one-person game. Let us now formalize the rules of the game. First, the goal of the game is a situation in which the monkey as the banana; that is, any state in which the last component is 'has':

state(_,_,_,has)

The above diagram shows the initial state of the monkey world represented as a structured object. The four components are:horizontal position of monkey,vertical position of monkey, position of box, monkey has or has not the banana.

Second, what are the allowed moves that change the world from one state to another? There are four types of moves..

1. Grasp Banana

2. Climb box

3. Push Box.

4. Walk around

Not all moves are possible in every possible state of the world. For example, the move 'grasp' is only possible if the monkey is standing on the box directly under the banana (which is in the middle of the room) and does not have the banana yet. Such rules can be formalized in Prolog as a three-place relation named move:


move(state1,M,state2) 

Above relation says state1 is the state before the move. Once the move M is executed current state is state2.

The move "Grasp" , with the necessary precondition on the state before the move, can be defined by the clause. 


move(state(middle, onbox, middle, has not),


                     grasp,


          state(middle, onbox, middle, has)

This fact says that after the move the monkey has the banana, and he has remained on the box in the middle of the room.

In a similar way we can express the fact that the monkey on the floor can walk from any horizontal position P1 to any position P2. The monkey can do this regardless of the position of the box and whether it has the banana or not.

All this can be defined by the following Prolog fact:

move( state( P1, onfloor, B, H),

walk( P1, P2),

state( P2, onfloor, B, H) ).

the above code explains followings.

• the move executed was "walk form some position P1 to some position P2"
• the monkey is on the floor before and after the move
• the box is at some point B which remains the same after move.
• the "has banana" status remains the same after the move.

The clause actually specifies a Applicable to any situation that Such a specification is therefore the concept of Prolog variables whole set of possible moves because it is matches the specified state before the move. Sometimes also called a move schema. Due to such schemas can be easily programmed in Prolog.

The other two types of moves, 'push' and ‘climb’ can be similarly specified.

The main kind of question that our program will have to answer is: Can the monkey in some initial state S get the banana? This can be formulated as a predicate

                        canget (S)

Where the argument S is a state of the monkey world. The program for canget can be based on two observations:

• For any state S in which the monkey already has the banana, the predicate canget must certainly be true; no move is needed in this case. This corresponds to the Prolog fact:

canget( state( -, -, -, has) )

• In other cases one or more moves are necessary. The monkey can get the banana in any state 51 if there is some move M from state S1 to some state S2, such that the monkey can then get the banana in state 52 (in zero or more moves). A Prolog clause that corresponds to this rule is:
  
  
  
  
              canget( S1) :-
  move( S1, M, S2),
  canget( S2).
  
  
  
  

A Complete Program for the Monkey and Banana Problem 

% Legal moves

move( state( middle, onbox, middle,hasnot), %Grasp banana

grasp,

state( middle, onbox, middle,has)).

move( state( P, onfloor, P, H), %climb box

climb,

state( P, onbox, P, H) ).

move( state( Pl, onfloor, Pl, H), %push box from P1 to P2

push( Pl, P2),

state( P2, onfloor, P2, H) ).

move( state( Pl, onfloor, B, H), %walk from P1 to P2

walk( Pl, P2),

state( P2, onfloor, B, H) ).

%canget(state):monkey can get banana in state

canget( state( -, -, -, has) ). %can1:monkey already has it

canget( Statel) :- %can2:Do some work to get it

move( Statel, Move, State2),%Do something

canget( State2). %Get it now

The graphical illustration can be as follows,

The monkey's search for the banana. The search starts at the top node and proceeds downwards, as indicated. Alternative moves are tried in the left-to-right order. Backtracking occurred once only. Without ever touching the box, or aimlessly push the box around. 

Hope this was useful for you..

Thank you.