An idea introduced by Newell, Simon and Shaw in their General Problem Solver (GPS) program was that instead of choosing actions blindly, as above, the planner should concentrate on those actions which are most likely to lead it towards the final goal. This is called means-end planning: choosing a means which is likely to achieve the desired end.
My planner uses a method called goal regression, and introduced by STRIPS. The idea is that we look at the add-lists of all the actions. Some actions will have add-lists which add propositions we want in our goal. We imagine that we'll apply one of these actions, and ask what new goals need to be satisfied in order for us to do so. We then treat these in the same way and pick an action that will satisfy them, and so on.
An example will help. As I showed in section 8.1, our goal state is
clear( [8,4] )We can select actions that might work towards this goal by looking at the add-lists. In essence, we want an action whose add-list contains a
clear: that is, one which makes a square clear. One such action
is to use a key. Its add- and delete-lists show that we would get the
state
clear( [8,4] )if we applied it to the following state:
have( key(1) ), square( door(2), [8,4] ).In other words, we can make
[8,4] clear if we have key 1, and we
use it on a door in [8,4]. But this requires us to have a key, so
we set that as a new goal. We now need to find an action which gets a
key into our hand: namely grab. But that requires us to be in the
same square as a key, so we must set the goal of getting to that square.
And so on. What we are doing is simplifying the problem by breaking the
original goal into a series of subgoals; in this case, using
goal-regression to do so.