Heuristic Planning for PDDL+ Domains

1 Introduction

Over the years, Automated Planning research has been continuously attempting to solve the most advanced and complex planning problems. The standard modelling language, PDDL [McDermott et al., 1998], has evolved to accommodate new concepts and operations, enabling research to tackle problems which more accurately represent real-world scenarios. PDDL2.1 [Fox and Long, 2003] enabled modelling numeric variables and temporal information in the domains, while PDDL+ [Fox and Long, 2006] introduced exogenous events and continuous processes in the models. PDDL+ is the most accurate standardised way yet, of defining hybrid problems as planning domains.

Planning with PDDL+ has been gaining research interest in the Automated Planning community in recent years. Hybrid domains are models of systems which exhibit both continuous and discrete behaviour. They are amongst the most advanced models of systems and the resulting problems are notoriously difficult for planners to cope with due to non-linear behaviour and immense search spaces.

UPMurphi [Della Penna et al., 2009], based on the Discretise & Validate approach, is the only planner able to handle the full range of PDDL+. However, the main drawback of UPMurphi is the lack of heuristics, which critically limits its scalability. In this paper, we fill the gap, and introduce DiNo, a new planner for PDDL+ problems with mixed discrete-continuous non-linear dynamics. DiNo is built on UPMurphi. It uses the planning-as-model-checking paradigm [Cimatti et al., 1997; Bogomolov et al., 2014], and relies on the Discretise & Validate approach [Della Penna et al., 2009] to handle continuous change and non-linearity.

DiNo uses a novel relaxation-based domain-independent heuristic for PDDL+, Staged Relaxed Planning Graph+ (SRPG+). The heuristic guides the Enforced Hill-Climbing algorithm [Hoffmann and Nebel, 2001]. In DiNo we also exploit the deferred heuristic evaluation [Richter and Westphal, 2010] for completeness (in a discretised search space with a finite horizon). The SPRG+ heuristic which improves on the Temporal Relaxed Planning Graph and extends its functionality to include information gained from PDDL+ features, namely the processes and events.

The domain-independent SRPG+ heuristic makes DiNo the only heuristic planner capable of handling non-linear system dynamics combined with the full PDDL+ feature set.

We begin by discussing the related work done in the area of PDDL+ planning in section 2. We then outline the basis of the Discretise & Validate method on which DiNo is based and the underlying UPMurphi architecture in section 3. In section 4 we describe the SRPG+ heuristic. Section 5 describes the experimental evaluation. Section 6 concludes the paper 1 .

2 RelatedWork

Various techniques and tools have been proposed to deal with hybrid domains [Penberthy and Weld, 1994; McDermott, 2003; Li and Williams, 2008; Coles et al., 2012; Shin and Davis, 2005]. Nevertheless, none of these approaches are able to handle the full set of PDDL+ features, i.e. nonlinear domains with processes and events. More recent approaches in this direction have been proposed by [Bogomolov et al., 2014], where the close relationship between hybrid planning domains and hybrid automata is explored. [Bryce et al., 2015] use dReach with a SMT solver to handle hybrid domains. However, dReach does not use PDDL+, and cannot handle exogenous events.

1 Research leading to these results has received funding from the European Commission under contract No. FP7-610532-SQUIRREL

On the other hand, many works have been proposed in the model checking and control communities to handle hybrid systems. Some examples include [Cimatti et al., 2015; Cavada et al., 2014; Tabuada et al., 2002; Maly et al., 2013], sampling-based planners [Karaman et al., 2011; Lahijanian et al., 2014]. Another related direction is falsification of hybrid systems (i.e., guiding the search towards the error states, that can be easily cast as a planning problem) [Plaku et al., 2013; Cimatti et al., 1997]. However, while all these works aim to address a similar problem, they cannot reason with PDDL+ domains. Some recent works [Bogomolov et al., 2014; 2015] are trying to define a formal translation between PDDL+ and standard hybrid automata, but so far only an over-approximation has been defined, that only allows proving plan non-existence. PDDL+ also presents important features, including Timed Initial Literals/Fluents, no-moving target rule, epsilon separation of actions. Currently, no control-based approaches can handle PDDL+ models.

