Purely Declarative Action Descriptions are Overrated: Classical Planning with Simulators

1 Introduction

Planning is a key component of human intelligence [Seligman et al., 2016] and one of the key areas of artificial intelligence since its beginnings [Newell and Simon, 1963]. Planning is normally conceived as "thinking before acting", and in AI, as the model-based approach to intelligent behavior, where model predictions are used to figure out what to do next [Geffner and Bonet, 2013]. Models come in a variety of forms, from classical to temporal and POMDP models, but what is common to most planners is that the models are described compactly using declarative languages [Nilsson and Fikes, 1971; McDermott, 2000]. Planning languages serve two roles: on the one hand, they are general so that different types of problems and domains can be fed into planners, on the other, they reveal problem structure that can be exploited computationally. Indeed, the planners that address the simplest (classical) planning models and scale up best all exploit in some way the problem structure encoded in action preconditions, effects, and goals. This includes from the first means-end and partial-order planners [Newell and Simon, 1963; Tate, 1977; Nilsson, 1980] to the latest SAT, OBDD, and heuristic search planners [Kautz and Selman, 1996; Edelkamp and Kissmann, 2009; Richter and Westphal, 2010; Rintanen, 2012]. The focus on standard, declarative planning languages has resulted in a dramatic progress in scalability, but has a downside too: some problems are not easy to model, and the runtime of planners is often very sensitive to the encodings. Moreover, there are many simulators available, that in many cases describe classical planning models (given initial state, deterministic actions, and reachability goals), but classical planners cannot be used for planning in them. These include simulators for the Atari video games [Bellemare et al., 2013], the games of the General Video Game competition [Perez-Liebana et al., 2016], Minecraft [Johnson et al., 2016], and Universe [OpenAI, 2016].

Domain-independent planners able to plan with simulators rather than planning languages would be a key addition to the planning toolbox while broadening the scope of planners. Such planners would be insensitive to the syntax of action descriptions, since they would not see such descriptions at all. Indeed, the result of applying an action to a state can be obtained from declarative descriptions or procedures, whatever is more convenient, reducing the challenge of modeling. The key question we pose is: is it possible to achieve the goal of planning with simulations while retaining the scalability of planners that make use of factored action representations? In other words, can a domain-independent planner that has access to the structure of states and goals only, approach the performance of planners that have also access to the structure of actions? To address this question, we develop planning algorithms that have no access to the structure of actions and compare them with state-of-the-art planners over standard planning benchmarks.

The paper is organized as follows. We review state models and classical planners, introduce factored state models, formulate and test the black box planning algorithms, and discuss the results and implications.

2 State Models and Classical Planners

A classical planning model S = 〈S, s0, SG, Act, A, f, c〉 is made up of a set of states S, the initial state s0 ∈ S, the set of goal states SG ⊆ S, the set of actions Act, the subsets A(s) of actions applicable in state s, the transition function f, where f(a, s) represents the state s′ that results from doing action a in state s, and the cost function c, where c(a, s) is the cost of applying a in s. The solution to a classical planning model S, or plan, is a sequence of actions that maps the initial state into a goal state, i.e., π = 〈a0, . . . , an〉 is a plan if there is a sequence of states s0, . . . , sn+1 such that ai ∈ A(si) and si+1 = f(ai, si) for i = 0, . . . , n, and sn+1 ∈ SG. The cost of plan π is given by the sum of action costs c(ai, si), and a plan is optimal if there is no plan with smaller cost. The classical planning model is the vanilla planning model, and differs from other models like temporal, conformant, contingent or POMDP models in its lack of uncertainty and sensing, and its focus on plans as action sequences.

A classical planner is a program whose input is a compact representation of a classical planning model S and whose output is a plan. Compact representations are expressed in a declarative planning language such as STRIPS or PDDL [McDermott, 2000]. The planning language provides a way to represent problems over completely different domains and reveals problem structure. For example, heuristic estimators [McDermott, 1999; Bonet and Geffner, 2001b], "helpful" actions [Hoffmann and Nebel, 2001], and landmarks [Hoffmann et al., 2004], all key techniques in modern planners such as LAMA [Richter and Westphal, 2010], are derived from the "delete-relaxation" of the compact problem representation but cannot be derived from the underlying planning model alone. The same holds for other planning techniques such as SAT, OBDD, and partial-order planning. Despite the PSPACE-completeness of the classical planning problem [Bylander, 1994], modern planners have been shown to scale up to problems that define huge state spaces.

