Landmarks for Numeric Planning Problems

1 Introduction

Numeric planning [Fox and Long, 2003] is the extension of classical/STRIPS planning where also numeric variables can participate into the definition of (sub)goals and actions of the problem. Despite being undecidable in the general case [Helmert, 2002], efficient reasoning in this setting is a key ingredient for planning in real world contexts, where propositional and numeric reasoning has to be done in an combined way [Della Penna et al., 2009; Scala et al., 2016b; Fox and Long, 2006; L¨ohr et al., 2012; Fox et al., 2011].

In propositional planning, landmarks [Hoffmann et al., 2004], meaning atoms/actions necessary to achieve the goal, have been a key mechanism to devise informed heuristics used by both optimal and satisficing state-of-the-art planners [Keyder et al., 2010; Helmert and Domshlak, 2009; Pommerening et al., 2014; Haslum et al., 2012]. In addition landmarks elicit some of the problem's structure, which may be used in other ways, for example to decompose the problem. Finding the complete set of landmarks is as hard as solving it [Hoffmann et al., 2004]; thus, most works approximate the landmark set using some kind of problem relaxation, and the hope is that such a relaxation still contains useful structural information. Recently, new relaxations for numeric planning have been devised [Scala et al., 2016a], which, under some conditions, improve on previous interval-based relaxation heuristics [Hoffmann, 2003; Scala et al., 2016b].

This paper studies landmarks for numeric planning through the lens of the subgoaling relaxation [Scala et al., 2016a]. For this relaxation we derive a hybrid version of the AND/OR graph introduced by Keyder et al. [2010], capturing achievers and dependencies of both numeric and propositional subgoals; this gives us a method for inferring both types of landmarks. Numeric landmarks are metric conditions that are necessarily achieved in every plan solving the problem. Extending previous cost-partitioning techniques [Karpas and Domshlak, 2009], we formulate a linear program that estimates not only which actions are necessary, but also can quantify the number of times that actions need to be executed in any plan solving the problem. The result is a landmark-based admissible heuristics for cost-optimal numeric planning, which we show to be more effective than the admissible numeric heuristic proposed by Scala et al. [2016a] for certain kinds of problems. Other (mainly inadmissible) heuristics for numeric planning have been studied in the past [Hoffmann, 2003; Coles and Coles, 2011; Eyerich et al., 2012]; yet, to the best of our knowledge, no other work has developed them from a landmarks perspective. This paper attempts to close this gap.

1.1 An Illustrative Example

Consider an N-dimensional, metric Travelling Salesman Problem: An agent, initially at 〈x0, ..., xn-1〉, must visit each of a set of regions, w0,w1, ...,wm-1, in any order, minimising its total movement. Each region wj is defined by a conjunction of simple inequalities ∧0≤i<n (xi + ki,j{≤,≥}0) that bounds it in each dimension. The position of the agent is represented by n numeric state variables. A goal proposition, gi, for each region is achievable by an action visiti whose precondition is that the agent is in the region. Because the agent's movement is encoded numerically, the propositional landmarks of this problem are are only the goals g0, . . . , gm-1, and the corresponding heuristic estimate is weak. The hybrid ˆhmax hbd admissible heuristic [Scala et al., 2016a], on the other hand, does capture dependencies between numeric and propositional reachability, but since it assumes subgoal independence it will see only the single most costly goal. The intuition here is that even though the order of visits is not fixed, any plan solving the problem has to intersect the goal regions at some point. These are necessary metric conditions; in other words, landmarks. This paper shows how such numeric landmarks can be found and used in a much more informed admissible estimate.

2 Fundamentals and Previous Work

This paper focuses on numeric planning problems, which extend propositional planning with numeric state variables. Numeric variables can appear in conditions ξ ⊵ k where ξ is an arithmetic expression, ⊵ ∈ {≤,<,=,>,≥} and k is a constant. In the fragment we consider, action preconditions and goals are conjunctions of numeric conditions and/or propositions, ξ is linear, and actions can assign boolean variables and/or increase/decrease the value of numeric variables by a constant factor. Conflicting assignments are not allowed. The semantics of numeric planning can be defined in terms of a state transition system following PDDL 2.1 level 2 [Fox and Long, 2003]. We adopt the set-theoretic representation [Ghallab et al., 2004].

