1

Instructions: Modify the attached program so that in order for the monkey to reach the bananas, he has to stand on a smaller box, which he has placed on top of a bigger one. At the beginning of the program, the boxes should be in two different locations in the room. Display on the screen the activities of the monkey.

I've been reading through the textbook (Prolog Programming for Artificial Intelligence), and Prolog is definitely proving difficult to pick up. While the book goes over how to solve the problem if there is one box, it does not mention how to begin to tackle this problem if there is more than one box. Any guidance / suggestions would be greatly appreciated. 

move(state(middle, onbox, middle, hasnot), grasp, state(middle, onbox, middle, has)).
move(state(Pos, onfloor, Pos, H), climb, state(Pos, onbox, Pos, H)).
move(state(P1, onfloor, P1, H), push(P1, P2), state(P2, onfloor, P2, H)).
move(state(P1, onfloor, P, H), walk(P1, P2), state(P2, onfloor, P, H)).

canget(state(_ ,_ ,_ , has)).
canget(state1) :-
  move(State1, Move, State2),
  canget(State2).

Question: 

canget(state(atdoor, onfloor, atwindow, hasnot)). % (monkey's horizontal position, monkey's vertical position, position of the box, and whether or not the monkey has the banana).

Only thing I can think of is to add another field to every clause for the second box's position, e.g., state(horizontal pos, vertical pos, pos for box1, pos for box2, and banana status).

mylasthope
  • 89
  • 7
  • I think I've [seen this problem before](http://stackoverflow.com/q/27674390/2936460)... – SQB Feb 22 '16 at 12:45

1 Answers1

2

Your suggested solution is one way to solve this: You can indeed simply add one more argument to the term that represents the state.

However, let us aim for something more general: How would you go about this if there are not only one or two, but n boxes in the room? Further, let us suppose the boxes are of sizes S_1, ..., S_n (S_i not necessarily distinct), and can only be stacked when the box on top is smaller than the one on which it is placed.

I suggest the following representation to denote such states:

We will use a pair Pos-Size to denote the position and size of each box. This is just infix notation for the term -(Pos, Size), i.e., functor - and arity 2.

We will use a list of such pairs, i.e., [Pos1-Size1, Pos2-Size2, ..., Pos_n-Size_n] to represent all boxes.

When stacking boxes at the same position, we need to ensure that the boxes that are already located at the same position allow such stacking. I leave this is an exercise for you.

Further, canget/1 is not really that interesting, is it? What we actually care about is the list of moves that take us to the solution! Hence, we extend the predicate with one argument that actually lets us see all moves on the toplevel, and use a more speaking name to denote what we are actually describing:

moves(state(_ ,_ ,_ , has), []).
moves(State0, [Move|Moves]) :-
        move(State0, Move, State),
        moves(State, Moves).

Now we can use iterative deepening to find concrete solutions:

?- length(Ms, _), moves(State0, Ms).

where State0 is the initial state of the puzzle.

When you become more experienced with Prolog, you will increasingly use notation to describe lists, in order to simplify the code. I leave this version here for you to study later:

moves(state(_ ,_ ,_ , has)) --> [].
moves(State0) --> [Move],
        { move(State0, Move, State) },
        moves(State).

Usage example, again using iterative deepening to find a shortest solution:

?- length(Ms, _), phrase(moves(State0), Ms).

Have fun, and also try The Art of Prolog!

mat
  • 40,498
  • 3
  • 51
  • 78
  • Thank you. I'm still taking baby steps when it comes to Prolog. As such, I've gone ahead and added another argument to each state instead of implementing the more general solution you've suggested. I've traced my program and it seems to just. However, I just want to make sure, I don't have to create any new clauses, right or will I have to create a new one so that the monkey can move either the small box or the big box independently? – mylasthope Feb 21 '16 at 23:40
  • Adding a new clause that describes the relation between states where only the new box is moved certainly seems like a good idea! It also seems a good idea to distinguish different "push" actions to denote which box is pushed. For example, either directly in the functor, is an `push_small(...)` and `push_big(...)`, or via a new argument as in `push(small, ...)` and `push(big, ...)`. The latter method certainly seems easier to generalize to further types of boxes. – mat Feb 21 '16 at 23:55
  • I think I'm doing this wrong. I edited my original program to implement different "push" actions. However, I'm running into a "Out of local stack" error. I have the following: `move(state(P1, onfloor, P1, Psmall, H), push_big(P1, P2), state(P2, onfloor, P2, Psmall, H)).` and `move(state(P1, onfloor, Pbig, P1, H), push_small(P1, P2), state(P2, onfloor, Pbig, P2, H)).` State is as follows: (monkey's pos, whether the monkey is on the box, big box's position, small box's position, and whether or not it has the banana). – mylasthope Feb 22 '16 at 04:14
  • See the predicate I gave above: It lets you reason **explicitly** about the moves that are tried. Hence, you can use *iterative deepening* to impose a certain lengths on the list of moves, as I also have shown above. Currently, you are likely running into cycles, but since you are not using any arguments to denote the moves, this is invisible for you. Make the list of moves explicit and generalize your program to see in which order the moves are tried! – mat Feb 22 '16 at 07:26