∃-STRIPS: Existential Quantification in Planning and Constraint Satisfaction

1 Introduction

Modeling and computation are essential components for using planners and many other automated tools. On the one hand, we want planners to scale up gracefully to large problems, even if the task is computationally intractable in the general case [Bylander, 1994]; on the other, we want users to be able to encode problems naturally and directly without having to understand how the different planners work. Indeed, the need to "hack" encodings to make planners work is one of the factors that hinder the use of planners by nonexperts. Since modeling and computation are heavily coupled, the problem cannot be entirely solved, yet this doesn't mean that progress on this front is not possible and necessary. In this work, we focus on the use of existentially quantified

Hector Geffner

ICREA & Universitat Pompeu Fabra Barcelona, Spain hector.geffner@upf.edu

variables in goals and action preconditions in STRIPS and the way in which they can have a positive impact on both modeling and computation. Existential variables provide indeed a very simple and convenient modeling feature in problems where the goal is not a fully-specified single state but leaves room for choices. The goal in a Sokoban-like problem, for instance, may require placing a set of packages in different target locations without explicitly saying in which target location to place each package; or in the blocks-world, the goal may be to reach a state where a blue block is on a red block, without specifying the exact block identities. While there are other mechanisms to model such open choices, existential variables make them explicit, which is useful for reasoning about them. Existentially quantified variables in preconditions and goals are part of the standard PDDL language [McDermott et al., 1998] but few planners support them, and those that do compile them away at a cost that is exponential in their number, which is not a good option from a computational standpoint. The usual alternative is to avoid existential variables altogether, which as we will show is not good either, since it leads to clumsy encodings that hide structure and result in less informed heuristics than the compilationbased approach, not to mention the fact that coming up with such alternative encodings is not always trivial. We illustrate these various points below.

Consider the problem of placing a blue block on top of a red block, and this block on top of a blue block. The problem can be easily encoded in PDDL with a goal formula

Modern classical planners like FF, FD, and LAMA [Hoffmann and Nebel, 2001; Helmert, 2006; Richter and Westphal, 2010] accept such existentially quantified formulas, but they precompile the quantification away, producing in this case a goal in disjunctive normal form (DNF) with terms

for all possible combinations of blocks a, b and c. This DNF goal is mapped in turn into an atomic dummy goal that can be achieved with extra actions whose preconditions are those terms [Gazen and Knoblock, 1997]. The immediate problem with this compilation is that it blows up. The number of terms in the compilation is exponential in the number of variables, and thus it cannot scale up to more than a few quantified variables. This is a problem because it is not always easy to find alternative, equivalent, and compact propositional encodings. Do and Tran [2013], for instance, present one such encoding for a similar problem, but the encoding assumes that the goal is complete and describes a single state. In such a case, one can actually forget about the blocks and describe the goal by stating the desired pattern of "cell colors" as blue(3↪ 1), red(2↪ 1), blue(1↪ 1), etc., which can be encoded compactly in STRIPS without existential variables, but represents a different, less general problem.

In other cases, it is simpler to come up with equivalent and compact encodings that avoid existential variables. The goal of placing n packages pi into n different target locations lk, for instance, can be expressed with existential quantification and equality as

The quantification and the compilation can be avoided here by using a clear predicate over target locations that becomes a precondition of the action of dropping a package in such locations. The resulting encoding is equivalent to the one obtained by compiling the previous formula in the sense that both encodings result in the same set of plans (dummy actions aside), and it has the advantage that its size does not grow exponentially with n. This compact encoding, however, is not only less clean and direct than the one with quantification, but it is also certainly not equivalent from a computational point of view. To see this, consider the standard delete-relaxation heuristics used in classical planning [McDermott, 1999; Bonet and Geffner, 2001] and a situation where none of the packages is at a target location. In the compilation, the heuristic would estimate the cost of taking each package to a different target location, while in the alternative compact encoding with no variables, the heuristic would estimate something different: namely, the cost of taking each package to its closest target location. These estimates will be different when several packages have the same closest target location. This is easy to see for n = 2 where the compilation results in a DNF goal with terms at(p1↪ l1) ^ at(p2↪ l2) and at(p1↪ l2) ^ at(p2↪ l1), but without the terms at(p1↪ l1) ^ at(p2↪ l1) or at(p1↪ l2) ^ at(p2↪ l2) where both packages end up at the same location. The encoding with clear predicates does not account for this difference, as both target locations will remain clear in the delete relaxation as long as they are clear in the state on which the heuristic is evaluated.

The last example illustrates that while compiling away the variables in the goal has an exponential cost, there are also hidden computational costs in the avoidance of existential variables to prevent the exponential blow-up. This point can be made more general and compelling once that we notice that existential variables in the goal allow us to encode naturally and directly constraint satisfaction problems [Dechter, 2003]. Indeed, a binary CSP with variables X1↪ ▷ ▷ ▷ ↪ Xn with domain D and constraints Ri↪j among all pairs of variables Xi and Xj can be naturally and directly encoded as a STRIPS problem with no actions at all, initial facts Ri↪j(a↪ b) for each value pair ha↪ bi in the domain allowed by the constraint Ri↪j , and an existentially quantified goal:

The compilation-based approach would convert such a quantified goal into a grounded DNF goal whose terms are all possible joint valuations of the CSP. Definitely, this is not an effective way of solving the CSP, yet the delete-relaxation heuristic for the compilation is exact: it will yield a heuristic value of 0 for the initial state iff the CSP is actually solvable. Alternative STRIPS encodings of the CSP that do not involve variables and are compact are certainly possible, yet such compact, polynomial encodings cannot yield a (polynomial) delete-relaxation heuristic equivalent to the heuristic obtained from the compilation unless P = NP.

In other words, while dealing with existential variables by compiling them away is exponential, avoiding them altogether results in poorer heuristic estimates in general. In this paper we show that there is a third option which is the explicit handling of existentially quantified variables during the computation of the delete-relaxation heuristic. The resulting method avoids the exponential blow-up in the compilation, and yet it delivers a heuristic that is equivalent to the one that would be delivered by the delete-relaxation in the grounded, compiled problem. For this, the construction of the relaxed planning graph must take into account the firstorder structure of the atoms. Actually, the evaluation of any action precondition or goal formula involving existentially quantified variables maps into a CSP that must be solved during the computation of the heuristic. The computation of the heuristic is thus intractable in the worst case, but as we will show, it can be informed and cost-effective in practice. The consideration of the first-order structure of formulas in the heuristic computation has a close relation with the Functional STRIPS (FSTRIPS) heuristic presented in [Franc`es and Geffner, 2015], which is also intractable in the worst case. Even more interestingly, the proper handling of existential variables in STRIPS gives a way for compiling pure FSTRIPS into 9-STRIPS as in [Haslum, 2008], but with no effect on the structure and informativeness of the resulting heuristic.

The rest of the paper is organized as follows. We present the 9-STRIPS language that extends STRIPS with existentially quantified variables, and formulate a version of the delete-relaxation heuristic for such a language. We then evaluate the resulting native 9-STRIPS planner, which we call ES, by comparing it with state-of-the-art STRIPS planners run on existentially-quantified encodings and on alternative, compact propositional encodings that avoid the compilation, and also with an extension of the FSTRIPS planner FS0.

2 9-STRIPS Language

We briefly review the language and semantics of STRIPS with existential quantification in action preconditions and goals. The classical planning model S = hS↪ s0↪ SG↪ A↪ fi is made up of a finite set of states S, an initial state s0, a set of goal states SG, and actions a 2 A(s) that deterministically map one state s into another s0 = f(a↪ s), where A(s) is the set of actions applicable in s. A solution or plan is a sequence of actions a0↪ ▷ ▷ ▷ ↪ am that generates a state sequence s0↪ s1↪ ▷ ▷ ▷ ↪ sm+1 such that ai 2 A(si), si+1 = f(ai↪ si), and sm+1 2 SG.

A classical planning problem P defines a classical model in compact form. In STRIPS, P is a tuple hF↪ I↪ O↪ Gi, where F is the set of atoms, I is the set of atoms characterizing the initial situation, O is the set of actions, and G is the set of goal atoms. The actions a in STRIPS are given by three sets of atoms: Pre(a), Add(a), and Del(a).

A STRIPS problem P = hF↪ I↪O↪Gi defines a classical model S(P) = hS↪ s0↪ SG↪A↪ fi where the states in S are subsets of F that represent truth valuations where an atom p is true in s iff p 2 s. The other elements in S(P) are s0 = I, SG that is given by the states that satisfy G, A(s) that stands for the actions a 2 O whose preconditions Pre(a) are true in s, and f(a↪ s) that stands for s0 = (s ∩ Del(a)) [ Add(a).

STRIPS is used as a propositional language even if it was originally a first-order language [Fikes and Nilsson, 1971]. Indeed, while in PDDL, STRIPS problems are given in a language featuring action schemas, and predicate and variable symbols, modern planners ground all these schemas using the object names and their types if available. A resulting ground atom like on(a↪ b) is then treated propositionally, but the addition of existential quantification to the language requires that we look into the structure of such atoms.

In 9-STRIPS, a problem is also a tuple P = hF↪ I↪O↪Gi, with the same semantics given by the state model S(P), but with one difference: in addition to ground atoms, preconditions and goals may feature e-formulas. An e-formula is a first-order formula of the form 9x1↪ ▷ ▷ ▷ ↪ xn▷ φ, where φ is a conjunction of atoms p(t1↪ ▷ ▷ ▷ ↪ tn) with the terms ti being constant symbols or variable symbols xi from the quantification prefix. The e-formula 9x1↪ ▷ ▷ ▷ ↪ xn▷ φ is true in a state s if the variable symbols xi can be consistently replaced by constant symbols ci so that the resulting grounded formula φ0 is true in s. This definition extends naturally when the quantified variables xi and the constant symbols ci in the instance have types - in such a case, variables have to be replaced by constants of a compatible type. When x is a tuple of variables, we write the e-formula 9x▷ φ as 9x▷ φ[x] so that the ground conjunction of atoms φ0 that results from the substitution x 7! c in φ can be written as φ[x 7! c] or simply φ[c]. For example, for the formula 9x1↪ x2↪ x3▷ p(x1↪ x2) ^ p(x2↪ x3), if φ is p(x1↪ x2) ^ p(x2↪ x3), φ[x1↪ x2↪ x3 7! c↪ d↪ c] denotes the variable-free formula p(c↪ d) ^ p(d↪ c).

As discussed in the introduction, determining if an eformula holds in a state s is an NP-complete problem. This means that plan verification in 9-STRIPS is NP-complete, and that any heuristic h able to distinguish between goal and non-goal states (i.e., such that h(s) = 0 iff s is a goal state) will be intractable. This however does not imply that such heuristics cannot be cost-effective.

3 9-STRIPS Heuristics

Adapting the relaxed planning graph (RPG) heuristic from STRIPS to 9-STRIPS is simple, even if the resulting heuristic is no longer polynomial. Recall that the RPG heuristic h(s) for STRIPS is given by the number of actions in a plan ⇡+(s) obtained from the delete-free relaxation by following a 2-step procedure [Hoffmann and Nebel, 2001]. In a first forward phase, the procedure incrementally builds a layered graph with propositional layers Pi and action layers Ai. Starting with i = 0 and with a proposition layer P0 that contains the ground facts that hold in s, action a makes it into layer Ai if each precondition atom in Pre(a) is in Pi, and similarly an atom p makes it into layer Pi+1 if there is an action a 2 Ai with p in Add(a). The procedure stops on the first propositional layer Pi such that the goals G are in Pi, or G 62 Pi and Pi = Pi+1. In addition, an action a 2 Ai is deemed a supporter of an atom p if p appears in layer Pi+1 for the first time and p 2 Add(a). The heuristic h(s) is set to 1 when the graph construction finishes without reaching the goal G, and is otherwise given by the number of different actions in a plan ⇡+(s) for the delete-relaxation obtained backward from the goal. The plan includes a supporter for each goal atom that is not in s, and recursively, a supporter for each precondition of such supporter that is not in s either. The relaxed plan and the heuristic are not unique, as an atom may have more than one support.

Extending the RPG heuristic from STRIPS to 9-STRIPS simply requires to define how to deal with e-formulas in preconditions and goals. While a ground atom p is deemed to be satisfiable in a propositional layer Pi when p belongs to Pi, we take an e-formula 9x▷φ[x] to be satisfiable in Pi when there is a substitution x 7! c such that all ground atoms in φ[c] belong to Pi. If, for instance, φ is p(x1↪ x2) ^ p(x2↪ x3), then the formula 9x1↪ x2↪ x3▷ φ is satisfiable in a layer Pi that contains the atoms p(c↪ d), p(c↪ e), and p(d↪ c), through the substitution [x1↪ x2↪ x3 7! c↪ d↪ c]. On the other hand, the same formula would not be satisfiable in that layer if only the first two atoms were contained in Pi.

Extending the RPG construction to take into account eformulas is simple to state but potentially complex to compute: the satisfiability test for e-formulas in a state or in a propositional layer Pi amounts to solving a CSP with variables that correspond to the variable symbols in the prefix, domains given by the sets of constant symbols (respecting type-consistency when types are used) and constraints given by the atoms p(t1↪ ▷ ▷ ▷ ↪ tn) in φ such that the the predicate symbols represent the tables that contain the tuples of constants c1↪ ▷ ▷ ▷ ↪ cn for atoms p(c1↪ ▷ ▷ ▷ ↪ cn) in layer Pi only. A substitution x 7! c satisfies φ if c is a solution to this CSP.

For plan extraction, the supporters of an e-formula 9x▷φ[x] that is satisfied in a layer Pi with substitution x 7! c are identified with the supporters of the atoms in φ[c]. Thus the plan extraction procedure that works backward from the goal does not see e-formulas at all, just ground atoms, as in the standard RPG procedure.

We call the relaxed plans and the heuristic that result from this procedure for the 9-STRIPS language ⇡e FF (s) and heFF (s) respectively. If instead of counting the actions in the relaxed plan we count the number of propositional layers, we get a variant of the hmax heuristic, hemax , that can be shown to be admissible for 9-STRIPS. The heuristic heFF (s) is not admissible, in the same way that hFF is not admissible for STRIPS. The consistency check for e-formulas in each layer Pi is delegated to the standard Gecode CP solver [Gecode Team, 2006].

4 Relation to Compilation and Functional STRIPS

The heuristics he formulated above for 9-STRIPS are equivalent to the corresponding heuristics h for the STRIPS compilation and can be regarded as a lazy version of them. The key difference is that the compilation requires time and space exponential in the number of existential variables, while the heuristics for 9-STRIPS require only exponential time in the worst case. The terms of the ground DNF formulas required for compiling away e-formulas 9x▷ φ[x] in preconditions and goals correspond indeed to the conjunctions of ground atoms φ[c] for each of the possible substitutions x 7! c. The computation of the heuristics however does not apply these possible substitutions all at once, and moreover, it does not explore the space of all possible substitutions exhaustively either. Instead, it uses constraint propagation to search for a substitution that makes the e-formula 9x▷ φ[x] satisfiable.

More interestingly, the heuristics proposed for 9-STRIPS have a strong relation to recently-proposed heuristics for Functional STRIPS, a language that extends STRIPS with (possibly fluent) function symbols [Geffner, 2000] - a feature recently incorporated to the PDDL 3.1 language standard under the name of object fluents. 1 Haslum [2008] has shown how pure Functional STRIPS (with no built-in functions) can be compiled into 9-STRIPS by adding existential variables and replacing functions by relations using the principles of Skolemization in reverse. For example, a grounded atom f(g(c1)) = c2 is replaced by the e-formula 9x1▷f 0 (x1↪ c2) ^ g0 (c1↪ x1) where the relations f 0 (x1↪ x) and g0 (c1↪ x) represent f(x1) = x and g(c1) = x respectively.

The heuristic hcFF developed recently for Functional STRIPS [Franc`es and Geffner, 2015] is aimed at capturing the constraints induced among state variables in preconditions and goals. In the COUNTERS domain, for instance, there is a set of integer variables X1, . . . , Xn and actions that allow us to increase or decrease by one the value of any variable within the [1↪ n] interval. Given some initial values, the goal is to achieve the inequalities Xi < Xi+1, for 1  i < n. Franc`es and Geffner show how delete-relaxation heuristics are not informative in this problem, as they all find that the goal is reachable in the first propositional layer Pi that makes each of the goals satisfiable. Yet there is a crucial difference between making each goal satisfiable and making all goals satisfiable at the same time. For example, a layer in which each variable Xi can take the values 1 and 2 will make each of the goals satisfiable but will not make the joint goal satisfiable. For this, each variable Xi must have the value i, for i = 1↪ ▷ ▷ ▷ ↪ n. The heuristic developed by Franc`es and Geffner captures such induced constraints. Interestingly, the proposed heuristics he for 9-STRIPS account for such constraints too. Indeed, the problem can be represented in 9-STRIPS in terms of atoms val(i↪ k) to state that variable Xi has value k, and static atoms less(k↪ k0 ) to express that value k is less than value k0 . The goal for the problem can then be encoded as

1 http://ipc.informatik.uni-freiburg.de/PddlExtension

This formula 9x▷ φ[x] will be satisfied in a propositional layer Pk only by the substitution that replaces the variable zi by the value i, because the heuristic accounts for the fact that the zi variables need to be replaced consistently in all goal subformulas. This is interesting because it means that the heuristic-search planner for FSTRIPS developed by Franc`es and Geffner can be emulated by compiling FSTRIPS into 9STRIPS through Haslum's translation and applying then the new heuristics. Running other planners on such translations would not deliver the same results. It must be said , however, that Haslum's translation captures the core of FSTRIPS only, leaving out the ability to use built-in functions and global constraints, which in certain problems can make a large difference. On the other hand, the heuristic for 9-STRIPS is simpler to describe and implement than the heuristic for FSTRIPS.

5 Experimental Results

We have developed a preliminary implementation of the CSPbased approach for handling existential quantification on top of the existing Functional STRIPS planner FS0 [Franc`es and Geffner, 2015], which already integrates a CSP solver. We call the resulting 9-STRIPS planner ES. The planner uses the heFF heuristic to drive a plain greedy best first search. As a side effect of the implementation, we also obtain the ability to deal with existential variables in the underlying Functional STRIPS planner.

STRIPS Setup. We consider four families of problems, each encoded both in 9-STRIPS and in a propositional STRIPS manual reformulation that avoids existential quantifiers while preserving equivalence. On these problems, we compare the performance of our ES planner running on the 9-STRIPS encoding against that of the Fast-Downward planner (FD) running on both encodings. FD is configured with the same search strategy; namely, greedy BFS with the hFF heuristic, a single queue, no EHC, and non-delayed evaluation. All planners run a maximum of 30 minutes on a cluster with AMD Opteron 6300@2.4Ghz nodes, and are allowed a maximum of 8GB of memory. The source code of ES plus all problem encodings are available on gfrances.github.io/pubs.

Domains. The four families of domains that we test are BW-PATTERN,VERTEX-COLORING, GROUPING and COUNTERS, the last two from [Franc`es and Geffner, 2015]. BWPATTERN, discussed in the introduction, is a variation of Blocksworld with colored blocks where we want to reach any block configuration that displays a given color pattern, such as "a red block on a blue block on a green block", which is modeled with the goal e-formula 9 b1↪ b2↪ b3▷ col(b1↪ red) ^ col(b2↪ blue) ^ col(b3↪ green) ^ on(b1↪ b2) ^ on(b2↪ b3). We test no propositional encoding, as it is not trivial to reformulate this problem without existential variables.

VERTEX-COLORING illustrates how any CSP can be easily embedded in an (action-less, fluent-less) 9-STRIPS planning problem. A classical k-VERTEX-COLORING problem with n nodes and edges E maps into an 9-STRIPS problem with k color objects and (typed) goal e-formula 9z1↪ ▷ ▷ ▷ ↪ zn 2 COLOR V(i↪j)2E zi 6= zj▷ The initial (and only) state of this planning problem will be detected as a goal iff the graph is k-colorable. We also test AGENT-COLORING, a variation of the domain where an agent moves around the graph picking up and dropping paint cans to paint the vertices "manually". We use two sets of instances: first, random instances (100  n  500, 10  k  30) where the graph results from adding edges at random to a uniform spanning tree to reach a certain graph density; second, standard instances from a public compilation from the literature, 2 of which we have pruned those instances reported as not solvable in less than 1 hour by state-of-the-art coloring methods or having a chromatic number χ > 10. From the remaining instances, we generate planning problems with a number of colors k 2 ¶χ↪ χ + 1♦.

Finally, COUNTERS is the problem described in Section 4 where we increase or decrease the value of certain integer variables Xi until the inequalities X1 < ▷ ▷ ▷ < Xn hold. We use two variations, labeled COUNT0 and COUNTRND, where variables are initially set to 0 and to random values, respectively. The 9-STRIPS encoding is the result of applying Haslum's compilation technique to the original FSTRIPS encoding, save for the substitution of the "<" built-in predicate

In GROUPING, several colored blocks are randomly placed on a grid and need to be moved so that two blocks end up on the same cell iff they have the same color. The original FSTRIPS formulation features a goal formula with an atom loc(bi) ./ loc(bj) for each pair of blocks bi, bj, where ./ is = (6=) if the two blocks have the same (different) color. This translates directly to 9-STRIPS, so that the goal of a problem with red blocks a and b and a blue block c is 9 l↪ l0 ▷ l 6= l0 ^ at(a↪ l) ^ at(b↪ l) ^ at(c↪ l0 ).

2 See https://sites.google.com/site/graphcoloring/.

for a less predicate with extensional denotation.

Results of STRIPS Planners. Table 1 shows the results of the ES planner running on 9-STRIPS ("E-ES") as well as of Fast-Downward on both the 9-STRIPS encoding ("EFF") and the manual propositional reformulation ("P-FF"). We next highlight the main conclusions that can be drawn from these results.

First, the exponential time and space required to compile away 9-STRIPS existential variables has a huge impact on domain coverage. In general, FD tends to either time or memory out during preprocessing. As an example, the planner times/memories out on GROUPING instances with more than 3 colors, and on COUNTERS instances with more than 9 variables. The only domain with acceptable coverage is GROUPING, but this is just because the benchmark set includes many instances with only 2 existential variables.

Second, the heuristic that can be derived from the propositional reformulations is less informed than the one computed from the compiled 9-STRIPS encoding. In GROUPING or in COUNT0, for instance, the average number of node expansions is orders of magnitude higher on the propositional reformulation, because the delete-relaxation does not account for certain constraints that are captured on the 9-STRIPS version, such as (in GROUPING) the constraint that all blocks of the same color must be on the same position at the same time. In spite of this, however, FD has much better performance on these propositional reformulations, because it avoids the exponential time and space required to compile away the existential variables and to process the result of the compilation.

Third, the constraint-based approach of ES to handle existential variables avoids the exponential time and space penalty of the compilation approach without making the resulting heuristics less informed, making it a more effective strategy, and resulting in consistently higher coverages.

Fourth, when compared to the performance of FD on the propositional reformulations, ES produces better coverage on two cases and worse coverage on two other cases, excluding the BW-PATTERN domain that is not simple to encode propositionally. The average number of expanded nodes is in general much lower for ES, up to one or two orders of magnitude in some cases, but at the same time node expansion rate is also around between one and two orders of magnitude faster in FD. Upon inspection, ES suffers a significant overhead caused by the lack of multivalued variables in 9-STRIPS, which results in CSPs with too many Boolean variables that could well be replaced by fewer multivalued variables. This shortcoming does not appear in Functional STRIPS, which in addition benefits from built-in functions and constraints.

Comparison with Functional STRIPS. As a side effect of our implementation of ES on top of the FS0 planner, and following the previous observation, we have also developed an extension of FS0, which we call FS, that is able to handle FSTRIPS with existential variables by following the same ideas that we have described for 9-STRIPS. In addition, and thanks to the compilation technique described in Section 4, this new FS planner can handle nested functional terms, which the original FSTRIPS planner FS0 cannot. Table 2 compares FD on the propositional STRIPS reformulations ("P-FF", which is the best option for Fast-Downward according to Table 1, leaving aside the reformulation effort) with ES on 9-STRIPS encodings ("E-ES") and with FS on equivalent FSTRIPS encodings that exploit both functions and existential variables ("EF-FS"). In some cases (COUNTERS, GROUPING), these are pure FSTRIPS encodings that do not need existential quantification, but in the remaining domains (BW-PATTERN, VERTEX-COLORING, AGENTCOLORING) existential quantification is necessary.

When compared to ES on 9-STRIPS encodings, FS on the FSTRIPS encodings shows higher node expansion rates and even a more informed heuristic in BW-PATTERN. This is because (1) FSTRIPS encodings usually need fewer grounded actions, (2) the CSPs used during the heuristic computation have significantly fewer variables (e.g. quadratically so in GROUPING) (3) they benefit from custom constraint propagators for FSTRIPS built-in symbols, such as the "<" symbol in COUNTERS, and (4) certain support extraction tie-breaking mechanisms are easily implemented for FSTRIPS, but have not yet been implemented in the current version of the ES planner, which might be harming the heuristic accuracy in BW-PATTERN.

Overall, the novel FS planner working on an extension of Functional STRIPS with existential quantification definitely pays off, offering a coverage which consistently dominates the other two planners, and plan length, average number of expanded nodes and overall running time figures which are consistently better. In particular, the extension of Functional STRIPS with existential quantification yields better results than the manual propositional STRIPS reformulations in all domains.

6 Discussion

We have presented a novel view of existential quantification in STRIPS that relates planning to constraint satisfaction and relational databases [Gottlob et al., 1999]. A goal that involves existential variables is indeed like a query; what makes it particular in the context of planning is that we are not simply evaluating the goal "query" in a static database, but can apply actions that modify the database in order to make the query satisfiable, and hence the goal true.

We have also argued that the use of existential quantification for leaving some choices open in goal and preconditions allows for simpler and more concise models, while giving planners the chance to reason about those choices. Instead of compiling existential variables away with an exponential technique or avoiding them altogether, we have shown how delete-relaxation heuristics can be extended to deal with existential variables by using constraint satisfaction techniques, resulting in heuristics that are more informed than those that can be obtained from alternative propositional encodings.

This view of existential variables in STRIPS has resulted in a new 9-STRIPS planner implemented on top of the existing Functional STRIPS FS0 planner, plus a new Functional STRIPS planner that completes support and extends the original language as defined in [Geffner, 2000]. We have evaluated these planners on four families of domains encoded in STRIPS and FSTRIPS with existential variables, and when feasible and simple enough, without them. The fact that the best computational results have been achieved for the more expressive language illustrates the importance of making problem structure explicit so that it can be exploited computationally [Rintanen, 2015; Ivankovic and Haslum, 2015].

Significantly enough, there is no domain featuring existential quantifiers in any of the last three international planning competitions. This lack is arguably due to the inefficiency of the standard compilation technique, which imposes a heavy burden on both modelers and planners. We hope that this work can contribute to change this situation.

Acknowledgments

The ES and FS planners are partially built on top of the Lightweight Automated Planning Toolkit (www.lapkt.org) and the Fast Downward PDDL parser (www.fast-downward. org). The authors thank Miquel Ram´ırez for useful discussions and insights. This work is partially supported by the M. de Maeztu Programme (MDM-2015-0502) and by grants TIN2015-67959 and CSD2010-00034, MEC, Spain.