A classic AI planning puzzle. Bananas hang from the ceiling, a box stands elsewhere in the room, and the monkey must walk, push, climb, and grab in the right order. EyeProlog searches short move sequences and returns every plan that works.
Run it in the playground · Source
The bananas are above loc1, the monkey is at loc2, and the box is at
loc3. The monkey can reach the bananas only by standing on the box directly
beneath them. Which sequences of at most five moves end with the monkey
holding the bananas?
initial_state([loc1, loc2, loc3, n, n]).
goal_state([_, _, _, _, y]).
legal_move([B, M, M, n, H], climb_on, [B, M, M, y, H]).
legal_move([B, M, M, y, H], climb_off, [B, M, M, n, H]).
legal_move([B, B, B, y, n], grab, [B, B, B, y, y]).
legal_move([B, M, M, n, H], push(X), [B, X, X, n, H]) :-
member(X, [loc1, loc2, loc3]),
(X \= M).
legal_move([B, M, L, n, H], go(X), [B, X, L, n, H]) :-
member(X, [loc1, loc2, loc3]),
(X \= M).
A state lists the bananas’ location, the monkey’s location, the box’s
location, whether the monkey is on the box, and whether it has the bananas.
Repeated variables do the work: grab applies only when bananas, monkey, and
box are all at the same place B.
plan(Moves) :-
candidate_plan(Moves),
initial_state(I),
goal_state(G),
reachable_state(I, Moves, G).
candidate_plan([_, _, _]).
candidate_plan([_, _, _, _]).
candidate_plan([_, _, _, _, _]).
reachable_state(S, [], S).
reachable_state(S1, [M|L], S3) :-
legal_move(S1, M, S2),
reachable_state(S2, L, S3).
A plan is a list of three, four, or five unknown moves; reachable_state/3
fills them in. Fixing the length first keeps the search finite.
eyeprolog examples/monkey-bananas.pl
plan(monkeyBananas, [go(loc3), push(loc1), climb_on, grab]).
plan(monkeyBananas, [go(loc1), go(loc3), push(loc1), climb_on, grab]).
plan(monkeyBananas, [go(loc3), push(loc1), climb_on, grab, climb_off]).
plan(monkeyBananas, [go(loc3), push(loc2), push(loc1), climb_on, grab]).
solved(monkeyBananas, true).
The shortest plan has four moves: walk to the box, push it under the bananas, climb on, grab. No three-move plan exists. The five-move plans add a detour or a final climb down.
step(plan([go(loc3), push(loc1), climb_on, grab]),
rule(1),
['Moves' = [go(loc3), push(loc1), climb_on, grab],
'I' = [loc1, loc2, loc3|"nn"],
'G' = [loc1, loc1, loc1|"yy"]],
[candidate_plan([go(loc3), push(loc1), climb_on, grab]),
initial_state([loc1, loc2, loc3|"nn"]),
goal_state([loc1, loc1, loc1|"yy"]),
reachable_state([loc1, loc2, loc3|"nn"], [go(loc3), push(loc1), climb_on, grab], [loc1, loc1, loc1|"yy"])]).
The plan is a four-move candidate that reaches the goal from the initial
state. In the goal everything is at loc1, with the monkey on the box and
holding the bananas. (The tail [n, n] is printed as "nn": a list of
one-character atoms is written in double-quote notation.)
condition('C1', resolution, ok, 41).
condition('C5', re_decision, ok, 8).
steps(49).
verified(41).
recomputed(8).
trusted(0).
verdict(checked).
Every move in every plan is replayed against the legal_move/3 clause it
uses, and the eight \= tests are recomputed. Nothing is trusted.
candidate_plan([_, _]) and confirm that no two-move plan exists.loc1). What is the
shortest plan now?jump that works only from the box. Which new plans appear?Learn more in The Art of EyeProlog, Chapter 24.