Monkeys and Bananas

(Written by yours truly.)

Prolog variables support generalizations. For example, the following monkeys and bananas solution supports climbing onto a box anywhere in the room as well as push anything to anywhere.

It uses the following database:

% making Move in State1 results in State2;
% move( State1, Move, State2)

% representing the current state
% state( MonkeyHorizontal, MonkeyVertical, BoxPosition, HasBanana)

Our goal is to get the banana.

goal(state(_,_,_,has)).

Our start state...

start(state(atfloor,onfloor,atwindow,hasnot)).

This is how we can get from state1 to state2:

canget( S,[]) :- goal(S).             % base case
canget( State1,[Act|Rest])  :-        % general case
  move( State1, Act, State2),         % Do something
  canget( State2,Rest).               % Repeat

The knowledge base:

move( state( middle, onbox, middle, hasnot),   % Before move
      grasp,                                   % Grasp banana
      state( middle, onbox, middle, has) ).    % After move
move( state( P, onfloor, P, H),
      climb,                                   % Climb box
      state( P, onbox, P, H) ). 
move( state( P1, onfloor, P1, H),
      push( P1, P2),                           % Push box from P1 to P2
      state( P2, onfloor, P2, H) ).
move( state( P1, onfloor, B, H),
      walk( P1, P2),                           % Walk from P1 to P2
      state( P2, onfloor, B, H) ).

Main program:

main :- start(S0), canget(S0,  Steps),
        forall(member(Step,Steps), (print(Step),nl)).

Output:

?- main.
walk(atfloor, atwindow)
push(atwindow, middle)
climb
grasp
true ;

We pause here (even though we asked PROLOG to backtrack and find more solutions with the ";" command) to comment that we we got to the bananas.

Moving on, as we backtrack, we see that the solution gets longer. This is not a bug. What is going on?

walk(atfloor, atwindow)
push(atwindow, _G251)
push(_G251, middle)
climb
grasp
true ; % new solution found

walk(atfloor, atwindow)
push(atwindow, _G251)
push(_G251, _G262)
push(_G262, middle)
climb
grasp
true ; % another solution found

walk(atfloor, atwindow)
push(atwindow, _G251)
push(_G251, _G262)
push(_G262, _G273)
push(_G273, middle)
climb
grasp
true . % yet another solution found

Hmm.... looks like we need to control how far the money walks.

Search control

(Adapted from John Fisher's excellent Prolog tutorial.)

Prolog's hardwired search is depth-first through its list of clauses. But this can easily be changed. For example, in this section we will code up DFID in Prolog.

Simple DFID

For our first DFID, we control the size of the list that shows the steps taken to reach the goal. We can build that leash using the following trick:

?-  between(1,5,N), length(List, N).
N = 1,
List = [_G292] ;
N = 2,
List = [_G292, _G295] ;
N = 3,
List = [_G292, _G295, _G298] ;
N = 4,
List = [_G292, _G295, _G298, _G301] ;
N = 5,
List = [_G292, _G295, _G298, _G301, _G304].

We will use this trick to define dfid as a loop around the monkey's "canget" predicate:

dfid(Max) :- 
	start(S0),
	between(1,Max,Depth), % on backtracking, Depth=1,2,3,...
	length(Steps,Depth),  % Steps is a list of size Depth
	print(leash(Steps)),nl,
	canget(S0,Steps),
	print(Depth),nl,
    forall(member(Step,Steps), (tab(4),print(Step),nl)).

For example:

?- dfid(5), fail. % backtrack through all solutions.
leash([_G254])
leash([_G254, _G257])
leash([_G254, _G257, _G260])
leash([_G254, _G257, _G260, _G263])

4
    walk(atfloor, atwindow)
    push(atwindow, middle)
    climb
    grasp

leash([_G254, _G257, _G260, _G263, _G266])

5
    walk(atfloor, atwindow)
    push(atwindow, _G280)
    push(_G280, middle)
    climb
    grasp
5
    walk(atfloor, atwindow)
    push(atwindow, middle)
    walk(middle, middle)
    climb
    grasp
5
    walk(atfloor, _G272)
    walk(_G272, atwindow)
    push(atwindow, middle)
    climb
    grasp