[AI planning] stack planning and prolog code

2016-08-08

In the previous article, I talked about the forward planning. However, there are still some problem:

  1. Plans may contain redundant steps
  2. Planning may not terminate for some problems(due to depth first search)

So a better way to solve STRIPS problems is to search backwards from the goal in world(situation) space.

  • Goals are matched against operator postconditions
  • Operator preconditions becomes subgoals
  • We stop when the operator preconditions(subgoals) are satisfied in the initial state

Searching backwards often reduces the branching factor.

Goal stack planning algorithm:

  1. Assume stack(starts empty), plan(starts empty), state(starts with initial state)
  2. Push the original conjunction of goals on the stack
  3. Repeat until the stack is empty
  • if the top of the stack is an achieved goal, pop it from the stack
  • if the top of the stack is a conjunctive goal, push its unachieved subgoals on the stack
  • if the top of the stack is a single unachieved goal, replace it by an action that achieves the goal and push the action’s precondition on the stack
  • if the top if the stack is an action, pop it from the stack, execute it(add it to the plan) and update the state using the action’s add and delete lists

Goal stack planning in Prolog:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
:- use_module(library(lists)).
gsp(S,G,P) :-
list_to_set(S,SS),
list_to_set(G,GS),
gsp(SS,GS,P,_).
gsp(S,G,[],S) :- holds(G,S).
gsp(S,[G|Gs],P,S1) :-
holds([G],S), !,
gsp(S,Gs,P,S1).
gsp(S,[G|Gs],P,S3) :-
pop(O,Pre,A,D),
member(G,A),
gsp(S,Pre,P1,S1),
apply(S1,A,D,S2),
gsp(S2,Gs,P2,S3),
append(P1,[O|P2],P).
holds([],_).
holds([Pre|Ps],S) :- select(Pre,S,S1), holds(Ps,S1).
apply(S,A,D,S1) :-
subtract(S,D,S2), union(S2,A,S1).
pop(move_to_table(X),
[block(X),block(Y),on(X,Y),clear(X)],
[on(X,table),clear(Y)],
[on(X,Y)]).
pop(move(X,Y),
[block(X),block(Y),on(X,Z),clear(X),clear(Y)],
[on(X,Y),clear(Z)],
[on(X,Z),clear(Y)]).
initial_state([block(a),block(b),block(c),
on(b,table),on(c,a),on(a,table),clear(b),clear(c)]).
goal_state([on(a,b),on(b,c),on(c,table)]).

Here is some description for the code:
gsp will be terminated when the states contains all the goals, that means, all the goals have been achieved. Else if the “states” contains the top of the stack of goals, we need to pop that goal. Else, we need to find a action which can produce a add list which contains the top of the stack(Goal). Then achieve that precondition, it will come out with a newState, apply the previous add list and delete list to the newState, then the newState will be the most updated state. We continue searching based on the new state.

Important notes:

The order of the pop really matters, for example,
we can not write:

1
2
3
4
5
6
7
8
pop(move(X,Y),
[clear(X),clear(Y),block(Y),on(X,Z)],
[on(X,Y),clear(Z)],
[on(X,Z),clear(Y)]).
pop(move_to_table(X),
[clear(X),block(Y),on(X,Y)],
[on(X,table),clear(Y)],
[on(X,Y)]).

We need to write:

1
2
3
4
5
6
7
8
pop(move_to_table(X),
[block(X),block(Y),on(X,Y),clear(X)],
[on(X,table),clear(Y)],
[on(X,Y)]).
pop(move(X,Y),
[block(X),block(Y),on(X,Z),clear(X),clear(Y)],
[on(X,Y),clear(Z)],
[on(X,Z),clear(Y)]).

It is so important, because clear precondition must appear first, even before block. We have no operator to achieve it, so it has to appear last, and match as part of the complete goal state.
This diagram illustrate the process of the goal stack planning:
stack

