learn.aathan.in

The Monkey and Banana Problem: Means-Ends Analysis

A monkey, a box, and a banana hanging out of reach. The four-part state tuple, the operators, why this problem became the standard test for logical planning, and a full solver in Python and Prolog.

A monkey is in a room. A bunch of bananas hangs from the ceiling, out of reach. There is a box in the corner. The monkey can walk around, push the box, climb on it, and grab.

How does the monkey get the bananas?

Every human solves this in about two seconds. That instant obviousness is precisely why it became a benchmark: the challenge isn’t finding the answer, it’s writing down the reasoning in a form a machine can execute. This problem is where AI worked out how to represent “I need to do X first, in order to do Y”.

The problem

bananas out of reach from the floor box ABC monkey herebox herebananas above here INITIAL STATE

What the monkey can do:

  • Walk from one place to another (on the floor)
  • Push the box from one place to another (must be beside it, on the floor)
  • Climb onto the box (must be at the box’s location, on the floor)
  • Grab the bananas (must be on the box, and the box must be under the bananas)

What makes it non-trivial for a machine: the goal action (grab) has two preconditions that are not true initially, and satisfying them requires actions that have their own preconditions. The monkey must reason backwards through a chain.

State representation

Four facts fully describe the world:

state=(monkeyPos,  onBox,  boxPos,  hasBananas)\text{state} = (\text{monkeyPos},\; \text{onBox},\; \text{boxPos},\; \text{hasBananas})

ComponentValuesMeaning
monkeyPosA, B, CWhere the monkey is
onBoxTrue / FalseIs the monkey standing on the box?
boxPosA, B, CWhere the box is
hasBananasTrue / FalseHas it got them?
initial = ('A', False, 'B', False)     # monkey at A, on floor, box at B, no bananas
goal    = lambda s: s[3] is True       # any state where hasBananas

State-space size: 3×2×3×2=363 \times 2 \times 3 \times 2 = 36. Many are physically impossible — the monkey can’t be on the box at position A while the box is at B — and the operators simply never produce those.

Note again that the goal is a predicate, not a target state. We don’t care where the monkey ends up, only that it has the bananas.

The operators

