Bridging the Gap Between Refinement and Heuristics in Abstraction

1 Introduction

One of the most widespread and important forms of abstraction in search and planning is state abstraction. In very general terms, this means that one forms an abstract state space from the original state space. The purpose of the abstract space is that it may help us to solve the original problem faster. Two dominating methods exist for exploiting state abstraction for this purpose: refinement and heuristics.

Refinement planning was pioneered in the ABSTRIPS planner [Sacerdoti, 1974], but the idea was used already in GPS [Newell et al., 1959]

the abstract version of the problem instance and then uses this plan as a skeleton for a plan for the original instance. If one is lucky, then it is sufficient to add more actions between the ones in this skeleton plan to obtain a valid plan. Otherwise, one has to backtrack and find a new skeleton plan. The abstraction heuristic method instead performs heuristic search in the original search space, using the abstract space to compute the heuristic. The heuristic search approach has proven very successful both in classical planning and in search, and a number of interesting and well-performing heuristics have been invented (see Helmert and Domshlak [2009] for a comprehensive survey and comparison).

Refinement used to be the dominating abstraction method in planning, but has largely been replaced with abstraction heuristics, although there are signs of a potential renaissance for refinements [Gregory et al., 2011; Seipp and Helmert, 2013]. Refinement has continued to be used, though, in other areas such as path planning [Sturtevant and Buro, 2005] and model checking [Clarke et al., 2003]. The refinement and heuristic approaches are usually considered as quite different and unrelated. That is a very superficial analysis, though: both approaches are firmly based on properties of the solutions in the abstract space, so some connections are bound to exist. Yet, the literature is almost void of attempts to investigate these connections. A notable exception is Helmert [2006] who made a pragmatic attempt at combining refinement and heuristics in his FD planner. A formal example is the DPP criterion [Zilles and Holte, 2010], intended to avoid certain bad types of abstractions in heuristic search, but also related to the backtracking issue.

The purpose of this paper is twofold. One is to extend our own previous abstract framework for modelling abstractions [B¨ackstr¨om and Jonsson, 2012a; 2012b] by adding metric properties in addition to the previous qualitative ones. The other purpose is to use this extended framework to provide the first formal analysis on an abstract method-independent level of how refinement and heuristics are related. This paper should not be viewed as a solitary one, but be read in the context of our previous publication on this framework.

The rest of the paper is structured as follows. Sections 2 and 3 recapitulate the abstraction framework that we use, and Section 4 discusses the three different refinement concepts previously studied within this framework. Our main results appear in Section 5, where we add new metric properties to the framework in order to express concepts like admissibility and consistency of heuristics. We further make an extensive investigation of how these metric properties relate to the previously proposed properties. An immediate consequence of this is that we identify several connections between refinement and heuristics. Section 6 gives further examples of using the extended framework to study various concepts in a different and more revealing way, eg. Valtorta's theorem and the DPP criterion. The paper ends with a discussion section.

2 STGs and STGTransformations

We here briefly present the framework for studying abstractions and refer to our previous papers [B¨ackstr¨om and Jonsson, 2012a; 2012b] for further details and explanations.

Let X be a set. Then |X| denotes its cardinality. A partition of X is a set P of non-empty subsets of X s.t. (1) ∪p∈Pp = X and (2) for all p, q ∈ P, if p ̸= q, then p ∩ q = ∅. Let f : X → Y be a function, then Rng(f) = {f(x) | x ∈ X} is the range of f. When the elements of Y are sets we define f(Z) = ∪x∈Zf(x) for all Z ⊆ X.

Definition 1. A state transition graph (STG) over a set L of labels is a tuple G = 〈S, E〉 where S is a set of vertices and E ⊆ S × S × L is a set of labelled arcs. Also define L(G) = {ℓ | 〈s, t, ℓ〉 ∈ E}. A sequence s0, s1, . . . , sk of states in S is a path in G if either (1) k = 0 or (2) 〈si-1, si, ℓi〉 ∈ E for 1 ≤ i ≤ k and some labels ℓ1, . . . , ℓk.