3 Factored State Models and Simulators

Purely declarative planning languages are not the only way to represent classical planning models in compact form. Indeed, state models S = 〈S, s0, SG, Act, A, f, c〉 can also be represented in general by using state variables and by encoding the functions A(s), f(a, s), and c(a, s) as black box procedures. Such a representation of actions has been seldom used in domain-independent planning, and in what follows we address the question of whether effective, general planning methods can be developed for it.

For this, we define a factored state model as a tuple F = 〈V , D, s0, G, Act, A, f , c〉 where V is a set of variables X, D represents the domains DX of the variables X ∈ V , s0 is an assignment to the variables compatible with their domains, G is a set (conjunction) of goal conditions expressed as Boolean functions of V , Act is a set of actions, and A : S ↦→ 2Act , f : A × S ↦→ S, and c : S → R are functions encoded as procedures that represent the set of actions applicable in each state, the state successor function, and the cost function. The tuple F provides a compact representation of the state model S = 〈S, s0, SG,Act,A, f, c〉 where S is the set of variable assignments compatible with their domains, and SG is the set of assignments satisfying each goal condition in G. The goal conditions in G do not have to be atoms of the form X = x, but can be arbitrary procedures mapping states into Booleans.

A problem in STRIPS is a tuple P = 〈F, I, G, O〉 where F is a set of atoms, I represents the set of atoms that are true initially, G the set (conjunction) of atoms to be made true, and O is the of operators characterized by three sets of atoms: the precondition list, the add list, and the delete list. A STRIPS problem can be easily converted into a factored state model F = 〈V,D, s0,G,Act,A, f, c〉. For this, V = F, all domains in D are Boolean, s0 is determined by I, Act = O, c(a, s) = 1, and the action applicability and successor state functions A and f are derived in linear time from the information in action preconditions and effects. This simple and polynomial translation is not bidirectional.

In what follows, a simulator will be a factored state model F = 〈V, D, s0, G, Act, A, f, c〉 where the functions A, f and c are given by black box procedures. The focus on black box methods that plan with simulators does not mean that these functions cannot be described declaratively or through hybrids involving procedures, but rather that simulation-based planning algorithms make no assumption about the form of such descriptions.

4 Width-based Search

The methods developed for planning in simulated environments like ALE and GVG-AI are based mainly on blind and heuristic search, Monte Carlo Tree Search (MCTS), widthbased search, and hybrids of these [Bellemare et al., 2013; Perez-Liebana et al., 2016; Soemers et al., 2016]. Blind search methods can be applied directly to factored state models that just encode weighted directed graphs in compact form. Heuristic search methods, on the other hand, require heuristics, which are not easy to derive from simulations. MCTS methods potentially combine the benefits of blind and heuristic search: they can be used off-the-shelf as the former, but scale up better as value functions akin to heuristic functions are incrementally learned and used to guide the search. Usually, however, MCTS performs this bootstrapping slowly when rewards are sparse and there is no domain-dependent knowledge in the form of informed base policies. This explains why MCTS is not used in classical planning.

Width-based methods have been used both in simulated environments like ALE and GVG-AI and in classical planning [Lipovetzky and Geffner, 2012; Lipovetzky et al., 2015; Geffner and Geffner, 2015; Shleyfman et al., 2016; Jinnai and Fukunaga, 2017]. The most basic width-based search method is IW(k), a breadth-first procedure that prunes states with novelty greater than k, and which runs in time and space that are exponential in k (unlike breadth-first search, which is exponential in the number of variables). The novelty w(s) of a state in the search is given by the size of the smallest subset (conjunction) Q of atoms X = x such that Q is true in s (i.e., all atoms in Q are true in s) and false in all the states of the search generated before s. For repeated states s, w(s) is set to |V | + 1. Interestingly, IW(k) with k = 2 has been shown to find plans over many of the planning benchmark domains when the goal features a single atom. In turn, the procedure Serialized IW (SIW), that calls IW(k) sequentially with k = 1, 2, 3, for achieving joint goals incrementally, one by one, has been shown to be competitive with a simple baseline heuristic search planner guided by state-of-the-art heuristics [Lipovetzky and Geffner, 2012]. Unlike heuristic search planners, SIW can work directly with simulators, but its performance on classical benchmarks does not compare well with the best planners that use other techniques as well.

