- based on Planning Graph structure.
- based on propositional logic : Pushing the Envelope: Planning, Propositionl Logic, and Stochastic Search
based on Planning Graph structure:
- Graphplan (Fast Planning Through Planning Graph Analysis): A Planning Graph encodes the planning problem in such a way that many useful constraints inherent in the problem become explicitly available to reduce the amount of search needed. Furthermore, Planning Graphs can be constructed quickly: they have polynomial size and can be built in polynomial time.
A Planning Graph is not the state-space graph. In fact, unlike the state-space graph in which a plan is a path through the graph, in a Planning Graph a plan is essentially a flow in the network flow sense.
Searching for a plan: Given a Planning Graph, Graphplan searches for a valid plan using a backward-chaining strategy. It uses a level-by-level approach, in order to best make use of the mutual exclusion constraints.
In particular, given a set of goals at time t, it attempts to find a set of actions (no-ops included) at time t − 1 having these goals as add effects. The preconditions to these actions form a set of subgoals at time t − 1 having the property that if these goals can be achieved in t − 1 steps, then the original goals can be achieved in t steps. If the goal set at time t − 1 turns out not to be solvable, it tries to find a different set of actions, continuing until it either succeeds or has proven that the original set of goals is not solvable at time t.
To implement this strategy, it uses the following recursive search method:For each goal at time t in some arbitrary order, select some action at time t − 1 achieving that goal that is not exclusive of any actions that have already been selected. Continue recursively with the next goal at time t. (Of course, if by good fortune a goal has already been achieved by some previously-selected action, we do not need to select a new action for it.) If our recursive call returns failure, then try a different action achieving our current goal, and so forth, returning failure once all such actions have been tried. Once finished with all the goals at time t, the preconditions to the selected actions make up the new goal.