The set S is called a state space and its members states. We allow multiple arcs between two states if they differ in direction or labels. Labels provide a means to identify sets of arcs, eg. the arcs induced by a particular action, but they are not of much relevance in this paper. The STG collapses to an ordinary directed graph if all arcs have the same label.

Definition 2. Let G1 = 〈S1, E1〉 and G2 = 〈S2, E2〉 be two STGs. A total function f : S1 → 2S2 is a transformation function from G1 to G2 if Rng(f) is a partition of S2. The corresponding reverse transformation function f : S2 → 2S1 is defined as f(t) = {s ∈ S1 | t ∈ f(s)}. A label relation from G1 to G2 is a binary relation R ⊆ L(G1) × L(G2). The reverse label relation R ⊆ L(G2) × L(G1) is defined as R(ℓ2, ℓ1) iff R(ℓ1, ℓ2). A transformation from G1 to G2 is a pair τ = 〈f,R〉 where f is a transformation function from G1 to G2 and R is a label relation fromG1 to G2.

Intuitively, f specifies how τ maps states in G1 to sets of states in G2, while R relates subsets of E1 with subsets of E2. Transformation functions are extended to sequences of states such that f(s1, . . . , sk) = f(s1), . . . , f(sk). Furthermore, if τ = 〈f,R〉 is a transformation, then: (1) s ∈ f(t) if and only if t ∈ f(s), (2) f is a transformation function from G2 to G1 and (3) 〈f,R〉 is a transformation from G2 to G1. As a convention, we will often not specify the STGs in definitions and theorems, tacitly assuming transformations to be from an STG G1 = 〈S1,E1〉 to an STG G2 = 〈S2,E2〉 unless otherwise specified. We also sometimes refer to G1 as the ground graph and G2 as the abstract graph.

3 Method Properties

We have earlier defined a number of properties that transformations can have, dividing these into method propeties and instance properties [B¨ackstr¨om and Jonsson, 2012a]. In brief, method properties are inherent for a particular transformation method and the actual STGs do not matter, while instance properties may hold only for particular pairs of STGs.

Definition 3. A transformation τ = 〈f,R〉 can have the following method properties:

• M↓: |f(s)| = 1 for all s ∈ S2.
• R↑: If 〈s1, t1, ℓ1〉 ∈ E1, then there is some 〈s2, t2, ℓ2〉 ∈ E2 such that R(ℓ1, ℓ2).
• R↓: If 〈s2, t2, ℓ2〉 ∈ E2, then there is some 〈s1, t1, ℓ1〉 ∈ E1 such that R(ℓ1, ℓ2).
• C↑: If R(ℓ1, ℓ2) and 〈s1, t1, ℓ1〉 ∈ E1, then there is some 〈s2, t2, ℓ2〉 ∈ E2 such that s2 ∈ f(s1) and t2 ∈ f(t1).
• C↓: If R(ℓ1, ℓ2) and 〈s2, t2, ℓ2〉 ∈ E2, then there is some 〈s1, t1, ℓ1〉 ∈ E1 such that s1 ∈ f(s2) and t1 ∈ f(t2).

We refer the reader to the original papers for further explanations of these properties. However, we provide a new alternative way to understand the properties, in terms of graph morphisms. We define the latter in the usual way for directed labelled graphs, ignoring the labels.

Definition 4. An M↑ transformation function f from G1 to G2 is (1) a homomorphism if for all s, t ∈ S1, 〈s, t〉 ∈ E1 implies 〈f(s), f(t)〉 ∈ E2; (2) a strong homomorphism if it is a homomorphism and for every 〈s, t〉 ∈ E2, there is some 〈s′ , t′ 〉 ∈ E1 s.t. f(s′ ) = s and f(t′ ) = t; (3) an embedding if f is a bijection that is a homomorphism ; (4) a retraction if it is an embedding fromG2 to G1.

These concepts have been extensively used as abstraction functions in search and planning. It turns out that the method properties suffice to capture and distinguish between these different concepts, which strongly indicates that the method properties are not arbitrary but express something essential.

