Difference between "plan-space" and "state-space"

State-space search produces inflexible plans.
State-space search wastes time examining many different orderings of the same set of actions.

Plan-space search:

1. no notion of states, just partial plans
2. adopts a least-commitment strategy: don’t commit to orderings, instantiations, etc, unless necessary
3. produces a partially ordered plan: represents all sequences of actions compatible with the partial ordering
4. benefits: speed-ups (in principle), flexible execution, easier replanning

(Part of the ordering in an action sequence is not related to causality)

Plan-space 里的基本要素

1. multiset O of operators {o1, . . . , on}
2. set < of ordering constraints oi < oj (with transitivity built in)
3. set B of binding constraints x = y, x ?= y, x ∈ D, x ?∈ D, substitutions.
4. set L of causal links oi →p oj stating that (effect p) of oi establishes precondition p of oj, with oi < oj and binding constraints in B for parameters of oi and of appearing in p

Action step

1. initial node is (O : {start,end},<: {start < end},B : {},L : {})
   with eff(start) = s0 and pre(end) = g (Nodes are partial plans)
2. Successors are determined by plan refinment operations.
   each operation add elements to O, <, B, L to resolve a flaw in the plan
3. Search through the plan space until a partial plan is found which has no flaw.

categary of flaw:
1.no open precondition: all preconditions of all operators in O are established by causal links in L
2.no threat (each linearisation is safe): for every causal link oi →p oj, every ok with eff?(ok) unifable with p is such that ok < oi or oj < ok
（任何一個(gè)operation 都不能改變?nèi)我籧ausal link（ oi →oj） 產(chǎn)生的針對(duì)下一個(gè)operation的precondition，即 它發(fā)生順序不能在oi和oj之間，只能在oi前或者oj后發(fā)生）
3.< and B are consistent(根據(jù)我們的添加方法多艇，這些flaw一般都是滿(mǎn)足的。)

Note:只要我們將flaws都解決了贪婉，那么order plan 也就出來(lái)了。

Solution of flaw
針對(duì)第一個(gè)flaw（no open precondition）：

1. find an operator o′ (either already in the plan or insert it) which can be used to establish p, i.e. o′ can be ordered before o and one of its effects can unify with p
2. add to B binding constraints to unify the effect of o′ with p(修改binding constraints set)
3. add to L the causal link o′ →p o (and the ordering constraint o′ < o).(修改causal links set)

針對(duì)第二個(gè)flaw（no threat （each linearisation is safe））：
3 possibilities:

1. order c after b(修改ordering constraints set)
2. order c before a(修改 ordering constraints set)
3. add a binding constraint preventing c to delete p(修改binding constraints set)

Note：

1. Plan-Space-Planning is sound and complete
2. Grounded variant: no binding constraints needed