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

Your code line starting with apply_add([activate(App)|Rest],State,InterimState) truncates prematurely with a $. Copy paste error? — lurker
It is really difficult to follow the logic of your program, but the problem seems to be that your end-of-recursion is not defined properly.... Moves is not instantiated at the beginning, but seems to be part of the solution, too.... — user1812457
I thought that's how I get sicstus to actually return the variable? — bamboo10
Well yes, but it is alone in the first call up there -- where is it coming from? If you remove the side effect (the printing out) you will immediately get a "singleton variable" error. And I still cannot run your code because I am missing some definitions in the code you have here : right now it is conditions_met — user1812457

Unknown Unknown · Accepted Answer · 2013-06-17T21:32:00

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.

Prolog planner only generates one plan

1 Answers