Theorem 5. If f is a transformation function then there is a label relation R s.t. the transformation τ = 〈f,R〉 is:

1. M↑R↑C↑ if and only if f is a homomorphism.
2. M↑R↕C↕ if and only if f is a strong homomorphism.
3. M↕R↑C↑ if and only if f is an embedding.
4. M↕R↓C↓ if and only if f is a retraction.

Proof sketch. (1-2) Follows from Theorem 9 in B¨ackstr¨om and Jonsson [2012a] since part 1 of the proof corresponds to homomorphism and part 2 to the additional criterion for strong homomorphisms. (3) Immediate from 1 plus definitions. (4) Immediate from 3.

We write X ⇒ Y to denote that every transformation that has property X also must have property Y, and we write X ̸⇒Y when this is not the case.

4 Path Refinement

It is often useful to consider an abstraction of a graph in terms of soundness and completeness. Loosely speaking, it is sound if every abstract path somehow correspond to a ground path and it is complete if every ground path somehow correspond to an abstract path. One way to formalize these concepts is to consider them in terms of state refinement. While it is common in planning to refine an abstract plan by using the corresponding ground actions as a skeleton plan, it is also possible to just use the ground states corresponding to the states along the abstract plan. In fact, this is the common way to do refinement in search, and Holte et al. [1996a] suggest that this is indeed a better way to do refinement.

We have previously defined three different types of state refinement, corresponding to different degrees of avoiding backtracking between levels [B¨ackstr¨om and Jonsson, 2012a]. Very briefly, all three refinements avoid backtracking to the abstract level but correspond to different amounts of backtracking on the ground level.

Definition 6. Let f be a transformation function and let σ = t0, t1, . . . , tk be an arbitrary path in G2. Then: 1) σ is trivially downward state refinable if there are two states s0 ∈ f(t0) and sℓ ∈ f(tk) s.t. there is a path in G1 from s0 to sℓ. 2) σ is weakly downward state refinable if there is a sequence s0, s1, . . . , sk of states in S1 such that si ∈ f(ti) for all i s.t. 0 ≤ i ≤ k and there is a path from si-1 to si in G1 for all i (1 ≤ i ≤ k). 3) σ is strongly downward state refinable if for every i s.t. 1 ≤ i ≤ k, there is a path from si-1 to si in G1 for all si-1 ∈ f(ti-1) and all si ∈ f(ti).

These concepts are illustrated in Figure 1. All three cases consider the same abstraction and the same path σ = t1t2t3t4 in the abstract graph, but different ground graphs. Curly arrows denote paths, i.e. they may consist of several arcs and pass through states not shown in the figure. Trivial refinement only requires that there is a path corresponding to σ in the ground graph. In this case it requires that there is a path from some state in f(t1) = {s11, s12} to some state in f(t4) = {s41, s42}, which is satisfied by the path from s11 to s42. Weak refinement additionally requires that we use all states along σ and also pass through some state in each of f(t2) and f(t3). This is satisfied, for instance, by the path s11s22s31s41. Finally, strong refinement requires that there is a path for any choice of states in f(t1), . . . , f(t4), which is satsified in the last example in the figure.

To continue, we must define reachability in graphs. Let G = 〈S,E〉 be an STG. Then for all s ∈ S, the set R(s) of reachable states from s is defined as R(s) = {t ∈ S | there is a path from s to t in G}. We extend this s.t. for all T ⊆ S, R(T) = ∪s∈TR(s). Using R1(·) for reachability in G1 and R2(·) for reachability in G2, instance properties are defined as follows.

Definition 7. A transformation function f can have the following instance properties:

Pk↓: For every path t0, . . . , tk in S2, there are s0, . . . , sk ∈ S1 s.t. si ∈ f(ti) for all i (0 ≤ i ≤ k) and si ∈ R1(si-1) for all i (1 ≤ i ≤ k).

Pk↑: For every path s0, . . . , sk in S1, there are t0, . . . , tk ∈ S2 s.t. ti ∈ f(si) for all i (0 ≤ i ≤ k) and ti ∈ R2(ti-1) for all i (1 ≤ i ≤ k).