Given a set of boolean (F) and numeric variables (X), a numeric planning problem consists in finding an action sequence 〈a0, ..., an-1〉 which, starting from an initial assignment to all variables (the initial state s0), brings the system to a state (sn) satisfying given goal conditions G (i.e., sn |= G). Each action has to be applicable in the state resulting from the plan prefix executed before it. Each action ai has a cost c(ai) ∈ ℜ≥0 and the cost of a plan π = 〈a0, ..., an-1〉 is ∑0≤i<|π∗ | c(ai); the objective is to minimize cost.

2.1 Landmarks

Propositional landmarks [Hoffmann et al., 2004] are propositions that need to be true at some point in any plan solving the problem, whereas action landmarks are the actions whose execution is necessary to achieve the goal: any plan solving the problem has to contain them.

A sound and complete algorithm to find landmarks is not tractable [Hoffmann et al., 2004]; therefore previous methods extract landmarks using a relaxed version of the problem. Intuitively, tighter relaxations bring more landmarks, but are expensive to compute. Looser relaxations are cheaper but bring limited information, resulting in fewer landmarks [Keyder et al., 2010]. This generates an obvious trade-off highlighting the importance of choosing the right relaxation.

2.2 Possible Achievers for Simple Numeric Conditions

Simple numeric conditions are linear numeric inequalities affected by only constant increase/decrease actions. 1 For this reason, they match the numeric planning fragment we are interested in. As shown by Scala et al. [2016a], possible achievers of simple numeric conditions can be obtained using a parametric regression operation:

1 Note that effects can be considered constant if their state dependent nature is ignored. Although possible and computationally feasible, this can make relaxation-based heuristics highly inadmissible in general [Scala et al., 2016a].

Definition 1. Let c = (∑x∈X wx,cx) + wn,c ⊵ 0, with ⊵ ∈ {≤,<,>,≥}, be a simple numberic condition. The m-times regression cr(a,m) of c through action a is:

where kx,a is the constant additive effect of a on x.

We say that a is a possible achiever of c in a state s if there exists an m such that s |= cr(a,m) . All the other elements of (1) are coefficients extracted from the action model [Scala et al., 2016a]. In the simple numeric condition case, possible achievers can be detected statically by looking at the relational operator (▷), the action coefficients and the targeted condition. This results from the regression being linear in time, and hence, having a constant derivative. Yet, the number m of repetitions needed to achieve the condition is a statedependent information.

In the numeric h1 's family of heuristics [Scala et al., 2016a], possible achievers over-approximate reachable numeric conditions, and have been used to restrict regression towards the actual relevant actions. This induces a computable relaxation of the problem. These possible achievers represent necessary but not sufficient conditions to achieve a numeric condition; a possible achiever ignores negative effects on other conditions that might be necessary to achieve - though it still captures interesting internal conflicting effects for multivariables inequalities. Interestingly, as for the propositional case, possible achievers are also a necessary (though not sufficient) condition for an action to be considered a landmark for the problem. Next section defines numeric landmarks; then we show how to compute and use them.

We use the term numeric achiever (NA) for an action that is a possible achiever of a numeric condition and propositional achiever (PA) when it sets to true the value of a boolean variable. An action can be both an NA of a (numeric) condition, and a PA of another (propositional) condition.

3 Numeric Landmarks and Hybrid Action Landmarks

A numeric landmark resembles a propositional landmark, yet it extends its interpretation to the numeric case.

Definition 2 (Numeric Landmark). A numeric condition c : ξ ⊵ k is said to be a numeric landmark if any plan solving the problem induces a trajectory of states S such that ∃s ∈ S such that s |= c.

A numeric landmark can be geometrically understood as defining a region in the metric space that the plan trajectory has to hit at some step of the execution. Goals and initial state atoms are landmarks by definition.

An action that must be present in any plan is called an action landmark. We call these hybrid (action) landmarks, since they may be justified by both propositional or numeric landmarks. A landmark is called causal if it belongs to the precondition of some hybrid action landmark or to the goal set.

Numeric planning is more expressive than propositional planning. For this reason, a complete numeric and hybrid action landmark discovery procedure is not tractable. To overcome this problem, we approximate the landmarks set using the landmarks of the underlying subgoaling relaxation given by hmax hbd , and defined by Scala et al. [2016a]. The intuition is that landmarks can be seen as necessary subgoals. Let s and G be our initial state and goal condition, respectively, a condition c (either numerical or propositional) is a landmark if at least one of the following holds: i) c is in the initial state, ii) c is a goal iii) the removal of any action preconditioned on c makes hmax hbd (s,G) =∞.

