Planning with Abstraction Hierarchies can be Exponentially Less Efficient

1 Introduction

One common approach to improving the efficiency of planning is to use a hierarchical planner based on state abstraction-ignoring certain literals, either in the op­ erator preconditions [Sacerdoti, 1974] or in the whole language [Knoblock, 1991, 1994]. First an abstracted version of the problem instance is solved, thus not tak­ ing all details into account and resulting in a plan which is correct at this abstraction level. This plan is then ,used as a skeleton plan to be filled in with more detail at the next lower level-a process referred to as refinement. Repeated refinement results in a solution to the original, non-abstract problem.

Although state abstraction cannot avoid exponential search spaces in the general case, it is usually considered a powerful method for reducing the search effort. The method has been demonstrated to speed up planning considerably for certain test examples [Knoblock, 1994; Bacchus and Yang, 1994]. This is augmented with the­ oretical results [Knoblock, 1991] showing that state ab­ straction can reduce the size ofthe search space from ex­ ponential to linear under certain ideal conditions. These conditions are very strong, however, and are not likely to be met in (m)any real applications. One of the condi­ tions is that the hierarchy satisfies the downward refinement property (DRP) [Bacchus and Yang, 1994], which guarantees that no backtracking occurs between abstrac­ tion levels. Bacchus and Yang [1994] analysed the ex­ pected search complexity when this particular condition does not hold-more precisely, as a function of the prob­ ability that a plan at some abstraction level can be re­ fined into a plan at the next lower level. They found that the search complexity is linear both when this probabil­ ity is close to 1 and when it is close to 0. However, there is a phase-transition effect increasing the search complexity considerably, when the probability is neither low nor high. Bacchus and Yang even reported that the expected search effort may be somewhat higher with a~­ straction than without in this middle region, namely 1f most search has to be redone at the ground level. How­ ever, the literature seems to tacitly assume that state abstraction will never do any big harm. Contrary to this, we show that just as state abstraction can speed up planning exponentially, it can also slow down plan­ ning exponentially, and even force the hierarchical plan­ ner to produce an exponentially longer solution than a non-hierarchical planner!

*This research was sponsored by the Swedish Research Council for Engineering Sciences {TFR) under grants Dnr 92-143 and Dnr 93-270.

Knoblock [1994] has further presented an algorithm, ALPINE, for generating abstraction hierarchies that are ordered monotonic-a property guaranteeing that no re­ finement of an abstract plan can undo any effects of the abstract plan. Bacchus and Yang [1994] have presented a modification of this algorithm, HIGHPOINT, whose hi­ erarchies are ordered monotonic and expected to satisfy the DRP more closely. While these algorithms produce good hierarchies in many cases, they are not guaranteed to be harmless. In fact, we show that both algorithms may produce the type of abstraction hierarchy that leads to exponentially longer solutions. Furthermore, we show that using the same underlying principle as in ALPINE and HIGHPOINT, it is computationally difficult to gen­ erate an abstraction hierarchy that allows a hierarchical planner to generate a solution with length within a con­ stant factor of the optimal plan length (we actually prove an even stronger approximation bound-a logarithmic factor in the size of the instance).

2 Basic Formalism

We first define some basic concepts.

Definition 2.1 Given a set S, we let Seqs(S) denote the set of all sequences formed by members of S. We further use the symbol ";" to denote sequence concate­ nation. Given a set 1' = {p1, ... ,pn} of proposi­ tional atoms, .Cp denotes the corresponding set of lit­ erals, ie. .Cp = {p, -,p I p E 1'}. A set S s;;; .Cp of literals is consistent iff there is no atom p such that {p, ..,P} s;;; S. For S s;;; .Cp we further define Gen( S) = {p I p E S or -,p E S}, ie. the set of atoms generating the literals in S.

Since we will only prove hardness results, we need only consider a propositional formalism, and the results will carry over automatically to more expressive for­ malisms. More precisely, we will use the ground version of the TWEAK formalism [Chapman, 1987], which is known [Backstrom, 1995] to be expressively equivalent, under polynomial reduction, to most other common vari­ ants of propositional STRIPS.

