Discussion:
An innovative approach to Monkey-Banana Problem?
(too old to reply)
Dan Christensen
2006-10-09 14:32:47 UTC
Permalink
Hi,

I am an amateur mathematician and software developer. Using my own proof
checking software, DC Proof, I have developed a formalization of the
so-called Monkey-Banana Problem that a friend assures me is really quite
innovative. It makes use of what he says is a new state concept that solves
a long outstanding problem in AI. Your comments would be appreciated.

The HTML version of my formalization, along with a simple proof
demonstrating it, is at:

http://www.dcproof.com/Monkey.html

The somewhat more readable DC Proof version is at:

http://www.dcproof.com/Monkey.proof

To read it, you must download my proof checker at:

http://www.dcproof.com

Regards,
Dan Christensen
d***@gmail.com
2006-10-09 17:12:25 UTC
Permalink
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).

What is the new state concept that has been introduced?
Dan Christensen
2006-10-10 03:46:54 UTC
Permalink
Post by d***@gmail.com
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Post by d***@gmail.com
What is the new state concept that has been introduced?
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.

Regards,
Dan
Download my DC Proof software at http://www.dcproof.com
Dave Seaman
2006-10-10 12:13:26 UTC
Permalink
Post by Dan Christensen
Post by d***@gmail.com
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Post by d***@gmail.com
What is the new state concept that has been introduced?
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.
Regards,
Dan
Download my DC Proof software at http://www.dcproof.com
No, it's not new. Here is a prolog program for solving the monkey-and-banana
problem. This program, or variations of it, has been around for decades.

-------------------------------------------------------------------------
% Monkey and banana problem

% Description of legal moves

move( state(middle, onbox, middle, hasnot),
grasp, % Grasp banana
state(middle, onbox, middle, has) ).

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) ).

% canget(State,Moves): monkey in State can get banana by performing Moves

canget( state(_,_,_,has), [] ).
canget(State1,[M|List]) :- move(State1,M,State2), canget(State2,List).

solve(Moves) :- canget(state(atdoor,onfloor,atwindow,hasnot),Moves).
-------------------------------------------------------------------------



Notice how states are identified by the word 'state' in the program source.
Here is a sample run:


-------------------------------------------------------------------------
orion:~/lang/statespace/monkey-and-banana dseaman$ swipl
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.10)
Copyright (c) 1990-2006 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- [mb].
% mb compiled 0.00 sec, 2,280 bytes

Yes
?- solve(Moves).

Moves = [walk(atdoor, atwindow), push(atwindow, middle), climb, grasp]

Yes
?-
-------------------------------------------------------------------------
--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/>
Dan Christensen
2006-10-10 12:57:50 UTC
Permalink
Post by Dave Seaman
Post by Dan Christensen
Post by d***@gmail.com
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Post by d***@gmail.com
What is the new state concept that has been introduced?
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.
Regards,
Dan
Download my DC Proof software at http://www.dcproof.com
No, it's not new. Here is a prolog program for solving the
monkey-and-banana
problem. This program, or variations of it, has been around for decades.
[snip prolog source code]

You could write a "solution" in any general-purpose programming language
(e.g. Java, C++, Basic). My formalism, however, is expressed in first-order
predicate logic and set theory. Is this not an advantage? My friend seems to
think so. I really don't know enough about the field of AI to say.

Dan
Dave Seaman
2006-10-10 20:43:57 UTC
Permalink
Post by Dan Christensen
Post by Dave Seaman
Post by Dan Christensen
Post by d***@gmail.com
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Post by d***@gmail.com
What is the new state concept that has been introduced?
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.
Regards,
Dan
Download my DC Proof software at http://www.dcproof.com
No, it's not new. Here is a prolog program for solving the
monkey-and-banana
problem. This program, or variations of it, has been around for decades.
[snip prolog source code]
You could write a "solution" in any general-purpose programming language
(e.g. Java, C++, Basic). My formalism, however, is expressed in first-order
predicate logic and set theory. Is this not an advantage? My friend seems to
think so. I really don't know enough about the field of AI to say.
What you said (or what you paraphrased your friend as saying) was simply
that you were "introducing the state concept" for an "action logic
problem". Not a word was said there about reducing it to first-order
logic. If you thought that was the entire point of the exercise, it's
strange that you didn't mention it in your description of what you
thought was new.

