This is how Graphplan [Blum & First, IJCAI 1995] implements this idea:
- Build a planning graph which can be viewed as a relaxation of the state space over k steps (note: a step includes several parallel actions). This can be done in polynomial time.
- The planning graph captures information about pairs of mutually exclusive actions and propositions. It gives us a necessary but insufficient condition for when the goal is reachable in k steps.
- Attempt to extract a parallel plan from the graph using a form of backward search through the graph.
- If the extraction is unsuccessful, k is incremented, the graph extended, and a new extraction performed, and so on, until a plan is found or we determine that the problem is unsolvable.
简言之，
- 建立a relaxation of the state space 在 k 个阶层里（每个阶层都可能会有并行的 actions），他们都可以在多项式时间内完成。
- The planning graph 收集互斥的actions 和互斥的命题。我们可以得到必要却不充足的条件，使目标在第k层达成。
- 使用backward search，尝试从整个graph里提取出并行的plan。
- 如果提取不成功，那么通过增加1个阶层扩大graph，再次提取。反复重复，直到plan被找到或者判定这个问题是无解的。
Details
Alternating layers of propositions and actions, P0, A1, P1, . . . , Ai, Pi, . . . Ak, Pk:
- P0 = s0
- Ai+1 contains the actions that might be able to occur at time step i + 1. Their preconditions must belong to Pi. We include maintenance actions (prec p, eff p) for each proposition p ∈ Pi to represent what happens if no action at this layer in the final plan affects p.
- Pi+1contains the propositions that are positive effects of actions in Ai+1
Mutual exclusion
The plan graph records limited information about negative interactions（It records pairs of actions which cannot happen in parallel and pairs of propositions which cannot be simultaneously true. These are called mutex）
Two actions at the same level of the graph are mutex if they:
• interfere: one deletes a precondition of the other
• are inconsistent: one deletes a positive effect of the other
• have competing needs: they have mutually exclusive preconditions
Two propositions at the same level are mutex if they:
• have inconsistent support: all ways of achieving both(Two propositions) are pairwise mutex.
Two actions are independent when executing them in any order is possible and yields the same result。
The action parallelism notion underlying（优先于） the mutex relation is independence
For independence, we must avoid:
- interference: one action deletes a precondition of the other (one of the two orderings is not possible)
- inconsistence: one action deletes a positive effect of the other (the two orderings yield different results)
Usage of the graph
Necessary condition for plan existence:
If the goal propositions are present and mutex-free at some level
then a k step parallel plan achieving the goal might exist
Heuristics for planning:
(may use the serial graph: any pair of actions at the same level are mutex)
• single proposition p: “cost” of achieving p is the index of the first level in which p appears
• set of propositions: max (or sum) of the individual costs, or index of the first level at which they all appear mutex-freePlanning:
Graphplan algorithm: build the graph up until the necessary condition is reached; try extracting a plan from the graph, if this fails, extend the graph over one more level; repeat until success or termination condition (failure)
Plan extraction
Backward search, from the goal layer to the initial state layer.
Works layer by layer:
• Select an open precondition at the current layer, and choose an action producing it. The action must not be mutex with any of the parallel actions already choosen for that layer.
• When there is no more open precondition at that layer, work on achieving, at the previous layer, the preconditions of the chosen actions.
Notice
- When can it terminate asserting failure?
• stop when k > |S|: complete but inefficient
• stop when P, A, μA, μP reach a fix point: incomplete unless PSPACE = NP
(The graph has a fixpoint n such that for all i ≥ n:
Pi =Pn,μPi =μPn,Ai =An,andμAi =μAn
The size of the fixpoint graph is polynomial in that of the planning problem.) - Graphplan is sound but complete