To compute landmarks we propose a hybridized AND/OR Landmark formulation [Keyder et al., 2010]; then we show how the extracted landmarks can be used to infer what we call disjunctive and additive hybrid action landmarks.

4 AND/ORGraph for numeric planning

An AND/OR Graph is a directed graph whose vertices are partitioned into AND nodes (Vand) and OR nodes (Vor), with edges only between AND and OR nodes or vice-versa.

In planning, AND/OR graphs have been used to compactly represent relaxed state spaces [Keyder et al., 2010]: Vand contains a node for each action (including a dummy initial action having empty preconditions and the initial state as its effect), and Vor contains a node for each proposition. There is an edge (a, b) if either a represents an action achieving proposition b, or if a is a proposition appearing in the precondition of action b. The AND/OR graph constructed this way nicely captures the semantics of the delete-free relaxation.

The extension to numeric planning is straightforward. Vor is extended with a node for each numeric condition that appears in problem; Vand is unchanged. Given an action a and a numeric condition b, there is an edge (a, b) if a is a possible achiever (NA) of b, as defined above. There is an edge (b, a) if the precondition of a contains b. In this case, edges can represent not only the single execution of an action, to achieve a propositional condition, but also the repeated execution necessary to achieve a numeric condition, as captured by the closed form of Eq. 1. The resulting encoding has only a single copy of each relevant action, also for the numeric part. This interpretation allows us to focus on the qualitative implications that the numeric structure has on reachability, so that, similarly to the propositional case, we can avoid the explicit layering of relaxed states in a traditional planning graphlike formulation [Hoffmann, 2003; Gerevini et al., 2008; Coles et al., 2010; Coles and Coles, 2011]. Most importantly, it enables the (almost) off-the-shelf use of Keyder et al.'s landmark discovery procedure for the intertwined inference of propositional and numeric landmarks.

4.1 Landmarks Extraction

Landmarks for the relaxed problem are those OR nodes of the associated AND/OR graph that lie on the intersection of all possible justifications, or paths to the goal nodes. This can be tackled using the following recurrence relation [Keyder et al., 2010] 2 :

2 Note here we use a slightly different formulation where the explicit initial state is substituted by a dummy action. The recurrence reaches a base case when the initial dummy action is selected.

The set of propositional and numeric landmarks is given by: LM(G) = ⋃v∈G LM(v). The intent of the intersection in the first line of Eq. 2, is to infer the strongest implicant of the landmarks of each of achievers (PAs or NAs) of a condition, i.e., a set of conditions that are implied by each of the sets of conditions LM(v′ ). In the propositional case this operation corresponds to intersecting these sets. Taking the intersection, treating numeric conditions as syntactic atoms, is valid also in the hybrid AND/OR graph. However, a stronger implicant can be found by examining the metric structure of the conditions. We consider numeric conditions pairwise: comparing two numeric conditions c1 and c2, if one implies the other, that is, if s |= c1 ⇒ s |= c2 holds for every state s, then the weaker (implied) condition, c2, is clearly the strongest implicant of the two.

This dominance relation can be checked syntactically. If the coefficient vectors of the two conditions are linearly dependent (that is, one can be obtained by scaling the other), then c1 implies c2 if and only if after scaling the right-hand side of c1 is greater than that of c2 in the direction of the inequality. For example, consider the two sets of conditions {(y > 5)} and {(2y > 9)}. Since they are syntactically different, set intersection yields the empty set. However, since y > 5 is equivalent to 2y > 10 it implies 2y > 9, so the implicant is the weaker condition (2y > 9).

In the general case, the strongest implicant of two sets of linear inequalities that is also a set of linear inequalities is the convex hull of the regions in the metric space defined by the disjuncts [Balas, 1998]. This characterization could potentially allow us to infer more landmarks, though at the cost of increased computational complexity. Our current implementation is therefore limited considering single conditions pairwise, as explained above. We leave the study of the more complex forms of reasoning, and its computational complexity implications, as a future work.

The union of numeric condition sets can also be refined analogously, leaving in this case only the stricter numeric condition. While this does not affect the information extracted, it may remove redundant numeric conditions.