I don't know whether an "action logic problem" is supposed to call for
something other than an ordinary state-space search (a standard AI
technique). What sort of "action logic problem" would not be amenable to
such methods? Certainly this one is. You describe the admissable states
and the allowable transitions between states. Then you perform a
standard search. I don't see what difference it makes what language you
use.
--
Dave Seaman
U.S. Court of Appeals to review three issues
concerning case of Mumia Abu-Jamal.
<http://www.mumia2000.org/>
David C. Ullrich
2006-10-10 13:45:24 UTC
Permalink
On Tue, 10 Oct 2006 12:13:26 +0000 (UTC), Dave Seaman
Post by Dave Seaman
Post by Dan Christensen
Post by d***@gmail.com
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Post by d***@gmail.com
What is the new state concept that has been introduced?
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.
Regards,
Dan
Download my DC Proof software at http://www.dcproof.com
No, it's not new. Here is a prolog program for solving the monkey-and-banana
problem. This program, or variations of it, has been around for decades.
What _is_ the problem? (I'm certain I could find out from google if
I looked, but the first few hits seemed to assume I already knew
the well-known problem...)
Post by Dave Seaman
-------------------------------------------------------------------------
% Monkey and banana problem
% Description of legal moves
move( state(middle, onbox, middle, hasnot),
grasp, % Grasp banana
state(middle, onbox, middle, has) ).
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) ).
% canget(State,Moves): monkey in State can get banana by performing Moves
canget( state(_,_,_,has), [] ).
canget(State1,[M|List]) :- move(State1,M,State2), canget(State2,List).
solve(Moves) :- canget(state(atdoor,onfloor,atwindow,hasnot),Moves).
-------------------------------------------------------------------------
Notice how states are identified by the word 'state' in the program source.
-------------------------------------------------------------------------
orion:~/lang/statespace/monkey-and-banana dseaman$ swipl
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.10)
Copyright (c) 1990-2006 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- [mb].
% mb compiled 0.00 sec, 2,280 bytes
Yes
?- solve(Moves).
Moves = [walk(atdoor, atwindow), push(atwindow, middle), climb, grasp]
Yes
?-
-------------------------------------------------------------------------
************************

David C. Ullrich
d***@gmail.com
2006-10-10 13:46:11 UTC
Permalink
A rough statement:
There is a room containing a monkey, a box, and a banana hanging from
the ceiling. The monkey cannot reach the banana from the floor. The
monkey has available the following actions: move box to a given
position in the room, stand upon or climb down from box, grab banana
(when possible). The problem is for the monkey to select the
appropriate sequence of actions that result in it having the banana
(preferably in as few actions as possible).