To date, the only viable approach in this direction is PDDL+ planning via discretisation. UPMurphi [Della Penna et al., 2012], which implements the Discretise & Validate approach, is able to deal with the full range of PDDL+ features. UPMurphi's main drawback is the lack of heuristics which strongly limits its scalability. However, UPMurphi was successfully used in the multiple-battery management domain [Fox et al., 2012], for urban traffic control [Vallati et al., 2016], and for unit commitment problem [Piacentini et al., 2016] . In all cases, a domain-specific heuristic was used.

3 Discretise &Validate Approach

As a successor to UPMurphi, DiNo relies on the Discretise & Validate approach [Della Penna et al., 2012] which approximates the continuous dynamics of systems in a discretised model with uniform time steps and step functions. Using a discretised model and a finite-time horizon ensures a finite number of states in the search for a solution. Solutions to the discretised problem are validated against the original continuous model using VAL [Howey et al., 2004]. If the plan at a certain discretisation is not valid, the discretisation can be refined and the process iterates. An outline of the Discretise & Validate process is shown in Figure 1.

In order to plan in the discretised setting, PDDL+ models are translated into finite state temporal systems, as formally described in the following 2 .

Definition 1. State. Let P be a finite set of propositions and V = ¶v1↪ ▷▷▷↪ vn♦ a set of real variables. A state s is a triple s = (p(s)↪ v(s)↪ t(s)), where p(s) ✓ P, v(s) = (v1(s)↪ ▷▷▷↪ vn(s)) 2 Rn is a vector of real numbers, and t(s) the value of the temporal clock in state s. We also denote with vi(s) the value of variable at the i-th position in v(s).

Note that real variables and temporal clock are discretised, according to the Discretise & Validate approach.

2 Our notation was inspired by Metric-FF [Hoffmann, 2003].

Definition 2. ∆-Action. A ∆-action updates the state during the search. It can be of three types: an instantaneous PDDL action, a snap action [Long and Fox, 2003], or a time-passing action, tp.

The effect of instantaneous actions and snap actions, is to update the state variables in the state resulting from their application, and to start/end a durative action, respectively.

The time-passing action implements the step function used to discretise the system dynamics, its effects are: (i) updating all numeric state variables affected by the combined effect of all processes that are active at the time of application, (ii) updating all state variables affected by events, and (iii) advancing time by ∆t.

Definition 3. Finite State Temporal System (FSTS). Let a Finite State Temporal System S be a tuple (S↪ s0↪ ∆A↪ D↪ F↪ T ) where S is a finite set of states, s0 2 S the initial state, ∆A is a finite set of ∆-actions and D = ¶0↪ ∆t♦ where ∆t is the discretised time step. F : S ⇥∆A⇥D!S is the transition function, i.e. F(s↪∆a↪ d) = s0 iff applying ∆-action ∆a with a duration d 2 D to a state s yields a new reachable state s0 . T is the finite temporal horizon.

Note that d can be 0 to allow for concurrent plans and instantaneous actions. In fact, d will equal ∆t only in the case of the tp action. The finite temporal horizon T makes the set of discretised states S finite.

Definition 4. Trajectory. A trajectory, ⇡, in an FSTS S = (S↪ s0↪∆A↪D↪ F) is a sequence of states, ∆- actions and durations ending with a state, i.e. ⇡ = s0↪∆a0↪ d0↪ s1↪∆a1↪ d1↪ ▷▷▷↪ sn where 8i ≥ 0↪ si 2 S is a state, ∆ai 2 ∆A is a ∆-action and di 2 D is a duration. At each step i, the transition function F yields the subsequent state: F (si↪ ∆ai↪ di) = si+1.

Given a trajectory ⇡, we use ⇡s(k)↪ ⇡a(k)↪ ⇡d(k) to denote the state, ∆-action and duration at step k, respectively. The length of the trajectory based on the number of actions it contains is denoted by ♣⇡♣ and the duration of the trajectory is denoted as ˜⇡ = P♣⇡♣-1 i=0 ⇡d(i) or, simply, as ˜⇡ = t(⇡s(n))