The combined propositional and numeric landmark discovery enjoys three important properties studied by Keyder et al. [2010] in the propositional case: the system of equations LM(·) admits only one maximal solution (with respect to set inclusion); the resulting landmarks set contains all the causal landmarks w.r.t. the subgoaling relaxation; all the landmarks are sound. The first two follow from the relationship between actions and numeric conditions being captured symbolically in the AND/OR graph construction. Thus, Keyder's et al. Theorem 1 still applies. Soundness follows from the fact that edges have relaxed any negative effect between conditions, thus all the landmarks found using the procedure are also landmarks for the non-relaxed problem. Of course, there may be landmarks in the problem that are not landmarks of the relaxation, and thus not identified by the procedure. This is way more complicated in the numeric case, since the number of conditions that can be expressed on the problem is infinite. Note here that we not only find all the causal landmarks for the relaxation, but because the intersection is sensitive to the metric structure of the problem, we can approximate some disjunctive landmark as well.

The existence of a unique maximal solution guarantees computability of the recurrence relation via a polynomial label-correcting algorithm. Yet the computation, although polynomial in the number of conditions, can be expensive, despite the use of efficient data-structures and looking only at those actions that are relaxed reachable. We will study its impact experimentally.

4.2 Orderings

As by-product of this novel AND/OR graph interpretation and Eq. 2, orderings among landmarks can also be extracted. A natural order ≺n between two landmarks c0, c1, (c0 ≺n c1) establishes that any valid plan needs to satisfy c0 first, and then c1. This can be inferred looking at whether c0 ∈ LM(c1). Other classic forms of orderings seem however more difficult to characterize in the numeric setting and probably require a more profound re-interpretation. At the moment we can also support greedy necessary ordering ≺gn (as defined by Keyder et al. [2010]), under the assumption that, given c0 ≺gn c1, c0 is a propositional landmark.