Problems with goal stack planning:

  • Working backwards from unachieved goals in goal stack planning focuses search and often leads to shorter plans
  • however there still problem:
    1. plans may still contain redundant steps
    2. plans may not achieve the goal
    3. planning may not terminate for some problems(due to depth first search)
  • More difficult to handle existentially quantified goals(general issue with regression planning)

Sometimes, it may exist clobbering. Clobbering is steps later in the plan destroy a state created by steps earlier in the plan that achieves an(already processed) subgoal. So we need to protect the achieved goals. The following is the prolog code with Goal stack planning with protected goals:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
:- use_module(library(lists)).
% gsppg(+State,+Goals,-Plan): Plan is a sequence of operators
% that applied in State achieves Goals
gsppg(S,Gs,P) :-
list_to_set(S,SS),
list_to_set(Gs,GS),
gsppg(SS,GS,[],P,_).
% gsppg(+State,+Goals,+ProtectedGoals,-Plan,-NewState): Plan is a
% sequence of operators that applied in State achieves Goals without
% clobbering any goal in ProtectedGoals and results in NewState
gsppg(S,Gs,_,[],S) :- holds(Gs,S).
gsppg(S,Gs,PGs,P,S3) :-
select_goal(S,Gs,G),
pop(O,Pre,A,D),
member(G,A),
intersection(D,PGs,[]),
intersection(Pre,PGs,[]), % avoid infinite regress
gsppg(S,Pre,[G|PGs],P1,S1),
apply(S1,A,D,S2),
gsppg(S2,Gs,[G|PGs],P2,S3),
append(P1,[O|P2],P).
% holds(+Goal,+State): Goal is achieved in State. As operators are
% ground, we can use member/2 rather than select/3.
holds([],_).
holds([G|Gs],S) :- member(G,S), holds(Gs,S).
% select_goal(State,+Goals,+Goal): Goal is goal in Goals not achieved in
% State
select_goal(S,Gs,G) :-
member(G,Gs), \+ member(G,S).
apply(S,A,D,S1) :-
subtract(S,D,S2), union(S2,A,S1).
pop(move_to_table(X),
[clear(X),on(X,Y)],
[on(X,table),clear(Y)],
[on(X,Y)]) :-
block(X), block(Y), X \= Y.
pop(move(X,Y),
[clear(X),clear(Y),on(X,Z)],
[on(X,Y),clear(Z)],
[on(X,Z),clear(Y)]) :-
block(X), block(Y), block_or_table(Z), X \= Y, X \= Z, Y \= Z.
block(a).
block(b).
block(c).
block_or_table(X) :- block(X).
block_or_table(table).
initial_state([on(b,table),on(c,a),on(a,table),clear(b),clear(c)]).
goal_state([on(a,b),on(b,c),on(c,table)]).

Here is some description for these code: Firstly, it selects a goal which is a member of the goals but it’s not a member of the states. intersection(A, B, C), C will be the same element between A and B, if it does not contain any repeated element, then it will return []. So intersection(D,PGs,[]) ensures that the achieved goals do not contain the delete item. intersection(Pre,PGs,[]) ensures that the achieved goals do not contain the precondition. (It can avoid infinite regress). There is a very important point that the operator mush be ground! You maybe confused at what is a ground operator, the below operator is not a ground operator:

1
2
3
pop(move(X,Y),
[block(X),block(Y),
clear(X),clear(Y),on(X,Z)], [on(X,Y),clear(Z)], [clear(Y),on(X,Z)]).

This is a ground operator:

1
2
3
4
5
pop(move(X,Y),
[clear(X),clear(Y),on(X,Z)],
[on(X,Y),clear(Z)],
[on(X,Z),clear(Y)]) :-
block(X), block(Y), block_or_table(Z), X \= Y, X \= Z, Y \= Z.

Because that may cause the clobber, so the only(simple) way to ensure that an operator won’t clobber a protected goal, is to force the planner to guess values for all uninstantiated variables in the operator.


Comments: