Introduction
PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion
References
Copyright By PowCoder代写 加微信 powcoder
AI Planning
12. Pattern Database Heuristics
It’s a Long Way to the Goal, But How Long Exactly?
Part III, How-To (A): Willfully Ignoring Some of Those Variables
A ́lvaro Torralba,
Winter Term 2018/2019
Thanks to Prof. Jo ̈rg Hoffmann for slide sources
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 1/63
1 Introduction
2 Pattern Database Basics
3 Pattern Database Implementation
4 Orthogonal Patterns, and How to Exploit Them
5 Redundant Patterns, and How to Recognize Them
6 Pattern Selection
7 Conclusion
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 2/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Reminder: Our Program for Abstraction Heuristics
We take a look at abstractions and their use for generating admissible heuristic functions:
In Chapter 11, we formally introduced abstractions and abstraction heuristics and studied some of their most important properties.
In This Chapter, we discuss a particular class of abstraction heuristics and its practical handling in detail, namely pattern database heuristics.
In Chapter 13, we will discuss another particular class of abstraction heuristics and its practical handling in detail, namely merge-and-shrink abstractions.
→ We handle all these methods in FDR, where they are most natural. We do not mention STRIPS at all (which is a special case anyway).
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 4/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Motivation for Pattern Database Heuristics
→ Pattern databases are a concrete method for designing abstraction functions α, and for computing the associated heuristic functions.
There’s many good reasons to be considering PDBs:
Pattern database (PDB) heuristics are the most commonly used class of abstraction heuristics outside planning (Games, mostly). PDBs are one of the two most commonly used classes of abstraction heuristics in planning (we discuss the other class in Chapter 13). PDBs have been a very active research area from their inception, and still are a very active research area today. (Theoretical properties, how to implement and use PDBs effectively, how to find good patterns, . . . )
For many search problems, pattern databases are the most effective admissible heuristics currently known.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 5/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Our Agenda for This Chapter
2 Pattern Database Basics: Formal definition; illustration.
3 Pattern Database Implementation: How to implement PDB heuristics
(namely, via a “pattern database”).
4 Orthogonal Patterns, and How to Exploit Them: How to admissibly sum-up multiple PDB heuristics. Important because PDB heuristics are a very restricted class of abstractions, and any single individual PDB is not typically very useful. Much of their power lies in summing up their values, where admissibly possible.
5 Redundant Patterns, and How to Recognize Them: A redundant pattern is one that wastes time and memory, incurring a larger than necessary PDB without any benefits. We introduce three easily recognizable cases where that happens.
6 Pattern Selection: How to find good pattern collections. There are many possible choices and it is important to identify good ones (no redundant patterns of course, but there’s much more to it than that).
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 7/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Pattern Databases in a Nutshell
92126 26 5 7 14 13 5 7
3 4 1 11 3 4 1
“Abstract the planning task by choosing a subset P of variables (the pattern), and ignoring the values of all other variables.”
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 6/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Pattern Database Heuristics
“Pattern database heuristics” = Heuristics induced by a particular class of abstraction mappings, namely projections:
Definition (Projection, PDB Heuristic). Let Π = (V, A, c, I, G) be an FDR planningtaskwithstatespaceΘΠ =(S,L,c,T,I,SG),andletP ⊆V. Fora partial assignment φ to V , by φ|P we denote the restriction of φ to P .
Let SP be the set of variable assignments to P . The projection πP : S → SP is definedbyπP(s):=s|P. WesaythatπP isatomicif|P|=1.
→ πP maps two states s1 and s2 to the same abstract state iff they agree on all variables in the pattern.
We refer to P as the pattern of πP . The abstraction heuristic induced by πP on
ΘΠ is called a pattern database heuristic, short PDB heuristic. We write hP as
a short-hand for hπP , and we write ΘP or ΘP as short-hands for ΘπP . ΠΠ
hP is usually stored in a lookup table called a pattern database (PDB). Atomic projections will be heavily used in Chapter 13.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 9/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
“Logistics mal anders”: State Space
LRR LLL RRR RLL BLL BRR
Logistics task with one package, two trucks, two locations:
State variable package: {L, R, A, B}. State variable truck A: {L, R}.
State variable truck B: {L, R}.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 10/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
“Logistics mal anders”: Projection 2
Abstraction induced by π{package,truck A}:
h{package,truck A}(LRR) = 2
A ́lvaro Torralba,
AI Planning Chapter 12: Pattern Database Heuristics 12/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs
Pattern Selection
Conclusion
References
“Logistics mal anders”: Projection 1
Abstraction induced by π{package}: ALR
A ́lvaro Torralba,
AI Planning Chapter 12: Pattern Database Heuristics
BRL h{package}(LRR) = 2
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Larger Pattern = Refinement
Reminder: → Chapter 11 Say α is an abstraction of Θ, and α′ is an abstraction of Θα. Then α is
called a refinement of α′ ◦ α.
Proposition (Larger Patterns are Refinements). Let Π be an FDR
planningtask,andletP′ ⊆P ⊆V. ThenπP isarefinementofπP′. Proof. πP ′ can be viewed as an abstraction of ΘP , i.e., in the above set
Θα := ΘP, and set α′ to be the projection of P onto P′.
Corollary (Larger Patterns Yield Better Heuristics). Let Π be an FDRplanningtask,andletP′ ⊆P ⊆V. ThenhP dominateshP′,i.e., hP ′ ≤ hP . (From previous proposition and Chapter 11)
And, of course, hV = h∗.
Pattern size controls the trade-off between accuracy and computational cost.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 13/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Questionnaire
Remember (Chapter 11): Optimal abstract plans are not necessarily just abstractions of optimal real plans: Given an optimal real plan ⃗a, skipping the non-α-affecting actions does not necessarily result in an optimal abstract plan. Spurious transitions may lead to “shortcuts” with no real correspondence.
(E.g., if we do not distinguish between the initial state and a state where we have a teleport machine.)
Can this happen for a projection of “Logistics mal anders”?
→ Yes! Example: In the abstraction induced by π{truck A,truck B}, the initial state is an abstract goal state. Hence the only optimal abstract plan is the empty one. (Similar for any pattern that does not include at least one goal variable; cf. slide 40.)
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 14/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(I) Precomputation Step: It’s Not That Easy
LetΠbeaplanningtaskandP apattern. LetΘ=ΘΠ andΘ′ =ΘπP.
We want to compute a graph representation of Θ′. So, what’s the issue?
Θ′ is defined through a function on Θ:
Each concrete transition induces an abstract transition, each concrete
goal state induces an abstract goal state.
In principle, we can we compute Θ′ by iterating over all transitions/goal states of Θ. BUT:
This would take time Ω(∥Θ∥).
Which comes down to solving the original (concrete, not abstract) planning task in the first place, using blind search.
→ We need a way of computing Θ′ in time polynomial in ∥Π∥ and ∥Θ′∥. A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 17/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
I Give You Pattern, You Give Me Database!
Asssume: You are given a pattern P . How do you compute hP ?
More precisely: How do you compute a data structure that efficiently represents the function hP (s), for all states s?
Here’s how:
In a precomputation step, we compute an explicit graph representation for the abstract state space ΘπP , and compute the
abstract remaining cost for every abstract state.
(II) During search, we use the precomputed abstract remaining costs in
a lookup step.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 16/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(I) Precomputation Step: Here’s How To
Definition (Syntactic Projection). Let Π = (V, A, c, I, G) be an FDR planning task, and let P ⊆ V . The syntactic projection of Π to P is the FDRplanningtaskΠ|P =(P,A|P,c,I|P,G|P)where
A|P := {a|P | a ∈ A} with prea|P := (prea)|P and eff a|P := (eff a)|P .
→ Π|P removes the variables outside P from all constructs in the planning task description Π.
Theorem (Syntactic Projection is Equivalent to Projection). Let Π
be an FDR planning task, and let P ⊆ V . Then Θ(Π|P ) is identical to
ΘπP except that labels a in the latter become labels a|P in the former. Π
Proof. Easy from definition.
→ The state space of the syntactic projection is (modulo label renaming)
the same as the abstract state space of the projection.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 18/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(I) Precomputation Step: Here’s How To, ctd.
Using the Theorem on the previous slide, we can compute pattern databases for FDR tasks Π and patterns P :
Computing Pattern Databases
def compute-PDB(Π, P): Π′ := Π|P .
Compute Θ′ := ΘΠ′ by a complete forward search (e.g., breadth-first). In the explicit graph Θ′, add a new node x with a 0-cost incoming edge
from every goal node
Run Dijkstra starting from x and traversing edges backwards, to compute
all cheapest paths to x and thus the remaining costs h∗Θ′ in Θ′ PDB := a table containing all remaining costs in Θ′
return PDB
→ This algorithm runs in time and space polynomial in ∥Π∥ + ∥Θ′∥.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 19/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(II) Lookup Step: Here’s How To
Perfect hash function ≈ numeral system over variable domains: Let P = {v1,…,vk} be the pattern.
Assume wlog that all variable domains are natural numbers counted from0,i.e.,Dv ={0,1,…,|Dv|−1}.
For all i ∈ {1,…,k}, we precompute Ni := i−1 |Dv |. j=1 j
Looking Up a Pattern Database Heuristic Value
def PDB-heuristic(s): index := ki=1 Nis(vi) return PDB[index]
Note: This lookup runs in time and space O(k). This is very fast. For comparison, delete-relaxation heuristics need time O(∥Π∥) per state.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 21/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(II) Lookup Step: Overview
Basic observations and method:
During search, we do not need the actual abstract state space (transitions etc): The PDB is the only piece of information necessary to represent hP .
→ We can throw away the abstract state space Θ′ once the PDB is computed.
→ Space requirement for the PDB heuristic during search is linear in number of abstract states S′: PDB has one table entry for each abstract state.
Design a perfect hash function mapping projected states s|P to numbers in the range {0,…,|S′|−1}.
→ Index PDB by these hash values. Given a state s during search, to compute hP (s), map πP (s) = s|P to its hash value and lookup the table entry of PDB.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 20/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(II) Lookup Step: “Logistics mal anders”
Abstraction induced by π{package,truck A}:
A ́lvaro Torralba,
AI Planning
Chapter 12: Pattern Database Heuristics
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
(II) Lookup Step: “Logistics mal anders”, ctd.
Pattern variables and domains:
P = {v1, v2} with v1 = package, v2 = truck A.
Dv1 = {L,R,A,B} ≈ {0,1,2,3}
Dv2 = {L,R} ≈ {0,1}
→ N1 = 0j=1 |Dvj | = 1. → N2 = 1j=1 |Dvj | = 4.
→ index(s) = 1 ∗ s(package) + 4 ∗ s(truck A). → Pattern database:
abstractstate LL RL AL BL LR RR AR BR index 01234567 value 20212011
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 23/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Pattern Collections
Pattern Collections? Why and How?
The space requirements for a pattern database grow exponentially with the number of state variables in the pattern.
→ Hence P must be small, severely limiting the usefulness of single-PDB heuristics hP for large planning tasks.
To overcome this limitation, planners using pattern databases can work with collections of multiple patterns.
Given heuristics hP1 and hP2 , we can always get an admissible heuristic dominating each of hP1 and hP2 by max {hP1 , hP2 }.
Combination of hP1 and hP2 that would be much preferable because it dominates the previous one: hP1 + hP2 . . . !
→ But, for this to be admissible, hP1 and hP2 must be additive. A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 26/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
And Now: The Australia Example
Variables: at : {Sy, Ad, Br, Pe, Ad};
v(x) : {T,F} for x ∈ {Sy,Ad,Br,Pe,Ad}.
Actions: drive(x, y) where x, y have a road.
Costs: Sy ↔ Br : 1, Sy ↔ Ad : 1.5, Ad ↔ Pe : 3.5, Ad ↔ Da : 4.
Initial state: at = Sy,v(Sy) = T,v(x) = F for x ̸= Sy. Goal: at = Sy,v(x) = T for all x.
Question: Say our pattern P is {v1 = v(Br),v2 = v(Pe),v3 = v(Da)}. What is the PDB?
→ Dv(Br) = {F,T} ≈ {0,1}, N1 = 1; Dv(Pe) = {F,T} ≈ {0,1}, N2 = 2; Dv(Da) = {F,T} ≈ {0,1}, N3 = 4.
abstractstate FFF TFF FTF TTF FFT TFT FTT TTT index 01234567 value 8.5 7.5 5 4 4.5 3.5 1 0
Note: “Value = sum over the Fs”, i.e. hP = sum of the corresponding single-variable heuristics. P is “causally disconnected”, cf. slides 44–46.
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 24/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
When Does a Label Affect a PDB?
Reminder: → Chapter 11 LetαbeanabstractionofΘ,andletlbealabelinΘ. Wesaythatl
affects α if Θα has at least one non-self-loop transition labeled by l. Let α1 and α2 be abstractions of Θ. We say that α1 and α2 are
orthogonal if no label of Θ affects both α1 and α2.
Lemma (Labels Affecting PDBs). Let P be a pattern for an FDR planning task Π, and let a be an action in Π. Then a affects πP if and only if there exists a variable v ∈ P on which eff a is defined.
Proof. Consider the syntactic projection Π|P .
→Onlyif: IfahasnoeffectonP thenitseffectinΠ|P isemptysoit can label only self-loops.
→ If: Design a state s in Π|P by projecting prea onto P and filling up the remaining P -values arbitrarily but different from eff a. Then a labels the non-self-loop transition (s, a, sa) in Π|P .
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 27/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Orthogonal Patterns
Lemma (Orthogonal Patterns). Let P1 and P2 be patterns for an FDR planning task Π. Then πP1 and πP2 are orthogonal if and only if there exists no action a in Π such that eff a is defined for variables v, v′ where v ∈ P1 and v′ ∈ P2. (Direct from Lemma on previous slide)
Terminology: In this situation, we also call the patterns P1 and P2 themselves (as opposed to πP1 and πP2 ) orthogonal.
On orthogonality and (non)-intersecting patterns:
If P1 ∩ P2 ̸= ∅, can P1 and P2 be orthogonal? No, except if all
v ∈ P1 ∩ P2 are not affected by any action, which is pathological.
If P1 ∩ P2 = ∅, are P1 and P2 necessarily orthogonal? No, there may be an action with a “cross-effect”, on one variable from each.
Note: Disjoint P1 and P2 are orthogonal iff there is no causal graph (ii) arc between them (effect-effect arcs, cf. Chapter 5 or slide 41).
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 28/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
Questionnaire
Variables, for boxes bi and cells ci: robotPos : {ci},
boxPos(x) : {ci} for each bi, free(ci) : {T, F } for each ci. Actions: move(c, c′) where c, c′ adjacent:
pre robotPos = c, free(c′) = T ; eff robotPos = c′.
push(b, c, c′, c′′) where c, c′, c′′ arranged in a line:
pre robotPos = c, boxPos(b) = c′; free(c′′) = T
eff robotPos = c′, boxPos(b) = c′′, free(c′′) = F, free(c′) = T. Goal: free(c) = F for the goal cells c.
What are orthogonal patterns Pi in this Sokoban task?
(A): robotPos ∈ Pi for ≤ one Pi (C): free(c)∈Pi ⇒f.a.j̸=i,c′
(B): For all bj: boxPos(bj) ∈ Pi for≤onePi
adjacent to c: free(c′) ̸∈ Pj
→ (C) is needed: Every cell is member of at least one line of 3 cells, so for every pair of
(D): Other (choose freely) adjacent cells c and c′, there is a push action affecting both free(c) and free(c′).
→ (A) and (B) are needed (else, the patterns intersect). But they are not enough! push actions affect robotPos and boxPos(bj). So if robotPos ∈ Pi then no other pattern can contain any boxPos(bj )! → The effectiveness of orthogonality depends on the domain . . .
A ́lvaro Torralba, AI Planning Chapter 12: Pattern Database Heuristics 30/63
Introduction PDB Basics Implementation Orthogonal PDBs Redundant PDBs Pattern Selection Conclusion References
The Australia Example (Strikes Ag
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com