PT↓: P1↓ holds.

PT↑: P1↑ holds.

PW↓: Pk↓ holds for all k > 0.

PW↑: Pk↑ holds for all k > 0.

P↓: If t ∈ R2(f(s)), then f(t) ∩R1(s) ̸= ∅.

P↑: If t ∈ R1(s), then f(t) ∩R2(f(s)) ̸= ∅.

PS↓: If t ∈ R2(f(s)), then f(t) ⊆R1(s).

PS↑: If t ∈ R1(s), then f(t) ⊆R2(f(s)).

The following relationships are known to hold. PS↓ ⇒P↓ ⇒PW↓ ⇒PT↓ PT↓ ̸⇒PW↓ ̸⇒P↓ ̸⇒PS↓ The instance properties capture refinement as follows.

Theorem 8. (B¨ackstr¨om and Jonsson, 2012a, Th. 15) For a transformation τ = 〈f,R〉, every path in G2 is trivially/weakly/strongly downward state refinable iff τ is PT↓/ PW↓/ PS↓.

5 Metrics and Heuristics

In this section we will augment our framework with a few metric properties, in addition to the previous qualitative ones, and investigate how these properties relate to each other. In particular, we will analyse on an abstract method-independent level how refinement and heuristics relate to each other. The results we will prove in this section are summarized in Figure 2, where the arrows denote the ⇒ and ̸⇒ relationships between the properties (the figure contains the new properties that are yet to be defined).

5.1 Metric Properties

Heuristic search attempts to find an optimal solution faster than blind search by using a heuristic function that approximates the true cost to guide the search. It is desirable that this function is admissible, i.e. that it never overestimates the true cost. For instance, the A∗ algorithm is optimal under this condition [Dechter and Pearl, 1985]. It is often useful to view both the original and abstract search spaces as graphs and to define the abstraction such that the length of paths in the abstract graph is an admissible heuristic for the length or cost of the corresponding paths in the ground graph [Holte et al., 1996a]. That is, abstraction is viewed as a graph transformation. It is also common to preprocess the abstract graph and store the path lengths in a pattern database [Culberson and Schaeffer, 1998], or to compute a heuristic from several such databases [Haslum et al., 2007].

Define N∞ = N ∪ {∞} and extend =, < and + to N∞ in the obvious way. Let G = 〈S, E〉 be an STG. A cost function for G is a function c : S2 → N∞, with the restriction that for all s, t ∈ S, c(s, t) = ∞ if and only if there is no path from s to t in G. A heuristic function h for a cost function c is itself a cost function. As usual, h is admissible for c if 0 ≤ h(s, t) ≤ c(s, t), for all s, t ∈ S and consistent for c if h(s, t) ≤ c(s, u) + h(u, t) for all s, t, u ∈ S. While s and t are sometimes assumed to be the initial and goal states, respectively, our definition is more general and is also common, cf. Yang et al. [2008]. It is better suited for our purpose of comparing refinement with heuristics, and it is a reasonable assumption for domain-independent heuristics. While truly arbitrary cost functions are sometimes considered, this is usually not the case in planning and many other contexts. We follow common practice and define cost functions as follows. First define a function w : E → N that assigns a weight to each arc in G. Then extend the cost function to paths such that c(s0, . . . , sk) = ∑ki=1 w(si-1, si). The cost c(s, t) between two states is then defined as the minimum of c(σ) over all paths σ from s to t, or ∞ when there is no path at all, ie. c(s, t) is the cost of the cheapest path from s to t. We also implicitly define the specific weight function d which assigns weight 1 to all arcs, which is known as the unit cost assumption. When considering two STGs G1 and G2 simultaneously we index their corresponding c, d and w functions analogously, for instance, w1 is the weight function for G1.