The solution is for the monkey to move the box under the banana, step
on the box, then take the banana.
Post by David C. Ullrich
On Tue, 10 Oct 2006 12:13:26 +0000 (UTC), Dave Seaman
Post by Dave Seaman
Post by Dan Christensen
Post by d***@gmail.com
Well... the proof is correct, I suppose. I'm not sure I see the point,
though. This task is easily formalized in terms of Markov decision
processes (and can be solved by common reinforcement learning
algorithms, I'm sure).
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Post by d***@gmail.com
What is the new state concept that has been introduced?
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.
Regards,
Dan
Download my DC Proof software at http://www.dcproof.com
No, it's not new. Here is a prolog program for solving the monkey-and-banana
problem. This program, or variations of it, has been around for decades.
What _is_ the problem? (I'm certain I could find out from google if
I looked, but the first few hits seemed to assume I already knew
the well-known problem...)
Post by Dave Seaman
-------------------------------------------------------------------------
% Monkey and banana problem
% Description of legal moves
move( state(middle, onbox, middle, hasnot),
grasp, % Grasp banana
state(middle, onbox, middle, has) ).
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) ).
% canget(State,Moves): monkey in State can get banana by performing Moves
canget( state(_,_,_,has), [] ).
canget(State1,[M|List]) :- move(State1,M,State2), canget(State2,List).
solve(Moves) :- canget(state(atdoor,onfloor,atwindow,hasnot),Moves).
-------------------------------------------------------------------------
Notice how states are identified by the word 'state' in the program source.
-------------------------------------------------------------------------
orion:~/lang/statespace/monkey-and-banana dseaman$ swipl
Welcome to SWI-Prolog (Multi-threaded, Version 5.6.10)
Copyright (c) 1990-2006 University of Amsterdam.
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- [mb].
% mb compiled 0.00 sec, 2,280 bytes
Yes
?- solve(Moves).
Moves = [walk(atdoor, atwindow), push(atwindow, middle), climb, grasp]
Yes
?-
-------------------------------------------------------------------------
************************
David C. Ullrich
Dan Christensen
2006-10-10 14:44:32 UTC
Permalink
Post by d***@gmail.com
There is a room containing a monkey, a box, and a banana hanging from
the ceiling. The monkey cannot reach the banana from the floor. The
monkey has available the following actions: move box to a given
position in the room, stand upon or climb down from box, grab banana
(when possible). The problem is for the monkey to select the
appropriate sequence of actions that result in it having the banana
(preferably in as few actions as possible).
The solution is for the monkey to move the box under the banana, step
on the box, then take the banana.
That may be the "solution" as far as the monkey is concerned. ;^) The
problem for AI, as I understand it (I'm no expert), is to formalize this
cartoon scenario using techniques that can applied to other, more serious
problems of the field of action logic.

Dan
a***@googlemail.com
2006-11-16 17:49:33 UTC
Permalink
hi everybody,

i am a student from germany... i try to figure out how to get the
monkey off the box. my teacher asked me to implement the
monkey-banana-problem as a prolog-program. i did that exactly the way
mr bratko did it in "prolog - programming for artificial intelligence".
so far, everything was fine. but if my first state is:
canget(state(atwindow,onbox,atwindow,hasnot)). prolog will say no. so i
thought of making the monkey climb down the box again. but when i tried
that, prolog said: ERROR: Out of local stack . i don't get it. can
somebody help me please?
goanna
2006-11-16 18:55:58 UTC
Permalink
Post by a***@googlemail.com
hi everybody,
i am a student from germany... i try to figure out how to get the
monkey off the box. my teacher asked me to implement the
monkey-banana-problem as a prolog-program. i did that exactly the way
mr bratko did it in "prolog - programming for artificial intelligence".
canget(state(atwindow,onbox,atwindow,hasnot)). prolog will say no. so i
thought of making the monkey climb down the box again. but when i tried
that, prolog said: ERROR: Out of local stack . i don't get it. can
somebody help me please?
Sounds like a recursion that never hits the base case.
Suggest you add some tracing to see where it's going.
PeskyBee
2006-11-16 18:57:52 UTC
Permalink
Post by a***@googlemail.com
hi everybody,
i am a student from germany... i try to figure out how to get the
monkey off the box. my teacher asked me to implement the
monkey-banana-problem as a prolog-program. i did that exactly the way
mr bratko did it in "prolog - programming for artificial intelligence".
canget(state(atwindow,onbox,atwindow,hasnot)). prolog will say no. so i
thought of making the monkey climb down the box again. but when i tried
that, prolog said: ERROR: Out of local stack . i don't get it. can
somebody help me please?
Out of stack errors are almost always a consequence of infinite
recursion. Search your code and look for a function that calls
something that calls something that eventually calls the first
function. If that still leaves you in the dark, try to post
your code, maybe we can help.

*PB*
Don Geddis
2006-11-16 18:57:50 UTC
Permalink
Post by a***@googlemail.com
i am a student from germany... i try to figure out how to get the
monkey off the box.
I suggest that you try putting the banana on the ground, instead of hanging
it in the air. That is likely to get the monkey off the box and back on the
ground.
Post by a***@googlemail.com
so i thought of making the monkey climb down the box again. but when i
tried that, prolog said: ERROR: Out of local stack . i don't get it.
Perhaps you need to buy a new computer with more memory.

-- Don
_______________________________________________________________________________
Don Geddis http://don.geddis.org/ ***@geddis.org
If trees could scream, would we be so cavalier about cutting them down? We
might, if they screamed all the time, for no good reason.
-- Deep Thoughts, by Jack Handey

d***@gmail.com
2006-10-10 13:58:09 UTC
Permalink
Post by Dan Christensen
I was not familiar with the Monkey-Banana problem until a few days ago when
friend asked if I could formalize it in my DC Proof system. He said, it is
one of the central problems in AI. I devised a formalization based on a
number of functions mapping N -> {1,2} (see links given). I was surprised
and delighted that he seemed to think it was an important innovation, and a
new way of looking at the problem.
Ah, well, one thing to remember is that the definition of a "problem"
in machine learning works a little differently than in, say, math. In
math (at least in my mind), to say that something is a problem sort of
implies it is unsolved. In AI or such fields, there are usually many
solutions to any given problem. The real goal is to create a solution
that solves as many such problems as possible, preferably in an
efficient manner.

So there are sets of problems in reinforcement learning/markov decision
process theory, sets of problems in old fashioned plannign like STRIPS,
other problems that people use neural networks for (say,
self-organizing maps), etc. If you can formalize problems from multiple
domains in the same manner, then you might be on to something. Though
one could say that since all such problems are implemented on
computers, one can formalize all problems in terms of basic operations,
so that should be extended to say that the formalization ought to be
useful in that, e.g., it provides insight into commonalities across
domains that can be exploited to make better solutions.
(Or such are my current thoughts on these matters... upon later
reflection I may change my mind; I reserve the right to do so :)).
Post by Dan Christensen
My friend said I was "introducing the state concept" for what he called
"action logic problems." I presume he was talking about my numbering of the
various problem states, defining each state in terms of previous ones, e.g.
for all i in N, if positionOfChair( i )=1 then positionOfChair( i+1 )=2. Is
this really something new? Any comments would be appreciated.
On this I'm unclear. STRIPS, an AI planning sort of things often taught
in AI classes (never took any such things myself though, but I believe
it's standard), seems to be rather close to what you're doing here. I
suppose your friend could have deeper understanding of this than I do,
but, as I said above, the real power of a formalism is when it provides
new insight into problems, so perhaps only by continuing this work
would you discover whether or not that is the case.

+grain of salt.
T.B.
2006-10-11 16:29:26 UTC
Permalink
Post by Dan Christensen
Hi,
I am an amateur mathematician and software developer. Using my own proof
checking software, DC Proof, I have developed a formalization of the
so-called Monkey-Banana Problem that a friend assures me is really quite
innovative. It makes use of what he says is a new state concept that solves
a long outstanding problem in AI. Your comments would be appreciated.
The HTML version of my formalization, along with a simple proof
http://www.dcproof.com/Monkey.html
http://www.dcproof.com/Monkey.proof
http://www.dcproof.com
Dan, did you see the Amzi Prolog tutorial?

http://www.amzi.com/AdventureInProlog/index.htm

The Monkey-Banana problem is discussed in the vocabulary of the
Baby-Nani (search) problem. The problem is generalized as recursion,
operators and control structures are added, which leads you to the
heart of natural language processing (all in a formalism very close to
FOPL & ST).

Tom
Loading...