Prolog planner only generates one plan

Question

I have a prolog planner which works correctly with one major problem of only generating one plan at the time. The plan is correct but for my application I really need to have all the possible plans.

plan(State, Goal, _, Moves) :-  subsetB(Goal,State),
                            write('moves are'), nl,
                            reverse_print_stack(Moves).
plan(State, Goal, Been_list, Moves) :-
                            effects(Name, [Preconditions, Add,Delete]),  //a list of of rules governing the domain
                            conditions_met(Preconditions, State),       //checks if all preconditions are present in the state
                            change_state(State, Add,Delete, Child_state), //add predicates from Add list, removes predicates in the Delete list and stores result in Child_state
                            \+(member_state(Child_state, Been_list)),     //checks if Child_state hasn't been previously visited
                            stack(Child_state, Been_list, New_been_list),
                            stack(Name, Moves, New_moves),
                    plan(Child_state, Goal, New_been_list, New_moves).


change_state(S, [],[], S).
change_state(S, [], Delete, S_new) :-   change_state(S, [],[], S2),
                                    apply_del(Delete, S2, S_new).
change_state(S, Add,Delete, S_new) :-   change_state(S, [], Delete, S2),
                                    apply_add(Add, S2, S_new).


apply_add([],State,State).
apply_add([activate(App)|Rest],State,InterimState) :-apply_add(Rest,State,S2),find_stones(App,State,StonesToBeActivated), make_active(StonesToBeActivated,S2, InterimState).
apply_add([First|Rest],State,InterimState) :- apply_add(Rest,State,S2),add_element(First, S2, InterimState).


apply_del([],InterimState,InterimState).
apply_del([First|Rest],InterimState,NewState) :- apply_del(Rest, InterimState,S2),del_element(First, S2, NewState).



subsetB([],_).
subsetB([F|R],S) :- member(F,S),subsetB(R,S).



%dropping a stone inside app1 
 effects(drop(X,app1),                     %action
   [[stone(X),active(X)],                  %preconditions
    [in(app1,X)],                          %postconditions : add list
    [active(X)]]).                         %postconditions : delete list

go(S,G,AllPlans):- findall(Moves, plan(S,G,[S],Moves),AllMoves).

conditions_met(P, S) :- subsetB(P, S).

Sample call go([in(app1,s1), stone(s2), active(s2),stone(s3),active(s3)],[in(app1,s1),in(app1,s3),in(app1,s2)],AllPlans).

Answer:

drop(s2,app1) drop(s3,app1) //correct _2368 _2366 _2364 _2362 _2360 _2358 _2356 _2354 _2352 _2350 _2348 _2346 _2344 _2342 _2340 _2338 _2336 etc... infinitely

Answer 1

For finding all solutions to a goal, look at bagof or findall. Or am I missing something?

Like this:

?- findall(Moves, plan(State, Goal, _, Moves), AllMoves).

The whole idea of these predicates is that you say which arguments you want to collect and get a list of all possible instantiations under that predicate. In this sense you normally have a "return" value (an argument that gets instantiated with the result) that you can then look at or print, instead of printing it explicitly in the predicate that finds solutions.

A simplistic example:

foo(1). foo(2). foo(3). foo(4). foo(5). foo(6).
bar(R) :- foo(A), A mod 2 =:= 0.

findall(R, bar(R), Even).

Now to recursion: how does it work? You cannot share variables between different clauses of the same predicate. For example, this is wrong:

baz(0, B).
baz(X, B) :- X0 is X - 1, B1 is B + 1, baz(X0, B1).

because B is a singleton variable in the first clause of baz. Instead, you can do:

baz(0, B, B).
baz(X, B, Result) :- X0 is X - 1, B1 is B + 1, baz(X0, B1, Result).

which you can now call:

?- baz(10, 2, Result).
Result = 12

but you will still run into problems after the first answer.

You get the single correct plan probably because the first clause of plan does not meet the requirements of subsetB, and you get to the second clause. There, you make a Moves that has a free variable at its Tail, but this is not a problem yet. The problem is, however, that when you find your first solution (all in the second plan clause, recursively), Moves is now bound to a list of actions, and instead of starting to look for a new solution, you get into the second clause again by backtracking, with the already filled in Moves, which probably messes up the rest of the algorithm.

To make it correct, you probably need to make sure that when your plan backtracks, it starts to look for a new solution, with a clean Moves. You can start by instantiating Moves to an empty list and collecting results in an accumulator, as shown in the simplistic baz predicate above.