We extend transformations with metric information, writing τ = 〈f, R, w1, w2〉 where 〈f, R〉 is a transformation from G1 to G2 and w1 and w2 are the weight functions for G1 and G2, respectively. The cost functions c1 and c2 are implicitly defined by w1 and w2. For instance, the common practice of using the path length in the abstract graph as a heuristic estimate for the path length in the ground graph correspdonds to an 〈f,R, d1, d2〉 transformation, while an 〈f,R,w1, d2〉 transformation estimates path costs in the ground graph with path lengths in the abstract graph. In order to take advantage of cost functions we will introduce some new metric properties. In this section, we only consider such properties for M↑ transformation functions, since abstraction heuristics usually assume that f is an ordinary function.

Definition 9. An M↑ transformation τ = 〈f,R,w1,w2〉 can have the following metric properties:

Properties A↓ and ∆↓ correspond to admissibility and consistency, respectively. Properties AC↓ and ∆C↓ are conditional variants of A↓ and ∆↓ for transformations that are incomplete; they are only required to hold in the cases where there actually is a path in G2. More precisely, we have:

Theorem 10. Let τ = 〈f,R,w1,w2〉 be an M↑ transformation. Then: 1) τ is A↓ iff c2 is an admissible heuristic for c1. 2) τ is ∆↓ iff c2 is a consistent heuristic for c1.

Property A↓ is a weaker criterion than ∆↓, while AC↓ and ∆C↓ are weaker variants of A↓ and ∆↓. The relationships between the metric properties can be summarized as follows.

Theorem 11. Let τ be an M↑ transformation. Then:

1) A↓ ⇒AC↓, 2) ∆↓ ⇒∆C↓, 3) AC↓ ̸⇒A↓, 4) ∆C↓ ̸⇒∆↓, 5) ∆↓ ⇒A↓, 6) ∆C↓ ⇒AC↓, 7) A↓ ̸⇒∆↓, 8) AC↓ ̸⇒∆C↓.

The results in the remainder of this section will fill in the rest of the arrows in Figure 2.

5.2 Metric Properties and Upward Refinement

The following theorem formalizes that admissibility implies completeness, but the opposite is false; not even the strongest form of completeness, PS↑, guarantees admissibility.

Proof. Let τ = 〈f,R,w1,w2〉 be anM↑ transformation.

• 1-2) Suppose τ is A↓. Let s, t ∈ S1 arbitrary such that t ∈ R1(s). Then c1(s, t) < ∞ and, thus, c2(f(s), f(t)) < ∞, since τ is A↓. Hence, f(t) ⊆ R2(f(s)) so τ is PS↑ since s and t were chosen arbitrarily. (2) Follows since ∆↓ ⇒A↓.
• Let S1 = S2 = {s1, s2, s3}, E1 = {〈s1, s2, ℓ〉, 〈s1, s3, ℓ〉, 〈s2, s3, ℓ〉} and E2 = {〈s1, s2, ℓ〉, 〈s2, s3, ℓ〉}. Let f be the identity function, R = {〈ℓ, ℓ〉}, w1 = d1 and w2 = d2. Then, τ is PS↑. However, it is not A↓ since c1(s1, s3) = d1(s1, s3) = 1 but c2(f(s1), f(s3)) = d2(f(s1), f(s2)) + d2(f(s2), f(s3)) = 2. (4) Follows since ∆↓ ⇒ A↓.

Figure 3 is an example of a PS↑ transformation. However, there is a one-arc path s12, s32 in G1 but the shortest path from f(s12) to f(s32) in G2 is of length 2. If we apply unit cost to both graphs, then the transformation cannot be A↓.

Property A↓ captures admissibility, which is complete, while AC↓ is a conditional variant that does not require completeness but only that the abstraction does not overestimate the cost of a ground path whenever there is a corresponding abstract path. It is, however, sufficient to combine conditional admissibility with the weakest form of completeness to get full admissibility, as the following theorem demonstrates. The analogous case holds for consistency.

5.3 Metric Properties and Downward Refinement

Admissibility enforces completeness but not soundness; that is, there can be an abstract path with no corresponding ground path. In fact, admissibility and downward refinement are largely orthogonal and incomparable concepts.