5 Classical Planning with BFWS(f)

Recently, state-of-the-art performance over classical benchmarks has been achieved by combining width and heuristic search [Lipovetzky and Geffner, 2017]. Best-first widthbased search is a standard best-first search that uses novelty measures to rank the nodes in OPEN. The novelty w(s) of a newly generated state s given the functions h1, . . . , hn is defined as the size of the smallest set (conjunction) of atoms that is true in s but false in all the states s′ generated before s that have the same hi values, i.e., such that hi(s) = hi(s′ ) for i = 1, . . . , n. This novelty measure is also written as w〈h1,...,hn〉. The best monolithic BFWS planner in [Lipovetzky and Geffner, 2017] is BFWS(f5), which uses w = w〈#g,#r〉, where #g(s) counts how many atomic goals in G are not true in s, and #r(s) is a subtler counter that has to do with potential subgoals that are not explicit in G. More precisely, when a state s is generated that achieves more goals than its parent sp, i.e., #g(s) < #g(sp), a set of atoms R(s) is computed such that, for any descendant s′ of s reached from s through states that do not achieve more goals than s, #r(s′ ) is the number of atoms in R(s) that are made true at some point in the way from s to s′ . For example, if R(s) is defined as a set of landmarks, then #r(s′ ) would count the number of those landmarks in R(s) achieved in the way from s to s′ , even if they do not hold in s′ anymore. In BFWS(f5), R(s) is not defined as a set of landmarks but as the set of atoms determined by a relaxed plan π(s) computed from s [Hoffmann and Nebel, 2001]; i.e., R(s) contains the preconditions and positive effects of the actions in π(s). Ties in BFWS(f5) are broken using the #g counter first (nodes with minimum #g preferred), and the accumulated cost to the node, second (cheaper nodes preferred). The algorithm BFWS(f5) solves as many problems of the 2014 Int. Planning Competition (IPC) as the best planners LAMA, Mercury [Katz and Hoffmann, 2014], and Jasper [Xie et al., 2014]. The general algorithm BFWS(R) below is BFWS(f5) but with different sets R(s).

6 Simulation Planning with BFWS(R)

The BFWS(f5) algorithm is a state-of-the-art method for classical planning, yet it cannot be applied to simulations. This is because the computation of the sets of atoms R(s) used in the definition of the #r counter relies on the deleterelaxation of the problem, which is not available from simulations. In order to have an algorithm that can plan with the black box functions A(s) and f(a, s) (action costs are assumed to be 1), we generalize the BFWS(f5) procedure into a family of search algorithms, called BFWS(R), that differ from BFWS(f5) in the way that the sets of atoms R(s) are defined and computed. Thus, BFWS(R) is a best-first search algorithm with a primary evaluation function given by novelty measures w〈#r,#g〉, breaking ties using the #g counter and accumulated costs. The BFWS(f5) algorithm is BFWS(R) with R(s) defined as the set of atoms in a relaxed plan computed from the state s, which we will denote as RX(s). Other methods for defining and computing R(s) are explored below, most of which do not require declarative action descriptions. Moreover, we focus only on methods that define and compute the set R once from the initial state s0 and then fix R(s) to R(s0) for any other state s where the set R is required. This is because the computation of such sets, while polynomial, can be expensive.

The intuition behind the BFWS(R) search schema, where R is a fixed set of atoms precomputed from the initial state, is that R represents a set of "potential subgoals" that, along with the given goals G, partitions the search nodes into classes associated with different "subproblems"; namely, the set of nodes that satisfy the same subset of goals from G and have reached the same set of subgoals from R. In each subproblem, the aim is to reach another goal or another potential subgoal that can eventually lead to another goal, ideally, by expanding novelty-1 nodes only (of which there is a linear number). Yet, since the number of such subproblems is exponential in the sizes of G and R, subproblems with the same number of goals and subgoals #g and #r are merged together. This is indeed what the novelty measure w〈#r,#g〉 used in BFWS(R) does. 1 In particular, a novelty measure of 1 for a state s means that s is the first state in the search that makes some atom p true, among the states s′ generated so far that belong to the same "subproblem" as s, namely, that have the same #g and #r counts. The result is that the total number of subproblems is given by |G| × |R|, and hence the maximum number of states that can have novelty k is |G| × |R| × |F |k , where |F| is the number of problem atoms.

