1

I'm working on the "monkey and bananas" problem but with 2 boxes instead of one. I tried adapting the code from 1 box to 2 boxes, but I have this problem.

I need to keep a list of "visited states" since the tree grows too big and my program crashes. In this list are all the visited states from start to the actual state, so if I'm going to go to an already visited state, the clause fails and backtrack occurs.

The problem is sometimes this happens:

 Call: (8) lists:member(estado(_G3634, p0, ventana, centro, noapiladas, notiene), [estado(_G3619, p0, ventana, centro, noapiladas, notiene)]) ? creep
 Exit: (8) lists:member(estado(_G3619, p0, ventana, centro, noapiladas, notiene), [estado(_G3619, p0, ventana, centro, noapiladas, notiene)]) ? creep

I need to check all possible positions (for instance: door (puerta), window (ventana) and middle (centro)) when trying to find all possible states, but since the variables are not instantiated, apparently they unify and member(State, List) returns true so the program backtracks and I never check all possible states.

I tried checking membership with \== but other problem happens: since the states (with uninstantiated variables) are always different (state(_G1234) is different from state(_2345)) I enter in an infinite loop and never ends since it's checking a lot of states with uninstantiated (but different) variables.

How could I solve this? Or should I try another approximation? I thought about defining a preset of "positions" but I'm not sure how to check all the different positions when executing the rules.

The rules are like this:

mover(estado(P, p0, P1, P2, A, E),
    desplazar(P, PD),
    estado(PD, p0, P1, P2, A, E)).

Where estado(P, p0, P1, P2, A, E) represents:

  1. Position of the monkey (X-Axis).
  2. Position of the monkey (Y-Axis).
  3. Position of the 1st box.
  4. Position of the 2nd box.
  5. If the boxes are stacked or not.
  6. If the monkey has the banana or not.

I should try to check all posible PD (Destiny position of the monkey) but I'm not sure how to do it.

Thanks in advance.

Shadark
  • 499
  • 1
  • 7
  • 18
  • There's one thing that's not clear to me, why is the the first argument of `estado` a variable in your list of visited states? It represents the coordinate of the monkey, right? So why is it a variable at all, why hasn't it been unified to a coordinate? That seems to me to be your problem here. – Oskar Mar 29 '15 at 16:51
  • @Oskar Sorry, I'm not sure about what are you trying to explain, I've working with Prolog since a few months ago so I don't grasp completely the concepts of unifying. I want to try all the different positions defined in my problem, but in the [original code](http://logos.cs.uic.edu/476/Resources/Prolog/monkey2.txt) doesn't seems to exist a list of different positions, they seem to work by "trial and error". I tried creating a series of posicion(centro). posicion(puerta),etc; then a function called es_posicion(X) :- posicion(X) but only works with centro since the other options are not checked. – Shadark Mar 29 '15 at 18:37
  • @Oskar I mean, how can I unify the variable to a coordinate? As I said before, in the original code I tried adapting the variables seem to unify in a posterior time (when checking different positions): `Call: (10) move(state(_G3220, onfloor, _G3220, hasnot), _G3235, _G3236) ? creep Exit: (10) move(state(_G3220, onfloor, _G3220, hasnot), climb, state(_G3220, onbox, _G3220, hasnot)) ? creep Call: (10) canget(state(_G3220, onbox, _G3220, hasnot)) ? creep Call: (11) move(state(_G3220, onbox, _G3220, hasnot), _G3240, _G3241) ? creep` – Shadark Mar 29 '15 at 18:45

1 Answers1

0

To prevent a list of variables with different names from unifying, you can use this alldif/1 predicate:

:- initialization(main).

main :-
    alldif([X,Y,Z]), % this goal succeeds
    Z=Y,
    alldif([X,Y,Z]). % this goal fails, since Z is unified with Y

alldif([]).
alldif([E|Es]) :-
   maplist(dif(E), Es),
   alldif(Es).
Anderson Green
  • 30,230
  • 67
  • 195
  • 328