Block world problem search runs out of stack space

Question

I have the following code:

move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)).
move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))).

move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)).
move(state(X, on(Y, NewY), OldZ), state(X, NewY, on(Y, OldZ))).

move(state(OldX, Y, on(Z, NewZ)), state(on(Z, OldX), Y, NewZ)).
move(state(X, OldY, on(Z, NewZ)), state(X, on(Z, OldY), NewZ)).

path(X,X,[]).
path(X,Y,[Z|ZS]) :- 
    move(X,Z),
    path(Z,Y,ZS).

Where move give us the possible movements that you can use and path should give us the path that you have to take from X to Y.

The problem is that the predicate path doesn't work as I want, i.e., if I type path(state(on(c,on(b,on(a,void))), void, void), state(void, void, on(c,on(a,on(b,void)))), X). I got ERROR: Out of local stack, but I want that that X would be

X=[state(void, void, on(c,on(a,on(b,void)))),
state(void, on(c,void), on(void(a,on(b,void))),
state(on(a,void), on(c,void), on(b,void)),
state(on(b,on(a,void)), on(c,void), void),
state(on(c,on(b,on(a,void))), void, void)].

So what am I doing wrong?

false · Accepted Answer

For a first test, there is no need to rewrite your code. Not since summer 1972¹. Instead, you can reformulate your queries sparingly.

Instead of asking for a concrete answer which demands from your Prolog system quite a bit of ingenuity, let's formulate your answer as a query! I tried it and realized that you have some nasty syntax errors in them, and after that, the query failed..

But there is a cheaper way! Let's just limit the length of the list and let Prolog fill out the rest. How long shall that list be? We know not (that is, I don't). OK, so let's try out any length! Also this is something Prolog loves. It is as easy as:

?- length(X,N),  % new
   path(  state(on(c,on(b,on(a,void))), void, void),
          state(void, void, on(c,on(a,on(b,void)))),
          X).
   X = [ state(on(b,on(a,void)),on(c,void),void),
         state(on(a,void),on(c,void),on(b,void)),
         state(void,on(c,void),on(a,on(b,void))),
         state(void,void,on(c,on(a,on(b,void)))) ],
   N = 4
;  ... .

See what I did? I only added length(X, N) in front. And out of a sudden Prolog answered with a shorter answer than you expected!

Now, is this really the best way to ask? After all, many of the answers might be simple cycles, putting a block into one place and back again... Are there really any cycles? Let's ask that first:

... --> [] | [_], ... .

?- length(X,N),
   path( state(on(c,on(b,on(a,void))), void, void),
         state(void, void, on(c,on(a,on(b,void)))),
         X),
   phrase((...,[E],...,[E],...), X).
   X = ...
   N = 6,
   E = state(void,on(c,void),on(a,on(b,void)))
;  ... .

Oh yes, there are! Now it does make sense to rule out such paths. Here is a clean way:

alldifferent([]).
alldifferent([X|Xs]) :-
   maplist(dif(X), Xs),
   alldifferent(Xs).

?- alldifferent(X),
   length(X,N),
   path( state(on(c,on(b,on(a,void))), void, void),
         state(void, void, on(c,on(a,on(b,void)))),
         X).

How far can you get with this formulation? Currently, I found a path of length 48 ... 55 ... Shouldn't it be finite? And: Is it possible to rule out such long paths for such trivial problems? Any toddler can keep the search space small... These are all fundamental questions, but they are independent of the programming problem as such.

Or, see it from another angle: The set of solutions for X is pretty large. So if we are exploring this set, where shall we start? What does it mean to be the best solution? The one that when uploaded on Utube produces the most upvotes? So what we are doing here is completely uninformed search. You would need to inform the program what kind of preference you have. It cannot guess it reasonably. OK, one heuristics would be the term size of a solution. length/2 did that.

Note that I did not dare to touch your clean code. Yes, I could have improved it somewhat, say by using path/4, but not by much. Rather stick to your highly clean style and rather do more querying instead! That is what Prolog is excellent at!

Other improvements: Use a list to represent the stack, this makes the state much more appealing.

_{1 That's the year Prolog was discovered/conceived/delivered.}

Block world problem search runs out of stack space

Answers (2)

Addendum: Probabilistic search

Related Questions