Following from Definition 1, each state s contains the temporal clock t, and t(s) counts the time elapsed in the current trajectory from the initial state to s. Furthermore, 8si↪ sj 2 S : F(si↪∆a↪ d) = sj↪ t(sj) = t(si) + d. Clearly, for all states s, t(s)  T .

Definition 5. Planning Problem. In terms of a FSTS, a planning problem P is defined as a tuple P = ((S↪ s0↪ ∆A↪ D↪ F↪ T )↪ G) where G ✓ S is a finite set of goal states. A solution to P is a trajectory ⇡⇤ where ♣⇡⇤ ♣ = n↪ ˜⇡  T↪ ⇡⇤ s (0) = s0 and ⇡⇤ s (n) 2 G.

3.1 Handling the PDDL+ Semantics through Discretisation

In the following we show how FSTS are used to handle the PDDL+ semantics, and describe how this approach has been first implemented in UPMurphi 3 .

Time and Domain Variable Discretisation. UPMurphi discretises hybrid domains using discrete uniform time steps and corresponding step functions. The discretisations for the continuous time and the continuous variables are set by the user. Timed Initial Literals and Fluents are variables whose value changes at a predefined time point [Edelkamp and Hoffmann, 2004]. UPMurphi can handle Timed Initial Literals and numeric Timed Initial Fluents to the extent that the discretisation used is fine enough to capture the happenings of TILs and TIFs. On the other hand, the time granularity of TILs and TIFs can be used as a guidance for choosing the initial time discretisation.

Actions and Durative-Actions. Actions are instantaneous, while durative-actions are handled following the start-processstop model introduced by [Fox and Long, 2006]. A durativeaction is translated into: (i) two snap actions that apply the discrete effects at start and at end of the action; (ii) a process that applies the continuous change over the action execution (iii) and an event that checks whether all the overall conditions are satisfied in the open interval of the durative-action execution. Following Definition 2, actions in UPMurphi are used to model instantaneous and snap actions, while the special action time-passing tp is used to advance time and handle processes and events.

Processes and Events. UPMurphi uses the tp action to check preconditions of processes and events at each clock-tick, and then apply the effects for each triggered event and active process. Clearly, the processes/events interleaving could easily result in a complex scenario to be executed, as for example an event can initiate a process, or multiple events can be triggered at a single time point. To address this kind of interaction between processes and events, UPMurphi works as follows: first, it applies the continuous changes for each active process and the effects of each triggered event. Second, it assumes that no event can affect the parts of the state relevant to the preconditions of other events, according to the no moving target definition provided by [Fox and Long, 2003]. In this way, the execution of events is mutually-exclusive, and their order of execution does not affect the final outcome of the plan. Third, UPMurphi imposes that, at each clock tick, any event can be fired at most once, as specified by [Fox et al., 2005], for avoiding cyclic triggering of events.

3 UPMurphi can also be used as Universal Planner, where a policy is generated, while we focus here on finding single plans.

4 Staged Relaxed Planning Graph+

This section describes the Staged Relaxed Planning Graph+ (SRPG+) domain-independent heuristic designed for PDDL+ domains and implemented in DiNo.

The SRPG+ heuristic is based on Propositional [Hoffmann and Nebel, 2001], Numeric [Hoffmann, 2003] and Temporal RPGs [Coles et al., 2010; 2012]. Like its predecessors, SRPG+ relaxes the original problem and ignores the delete effects of actions on propositional facts. Numeric variables are represented as upper and lower bounds which are the theoretical highest and lowest values each variable can take at the given fact layer. Each layer is time-stamped to keep track of its time of occurrence.

The SRPG+, however, extends the capability of its RPG predecessors by tracking processes and events to capture the continuous and discrete evolution of the system.

For clarity, we denote SRPG+ as the heuristic and SRPG as the internal relaxed planning graph structure.

