In the previous article, I talked about the forward planning. However, there are still some problem:
- Plans may contain redundant steps
- 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.
- Assume stack(starts empty), plan(starts empty), state(starts with initial state)
- Push the original conjunction of goals on the stack
- 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
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.
The order of the
pop really matters, for example,
we can not write:
We need to write:
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:
- Working backwards from unachieved goals in goal stack planning focuses search and often leads to shorter plans
- however there still problem:
- plans may still contain redundant steps
- plans may not achieve the goal
- 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:
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:
This is a ground operator:
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.