Proof. 1-2) Let S1 = S2 = {s1, s2, s3}, E1 = {〈s1, s2, ℓ〉, 〈s1, s3, ℓ〉, 〈s2, s3, ℓ〉} and E2 = {〈s1, s2, ℓ〉, 〈s2, s3, ℓ〉}. Also let f be the identity function, R = {〈ℓ, ℓ〉} and τ = 〈f,R, d1, d2〉. Then τ is PS↓. However, c1(s1, s3) = d1(s1, s3) = 1 but c2(f(s1), f(s3)) = d2(f(s1), f(s2)) + d2(f(s2), f(s3)) = 2, so τ is not AC↓. Hence, τ is not ∆C↓ since ∆C↓⇒AC↓.

3-4) Let S1 = S2 = {s1, s2, s3}, E1 = ∅ and E2 = {〈s1, s2, ℓ〉, 〈s2, s3, ℓ〉}. Also let f be the identity function, R = {〈ℓ, ℓ〉} and τ = 〈f,R, d1, d2〉. Then τ is A↓ and ∆↓ but it is not PT↓ since E1 = ∅.

5-6) Let S1 = {sij | 1 ≤ i ≤ 4, 1 ≤ j ≤ 2}, S2 = {s1, s2, s3, s4}, let E1 = {〈s11, s21, ℓ〉, 〈s11, s31, ℓ〉, 〈s31, s41, ℓ〉, 〈s22, s42, ℓ〉} and let E2 = {〈s1, s2, ℓ〉, 〈s2, s4, ℓ〉, 〈s1, s3, ℓ〉, 〈s3, s4, ℓ〉}. Also let f(sij) = si for all sij ∈ S1, let R = {〈ℓ, ℓ〉} and let τ = 〈f, R, d1, d2〉. Then τ is obviously PT↓, A↓ and ∆↓. However, the path s1, s2, s4 in G2 is not weakly refinable, so τ is not PW↓.

The major reason for these results is that refinement is defined without any metrics; even if we have a guarantee that an abstract plan can be refined into a ground plan, we have no guarantee that there is no shorter ground plan.

5.4 RelatingMetric andMethod Properties

Also method properties have metric connections.

Theorem 15. Let τ = 〈f,R,w1,w2〉 be an M↑R↑C↑ transformation. Then: 1) If w2(f(s), f(t)) ≤ w1(s, t) for all 〈s, t〉 ∈ E1 such that 〈f(s), f(t)〉 ∈ E2, then τ is A↓∆↓. 2) Otherwise, τ need not be neither A↓ nor ∆↓.

Proof. 1) It follows from Theorem 5 that f is a homomorphism since τ is M↑R↑C↑. Hence, for every path σ in G1 also f(σ) is a path in G2. Let s, t ∈ S1 be arbitrary states. If there is no path from s to t in G1, then c1(s, t) = ∞ so c2(f(s), f(t)) ≤ c1(s, t) holds trivially. Otherwise, let

σ = s0, . . . , sk, where s0 = s and sk = t, be the cheapest path from s to t. Then c1(s, t) = ∑ki=1 w1(si-1, si). Since also f(σ) must be a path in G2 we get c2(f(s), f(t)) ≤ ∑ki=1 w2(f(si-1), f(si)). It follows that c2(f(s), f(t)) ≤ c1(s, t) since w2(f(u), f(v)) ≤ w1(u, v) for all u, v ∈ S1. Hence, τ is A↓ since s and t were chosen arbitrarily.

Let s, t, u ∈ S1 be three arbitrary states. We first note that c2(f(s), f(t)) ≤ c2(f(s), f(u)) + c2(f(u), f(t)) by the definition of cost functions. We also note that c2(f(s), f(u)) ≤ c1(s, u) since τ is A↓. Hence, c2(f(s), f(t)) ≤ c2(f (s), f (u)) + c2(f (u), f (t)) ≤ c1(s, u) + c2(f (u), f (t)), that is, τ is ∆↓ since s, t and u were chosen arbitrarily.

2) Let S1 = S2 = {s1, s2}, let E1 = E2 = {〈s1, s2, ℓ〉}, let f(s) = {s} for all s ∈ S1 and let R = {〈ℓ, ℓ〉}. Also set w1(s1, s2) = 1 and w2(s1, s2) = 2. Then τ is M↑R↑C↑ but neither A↓ nor ∆↓ for this instance.

