Abstraction heuristics --------is admissible (and consistent)

Simplify the problem by ignoring parts of it.

1. Drop preconditions from actions.
2. Consider only a subset of predicates/propositions.
3. Count objects with a given property, ignoring the identity of objects.(eg. count clear boxes)
4. Ignore so much that the abstract problem is small enough to be solved by uninformed search.
5. Use memory to avoid repeated searches (pattern databases).

Formal definition
ProblemP′ = (S′,A′,γ′,s′0,SG′ ,c′)isanabstractionofP = (S,A,γ,s0,SG,c) if there exists an abstraction mapping φ : S → S′, then

1. φ preserves the initial state: φ(s0) = s′0
2. φ preserves goal states: ifs∈SG thenφ(s)∈SG′
3. φ preserves transitions:
   if γ(s, a) = t then ?a′ ∈ A′ γ′(φ(s), a′) = φ(t) with c′(a′) ≤ c(a)

The abstraction heuristic hφ(s, g) induced by φ is given by the the cost of the optimal path from φ(s) to φ(g) in P′

Landmark heuristics

Proposition l is a landmark for problem P iff all plans for P make l true.

Sufficient condition for proposition l to be a landmark for problem P: the delete relaxation P+ is not solvable when l is removed from the add-list of all actions.(一個(gè)命題是 landmark 則，如果命題 l 不屬于actions list ，那么p+ 不能夠被解決)

啟發(fā)之定義：counts the number of yet unachieved landmarks. generalisation of the number of unachieved goals heuristic used in the LAMA planner [Richter, AAAI 2008]

The current best heuristics are landmark heuristics variants

P+ be the relaxed problem obtained by ignoring the negative effects (delete list) of every action

Progression planning（Forward-Search）

Forward-Search feature

1. can be used in conjunction with any search strategy to implement choose, breadth-first search,depth-first search, iterative- deepening, greedy search, A*.
2. Forward-Search is sound: any plan returned is guaranteed to be a solution to the problem.
3. Forward-Search is complete: provided the underlying search strategy is complete, it will always return a solution to the problem if there is one.

Forward-Search problem
it can have a large branching factor, It wastes a lot of time trying irrelevant actions.

solution:

1. domain-specific: search control rules, heuristics.
2. domain-independent: heuristics extracted from the STRIPS .
3. problem description backward search: from the goal to the initial state.

Regression planning (backward search)

Comparation
For forward search, we started at the initial state and computed state transitions, leading to a new state γ(s, a)

For backward search, we start at the goal and compute inverse state transitions a.k.a regression, leading to a new goal γ?1(g, a)

不同之處：

1. Regression planning is in the space of goals. Goals don't make the closed world assumption, so you don't know the value of the propositions that are not mentioned in the goal.
   The way to forbid loops is to check that no ancestor is labelled by a goal (set of propositions) that is a susbset of the goal labelling the current node.

2. Forward search the nodes are labelled by states: everything mentioned in a state is true and the rest is false.
   The way to forbid loops is just to check whether the state labelling of your ancestor is the same state labelling the current node

使用說(shuō)明：當(dāng)start點(diǎn)leaf node多，那么就用backward search，反之，就用forward search。In both of them need to "forbid" loops in conjunction with DFS

the way to form last state: If a is relevant for g then: γ?1(g, a) = (g \ eff+(a)) ∪ pre(a)

An action a is relevant for goal g if:
– it makes at least one of g’s propositions true: g ∩ eff+(a) ?= { }
– it does not make any of g’s proposition false: g ∩ eff?(a) = { }

Example
– g = {on(D, B), clear(D), ontable(A), clear(A)}

– a = putdown(R1, A)
operator putdown(r, x)
precondition {holding(R1,A)}
effect {ontable(A), clear(A), handempty(R1), ?holding(R1, A)}

– γ?1(g, a) = {on(D, B), clear(D), holding(R1, A)}

性質(zhì)：
Backward-Search is sound: any plan returned is guaranteed to be a solution to the problem.

Backward-Search is complete: provided the underlying search strategy is complete, it will always return a solution to the problem if there is one.

Regression planning (backward search) 改進(jìn)——Lifting

We can substancially reduce the branching factor if we only partially in- stanciate the operators.

For instance, in the Blocks World, we may not need to distinguish between using robot hand R1 and robot hand R2. Just any hand will do.

After the regression, we obtain
g←{on(D,y),clear(D),handempty(r),on(A,B),clear(A),handempty(r′),y?=B,r?=r′}
π←?unstack(r′,A,B),unstack(r,D,y),putdown(r′,A),stack(r,D,E)? withy?=B,r?=r′

while,
initial state: s = {on(D, E), clear(D), handempty(R1), on(A, B), clear(A), handempty(R2), . . .}
therefore, s satisfies g:σ←{r←R1,r′ ←R2,y←E}

result plan:
π ← ?unstack(R2, A, B), unstack(R1, D, E), putdown(R2, A), stack(R1, D, B)?

總結(jié)

State-space planning produces totally-ordered plans by a forward or backward search in the state space. This requires domain-independent heuristics or domain-specific control rules to be efficient