WALK(from → to)PUSH(from → to) CLIMBGRAB pre:eff: pre:eff: pre:eff: pre:eff: monkey is at `from`, NOT on the box (can't walk while standing on a box) monkeyPos ← to monkey at `from`, box at `from`, monkey NOT on the box monkeyPos ← to, boxPos ← to monkeyPos == boxPos, NOT on box (must be beside the box to climb it) onBox ← True onBox is True AND boxPos == C (on the box, under the bananas) hasBananas ← True

Two preconditions carry all the difficulty:

  • PUSH requires the monkey and the box to be in the same place. So the monkey can’t push the box from across the room — it must walk there first. That’s one link in the chain.
  • GRAB requires onBox AND boxPos == C. Being on the box isn’t enough; the box must already be under the bananas. So the push has to happen before the climb — and climbing first is a trap, because a monkey standing on a box can’t push it.

That last point is a real dead end in the state space, and it’s what makes the problem instructive. A search that climbs too early has to back out.

BANANA_POS = 'C'
PLACES = ['A', 'B', 'C']

def successors(state):
    pos, on_box, box, has = state
    if has:
        return []                                # nothing left to do

    out = []
    if not on_box:
        for p in PLACES:
            if p != pos:
                out.append(((p, False, box, has), f'walk {pos}→{p}'))
        if pos == box:
            for p in PLACES:
                if p != pos:
                    out.append(((p, False, p, has), f'push box {pos}→{p}'))
            out.append(((pos, True, box, has), 'climb onto box'))
    else:
        out.append(((pos, False, box, has), 'climb down'))
        if box == BANANA_POS:
            out.append(((pos, True, box, True), 'GRAB BANANAS'))
    return out

The solution, traced

1. WALK A → B ABC The monkey must be at the box before it can push it. This step has no other purpose — it exists purely to enable the next one. 2. PUSH box B → C ABC Pushing moves both the monkey and the box — one action, two changes to the state. Now boxPos = C, satisfying half of GRAB's precondition. 3. CLIMB onto box ABC Order matters — climbing before pushing is a dead end. PUSH requires `not onBox`, so a monkey already standing on the box must climb down before it can move it anywhere. 4. GRAB ✓ ABC Both preconditions now hold: onBox = True ✓ boxPos = C ✓ Four actions. Three of them exist only to enable the fourth.
#ActionState after
—start('A', False, 'B', False)
1walk A→B('B', False, 'B', False)
2push box B→C('C', False, 'C', False)
3climb onto box('C', True, 'C', False)
4GRAB BANANAS('C', True, 'C', True) ✅

Means-ends analysis: reasoning backwards

The solution above reads forwards, but that’s not how you find it — and it’s not how GPS (the General Problem Solver, Newell and Simon, 1959) found it either. The technique is means-ends analysis: start from the goal and work backwards, asking “what’s the difference between where I am and where I want to be, and which operator reduces that difference?”

GOAL: hasBananas apply GRAB but GRAB needs two things to be true first: sub-goal: onBox sub-goal: boxPos = C apply CLIMB apply PUSH B→C both need: monkeyPos = boxPos → WALK A→B CLIMB needs the monkey to be beside the box. PUSH needs the same, and `not onBox`.

The algorithm, stated plainly:

  1. Compare the current state with the goal. What’s different?
  2. Pick an operator whose effect reduces that difference.
  3. If its preconditions don’t hold, recursively make them hold — that becomes a sub-problem.
  4. Apply the operator. Repeat.

Applied here:

  • Difference: hasBananas is False, want True.
  • Operator that fixes it: GRAB.
  • Preconditions unmet: onBox and boxPos == C. Two new sub-problems.
  • boxPos == C → operator PUSH. Its precondition monkeyPos == boxPos is unmet → sub-problem → operator WALK A→B. That one’s applicable now.
  • Unwind: walk, push, climb, grab.

Means-ends analysis was a genuine breakthrough — Newell and Simon’s GPS solved this and a dozen similar problems with one general engine. It also revealed the approach’s limits: it depends entirely on being able to quantify the difference between two states, and for problems where progress isn’t measurable in an obvious way, it flounders. Notice too that it hits the same interference problem as block world — CLIMB and PUSH conflict, and the ordering has to be discovered rather than assumed.

Full working code

from collections import deque

PLACES = ['A', 'B', 'C']
BANANA_POS = 'C'


def successors(state):
    """state = (monkeyPos, onBox, boxPos, hasBananas)"""
    pos, on_box, box, has = state
    if has:
        return []

    out = []
    if not on_box:
        # WALK
        for p in PLACES:
            if p != pos:
                out.append(((p, False, box, has), f'walk {pos}→{p}'))
        if pos == box:
            # PUSH — moves the monkey too
            for p in PLACES:
                if p != pos:
                    out.append(((p, False, p, has), f'push box {pos}→{p}'))
            # CLIMB
            out.append(((pos, True, box, has), 'climb onto the box'))
    else:
        out.append(((pos, False, box, has), 'climb down'))
        if box == BANANA_POS:
            out.append(((pos, True, box, True), 'GRAB THE BANANAS'))
    return out


def solve(initial):
    frontier = deque([(initial, [])])
    seen = {initial}
    while frontier:
        state, path = frontier.popleft()
        if state[3]:                                  # hasBananas
            return path
        for nxt, action in successors(state):
            if nxt not in seen:
                seen.add(nxt)
                frontier.append((nxt, path + [(action, nxt)]))
    return None


if __name__ == '__main__':
    initial = ('A', False, 'B', False)
    print(f'start: monkey at {initial[0]}, box at {initial[2]}, '
          f'bananas above {BANANA_POS}\n')
    for i, (action, state) in enumerate(solve(initial), 1):
        pos, on_box, box, has = state
        where = f'monkey {pos}{" (on box)" if on_box else ""}, box {box}'
        print(f'{i}. {action:<22} → {where}')

Output:

start: monkey at A, box at B, bananas above C

1. walk A→B             → monkey B, box B
2. push box B→C          → monkey C, box C
3. climb onto the box    → monkey C (on box), box C
4. GRAB THE BANANAS      → monkey C (on box), box C

The Prolog version

This problem is the traditional “hello world” of Prolog, because logical programming expresses preconditions so directly. The whole solver is nine lines:

% state(MonkeyPos, OnBox, BoxPos, HasBananas)

move(state(P, onfloor, P, H),  climb,        state(P, onbox,   P, H)).
move(state(P, onbox,   P, H),  climbdown,    state(P, onfloor, P, H)).
move(state(P1, onfloor, P1, H), push(P1,P2), state(P2, onfloor, P2, H)).
move(state(P1, onfloor, B, H),  walk(P1,P2), state(P2, onfloor, B, H)).
move(state(c, onbox, c, no),    grab,        state(c, onbox, c, yes)).

canget(state(_, _, _, yes), []).
canget(State1, [Move|Rest]) :-
    move(State1, Move, State2),
    canget(State2, Rest).

Query it:

?- canget(state(a, onfloor, b, no), Plan).
Plan = [walk(a,b), push(b,c), climb, grab].

Prolog’s backtracking search is the state-space search — you write the operators and the goal, and the language finds the path. That’s the appeal that made logic programming a major branch of AI in the 1980s.

A caution about the Prolog version: canget has no cycle detection, so depth-first search can loop forever (walk A→B, walk B→A, walk A→B…) on harder variants. Real Prolog planners add a visited list or an iterative depth bound. The nine-line version works here only because a solution exists at shallow depth and Prolog happens to try the productive clauses first.

Variants and what they teach

VariantWhat changesWhy it’s interesting
Two boxes needed (bananas higher)Must stack boxesSub-goals now interfere — the Sussman anomaly again
Box is too heavy aloneNeeds a second monkeyMulti-agent planning and coordination
Monkey doesn’t know where the box isPartial observabilityRequires sensing actions and belief states
Push might failStochastic actionsBecomes an MDP — solved with value iteration, not search
Bananas moveDynamic environmentNeeds replanning, not a one-shot plan

That progression is a decent map of the last fifty years of AI planning research. Each variant breaks an assumption of the classical formulation — determinism, full observability, a static world — and each break spawned a subfield.

Why this problem matters

Monkey and banana is the canonical demonstration that intelligent behaviour can be produced by explicit reasoning over a symbolic representation. That was genuinely in doubt in the 1950s. Newell and Simon’s GPS solving it, along with logic theorems and cryptarithmetic puzzles, with one engine, was the evidence that launched symbolic AI.

The concrete ideas that outlived it:

  • Preconditions and effects — now formalised as PDDL, used by every automated planner from factory scheduling to spacecraft operations.
  • Backward chaining — reasoning from goal to available actions. This is how Prolog resolves queries, how expert systems diagnose, and how a modern LLM agent decomposes “book me a flight” into steps.
  • Enabling actions — three of the four steps here produce nothing of value themselves. Recognising that some work exists only to make other work possible is what separates planning from reacting.

And it’s a fine model for the tool-using agents being built right now. An agent asked to “summarise the config file” must chain: to summarise, it needs the contents; to get the contents, it needs the path; to get the path, it needs to search. Precondition chains, backward-chained. The monkey has been solving that problem since 1959.

Where to go next