The choices of the sets R of atoms in the general algorithm BFWS(R) that we consider are all fixed, in the sense that each is computed once from the initial state s0 as a polynomial form of preprocessing from the simulation, so that for any state s where the set R(s) is required, R(s) = R(s0). The different sets R that we consider are:

• R0 is the empty set. For this set, #r(s) = 0 for all s,
• RA is the set of all atoms; i.e., RA = F,
• R[k] is the set of atoms that are true in the states that are reachable from s0 by running IW(k), k ∈ {1, 2},
• RG is a goal-oriented version of the R[k] sets obtained from the plans for the individual goals computed by IW(1) and IW(2) from s0, if any,
• R∗G is a variant of RG that skips the IW(2) computation when the number of ground actions is too large, and
• RX is the union of the preconditions and positive effects of the actions in a relaxed plan computed from s0. This set cannot be computed from simulations and is included only as a baseline.

The exact definition of RG is as follows. The procedure IW(1) is run from s0; if that single invocation of IW(1) finds plans that reach each one of the individual problem goals, 2 then RG is set to the collection of atoms made true by such plans. If, on the contrary, IW(1) does not return a plan for some goal, then IW(2) is run from s0. If IW(2) finds plans for each of the problem goals, RG is set to the collection of atoms made true by such plans. Last, if neither IW(1) nor IW(2) reach each of the problem goals, RG is set to RA; i.e., the collection of all atoms. This definition takes advantage of the fact that the width of many standard domains when the goals are atomic is often 1 or 2, meaning that IW(1) or IW(2) will find plans for them in low polynomial time [Lipovetzky and Geffner, 2012]. The requirement that IW(1) and IW(2) reach all of the goals in order to consider the atoms appearing in state trajectories reaching a goal is there just to keep things simple. Indeed, one could consider the atoms in such trajectories even if, say, 10% of the goals are not reached. Also for simplicity, when each of the problem goals is reached by IW(1) or IW(2) through more than one plan, we collect in RG the atoms made true by only the first plan found for each goal, discarding all the others, which in principle could also yield useful information.

1 A related discussion can be found in [Lipovetzky, 2014].

The definition of RG is reminiscent of the use of relaxed plans in PDDL planning. Indeed, the union of the plans found by IW(k) that reach each of the individual problem goals is a plan for a problem relaxation which is tighter than the standard delete-relaxation: whereas the relaxed plan for a goal G1 ∧ . . . ∧Gn in the delete-relaxation is the union of relaxed plans for each of the Gi goals, the relaxed plans computed by IW(k) are made up of actual plans for each Gi. The downside of this is that IW(k) will not deliver any individual plan if the width of the atomic goals Gi is higher than k, and that even IW(3), while polynomial, can be expensive [Lipovetzky and Geffner, 2012].

2 Notice that finding plans that reach each of the goals individually is different than finding plans that reach all goals jointly.

The set R∗G is defined exactly as the set RG except for problems involving too many ground actions (> 40, 000), where running IW(2) becomes too expensive. For such problems, R∗G is set to RG when the IW(1) run reaches all of the problem goals, but when not, the IW(2) computation is skipped and R∗G is set directly to the collection of all atoms RA.

Notice that the first three R options, R0, RA and R[k], are independent of the problem goal, while the last three, RG, R∗G, and RX, are all goal-oriented, with RX being the only option that assumes knowledge of action preconditions and effects. For the other R sets, BFWS(R) is a simulation-based planning method.

7 Experimental Results

The performance of the simulation-based planning algorithm BFWS(R) for different R's is shown in Tables 1 and 2. The first table compares the top-performing R, R∗G, against two state-of-the-art PDDL planners, LAMA, and BFWS(f5), and a version FF∗ of the FF planner [Hoffmann and Nebel, 2001] that is supported in the Fast Downward planner, where FF's heuristic is used to drive a best-first search with two queues, one restricted to the nodes obtained with helpful actions only [Helmert, 2006]. FF is a second-generation heuristic search planner that uses helpful actions, while LAMA is a third-generation heuristic search planner that uses a landmark heuristic as well. Together, FF and LAMA have been the top-performing classical planners for the last 15 years. The original version of FF could not be used, as many instances include cost information. For the experiments, however, actions costs are taken to be 1 so that plan cost is equal to plan length. The second table evaluates BFWS(R) for the different choices of R, including the baseline option, R = RX, that relies on PDDL encodings for computing a relaxed plan once from the initial state.