The validity of such ordering relationships is preserved by construction, since, although these conditions have a different semantics, the kind of reasoning performed at this level is, again, completely qualitative. Figure 1 shows an example of numeric landmarks and natural orderings inferred in the GARDENING domain [Franc`es and Geffner, 2015].

5 Disjunctive/Additive Hybrid Landmarks

Quantitative information can also be captured from the AND/OR graph. It is in fact sufficient to store for each possible way of achieving a condition, information regarding the number of times actions need to be repeated in order to achieve such a condition (i.e., using Eq. 1). This quantitative information can be used to obtain an admissible estimate by minimising over the number of repetitions needed for all the NAs/PAs. To account for this optimisation problem systematically we propose a generalised form of cost partitioning by Karpas and Domshlak [2009] that considers numeric and propositional conditions altogether. The formulation contains a linear constraint for each numeric and propositional landmark found and minimizes the cost.

In particular: let O be the set of reachable actions (according to the relaxation), we denote with O(c) the subset of O containing the NAs for a numeric condition c, and O(p) the set of PAs for a propositional condition p. Given a ∈ O(c) with λ(a, c) we define the contribution of an action a to achieve a condition c, and with γ(a) its cost. With t(c) we define the target value for a condition c. In the propositional case the contribution of each action as well as the target value is 1. For the numeric case the contribution and the target value can be computed in closed-form on a perstate basis by manipulating Eq. 1. For the ≥ and > case 3 λ(a, c) = ∑x∈X wx,ckx,a (kx,a is the result of the additive effects of a onto c and wx,c represents the weight of the action on the numeric condition) ; t(c) = -(∑x∈X wx,cx + wn,c) (this captures what is missing to satisfy condition c). Note that both λ(a, c) and t(c) are to be evaluated on the state.

For each action we introduce a counting variable Y (a). Each O(p/c) is de facto a disjunctive/additive hybrid landmark. In the propositional case this disjunction implies the existence of at least one of these actions in any plan solving the problem. In the numeric case the equation is a weighted summation of variables that needs to satisfy a given bound. Each plan has to contain actions such that the resulting constraint is satisfied. This is effectively an additive hybrid landmark. Note that an additive hybrid landmark captures actions repeatable an arbitrary number of times, so directly exploiting numeric structural properties of the problem. These hybrid landmarks can be encoded in an integer linear problem, from which we take its continuous relaxation 4 :

The result of this optimisation problem is our landmarkbased heuristic: hlm hbd , where the subscript stands for HyBriD.

Theorem 1. If LM(G) contains only sound landmarks, the optimal cost induced by Eq. 3 gives us an admissible estimate, i.e., hlm hbd (s) ≤ h∗ (s)

Proof Sketch. Easy by contradiction; assume the cost produced by the linear program was overestimating the real cost; this implies at least one constraint requiring some unnecessary action. However, this contradicts either the formulation of NAs/PAs or the soundness of the landmarks, or both.

3≤ and < can be reduced to ≥ and >, respectively, by a simple mathematical manipulation.

4 The continuous relaxation (LP) of a MIP has polynomial worstcase complexity, while its integral counter-part is NP-hard. The LP cost lower bounds the integer solution cost.

The resulting heuristic is both polynomial (inferring the landmark plus solving the Linear Program), and because admissible it also is safe-pruning: i.e., it gives infinity values only for actually unsolvable problems. Its computational cost trivially derives from Keyder et al.' procedure [2010].

6 GettingMore Landmarks

Numeric planning makes explicit structural and metric properties of the search space. Such information is crucial not only to infer repeated action applications within the heuristic, but also to constrain the solutions space by adopting redundant constraints. Redundant constraints have been used in scheduling [Getoor et al., 1997], but also in planning [Scala et al., 2016a] to tighten the relaxation. It is known that tighter relaxations lead to more landmarks [Keyder et al., 2014], therefore our research question is: can we obtain more landmarks using redundant constraints? How useful is that?

Consider two numeric goals c1 : x ≥ 10 and c2 : y ≥ 10, an initial state 〈x = 0, y = 0〉 and three unit cost actions a : 〈∅, {x+= 5, y-= 5}〉, b : 〈∅, {x+= 1}〉 c : 〈∅, {y+= 1}〉. This formulation generates two additive hybrid landmarks: 5Y (a) + Y (b) ≥ 10 and Y (c) ≥ 10. The estimated cost is 12, given by executing c 10 times, and a twice.

For the purpose of studying the impact of redundant landmarks we adopt the same technique presented in Scala et al. [2016a]. For each set of conditions S (action precondition and goal), we augment S with a number of redundant constraints obtained looking at some of the necessary condition for the satisfaction of each pair of numeric conditions in S. Given c0 : ξ ▷ k and c1 : ξ ′ ▷′ k′ the redundant numeric condition added is red(c0, c1) : ξ + ξ ′weaker(▷,▷′ )k + k′ . The weaker operator intuitively selects the less strict comparator.

In our previous example the generated redundant constraint is x + y ≥ 20 and requires the additive hybrid landmark Y (b) + Y (c) ≥ 20: the overall estimate here is 20.

Redundant constraints approximate conjunctive landmarks in a very interesting way whilst preserving admissibility. This however comes at a price in our landmark inference and our LP heuristic, since they both have polynomial worst case complexity in the number of conditions. We study their benefit experimentally; the resulting heuristic is hlm+ hbd .

Theorem 2. hlm hbd (s) with redundant constraints is potentially more informative, whilst still admissible

7 Experiments

Our experimental evaluation compares the landmark heuristics with the hybrid ˆhrmax hbd heuristic [Scala et al., 2016a], which is, to our knowledge, the only existing admissible heuristic for cost-optimal numeric planning.

We apply the heuristics in a standard forward state space planner using A∗ , so as to minimise any noise in the evaluation. The cost-partitioning problem is solved with CPLEX 12.63. Ties are broken preferring higher g-values. All heuristics are computed on a per-state basis. 5

5 The implementation is part of the ENHSP planning sys-

The evaluation is done over four numeric, non-temporal domains that have featured in the International Planning Competition 6 , the SAILING and FARMLAND domains from our earlier paper [Scala et al., 2016a], and the COUNTERS and GARDENING domains by Frances & Geffner [2015].

COUNTERS is a very simple numeric domain with N numeric variables (X1,X2, ...,XN) that have to be set to a specific configuration (X1 < X2∧X2 < X3∧...∧XN-1 < XN ) through unit increase and decrease actions. Instances scale with N (from 2 to 40), and are split in three groups, with the initial values all 0, ordered inversely to the goal, or random. GARDENING models an agent that has to water a number N of plants located in a M ×M grid, can carry a limited amount of water, and can be refill at a specific location. Moving, watering and refilling actions have only numeric effects. Instances scale in the number of plants (from 1 to 3) and grid size (4 to 10).

SAILING models N boats navigating in an unbounded 2-D space which must reach and rescue M persons scattered in the sea. To rescue a person, a boat must be inside a region defined by a set of inequalities. Instances scale with N and M (both from 1 to 5). FARMLAND models the problem of allocating manpower to farms whilst preserving a hard constraint on a metric measuring benefit. Each farm contributes differently to the overall metric. Instances scale with the number of farms (from 2 to 6), and workers at disposal (from 100 to 1000).

Table 1 shows a summary of the results. We make the following general observations: In almost all domains, hlm hbd and hlm+ hbd require fewer node expansions than ˆhrmax hbd (we discuss one exception in detail in the next subsection). Where the reduction is substantial, this also translates into improved runtime or coverage. In the domains where using redundant constraints generates more landmarks, hlm+ hbd also expands fewer nodes than hlm hbd . Among the IPC domains, ZENO TRAVEL is only one in which an action precondition (or goal) contains more than one numeric condition, and therefore the only one in which a redundant constraint is generated. However, in this domain it does not lead to more landmarks being found, and there is a runtime overhead.

We also tried disabling dominance testing in the intersection of numeric conditions, as described in the section on landmark extraction. This configuration is faster (both landmark heuristics solve one more instance in DEPOT) and finds slightly fewer landmarks only in ZENO TRAVEL.

In-Depth: SAILING. The SAILING domain highlights a significant difference between the landmark-based heuristics and ˆhrmax hbd . As we scale up the number of goals (persons to be rescued) with a single boat, the landmark heuristics, which add up actions needed to reach the precondition area of each rescue action, remains informative, while ˆhrmax hbd , which considers only the single most expensive goal requires much more search. However, when the number of boats becomes greater than one, each goal has multiple achievers (boats) with disjoint preconditions, so that the landmark heuristics reduce to simply counting unsatisfied goals.

tem, open sourced at https://bitbucket.org/enricode/ the-enhsp-planner. Experiments have run on a Xeon E52660 V3 with 8G of RAM.

6 See http://www.icaps-conference.org/index. php/Main/Competitions for information on these domains.

To show this, Table 1 separates results for subsets SAILING instances that scale in different ways. We also created additional instances with a single boat and more goals (up to 20). Figure 2 shows planner run-times with the three heuristics, as well the number of landmarks found, on this instance set only. With redundant constraints, the run-time increases nearly linearly with the number of goals.

In-Depth: COUNTERS. The COUNTERS instances used by Frances & Geffner [2015] scale up very rapidly, having 2, 4, 8, 12, 20, and 24 counters. This set is intended for evaluating satisficing planners, and does not reveal meaningful results for optimal planning (as can be seen in Table 1 only a few problems are solved with any heuristic). We created additional instances, increasing problem size (number of counters) by steps of one from 2 up to 9, which is the smallest that no configuration solves. Table 2 shows results on this set. The landmark heuristic values without redundant constraints equate to h+. Redundant constraints tighten the underlying relaxation enabling more landmarks to be found, and thus the heuristic value increases faster with problem size, though not as fast as the optimal plan length, which grows quadratically.

8 Conclusion

Landmarks have proven very useful in propositional planning, and recently the notion has also been applied to temporal propositional [Karpas et al., 2015] and HTN [Elkawkagy et al., 2012] planning. However, over a decade since first introduced in classical planning [Hoffmann et al., 2004], this paper is the first to explain how landmarks and landmark extraction mechanisms can be developed for planning with both propositional and numeric variables.

We have applied our proposal to cost-optimal numeric planning, yet the presented mechanisms can be beneficial in other forms of intertwined numeric and propositional reasoning as well. Landmarks allow automatic identification of problem decompositions, as well as inducing (in)admissible heuristics. We believe this extension allows similar, perhaps even more powerful mechanisms. Numeric planning in fact makes explicit structural, metric information about the problem that is difficult to capture in a purely propositional representation. As future work we plan to improve landmark extraction with stronger reasoning about the disjunction of sets of numeric conditions, and extend the characterisation to support autonomous processes and temporal landmarks together.

Acknowledgements

This work is supported by ARC project DP140104219, "Robust AI Planning for Hybrid Systems". The Australian Research Council through the ICT Centre of Excellence Program. We thank Da An for help in the implementation, and the anonymous reviewers for their useful comments.