Definition 2.2 A planning problem instance is a quadruple II = (1', 0, I, Q) where

• 1' is a finite set of atoms;
• 0 is a finite set of operators of the form (pre, post) where pre, post s;;; .Cp are consistent and denote the pre- and post-condition respectively;
• I, g s;;; .Cp are consistent and denote the initial and goal state respectively.

Foro= (pre, post) s;;; 0, pre(o) and post(o) to denote pre and post respectively. A sequence (o11 ... , on) E Seqs(O) of operators is called a plan over II. The func­ tion Result is defined for all consistent states S s;;; .Cp and plans (o1, ... , on) E Seqs( 0) as

Result((), S) = S

Result( (o1, ... , on), S) =

Result( (o2, ... , on), S U post(o)- {p I -,p E post(o)})

We say that a plan (o11 ··· , on) E Seqs(O) is a solution to an instance II = (1', 0, I, Q) iff

1. pre(ol) s;;; I;
2. g s;;; Result((o1, ... ,on),I) and
3. pre(oi) s;;; Result((o1, ... ,oi -1),I) for all1 < i ~

n.

3 State Abstraction

There are two common ways of doing state abstraction: the relaxed method and the reduced method. The re­ laxed method was pioneered for planning in the AB­ STRIPS planner [Sacerdoti, 1974]. Criticality values are assigned to the literals and at each abstraction level i, all literals with criticality value < i are omitted from the operator preconditions. The reduced method [Knoblock, 1991, 1994] goes even further by restricting the whole language at level i to only those literals having criti­ cality value ~ i. We will base our theorems on the reduced model, but they trivially hold also under the relaxed model.

Definition 3.1 Given a set of of atoms 1', an abstrac­ tion of 1' is a set of atoms 1'' s;;; 1'. An n-level ab­ straction hierarchy on 1' is a chain pn s;;; . . · s;;; 1'1 s;;;

1' 0 where pn = 0 and 1' 0 = 1'. We will mostly write the abstraction hierarchy as an ordered partition­ ing (vn- 1 , ··· , 'D 0 ) of 1' where 1Ji = pi -1'i+1 for all i. The mapping of a state S s;;; .Cp onto the abstract level i, for some 1 ~ i ~ n, is denoted Si and is de­ fined as Si = S n .Cp· . Similarly, the mapping of a ground operator o = (pre, post) onto the abstract level i is denoted oi and defined as oi = (prei,posti). The mapping of an operator set to level i is consequently de­ fined as Oi = { oi I o E 0} and the mapping of a plan­ ning instance II = (1', 0, I, Q) to level i is defined as IIi = ('Pi, Oi, T, gi). We refer to level 0 as the ground level.

The general method for planning with abstraction hi­ erarchies can be cast as an algorithm, HPLAN (see Fig­ ure 1). This planner relies on a non-hierarchical planner PLAN for solving subproblems within abstraction levels. PLAN can be any planner for the language at hand, but it must be sound and complete to guarantee soundness and completeness of HPLAN. We will further assume that PLAN generates shortest plans.

When solving an instance II = (1', O,I, g) under an abstraction hierarchy ('Dn- 1 , ... , 'D 0 ), HPLAN first uses PLAN to solve the most abstract version, rrn- 1 ' of this instance. This results in a plan (o~- 1 , ... , o~- 1 ) over the abstract operator set on- 1 · This plan is used as a skeleton for solving the instance rrn- 2 ' with initial and goal states zn- 2 and gn-2 respectivelr In addition, the intermediate states S1 = Result(o~- ,zn-1 ), ... , Sk = Result(o~- 1 , Sk-d on level n- 1 are used as new sub­ goals on level n-2. In this way we get k + 1 subproblems to solve on level,n - 2, each one hopefully easier than solving rrn- 2 from scratch. Each of these subproblems is solved using PLAN, and these solutions are concate­ nated into a solution for rrn-2. This process is then repeated until we reach the ground level, which results in a solution for II 0 = II.

1 procedure HPLAN(O,I,Q,('Dn-1, ... ,'Do)) 2 w +-- PLAN(on-1,zn-1,gn-l) 3 if no such plan then fail 4 for i from n - 1 to 1 do 5 w +-- Refine(w, i) 6 return w 1 procedure Refine(w,.i) 2 Assume w = (oi, ... , oA:) 3 So +-- T; To +-- r- 1 4 for j from 1 to k do 5 S; +-- Result(oj, S;-d 6 for j from 1 to k do 7 w; - PLAN (oi-l, T;- 11 S;) 8 if no such plan then fail 9 T; +-- Result(w;, T;-d 10 wk+1 - PLAN c oi- 1 , Tk, gi-l) 11 return W1i· .. ;wk+1

Figure 1: The hierarchical planning algorithm (search control omitted).

The process of using a plan on one abstraction level as a skeleton for producing a plan at the next lower level is called refining the plan. In the general case, for abstrac­ tion hierarchies not satisfying the DRP, HPLAN must also use backtracking and try refining another skeleton plan on some level whenever a subproblem cannot be solved. However, to simplify matters we omit backtrack­ ing in this paper since we will only use HPLAN for hier­ archies satisfying the DRP.

4 Exponential Slow-down

Knoblock [1991] has shown that, under certain ideal con­ ditions, the size of the search space can be reduced from exponential to linear by using HPLAN and an abstraction hierarchy instead of an ordinary non-hierarchical plan­ ner. Most of these conditions are expressed in terms involving properties of the actual planning process and properties of the final solution, and are thus difficult to cast in terms involving only properties of the instance. One of the conditions is the DRP, ie., there is no back­ tracking between abstraction levels.

This section presents some complementary results: state abstraction can also cause an exponential blow-up of the search space, causing an exponential slow-down, under certain conditions-even for hierarchies satisfying the DRP. Furthermore, this exponential slow-down is ac­ companied by the even worse result that the generated solution is exponentially longer than the shortest one!

Consider the following generic planning instance, En, and the two possible abstraction hierarchies 111 and 112.

Definition 4.1 For all even n > 0 we define En = ({po, ... ,Pn-1}, On, 0, {pn-2,Pn-1}), where On con­ tains the 2n operators so, ro, ... , sn-1, rn-1 as defined in Table 1. We further define the following two abstraction hierarchies for En,

Both 111 and 112 obviously satisfy the DRP and are or­ dered.

We can now prove that there is an exponential dif­ ference in the sizes of the solutions and search spaces depending on the choice of abstraction hierarchy.

Theorem 4.2 HPLAN will produce a solution of length n for En under 111.

Proof: Let Ln be the length of the shortest plan HPLAN can produce under 111 · We prove by induction

Table 1: Operators for the planning instance En, where 0 ~ 2i < n and with the exception that the operators so, ro, s1 and r1 have empty preconditions.

over n that for even n > 0,

Base step: For n = 2 all operators have empty pre­ conditions, so the behaviour of HPLAN will correspond to the two uppermost levels of Figure 2. The resulting plan is (s1,so), which clearly must be a shortest plan. Hence, L2 = 2.

Induction step: Assume the claim holds for all even k < n for some even n > 2. Planning on the four most abstract levels will proceed as shown in Figure 2. The initial state will be empty on all abstraction levels and orderedness of the abstraction hierarchy guarantees that the last three states on level n - 4 will be refined into states subsuming these states. Hence, the operators s~=1 and s~=~ will be refined into the single-operator plans (s~_1 ) and (s~_2 ) respectively at each level i < n- 4. It remains to analyse the subplan (s~=~, s~=!). Ordered­ ness guarantees that the atom Pn-1 cannot be affected and will not be required for any refinement of this sub­ plan. Hence, this atom can be ignored for the expansion. Substituting indices n - 1 and n - 2 for n - 3 and n - 4 respectively then shows that the subplan (s~=~, s~=!) is isomorphic to the plan (s~=~, s~=~) on level n- 2, and similarly for the adjacent states. That is, by ignoring the atom Pn-1 we see that the subplan (s~=~, s~=!) is the solution at level n- 4 for the instance En_2, so it follows from the induction hypothesis that it will be re­ fined into a ground solution of length Ln_2 · It follows that Ln = 2 + Ln-2 for even n > 4, which proves the claim and ends the induction.

The solution to the recursive equation is Ln = n, which proves the theorem. D

Theorem 4.3 The shortest solution HPLAN can gener­ ate for En under 112 is of size !l(2f ).

Proof: Let Ln be the length of the shortest plan HPLAN can produce under 112. We prove by induction over n that for even n > 0,

Base step: For n = 2 all operators have empty pre­ conditions, so the behaviour of HPLAN will correspond to the two uppermost levels of Figure 3. The resulting plan is (so, s1), which clearly must be a ahortest plan. Hence, L2 = 2.

Induction step: Assume the claim holds for all even k < n for some even n > 2. For n ~ 4, planning on the four most abstract levels will proceed as shown in Figure 3. Analogous to the previous proof we see that the operators s~=~ and s~=~ will be refined into the single­ operator plans (s~_1 ) and (s~_2 ) respectively at each level i < n - 4. Also by analog reasoning, the atoms Pn-1 and Pn-2 can be ignored wrt. the expansions of the subplans (s~=:,s~=!) and (r~=:,r~=!). The first of these is clearly the solution at level n - 4 for :En_2 and it, thus, follows from the induction hypothesis that it expands into a ground subplan of length Ln_2· Since the operators rn-3 and rn-4 have the same preconditions as Sn-3 and Sn-4 respectively, it is immediate that the two subplans will have isomorphic refinements. Hence, also the second subplan expands into a ground subplan of length Ln-2· It follows that Ln = 2 + 2Ln-2 for even n > 4, which proves the claim and ends the induction.

The solution to the recursive equation is Ln = 2~+1-2 so Ln E 0(2~ ), which proves the theorem. 0

These results mean that if we happen to make a for­ tuitous choice of abstraction hierarchy, then HPLAN will generate a linear-size solution, using only a linear-size search space. On the other hand, if we are less fortunate, then HPLAN is forced to explore an exponential number of nodes generating an exponentially longer solution.

Obviously, an unfortunate choice of abstraction hier­ archy can force HPLAN to take exponential time, pro­ ducing an exponentially suboptimal solution. It is thus interesting to compare this to the performance of a non­ hierarchical planner. Such a planner may also have to explore an exponential-size search space. However, al­ lowing the planner to search the whole, exponential-size search space would at least guarantee generating a short­ est, ie.linear-size, solution. Furthermore, a standard planner using a domain-independent standard heuristic can guarantee finding a solution exploring only a linear number of nodes in this case.

Theorem 4.4 SNLP [McAllester and Rosenblitt, 1991]

solves :En in polynomial time if equipped with a heuris­ tic which prefers existing actions to new ones for goal establishment.

5 Building Abstraction Hierarchies

Knoblock [1994] has suggested defining a preorder ~ in the set of atoms and then use this order to define an abstraction hierarchy satisfy~:r.g the following restriction.

Restriction 5.1 Define ~ on P s.t. for all p,p' E 'P and every o E 0,

1. if p,p' E Gen(post(o)) and p"f;p! then p ~ p' and p' ~Pi
2. ifpEGen(pre(o)) andp'EGen(post(o)), thenp ~p'. For all atoms p E pi, p' E pi, if p ~ p', then i ::::; j.

The intention is that if p ~ p', then p must not occur higher up in the abstraction hierarchy than p'. Restric­ tion 5.1 is known [Knoblock, 1994] to be a sufficient, though not necessary, condition for an abstraction hier­ archy to be ordered monotonic.

Knoblock [1994] has further presented an algorithm, ALPINE, for generating maximally deep abstraction hi­ erarchies satisfying Restriction 5.1, thus generating or­ dered abstraction hierar~hies. The basic ALPINE algo­ rithm appears in Figure 4. 1 The actual ALPINE algo­ rithm [Knoblock, 1994] is somewhat more advanced and also comes equipped with certain heuristics. Further, it handles a first-order language, while our version is in­ tended only for a propositional language. These differ­ ences do not affect the results to be proven in the fol­ lowing section, however-a topic which will be further discussed later in this paper.

ALPINE builds a directed graph, G, corresponding to the preorder ~ and then collapses all strong components in G, resulting in a set C of equivalence classes over 'P. The final line of the algorithm sorts the partially ordered set C topologically, but does not specify any preference for a particular topological sort. Hence, ALPINE cannot always distinguish between good and bad abstraction hi­ erarchies, like ?-£1 and ?-£2.

Theorem 5.1 Given the planning instance :En, ALPINE arbitrarily generates any of a number of possible abstrac­ tion hierarchies including ?-£1 and ?-£2.

Proof: The first step of ALPINE will produce the graph Gin Figure 5 {corresponding to the preorder ~). Since there are no strong components of size > 1, step 2 will

1 Note that, contrary to Knoblock, we direct the arcs in the standard way.

1 procedure ALPINE{'P, 0) 2 G +- (P, 0) 3 for all p,p' E P do 4 if p ~ p' then insert arc (p,p') in G 5 Collapse the strong components in G and let G' = (C, A) be the reduced graph 6 return any topological sorting of A

Figure 4: The ALPINE algorithm.

pr~duce an isomorphic graph, with each element being a smgleton component, inducing a partial order on the atoms. Finally, step 3 may produce any topological sort­ ing of this partial order, which clearly include the total orders reflected by the graphs T1 and T2 in Figure 5. Ob­ viously, T1 correspond to 1i1 and T2 to 1i2, which proves the theorem. o

What, then, are the chances of improving ALPINE by making a more informed choice in line 6? The imple­ mented version comes equipped with certain heuristics [Knoblock, 1994, pp. 272-273], of which only one (num­ ber 3) applies to the propositional case. This heuristic specifies that adjacent levels not containing any goal lit­ erals should be merged into one single level. Applying this heuristic would cause the atoms p0 , ··· ,Pn-3 to end up on the same level. 2

A modified version of the algorithm, HIGHPOINT [Bac­ chus and Yang, 1994], uses a sampling method to deter­ mine for each pair of components ci, Cj E C that could be ordered the expected probability that a plan at level i can be refined at level j if ordering i above j. These probabilities are then used to further collapse some com­ ponents and to guide the topological sorting of the re­ maining components. However, for En, HIGHPOINT will always find that the probability of refinement is 1 so it is p~ovided no extra information to guide the topol~gical sortmg. Hence, HIGHPOINT is bound to suffer from the same problem as ALPINE, ie., not being able to prefer 'H1 to 1i2.

This is hardly surprising, however, since it is possible to show that no modification or heuristic can improve the topological sorting to always allow HPLAN to produce shortest plans.

Definition 5.2 The search problem ALPGENMIN is de­ fined as follows:

Instance: A planning instance II = ('P, 0, I, 9) .

Problem: When executing the ALPINE algorithm on II, find a topological sorting in the final step that results in an abstraction hierarchy which allows HPLAN to find a shortest solution.

Theorem 5.3 ALPGENMIN is NP-hard.

2 Knoblock [personal comm., 1995] argues that this is the right behaviour in this case. However, our Theorems 4.2 and 4.3 would hold also under heuristic 3 if setting 9 = 1' in :En.

Proof: Proof by reduction from MINIMUM CoVER [Garey and Johnson, 1979, p. 222], which is NP­ complete. Let X = {x1, ... , Xm} be a set, let C = {C1, ... , Cn} be a set of subsets of X and let K be an in­ teger. W.l.o.g. we restrict the problem to having covers of even size only, by requiring that m is even and that the atoms x2i and X2i+l always appear together in members of C. Define a planning instance II = ('P, 0, 0, {p}) where 'P is partitioned into the three sets 'Ptop = {p}, 'PMc = XU{r}, and 'Ptiz = {qo, ... ,qK+l}· The set of operators is similarly partitioned into three sets Otop, OMc and Otiz· s.t. the operators in Otop change only atoms in 'Ptop etc. The set OMc contains one operator Oi for each member Ci of C, having no precondition and Ci U { r} as its effect. The set 0 fix contains one operator Oi for each atom qi E 'Ptiz· having no precondition and {qo, qi} as its effect. Finally, Otop consists of the two operators OMC and Ofiz· both having the effect p and having the preconditions 'PMc and 'Ptiz respectively.

When applying ALPINE to II, it will find the three maxim~ strong components 'Ptop, 'PMc and 'Ptiz· the first bemg ordered above the two latter, which are mu­ tually unordered. Hence, there are two possible ab­ straction hierarchies: 1iMc = ('Ptop, 'Ptiz· 'PMc) and 1itiz = ('Ptop, 'PMc, 'Ptiz)· Obviously, under hierarchy 1iMc it is possible to find a plan of lenght K* + 1, where K* is the size of the minimum cover for X. 1itiz· on the other hand, will force the planner to generate a plan of length K + 2, which is optimal iff K* > K (remem­ ber that K* must be even). Now, if we could choose in polynomial time the hierarchy allowing us to find an optimal plan, then we could also solve MINIMUM CovER in polynomial time. Hence, ALPGENMIN is NP-hard. 0

Note that the theorem is not about whether HPLAN will generate a shortest plan, but only about whether the abstraction hierarchy prevents it from doing so or not. This is a disappointing result since one of the condi­ tions guaranteeing a linear-size search space for HPLAN is that HPLAN generates a shortest plan [Knoblock, 1991]. Knoblock mentions, however, that this condition can be relaxed; it is sufficient that HPLAN finds a plan of length within a constant factor longer than the short­ est one. Unfortunately, ALPGENMIN cannot be approxi­ mated within any constant factor, unless P=NP. In fact, an even stronger approximation limit can be proven.

Theorem 5.4 ALPGENMIN cannot be asymptotically approximated within a factor clog2 ~ for any c < ~ unless NP ~ DTIME(nloglogn).

Proof sketch: Suppose the theorem were not true. Then it would follow from the construction in the proof of Theorem 5.3 that we could approximate MINIMUM COVER within clog2IXI for some c < ~· However, this is impossible unless N P ~ DTIME ( n 10 s log n) [Bellare et al., 1993], contradicting the assumption. 0

We have previously required that the algorithm PLAN underlying HPLAN always generates optimal plans. Un­ fortunately, generating an optimal plan at an abstract level does not guarantee that we find an optimal plan at the ground level. This does not affect Theorems 5.3 and 5.4, however, since it is obvious from their proofs that neither theorem depends on the assumption that PLAN generates an optimal plan.

6 Discussion

It is well-known [Knoblock, 1991] that state abstraction can speed up planning exponentially. Under certain ideal conditions, plans can be generated in linear time in the length of the solution for some planning problems, eg. the Towers-of-Hanoi problem. However, the value of this demonstration is questionable since the problem is unrealistic in the sense that it has exponentially sized minimal solutions. 3 One of these ideal conditions is the downward refinement property (DRP), which guarantees that no backtracking occurs between abstraction levels. We have added to previous analyses of state abstrac­ tion by showing that not only can state abstraction give exponential speed-up in some cases; it can also cause ex­ ponential slow-down in other cases-even for hierarchies satisfying the DRP. More precisely, there exist problem instances such that the ideal choice of abstraction hier­ archy leads to the generation of a linear-size plan, while a more unfortunate choice forces the generation of an exponential-size plan, taking exponentially longer time to generate. This may even happen in cases where a standard non-hierarchical planner equipped with a sim­ ple, domain-independent heuristic produces a shortest, ie. linear-size, solution in polynomial time. Instances of this kind seem no less realistic than, for instance, Towers­ of-Hanoi.

We have further shown that the ALPINE [Knoblock, 1994] and HIGHPOINT (Bacchus and Yang, 1994] algo­ rithms for generating abstraction hierarchies are not able to distinguish between such good and bad hierarchies as mentioned above. Furthermore, we have also shown that it is even impossible to design an algorithm based on the same underlying principle as ALPINE and HIGHPOINT that always produces hierarchies allowing a hierarchical planner to generate plans of length within a constant factor of the shortest length (actually, not even within a logarithmic factor in the size of the instance). We have choosen in this paper to concentrate on state abstraction as defined and used by Knoblock [1994], ie. using a total­ order hierarchical planner. We are currently investigat­ ing the consequences of using a partial-order hierarchical planner like ABTWEAK [Yang and Tenenberg, 1990] in­ stead. Although ABTWEAK seems to handle correctly the particular example we have used to demonstrate the exponential slow-down effect, we do not believe there is any fundamental difference in general. In fact, the ap­ proximation result mentioned above should be valid also for partial-order planners like ABTWEAK.

The message of this paper is not that state abstrac­ tion and the use of algorithms like ALPINE and HIGH­ POINT should be abandoned; in many cases, these can still be powerful tools for tackling the search complexity in planning. However, the results tell us that we must be very careful; state abstraction is a powerful tool, but a tool that may occasionally turn its power against us, making things exponentially worse. Even if good ab­ straction hierarchies exist in many domains, the task of finding these is non-trivial and seems to remain a highly domain-dependent heuristic endeavour. We believe that more research is needed in order to understand when state abstraction works and how to exploit the inher­ ent structure of problems for building good abstraction hierarchies. ·

3 See Backstrom and Nebel [1993] or [Garey and Johnson, 1979, pp. 11-12] for a discussion of this topic.

Acknowledgements

We would like to thank Craig Knoblock, Jalal Maleki, Qiang Yang and the anonymous referees for comments which helped improving this paper.