6 Examples

In this section we give examples of how the extended framework can be used to express new things or express old things in new ways. The examples are deliberately quite different from each other in order to demonstrate the breadth of applicability of an abstract framework of this kind.

Admissibility and Homomorphisms

Homomorphisms, i.e. M↑R↑C↑ transformations, are known to be very suitable as abstraction functions in heuristic search, cf. Holte et al. [1996a], Helmert et al. [2007] and Zilles and Holte [2010]. One reason for this is that they are admissible. The following result shows that also the opposite holds, admissibility implies that the abstraction function is a homomorphism, if all arcs in both graphs have unit cost. Without unit costs, this relationship breaks down. This is a most relevant observation in the context of using the path length in the abstract graph as the heuristic estimate for the path length or path cost in the ground graph. Zero cost arcs are typically not considered in this context.

Theorem 16. Let τ = 〈f,R,w1, d2〉 be an M↑A↓ transformation s.t. d1(s, t) ≤ w1(s, t) for all edges 〈s, t〉 ∈ E1. Then: 1) f is a homomorphism if w1 = d1. 2) Otherwise f need not be a homomorphism.

Proof. We ignore labels since they are irrelevant.

1) Suppose τ is M↑A↓ and w1 = d1 but f is not a homomorphism. Then there is some 〈s, t〉 ∈ E1 s.t. 〈f(s), f(t)〉 ̸∈ E2. That is, c1(s, t) = d1(s, t) = 1, but if there is a path from f(s) to f(t), then it must be of length 2 or more. Hence, c2(f(s), f(t)) ≥ 2 so τ cannot be A↓. This contradicts the assumption, so f must be a homomorphism.

2) Let S1 = S2 = {s1, s2, s3}, E1 = {〈s1, s3〉}, E2 = {〈s1, s2〉, 〈s2, s3〉}. Let f(s) = s for all s ∈ S1 and let w1(s1, s3) = 2. Clearly, τ is A↓ for this example. However, f is not a homomorphism since 〈s1, s3〉 ∈ E1 but 〈f(s1), f(s3)〉 ̸∈ E2.

Spurious States

The downward path preserving (DPP) property [Zilles and Holte, 2010] guarantees that the abstract search space does not contain any spurious states (abstract goals states not corresponding to ground goal states). We have earlier proved that DPP is equivalent to P↕ [B¨ackstr¨om and Jonsson, 2012a]. However, A↓ ⇒ PS↑ and PS↑ ⇒ P↑, so P↓A↓ ⇒ DPP. Although P↓A↓ is a stronger criterion than DPP, it means that we need not verify independently that P↑ holds if we already know that the heuristic is admissible, which is typically the case when considering DPP.

Globally Admissible Heuristics

Karpas and Domshlak [2012] considered optimal solutions with non-admissible heuristics. One example is so called globally admissible heuristics, which need only be admissible for the states along some optimal plan. Let G = 〈S, E〉 be an STG, c a cost function for G and h a heuristic for c. Then, for arbitrary s, t ∈ S, h is globally admissible for c from s to t if there is an optimal path s0, . . . , sn such that s0 = s, sn = t and h(si, t) ≤ c(si, t) for all i, 0 ≤ i ≤ n. This concept can be alternatively characterized as follows.

Theorem 17. Let τ = 〈f,R,w1,w2〉 be an M↑AC↓ transformation. Then, if there is an optimal path σ from s to t in G1 such that f(σ) is a path in G2, then c2 is a globally admissible heuristic for c1 from s to t.

This makes use of properties M↑ and AC↓ and a type of completeness property that is even weaker than PT↑.

Valtorta's Theorem

Valtorta [1984] proved that when using embeddings as abstraction functions, it is not possible to explore fewer nodes in total, counting both ground and abstract nodes, when using A∗ search with path length in the abstract graph as heuristic estimate. This was later generalized to abstraction functions in general, by Holte et al. [1996b], known as the generalized version of Valtorta's theorem.