Benchmarked problems include all instances from the last planning competition (IPC 2014), along with all instances from IPC 2011 domains that did not appear in IPC 2014, with the exception of Parcprinter, Tidybot and Woodworking, which produced parsing errors. There are thus a total of 19 domains, with 20 instances each, for a total of 380 instances. All planners and configurations in both tables have been run on AMD Opteron 6378@2.4Ghz CPUs with CPUtime and memory cutoffs of 1h and 16GB respectively. Tables report the standard measures: coverage (number of instances solved), and average plan lengths, (total) runtimes, and number of node expansions. Average times are in seconds rounded to the nearest integer. All averages are over the instances solved by all planners except when there are less than three such instances. Implementation details of the BFWS planners are given in the next Section; LAMA-11 and FF∗ are run using the latest version of Fast Downward [Helmert, 2006] available at the time of writing.

Table 1 shows that the best simulation-based BFWS(R) planner, BFWS(R∗G), performs extremely well in spite of not using any information about action structure, when compared to the state-of-the-art PDDL planners. Indeed, while LAMA solves 264 of the 380 instances (69.5%), BFWS(R∗G) solves 282 (74.2%). The PDDL planner BFWS(f5) does only slightly better, solving 283 (74.5%). FF∗ , on the other hand, solves 172 instances (45.3%), which illustrates that the considered problems are challenging. The planners, however, do very differently in the different domains. For example, in the domains Barman, Hiking, and Openstacks, LAMA solves 19, 18, and 20 instances respectively, while BFWS(R∗G) solves 9, 7, and 14. On the other hand, in domains such as CityCar, Maintenance, and Tetris, LAMA solves 5, 0, and 10 instances, while BFWS(R∗G) solves 19, 16, and 20. Surprisingly, these numbers are better than those of BFWS(f5) that solves 5, 16, and 11 instances, suggesting that relaxed plans are not helping that much in such domains. This seems to be confirmed by the other PDDL planner, RX, shown in Table 2, that solves 4, 14, and 17 of the instances. In terms of average plan lengths and times, there is no clear pattern, although BFWS(f5) is usually fastest, and along with LAMA-11, is the one that expands fewer of nodes. The averages of normalized plan lengths, times, and number of expanded nodes, displayed at the bottom of both tables, show that the simulation planner BFWS(R∗G) is only a bit slower than LAMA, produces plans of similar quality and, somewhat surprisingly, does not expand too many more nodes on average, in spite of the strong exploratory nature of BFWS algorithms.

Table 2 evaluates BFWS(R) for different alternatives of R. While none of them is better than R∗G in terms of coverage, they all do better than FF∗ and some approach the performance of LAMA. Except for RX, they are all simulated algorithms that do not exploit action descriptions. In comparison with the simulation planners, the relaxed plan computed by RX appears to provide useful guidance in domains such as Hiking, Openstacks, and Nomystery, where simulation planners solve much less instances. In fact, in Nomystery RX solves many more instances than LAMA and BFWS(f5), 19 vs. 11 and 14 respectively, meaning that the computation of all the other relaxed plans does not pay off. Since R∗G is RG except in instances that have more than 40,000 ground actions, it is only on those instances where the performance of BFWS(R∗G) and BFWS(RG) differ. These instances are mainly in Parking and Transport where the latter solves 16 and 7 instances, while the former solves them all. The empty R set, R0, is the weakest R, with 217 instances solved, well behind the other options and LAMA, although well ahead of FF∗ , which solves 172 instances.

The domains where simulated BFWS(R) algorithms struggle are of two types: problems where the atomic goals have a high width, and problems with tightly constrained plans where goals and subgoals are not easy to serialize. Examples of the former class of domains include Barman, Hiking, and Openstacks. Examples of the latter include Cavediving, Childsnack, and Floortile. This last class of domains, like any tight constraint satisfaction problem encoded as a planning problem, are hard also for heuristic PDDL planners like LAMA and BFWS(f5), which nevertheless perform much better in the first class of problems due to the exploitation of action structure in the form of relaxed plans.

8 Planner