4.1 Building the SRPG

Apart from the inclusion of processes and events, the SRPG+ significantly differs from the Temporal RPG in time-handling. The SRPG contains every fact layer with the corresponding time clock, and in this sense the RPG is "staged", as the finite set of fact layers are separated by ∆t. In contrast, the TRPG takes time constraints into account by time-stamping each fact layer at the earliest possible occurrence of a happening. Only fact layers where values are directly affected by actions are contained in the TRPG.

Definition 6. Fact Layer. A fact layer b s is a tuple (p+(b s)↪ v+(b s)↪ v-(b s)↪ t(b s)) where p+(b s) ✓ P is a finite set of true propositions, v+(b s) is a vector of real upper-bound variables, v-(b s) is a vector of real lower-bound variables, s) is the value of the temporal clock.

and t(b Notationally, v+ i (s) and vi (s) are, respectively, the upper and lower-bound values of the variable at position i in v(s).

In the following we give a formal definition of an SRPG, starting from the problem for which it is constructed.

Definition 7. SRPG. Let P = (S↪ G) be a planning problem in the FSTS S = (S↪ s0↪ ∆A↪ D↪ F↪ T ), then a Staged Relaxed Planning Graph b S is a tuple ( b S↪ b s0↪ d ∆A↪∆t↪ b F ↪ T ) where b S is a finite set of fact layers, b s0 is the initial fact layer, d ∆A is a set of relaxed∆actions, ∆t is the time step. b F : b S⇥2d ∆A ⇥∆t ! b S is the SRPG transition function. T is the finite temporal horizon.

The SRPG follows the priority of happenings from VAL, i.e. each new fact layer b s0 is generated by applying the effects of active processes in b s, applying the effects of any triggered events and firing all applicable actions, respectively. Note that, as for the FSTS, also in the SRPG the time passing action tp is used for handling processes and events effects and for advancing time by ∆t.

Fact layers and relaxed actions in the SRPG are defined as in the standard numeric RPG, except for the fact that each fact layer includes also the temporal clock.

Algorithm 4.1: Building the SRPG

Data: P = ((S↪ s0↪ ∆A↪ D↪ F↪ T )↪ G); [ Proc = Set of processes; c Ev = Set of events; Result: return a constructed SRPG object if exists 1 b s := s0; 2 b S := ¶s0♦; 3 b S := (b S↪ b s↪ d ∆A↪∆t↪ b F ↪ T ); 4 while (8g 2 G : p+(g) * p+(b s)) _ (9vi 2 v(g) : vi < vi (b s) _ vi > v+ i (b s)) do 5 if t(b s) > T then 6 return fail; 7 forall d proc 2 [ P roc do 8 if p(pre(d proc)) ✓ p+(b s) ^ (8vi 2 v(pre(d proc)) : vi ≥ vi (b s) ^ vi  v+ i (b s)) then 9 8vi 2 v+(e↵ (d proc)) : v+ i (b s) := v+ i (b s) + vi ; 10 8vi 2 v-(e↵ (d proc)) : vi (b s) := vi (b s) - vi ; 11 forall b ev 2 c Ev do 12 if p(pre( b ev)) ✓ p+(b s) ^ (8vi 2 v(pre( b ev)) : vi ≥ vi (b s) ^ vi  v+ i (b s)) then 13 p+(b s) := p+(b s) [ p+(e↵ ( b ev)); 14 8vi 2 v+(e↵ ( b ev)) : v+ i (b s) :=max(v+ i (b s)↪ vi) 8vi 2 v-(e↵ ( b ev)) : vi (b s) :=min(vi (b s)↪ vi) 15 b sc := b s; 16 forall ba 2 d ∆A do 17 if p(pre(ba)) ✓ p+( b sc) ^ (8vi 2 v(pre(ba)) : vi ≥ vi (b sc) ^ vi  v+ i (b sc)) then 18 p+(b s) := p+(b s) [ p+(e↵ (ba)); 19 8vi 2 v+(e↵ (ba)) : v+ i (b s) :=max(v+ i (b s)↪ vi); 20 8vi 2 v-(e↵ (ba)) : vi (b s) :=min(vi (b s)↪ vi); 21 t(b s) := t(b s) + ∆t; 22 b S := b S [ b s; 23 return b S;

p+(e↵ (x))↪ p-(e↵ (x)) ✓ P (add and delete effects respectively), v+(e↵ (x)) and v-(e↵ (x)) are effects on numeric values (increasing and decreasing, respectively), and x can be any ∆-action, process, or event. Preconditions are defined analogously: pre(x) = (p(pre(x))↪ v(pre(x))) where p(pre(x)) ✓ P is a set of propositions and v(pre(x)) is a finite set of numeric constraints. p+i (e↵ (x)) 2 p+(e↵ (x)) is effect on the i-th proposition in p(s), v+ i (e↵ (x)) and vi (e↵ (x)) are the real values of the i-th increasing and decreasing effects affecting upper bound v+ i (s) and lower bound vi (s), respectively.

The SRPG transition function b F is a relaxation of the original FSTS transition function F , and follows the standard RPG approach: effects deleting any propositions are ignored and the numeric effects only modify the appropriate bounds for each numeric variable. Note that the set d ∆A of relaxed ∆ actions includes the time passing action tp as from Definition 1. Also in the SRPG the tp is responsible for handling processes and events, whose effects are relaxed in the standard way. The construction of SRPG is shown in Algorithm 4.1. The first fact layer consists of the initial state (lines 1-3). Then the SRPG is updated until a goal state is found (line 4) or the time horizon is reached (line 5). In the former case, the SRPG constructed so far is returned, and the relaxed plan is extracted using backwards progression mechanism introduced in [Hoffmann, 2003]. In the latter case, a heuristic value of infinity (h(s) =1) is assigned to the current state. To construct the next fact layer, first the active processes are considered (lines 7-8) and the relaxed effects are applied to update upper and lower bounds of variables (lines 9-10). The same is then applied for events (lines 11-15) and instantaneous actions (lines 16-20), that can also add new propositions to the current fact layer. The last step is to increment the temporal clock (line 21), and the new fact layer is then added to the SRPG (line 22).

Note that, as a back-up strategy, DiNo reverts to a breadthfirst search if the SRPG+ is unable to extract sufficient information from the domain to reach the relaxed goal within the set temporal horizon T (i.e. h(s) =1 for all states).

4.2 Time Handling in the SRPG

The time-passing action plays an important role as it propagates the search in the discretised timeline. During the normal expansion of the Staged Relaxed Planning Graph, the timepassing is one of the ∆-actions and is applied at each fact layer. Time-passing can be recognised as a helpful action [Hoffmann and Nebel, 2001] when its effects achieve some goal conditions (or intermediate goal facts). However, if, at a time t, no helpful actions are available to the planner, time-passing is assigned highest priority and used as a helpful action. This allows the search to quickly manage states at time t where no happenings of interest are likely to occur.

This is the key innovation with respect to the standard search in the discretised timeline performed, e.g., by UPMurphi. Indeed, the main drawback of UPMurphi is in that it needs to expand the states at each time step, even during the idle periods, i.e., when no interesting interactions or effects can happen. Conversely, SRPG+ allows DiNo to identify time-passing as a helpful action during idle periods and thus advance time, mitigating the state explosions.

An illustrative example is shown in Figure 2, that compares the branching of the search in UPMurphi and DiNo when planning with a Solar Rover domain. The domain is described in detail in Section 5. Here we highlight that the planner can decide to use two batteries, but the goal can only be achieved thanks to a Timed Initial Literal that is triggered only late in the plan. UPMurphi has no information about the future TIL, therefore it tries to use the batteries at each time step. On the contrary, DiNo recognises the time-passing as a helpful action, and this prunes the state space dramatically.

4.3 Processes and Events in SRPG+

As the SRPG+ heuristic is tailored for PDDL+ domains, it takes into account processes and events. In the SRPG, the continuous effects of processes are handled in the same manner as durative action effects, i.e. at each action layer, the numeric variables upper and lower bounds are updated based on the time-step functions used in the discretisation to approximate the continuous dynamics of the domain.

Events are checked immediately after processes and their effects are relaxed as for the instantaneous actions. The events can be divided into "good" and "bad" categories. "Good" events aid in finding the goal whereas "bad" events either hinder or completely disallow reaching the goal. Currently, DiNo is agnostic about this distinction. However, as a direct consequence of the SRPG+ behaviour, DiNo exploits good events and ignores the bad ones. Future work will explore the possibility of inferring more information about good and bad events from the domain.

5 Evaluation

In this section we evaluate the performance of DiNo on PDDL+ benchmark domains. Note that the only planner able to deal with the same class of problems is UPMurphi, which is also the most interesting competitor as it can highlight the benefits of the proposed heuristic. For sake of completeness, where possible, we also provide a comparison with other planners able to handle (sub-class of) PDDL+ features, i.e. POPF [Coles et al., 2010] and dReach [Bryce et al., 2015] 4 .

For our experimental evaluation, we consider two benchmark domains: Generator and Car. In addition, we also consider two more domains that highlight specific aspects of DiNo: Solar Rover that shows how DiNo handles TILs, and Powered Descent that further tests its non-linear capabilities.

Note that to achieve the results a discretisation of ∆t = 1▷0 was chosen, except non-linear Generator where some problems required refinement to ∆t = 0▷5.

For a fair comparison, all results were achieved by running the competitor planners on a machine with an 8-core Intel Core i7 CPU, 8GB RAM and Ubuntu 14.04 operating system. For more information visit kcl-planning.github.io/DiNo

Generator. This domain [Howey and Long, 2003] is wellknown across the planning community and has been a test-bed for many planners. The problem revolves around refueling a diesel-powered generator which has to run for a given duration without overflowing or running dry. We evaluate DiNo on both the linear and non-linear versions of the problem. In both variants, we increase the number of tanks available to the planner while decreasing the initial generator fuel level for each subsequent problem.

4 We do not consider [Bogomolov et al., 2014] as they only focus on proving plan-non-existence.

The non-linear Generator models fuel flow rate using Torricelli's Law which states: Water in an open tank will flow out through a small hole in the bottom with the velocity it would acquire in falling freely from the water level to the hole. The fuel level in a refueling tank (Vfuel) is calculated by:

Vinit the initial volume of fuel in the tank, k the fuel flow constant (which depends on gravity, size of the drain hole, and the cross-section of the tank), and tr is the time of refueling (bounded by the fuel level and the flow constant). The rate of change in the tank's fuel level is modelled by:

This domain has been previously encoded in PDDL by [Howey and Long, 2003].

The results for the linear Generator problems show that DiNo clearly outperforms its competitors and scales really well on this problem whereas UPMurphi, POPF and dReach all suffer from state space explosion relatively early.

The non-linear version could only be tested on DiNo and UPMurphi as the remaining planners do not support non-linear behaviour. However, the search space proved too large for UPMurphi, it failed to solve any of our test problems. DiNo found solutions to problems using ∆t = 1▷0. However, some of the found plans were invalid. Applying the Discretise & Validate approach, we refined the discretisation to ∆t = 0▷5 and valid solutions were returned. In both variants of the domain, time horizon was set to T = 1000, that is the duration for which the generator is requested to run.

Though dReach is able to reason with non-linear dynamics, their results have been left out of our comparison due to the difficulty with reproducing our domain (written in PDDL+) using the dReach modelling language. The dReach domain and problem descriptions are not standardised and extremely difficult to formulate. Each mode has to be explicitly defined, meaning that the models are excessive in size (i.e. the files for 1, 2, 3 and 4-tank problems are respectively 91, 328, 1350, 5762 lines long). Furthermore, compared to our model, Bryce et al. use a much simplified version of the problem where the generator can never overflow, the refueling action duration is fixed (tanks have no defined capacity), and the flow rate formula is defined as (0▷1 ⇤ (tank refuel time2 )). Still, in this simplified domain, dReach could only scale up to 3 tanks.

In contrast, our variant of the non-linear Generator problem uses the Torricelli's Law to model the refueling flow rate (2), the refueling actions have inequality-based duration dependent on the tanks' fuel levels (1), and the generator can easily overflow. As a result, our domain is far more complex and further proves our improvement.

As can be noticed, DiNo scales very well on these problems, and drastically reduces the number of explored states and the time to find a solution compared to UPMurphi.

Solar Rover. We developed the Solar Rover domain to test the limits and potentially overwhelm discretisation-based planners, as finding a solution to this problem relies on a TIL that is triggered only late in the plan.

The task revolves around a planetary rover transmitting data which requires a certain amount of energy. To generate enough energy the rover can choose to use its batteries or gain energy through its solar panels. However, the initial state is at night time and the rover has to wait until daytime to be able to gather enough energy to send the data. The sunshine event is triggered by a TIL at a certain time. The set of problem instances for this domain has the trigger fact become true at an increasingly further time point (50 to 1000 time units).

This problem has also been extended to a non-linear version to further test our planner. Instead of instantaneous increase in rover energy, the TIL triggers a process charging the rover's battery at an exponential rate: ∆E = 0▷0025E2 .

For both variants of the domain, the time horizon is set depending on the time point at which the sunexposure TIL is triggered (as defined in the problems).

DiNo can easily handle this domain and solve all test problems. UPMurphi struggles and can only solve the smallest problem instance of either variant. POPF and dReach could not solve this domain due to problems with handling events. Powered Descent. We developed a new domain which models a powered spacecraft landing on a given celestial body. The vehicle gains velocity due to the force of gravity. The available action is to fire thrusters to decrease its velocity. The thrust action duration is flexible and depends on the available propellant mass. The force of thrust is calculated via Tsiolkovsky rocket equation [Turner, 2008]:

∆v is the change in spacecraft velocity, Isp is the specific impulse of the thruster and g is the gravitational pull. m0 is the total mass of the spacecraft before firing thrusters and m1 = m0 -qt is the mass of the spacecraft afterwards (where q is the rate at which propellant in consumed/ejected and t is the duration of the thrust). The goal is to make a controlled landing from the initial altitude within a given time-frame.

Powered Descent problems were set with increasing initial altitude of the spacecraft (from 100 to 2000 metres) under Earth's force of gravity. The SRPG time horizon was set to T = 20 for the first 3 problems and T = 40 for the remaining problem instances based on the equations in the domain.

DiNo clearly outperforms UPMurphi which suffers from state explosion relatively early.

Car. The Car domain [Fox and Long, 2006] shows that DiNo does not perform well on all types of problems. SRPG+ cannot extract enough information from the domain and as a result loses out to UPMurphi by approximately one order of magnitude. Table 1 shows results for problems with processes and events. The plan duration and acceleration are limited, and the problems are set with increasing bounds on acceleration (corresponding to the problem number). The SRPG+ time horizon was set to T = 15 based on the goal conditions.

The reason behind our heuristic struggling in this case is that the domain is focused on continuous dynamics and, in fact, little search is required. Also, there is no direct link between any action and the goal conditions, since only the processes affect the necessary variables. As a consequence, DiNo reverts to a blind search and explores the same number of states as UPMurphi. The results show the overhead generated by the SRPG+ heuristic in DiNo that fundamentally depends on the sizes of states and the length of the solution.

6 Conclusion

We have presented DiNo, the first heuristic planner capable of reasoning with the full PDDL+ feature set and complex nonlinear systems. DiNo is based on the Discretise & Validate approach, and uses the novel SRPG+ domain-independent heuristic that we have introduced in this paper. We have empirically proved DiNo's superiority over its competitors on benchmark problems set in hybrid domains. Enriching discretisation-based planning with an efficient heuristic that takes processes and events into account is an important step in PDDL+ planning. Future research will concentrate on expanding DiNo's capabilities for inferring more information from the PDDL+ models.