Theorem 18. [Generalized Valtorta's theorem, [Holte et al., 1996b]] Assume τ = 〈f, R, w1, d2〉 is an M↑ transformation and d1(s, t) ≤ w1(s, t) for all 〈s, t〉 ∈ E1. Let u be any state in G1 that is necessarily expanded when the instance 〈s, t〉 is solved by BFS in G1 and let the heuristic function h be h(u, t) = d2(f(u), f(t)), computed by BFS in G2. If A∗ solves this instance, then either u or f(u) will be expanded during the search.

Holte et. al. noted that this does not rule out that some abstractions might explore fewer nodes in total. (The theorem is somewhat weak, though, since it only tells us that u or f(u) is expanded, allowing the possibility that both are expanded). It is well known that this requires that there are abstract nodes corresponding to two or more ground nodes; the expansion of an abstract node can then result in a heuristic estimate that prevents A∗ from exploring the corresponding ground nodes. An alternative characterization of this is that f is not M↓. While this is hardly an interesting new result itself, it demonstrates that the framework defined so far is sufficient to express this important criterion for A∗ search.

We may also step outside the M↑ assumption. Suppose we have some concept of expanding f(u) for a state u when f is not M↑. We need not have a precise definition of this concept to see that Theorem 18 still holds, and that f must still not be M↓ to have any chance of exploring fewer nodes.

7 Discussion

We previously used our framework to model a number of abstraction methods in planning, derive their transformation properties and draw conclusions from that regarding soundness and completeness [B¨ackstr¨om and Jonsson, 2012a]. We will very briefly sketch how these results together with the new results of this paper can sometimes be used to also say about the metric properties of these abstraction methods.

Method ABII (ABSTRIPS in the version where non-critical atoms are removed everywhere, cf. Knoblock [1994]) is known to be an M↑R↑C↑ transformation, i.e. a homomorphism. Hence, it is also an A↓∆↓ transformation, i.e. it can be used as an admissible and consistent heuristic. Although this is already known, it is interesting that the result can be deduced in this way, using only abstract transformation properties. Methods RRAa and RRAb are two extreme cases of the concept of removing redundant actions [Haslum and Jonsson, 2000]. It is not hard to see that RRAa is M↑R↑C↑ and, consequently, A↓∆↓ while RRAb is neither A↓ nor ∆↓. Method IDL is the common abstraction method of ignoring delete lists of actions, and it is M↕R↕ but not C↑ or C↓. Hence, it is not admissible, which might seem to contradict known results. It does not, however, since B¨ackstr¨om and Jonsson allowed negative preconditions, which is usually not considered when ignoring delete lists. This indicates that the equivalence between STRIPS with and without negative preconditions [B¨ackstr¨om, 1995] must be taken with care in some cases, like delete relaxation.

Let us finally discuss some future research directions. Our results make no particular assumptions about the function f and the relation R in the transformations. Looking also at restricted cases would be interesting, since the abstraction methods used in the literature impose various restrictions on f and R. The preceeding paragraph gives some ideas about what kind of results could be achieved this way.

The results in Section 5 clearly demonstrate that the lack of metrics in usual refinement concepts makes it hard to prove further positive results on the connections between refinement and heuristics. The obvious way forward would be to somehow add metric aspects also to refinements. The properties Pk↑ and Pk↓ actully do so, but not in a sufficient way. For instance, one might consider a property Pmk↓ that is like Pk↓ but additionally requires that each arc along the path can be refined into a path of length m at most. This might allow for finding tighter relationships between refinement and heuristics, perhaps relating Pmk↓ to approximate heuristic search (eg. using weighted A∗ ). However, it could also provide a deeper insight into refinement itself; it is well known that purely qualitative criteria can cause anomalous behaviour in refinement [B¨ackstr¨om and Jonsson, 1995].

Another future direction is to study abstractions and heuristics for non-M↑ functions. We note that the literature on this topic is very scarce, and defining such heuristics is much less straightforward. For instance, we can no longer exploit ordinary homomorphisms. One interesting exception is Pang and Holte [2012] who introduce so-called multimapping abstractions as a method for aggregating multiple heuristics.