The BFWS(R) algorithms are all implemented in the Functional STRIPS planner FS [Franc`es and Geffner, 2015], on top of the LAPKT toolkit (http://lapkt.org) in an extension that allows the free use of procedures for providing the denotation of fixed function and predicate symbols appearing in goals and action preconditions and effects. This free use of procedures greatly expands the modeling capabilities of the language, but is not easy to accommodate when heuristics are supposed to be derived automatically. Nevertheless, when FS runs in simulation mode no attempt at deriving heuristics is made (the whole action structure being invisible to the planner), and thus fixed symbols with procedural denotations pose no particular challenge.

The use of simulation mode does however affect the complexity of computing novelty measures. In propositional mode, testing if the state generated by an action has novelty 1 can be done in constant time by checking whether each one of the (bounded number of) atoms added by the action is new. In simulation mode, this test is linear in the number of variables, as there is no information about action effects, and the value of all variables in the resulting state needs to be checked. In general, while novelty-i tests in propositional mode are exponential in i - 1, in simulation mode they are exponential in i. For this reason, novelty measures greater than 1 are determined lazily; namely, only when no node with novelty 1 remains in the OPEN list of the search. Moreover, following [Lipovetzky and Geffner, 2017], only novelty-1 and novelty2 measures are computed, and even the latter are skipped in the BFWS(R) search when the number of atoms is too large. The selected set R is computed in a preprocessing step.

action move(x1: location) prec alive(p) ∧ @valid_move(loc(p), x1) effs loc(p) := x1 ¬pellet_at(x1) pellet_at(x1)-→ C := C + 1 ∀g ∈ ghost [loc(g) := @moveG(loc(g), x1)] goal alive(p), C =K init alive(p), C = 0, pellet_at(l1), . . . def alive(p: pacman)≡ ∀g : ghost loc(g) ̸= loc(p)

9 New Possibilities for Modeling and Control

We have seen how a move from purely declarative planning languages to simulation languages that freely combine declarative representations with procedures does not entail a significant performance loss, as one can plan effectively by exploiting state and goal structure while ignoring action structure. We now illustrate what can be gained from this move by considering two other aspects: modeling and control knowledge.

9.1 Modeling

Many classical problems that require reaching a goal by applying deterministic actions from a known initial state cannot be modeled easily using the standard planners, sometimes because of limitations of planners, that do not always provide good support to complex language constructs [Ivankovic and Haslum, 2015], sometimes because of limitations of planning languages. Challenging domains include, for instance, socalled "pseudo-adversarial" problems involving adversaries that follow a known, deterministic strategy that is nonetheless difficult to express propositionally, and problems like Pong, where physical actions have complex ramifications, like a ball bouncing against walls. Many of these limitations, however, can be overcome in one shot through the combination of expressive modeling languages and black box planning algorithms. A modeling language like Functional STRIPS [Geffner, 2000] offers the best of the declarative and procedural worlds; namely, a declarative, first-order logical language for modeling, where the denotation of fixed function and predicate symbols can be given extensionally, through sets of atoms, or intensionally, by means of procedures. This distinction makes no difference to simulated planning algorithms like BFWS(R) that get to see only the black box action transition and applicability functions.

Fig. 1 shows a fragment of a possible Functional STRIPS encoding of Pacman. In Pacman, the agent has to collect a number of food pellets (dots) by moving around in a maze, while avoiding a number of deadly ghosts that chase him. Functional (predicate) symbols @f denote (Boolean) functions specified by external procedures. In this case, the maze is implicitly encoded by the Boolean function @valid move, and the deterministic strategy followed by the ghosts (move always to the adjacent grid position that is closest to the pacman according to the Manhattan-distance) is encoded by the @moveG procedure, where ghosts are assumed to know where the pacman is moving. For simplicity, "power pellets" are omitted. We have run different versions of BFWS(R) in these and other domains that are difficult or impossible to tackle with PDDL planners. These include a singleagent version of the Pong videogame, where the agent controls a paddle and aims at hitting a ball with billiard-like dynamics a certain number of times; Trapping [Ivankovic and Haslum, 2015], where the agent has to trap an opponent (a cat) that is always looking for the nearest exit; Helping, in which the agent guides the cat to an exit by turning lights on that the cat will follow if sufficiently close, and Pursuit, a predators-and-prey game. All problem encodings and results can be found at https://github.com/ aig-upf/2017-planning-with-simulators. Interestingly, the GVG-AI competition problems encoded in VGDL, an elegant language for encoding grid-problems that is part declarative and part procedural [Schaul, 2013], should be easy to translate into Functional STRIPS, once dynamic object creation and non-determinism are excluded. Non-deterministic and probabilistic extensions of Functional STRIPS were implemented early in the GPT planner, that deals with MDPs and POMDPs [Bonet and Geffner, 2001a].

9.2 Control Knowledge: Features and BFWS(F)

Features offer a way to express domain-dependent knowledge in the context of width-based search algorithms like IW and BFWS. A feature φ is a Boolean function of the state which can be used as an extra atom in the computation of novelty. For example, in blocks-world problems, a Boolean feature φx,y can be defined for each goal atom on(x, y), that is true in a state s when clear(x) and clear(y) are both true in s. By adding such a feature, BFWS(R0), for example, decrements the number of nodes expanded to reach the goal by an average factor of 3. Such a reduction happens because some relevant states that are reached in the search with novelty 2, will have novelty 1 once the extra atoms are considered. This is indeed what conjunctive features do: they promote or give priority to states that achieve certain conjunctions of atoms. Yet features can be arbitrary Boolean functions of the state, not just conjunctions, and an interesting generalization can be obtained by combining features and explicit priorities.

Let a ranked feature list be a list F = 〈F1, . . . , FM〉 where Fi is a set of Boolean features with priority i. Ranked feature lists provide an abstraction and generalization of the algorithms IW and BFWS, where the notion of novelty is decoupled from the problem atoms and the size of conjunctions. For this, let the F-novelty of a state s in the search, wF (s), be the minimum i such that for some feature φ in Fi, φ is true in s for the first time in the search, with the convention that wF (s) is M + 1 when there is no such feature.

The IW(1) algorithm can be seen as a breadth-first search where states with novelty wF (s) > 1 are pruned, where F = 〈F1〉 and F1 is given by the features φ〈p〉, one for each problem atom, such that φ〈p〉(s) is true iff p is true in s. Similarly, IW(2) is a breadth-first search where states with novelty wF (s) > 2 are pruned, where F = 〈F1, F2〉, and F2 contains a feature φ〈p,q〉 for each pair of different atoms p and q, and φ〈p,q〉(s) is true iff p and q are both true in s.

More interestingly, BFWS(R) for R = R0 (empty R) is a plain best-first algorithm guided by a novelty function wF where the features are F = 〈F1, F2〉, and F1 and F2 contain the features φ〈p,i〉 for each atom p, and the features φ〈p,q,i〉 for each pair p, q, where 1 ≤ i ≤ |G|. The feature φ〈p,i〉 is true in a state s when p is true in s and #g(s) = i, while φ〈p,q,i〉 is true in s when both p and q are true in s, and #g(s) = i. Finally, the general BFWS(R) algorithm can be approximated when the features in F1 and F2 are defined as φ〈p,i,j〉 and φ〈p,q,i,j〉 where in both cases the new j component, 1 ≤ j ≤ |R|, tests whether the number of atoms in R that are true in s, #r′ (s), is equal to j. This is an approximation because the #r′ counter is state-dependent, while the actual counter #r used in BFWS(R) is path-dependent (counts number of atoms from R reached in the way to s).

The algorithms IW(F) and BFWS(F) refer to the IW and BFWS algorithms where novelties are computed according to the ranked feature list F. The use of these lists not only provides a uniform way for understanding and programming width-search based algorithms, but also opens up the possibility of encoding control knowledge by playing with features and priorities, which could potentially be inferred from training data using machine learning algorithms.

10 Conclusions

We have developed a new class of black box planning algorithms that approach the performance of the best classical planners over the existing PDDL benchmarks. The black box or simulated algorithms have access to the structure of states (the variables), the initial state, and the set of goals, but have no access to the structure of actions; namely, action preconditions and effects. This suggests that the computational role of declarative planning languages such as PDDL may be overrated. Declarative languages, however, remain important from the point of view of modeling. First-order logical planning languages such as Functional STRIPS appear to provide the best of both worlds by allowing fixed function and predicate symbols to denote actual procedures. While this expressive power is not compatible with mainstreammethods, it can be exploited by the methods proposed here. Effective black box planning methods can indeed produce a radical change in the scope and use of planners, and in the ways in which planning problems are modeled.

Acknowledgments

G. Franc`es is supported by the M. de Maeztu Programme (MDM-2015-0502) and H. Geffner by grant TIN2015-67959P, both from MINECO, Spain. M. Ramirez and N. Lipovetzky have been partially funded by the Australian DST Group.