Taming Discretised PDDL+ through Multiple Discretisations

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-06 21:51:20

Abstract: The PDDL+ formalism allows the use of planning techniques in applications that require the ability to perform hybrid discrete-continuous reasoning. PDDL+ problems are notoriously challenging to tackle, and to reason upon them a well-established approach is discretisation. Existing systems rely on a single discretisation delta or, at most, two: a simulation delta to model the dynamics of the environment, and a planning delta, that is used to specify when decisions can be taken. However, there exist cases where this rigid schema is not ideal, for instance when agents with very different speeds need to cooperate or interact in a shared environment, and a more flexible approach that can accommodate more deltas is necessary.  To address the needs of this class of hybrid planning problems, in this paper we introduce a reformulation approach that allows the encapsulation of different levels of discretisation in PDDL+ models, hence allowing any domain-independent planning engine to reap the benefits. Further, we provide the community with a new set of benchmarks that highlights the limits of fixed discretisation.

Main paper: 
 introduction 20: 
 The ability to represent hybrid discrete-continuous changes is crucial to exploit automated planning techniques in realworld applications. The PDDL+ language has been introduced and designed to support a compact encoding of models involving hybrid changes, via the use of specialised constructs such as events and processes (Fox and Long 2006) .Hybrid PDDL+ problems are notoriously challenging to tackle, due to the intertwined nature of numeric variables and time. A well-established approach to reason upon hybrid PDDL+ problems is discretisation (Della Penna, Magazzeni, and Mercorio 2012; Percassi, Scala, and Vallati 2023b) , which allows breaking down complexity by assuming the time is discrete, and so are the actual numeric changes. A similar assumption is also made in the simpler context of temporal planning through durative actions (Dvorak et al. 2014; Rintanen 2015; Cushing et al. 2007 ). An important aspect of this approach is the ability to re-use well-established and general search techniques based on forward state-based exploration to tackle PDDL+ problems; it is indeed widely exploited by existing domain-independent planning engines such as DINO (Piotrowski et al. 2016) , UPMURPHI (Della Penna, Magazzeni, and Mercorio 2012) and ENHSP (Scala et al. 2016) . The first two solvers rely on only one discretisation step for both simulation (process and events) and decision (actions) , while ENHSP utilises a more advanced approach that can support two deltas: a (usually smaller) simulation delta to approximate complex dynamics and a (usually larger) planning delta to reduce the burden on planning by avoiding unnecessary decision points.Notably, there can be cases where even the advanced technique of using two different discretisation deltas does not allow to efficiently reason upon the dynamics of the problem at hand. In the logistics context, for example, it is common to have a range of means of transport, each having a different speed and a different granularity of timings in which actions must be performed (e.g. a plane is faster than a truck which is faster than a delivery man) and if the different agents involved have to coordinate, they must necessarily do it at the discretisation step of the slower one, making the solving unnecessarily challenging. Even the same agent could benefit from different granularity in different moments of the plan: for example, a ship must be finely controlled while manoeuvring in the harbour, but its course can be sporadically altered while at open sea. To effectively address the described class of hybrid problems, approaches capable of supporting even more than two discretisation deltas are needed.In this work, we address this need by introducing a reformulation approach that encapsulates such multiple deltas straight into the PDDL+ models, hence allowing domain-independent planning engines to exploit the benefits. More precisely, we formally define the dynamic planning-discretised PDDL+ problem, and introduce a sound and complete compilation allowing one to generate a corresponding PDDL+ model that encodes the notion of multiple deltas. Any planning engine that supports PDDL+ can reason upon the reformulated models, thus extending the ability of existing systems to solve challenging hybrid problems. Further, we present an innovative PDDL+ benchmark domain, based on a realistic example, that stresses the need for reasoning with multiple deltas. Our extensive empirical analysis demonstrates the merits of the introduced reformulation on a range of PDDL+ benchmarks and planning approaches. The PDDL+ formalism is the most expressive formalism of the PDDL family of languages, that also includes PDDL (McDermott et al. 1998 ) and PDDL2.1 (Fox and Long 2003) . The modelling capabilities of PDDL+ have enabled the use of automated planning to solve complex realworld problems such as traffic control (Vallati et al. 2016) , safety requirements for cyber-physical systems (Aineto et al. 90 2023), train dispatching (Cardellini et al. 2021) , unmanned aerial vehicle control (Kiam et al. 2020) , pharmacokinetic optimisation (Alaboud and Coles 2019) , and popular video games (Piotrowski et al. 2023) . Due to its expressive power, finding solutions for PDDL+ problems remains a daunting 95 challenge. This is further compounded by the scarcity of planners capable of effectively handling PDDL+ problems.Existing solvers deal with the continuous nature of Ordinary Differential Equations (ODEs) in two ways: either by (i) solving the underlying integral, or (ii) by discretising the 100 time horizon and treating the ODEs as discrete sums. In the first category, solvers like SMTPLAN+ (Cashmore, Magazzeni, and Zehtabi 2020) and dReal (Bryce et al. 2015 ) make use of SMT techniques and mathematical solvers to solve the integrals. Due to the mathematical complexity of these operations, both planners apply restrictions to the possible set of functions which can be expressed in the ODEs. To the second category, instead, belongs planners like UPMUR-PHI (Della Penna, Magazzeni, and Mercorio 2012) , DiNo (Piotrowski et al. 2016) and ENHSP (Scala et al. 2016) 110 which make use of the Discretise & Validate approach (Della Penna, Magazzeni, and Mercorio 2012), allowing them to deal with a larger set of ODEs functions but being dependant of the discretisation step for the validation of the plan.Both DiNo and UpMurphi consider a single delta, that is used for both simulating the evolution of the dynamic environment and for identifying decision points for planning.A more advanced approach, presented by (Ramirez et al. 2017 ) and supported by ENHSP, is to consider two different deltas: a simulation delta, to be as small as possible to better approximate complex hybrid dynamics, and a planning delta, that can be discretionally large, to reduce the burden on the planning process by avoiding decision points when no actions are likely to be applicable. An approach similar in nature, but domain-specific, has been proposed for the Train Dispatching Problem (Cardellini et al. 2021) , where the ENHSP planner has been modified to skip irrelevant decisions points when controlling the dispatching of trains.In this section, we present a novel domain, COOPROVERS, in which two agents operate at different speeds and need to coordinate to reach the stated goals. Figure 1 provides an example of an initial state (left) and a goal condition (right) in which two rovers (Red and Green) are performing two experiments (A and B) in two separate locations and need to exchange a tool. For safety reasons, the rovers are only allowed to move from the base camp to their working zone, and hence they can only meet at the base camp to exchange the mentioned tool. The two rovers are equipped with a battery and solar panels that allow them to recharge. Since the location of the Experiment B is α times more distant from the base camp than that of Experiment A, the Green rover has been equipped with a lighter, more efficient battery (discharges at 20 α %/m), consuming less than the Red rover (20%/m) and allowing longer trips. At any point, while moving between the locations, the rovers can deploy their solar panels and recharge (at the speed of 1%/s) for some time before restarting their trip. The battery must always stay above 20% to allow emergency operations and the deployment of solar panels. The rovers are also equipped with a holding container for transporting tools. The speed of the two rovers is the same (1m/s) but, given the differences in distances to be covered and discharging rates, their movements should be modelled and controlled with different granularities. For example, with α = 100, the Green rover would need to move 1.2 km at a velocity of 1 m/s, discharging at 0.2%/m. In this case, it is easy to notice that the Green robot would benefit more from a discretisation step one hundred times larger than the Red robot.A PDDL+ planning problem, denoted by Π, is a tuple ⟨F, X, I, G, A, E, P ⟩, where F is a set of Boolean variables and X is a set of numeric variables taking values from {⊤, ⊥} and Q, respectively. These variables can be used in propositional formulas with numeric and Boolean conditions. Numeric conditions are of the form ⟨ξ ▷◁ 0⟩, where ξ is a numeric expression over X and Q, and ▷◁∈ {≤, <, = , >, ≥}. Boolean conditions are of the form ⟨f = b⟩ with f ∈ F and b ∈ {⊤, ⊥}. A formula is therefore a propositional formula using standard connectives from logic involving numeric and Boolean conditions. I is the description of the initial state, expressed as a full assignment to all variables in X and F . G is the description of the goal, expressed as a formula. A and E are the sets of actions and events, respectively. An action or event is a pair ⟨p, e⟩, where p is a formula and e is a set of Boolean or numeric effects. A Boolean assignment has the form ⟨f := b⟩, where f ∈ F and b ∈ {⊥, ⊤}. A numeric assignment has the form ⟨op, x, ξ⟩, where op ∈ {asgn, inc, dec}, x ∈ X, and ξ is a numeric expression over X and Q. Specifically, op can be the contraction of the keywords assign (x := ξ), increase (x := x + ξ) and decrease (x := xξ). P is a set of processes and a process is a pair ⟨p, e ′ ⟩, where p is a formula and e ′ is a set of continuous numeric effects expressed as pairs ⟨x, ξ⟩, where x ∈ X and ξ is a numeric expression defined as above. ξ represents the additive contribution to the first derivative of x as time flows continuously. In the discrete context, ξ is the additive contribution to the discrete change of x. Let a = ⟨p, e⟩ be an action, event, or process, we use pre(a) to refer to the precondition p of a, and eff(a)to the effect e of a. In the following, we will use a, ρ, and ε to refer to a generic action, process, and event, respectively.A PDDL+ plan π t is a pair ⟨π, t e ⟩, where π = ⟨⟨a 1 , t 1 ⟩, ..., ⟨a n , t n ⟩⟩ is a sequence of timestamped actions and t e ∈ Q ≥0 is the makespan within the plan π is executed.A state s is a full assignment of the variables X ∪ F . An action a (event ε) is applicable (is triggered) in a state s iff s |= pre(a) (s |= pre(ε)). For describing how a state changes when an action (event) is executed (triggered) we use the transition function γ(s, z). Given a state s and an action/event z ∈ A ∪ E, γ(s, z) denotes the state resulting from the application of a in s accordingly to the effect eff(z). The difference between actions and events is that the former prescribe may transitions under the control of the agent and can be executed if the current state meets the preconditions, while the latter prescribe must transitions, i.e., events are triggered immediately if their preconditions are met.Following some early works (Shin and Davis 2005; Percassi, Scala, and Vallati 2023b) , we formalise the PDDL+ discrete semantics through the notion of time points, histories and plan projections. Given a discretisation step δ ∈ Q >0 , a time point, denoted by T , is a pair ⟨t = δ • n, n ′ ⟩, where n, n ′ ∈ N; t denotes the clock of T while n ′ is the counter used to order actions and events happening at t. Time points are ordered lexicographically. A history H over a sequence of time point T H maps each element from T H into a situation. A situation at time point T is the tuple H(T ) = ⟨H A (T ), H s (T )⟩, where H A (T ) is the action executed at time point T (if any) and H s (T ) is the state associated with T . We denote by H s (T ) [v] and H s (T )[ξ] the value assumed by v ∈ F ∪ X and by a numeric expression ξ, respectively, in state H s (T ). E trigg (T ) indicates the sequence of events triggered in T . 1The validity of plans relies on defining the discrete PDDL+ plan projection, which describes how π t is projected onto a history, taking into account the effects of actions and changes yielded by events and processes. This projection is constructed through two types of transitions: instantaneous and temporal. Instantaneous transitions originate from the execution (triggering) of actions (events), whereas tempo-230 ral transitions result from the passage of a discrete quantum of time. Each transition is associated with a starting time point and one linked to the resulting state after the transition. These time points are referred to as significant (STPs).Intuitively, we define the plan projection based on a set 235 of rules that describe how history progresses over time. The first rule (R1) states that if an event is triggered at a specific time point, a successor state must exist with the same clock time and an increased counter. The second rule (R2) states the same for actions. The third and fourth rules (R3-240 R4) are used to ensure that the actions in a PDDL+ plan are projected, preserving their original ordering. The fifth rule (R5) is used to describe how numeric variables change over time in a discrete fashion when time advances by a discrete quantity. Notably, continuous numeric changes are discre-245 tised according to the formula ∆(ξ, δ) = δ • ξ. Definition 1 (Discrete PDDL+ Plan Projection). Let Π be a PDDL+ problem, δ ∈ Q >0 a discretisation step, H an history and π t = ⟨π, t e ⟩ a plan for Π. We say that H is a discrete projection of π t which starts in I iff H induces the STPs 250 T H = ⟨T 0 = ⟨t 0 = 0, 0⟩, ..., T m = ⟨t m = t e , n m ⟩⟩, where either t i+1 = t i + δ or t i+1 = t i , H s (T 0 ) = I and, for all i ∈ {0, ..., m}, the following rules hold:R1 [Instantaneous Transition (events)] E trigg (T i ) ̸ = ⟨⟩ iff H s (T i+1 ) = γ(H s (T i ), E trigg (T i )), H A (T i ) = ⟨⟩, 255 t i+1 = t i and n i+1 = n i + 1; R2 [Instantaneous Transition (actions)] H A (T i ) ̸ = ⟨⟩ iff H s (T i+1 ) = γ(H s (T i ), H A (T i )), E trigg (T i ) = ⟨⟩, t i+1 = t i and n i+1 = n i + 1; R3 [Action Projection] ⟨a i , t i ⟩ ∈ π iff it exists one and 260 only one T i = ⟨t ′ , n⟩ ∈ T H s.t H A (T i ) = ⟨a i ⟩ and t ′ = t i ; R4 [Actions Ordering]for each ⟨a i , t i ⟩, ⟨a j , t j ⟩ in π, with i < j and t i = t j there existsT k , T z in T H such that H A (T k ) = ⟨a i ⟩ and H A (T z ) = ⟨a j ⟩ and where t k = 265 t z = t i and n k < n z ; R5 [Temporal Transition] for each pair of contiguous STPs T i = ⟨t i , n i ⟩, T i+1 = ⟨t i+1 , n i+1 ⟩ such that t i+1 = t i + δ,we have that n i+1 = 0 and the value of each numeric variable x ∈ X is updated as:270 H s (T i+1 )[x] = H s (T i )[x] + ⟨x ′ ,ξ⟩∈eff(ρ), x ′ =x ρ∈P s.t. Hs(Ti)|=pre(ρ) H s (T i )[∆(ξ, δ)]and values of unaffected variables remain unchanged (frame-axiom). Definition 2 (Valid PDDL+ plan under δ discretisation). π t is a valid plan for Π under δ discretisation iff H s (T m ) |= G and, for each T ∈ T H such that H A (T ) = ⟨a⟩, then 275 H s (T ) |= pre(a).We are now in the position to illustrate how to model 2 the COOPROVERS domain using PDDL+. The movement of a rover r from two connected locations a and b is managed through the triplet of action startMoving(r,a,b), process moving(r,a,b), and event endMovement(r,a,b). The moving(r,a,b) action is active only when the battery is above the threshold of 20% and keeps updating a variable dRun(r,a,b) whose role is to track the progress of the rover in going from a to b. During the movement, process discharge(r) models the draining of the battery, and does so with a rate of cRate(r). The planning engine can decide to interrupt and restart the movement through action startCharging(r) and action stopCharging(r), respectively. Between these two actions, the process charging(r) gets activated, and the rover battery charges with a rate of 1%/s. To collect and exchange tools, the actions drop(r,o) and pick(r,o) model the handling of the object o by rover r. In the initial condition, the robots are set in the configuration shown in Figure 1 (left). The goal is to reach a state where the tool has been brought to the location of Experiment B (Figure 1 (right)).To address the kind of hybrid problems that require the ability to deal with different dynamics, here we characterise the dynamic planning-discretised PDDL+ problem.A dynamic planning-discretised PDDL+ problem (shortened as PDDLδ+ problem) is the tuple ⟨Π, K δ = ⟨J, ∇⟩⟩, where Π is a PDDL+ problem defined as above and K δ is the discretisation knowledge detailed as follows. J is a function A ∪ E → {1, ..., m} which partitions the set of actions and events in m classes such that A = m j=1 A j and E = m i=j E j , whereA j = {a ∈ A | J(a) = j} and E j = {ε ∈ E | J(ε) = j}.The number of partitions induced by J defines the number of discretisation variables, i.e., δ m = {δ 1 , ..., δ m }, with each of them taking values in Q >0 . Intuitively, every δ j manages a different aspect of the problem by controlling when actions from A j can be executed. ∇ is the function which controls the dynamic of the discretisation steps, that is, how the δ m variables change according to the actions applied and the triggered events. Such a function maps every action and event into a positive rational number plus a special symbol κ, i.e., ∇ : A ∪ E → Q >0 ∪ {κ}; the special symbol κ is the persist value, and it represents that the affected discretisation variable remains unchanged when an action (event) z with ∇(z) = κ is applied (triggered). With a little abuse of notation, we allow the ∇ function to also accept the initial state as input and return a full assignment of δ m , i.e.,∇(I) = {⟨δ i := δ 0 i ⟩ | δ i ∈ δ m }.This allows us to initialise the discretisation variables in the initial state.A discretisation knowledge K δ may induce a nondeterministic behaviour w.r.t. events. In particular, it is known that events can generate non-determinism in PDDL+ problems (Fox and Long 2006) and this can also affect the discretisation variables δ m . That said, we define a discretisation knowledge K δ as event-deterministic iff for each state s, and for all ε, ε ′ ∈ E where J(ε) = J(ε ′ ) and s |= pre(ε) ∧ pre(ε ′ ), it holds that ∇(ε) = ∇(ε ′ ). In simpler terms, for any pair of events belonging to the same partition that can be triggered simultaneously, the ∇ function consistently prescribes the same discretisation value.Intuitively, solving a PDDLδ+ problem ⟨Π, K δ ⟩ consists 340 in finding a valid PDDL+ plan for Π such that every executed action is compatible with the discretisation steps prescribed by K δ .To formally define the semantics of PDDLδ+, we begin by introducing a new set of m memory variables denoted 345 as {M j = ⟨ tj , δ j ⟩ | j ∈ {1, ..., m}}. Each element in this set is a pair of positive rational numbers. Essentially, for a given partition j ∈ {1, ..., m}, the first component of M j , i.e., tj , represents the most recent timestamp at which an action (event) from A j (E j ) was executed (triggered). The 350 second component, i.e., δ j , indicates the latest discretization step assigned to partition j based on the ∇ function. The combination of these two elements determines all the following timestamps in which the actions from each partition are applicable.We now extend the definition of a history to keep track of the memory variables introduced so far. To be specific, given a history H, H K (T ) specifies a full assignment to the memory variables at time point T . We denote by H K (T )[M j ] the value assumed by M j = ⟨ tj , δ j ⟩ at T . In the plan pro-360 jection, for the first STP, such an assignment is equal toH K (T 0 ) = {⟨ tj = 0, δ j = δ 0 j ⟩ | j ∈ {1, ..., m}}. Furthermore, H K is updated whenever an action is executed or an event is triggered, while it persists when time flows. Whenever an action a from partition j (a ∈ A j ) is applied 365 at time t i (R2 applies), the variable tj is updated to t i to keep track of the most recent timestamp when an action from A j was executed. Simultaneously, the discretisation variable δ j is updated based on ∇(a): if ∇(a) is equal to κ (persist value), the current discretisation value is retained; otherwise, 370 it is modified. When an event ε from partition j (ε ∈ E j ) is triggered at time t i (R1 is applied), the variables tj and δ j are updated to t i and ∇(ε), respectively, only if ∇(ε) ̸ = κ. Otherwise, the current values of M j are retained. Definition 1 is extended by reshaping R1-R2, which are responsible for 375 handling actions and events. Definition 3 (Discrete PDDLδ+ Plan Projection). The discrete PDDLδ+ plan projection of plan π t is defined in the same way as a discrete PDDL+ plan projection, except for R1 and R2 which are extended as follows:380 R1 E trigg (T i ) ̸ = ⟨⟩ iff H s (T i+1 ) = γ(H s (T i ), E trigg (T i )), H A (T i ) = ⟨⟩, t i+1 = t i and n i+1 = n i + 1; furthermore, given ε in E trigg (T i ), H K (T i+1 )[M J(ε) ] = ⟨U T (ε), U D (ε)⟩; R2 H A (T i ) = ⟨a⟩ iff H s (T i+1 ) = γ(H s (T i ), H A (T i )), 385 E trigg (T i )) = ⟨⟩, t i+1 = t i and n i+1 = n i + 1; further- more, H K (T i+1 )[M J(a) ] = ⟨t i , U D (a)⟩.The functions used for updating H K (T i+1 ) are defined as: U T (z) = t i if ∇(z) ̸ = κ t last otherwise U D (z) = ∇(z) if ∇(z) ̸ = κ δ last otherwise m = 1 m > 1 ∇ is globally flat Unitary-Static Multiple-Static ∇ is not globally flat Unitary-Dynamic Multiple-Dynamic⟩ = H K (T i )[M J(z) ] and z ∈ A ∪ E.There is also the need to extend Definition 2 for the PDDLδ+ plan validity. In particular, a plan π t is valid for a PDDLδ+ problem ⟨Π, K δ ⟩ iff π t is valid for Π and every action of π t is executed in a time-stamp compatible with K δ . Definition 4. A PDDL+ plan π t is valid for a PDDLδ+ problem ⟨Π, K δ ⟩ iff π t is valid for Π and for each T = ⟨t, n⟩ ∈ T H such that H A (T ) = ⟨a⟩, there exists an s ∈ N such thatt = t last + s • δ last , where ⟨t last , δ last ⟩ = H K (T )[M J(a) ].Different levels of discretisation control can be achieved based on the definition of K δ , formalised as follows. In particular, we consider two dimensions: the number of partitions of A ∪ E induced by J, i.e., m, and the dynamic of ∇ for each partition. If m = 1, K δ induces a unitary PDDLδ+ problem while, if m > 1, a multiple one. If the function ∇(z) = κ for each z ∈ A j ∪ E j we say that ∇ is flat w.r.t. 405 the partition j, otherwise is not. When ∇ is flat for each partition (globally flat), we say that K δ induces a static PDDLδ+ problem, otherwise a dynamic one. Table 1 shows the different levels of discretisation control that can be achieved using the PDDLδ+ framework.Most of the PDDL+ discrete planning engines leverage a unique discretisation step δ e , both to model the granularity of the environmental changes and the agent's actions. Such a model can be expressed within the PDDLδ+ framework by a discretisation knowledge K δ in which the function J in-415 duces a single partition so that, J(z) = 1 for each z ∈ A∪E, there is a single discretisation step δ 1 = {δ 1 } that is initialised as {⟨δ 1 := δ e ⟩} and finally ∇(z) = κ for each z ∈ A ∪ E.ENHSP goes one step further in the direction of handling PDDL+ models with multiple discretisation steps. It separates the discretisation step for controlling the granularity of environmental changes δ e and the one for controlling the granularity of the agent's actions δ p . Such a model is useful when it is necessary to have a fine approximation of the envi-425 ronmental dynamics while the agent, being characterised by a slower dynamic, performs actions more sporadically. Such a model can be expressed within the PDDLδ+ framework by a K δ in which the function J induces a single partition so that, J(z) = 1 for each z ∈ A ∪ E, there is a single discretisation step δ 1 = {δ 1 } that is initialised as {⟨δ 1 := δ p ⟩} and finally ∇(z) = κ for each z ∈ A ∪ E.We have shown that the discretisation models currently supported by the PDDL+ discrete planning engines fall in the Unitary-Static level of our framework. All models outside this are not supported by existing PDDL+ reasoners.Motivating example (cont'd). We now show how the discretisation knowledge K δ can be expressed in the COOPROVERS domain. Intuitively, the actions and events can be partitioned by the rover which performs the action or is subject to the events. For example, J(startCharging(red)) and J(startMoving(red,expA,bc)) are set equal to 1 and J(startCharging(green)) and J(startMoving(green,expB,bc)) equal to 2. This partition induces the set δ 2 = {δ 1 , δ 2 }. The function ∇ is set to allow for (i) differentiating the various time scales of the two rovers when they are moving, and (ii) allowing for the same timescale when the two rovers are charging. For this reason, ∇(startMoving(red,expA,bc) (and the symmetric action for moving from bc to expA) is set to 3 while ∇(startMoving(green,expB,bc) (and symmetric) is set to 3α, allowing for (i). ∇(startCharging(red)) and ∇(startCharging(green)) are all set to 30, allowing for (ii). For all the other actions and events, ∇ returns κ. The initial condition sets the initial deltas to their respective delta of movements: ∇(I) = {⟨δ 1 := 3⟩, ⟨δ 2 := 3α⟩}. Since m = 2 and the ∇ function is not flat, the motivating example falls in the Multiple-Dynamic discretisation control level, i.e., the most general among the introduced levels.Let ⟨Π = ⟨F, X, I, G, A, E, P ⟩, K δ = ⟨J, ∇⟩⟩ be a PDDLδ+ problem. We introduce the FLAT translation, that produces an equivalent PDDL+ problem Π FLAT = ⟨F, X δ , I δ , G, A δ , E δ , P δ ⟩, whose components are presented in Figure 2 . Equation (1) augments the set of numeric predicates X with new fluents, producing X δ . The fluent ck represents the clock of the system, which keeps track of the flowing of time. Two fluents δ j and tk j are inserted for every partition induced by J: the fluent δ j keeps track of the value of the discretisation step of the actions of the partition j during the plan and tk j keeps track of the next time an action will be applicable in that partition (tk stands for tick). Equation (2) expands the initial state of the original problem with (i) the set given by ∇(I), which states the initial value of δ m , and (ii) the initialisation of the clock and all the ticks of the system to zero. Equation (3) redefines every original action a of Π, augmenting its precondition with a condition enforcing the action to be applicable only when the clock reaches the correct point, established by the value of tk J(a) ; here J(a) returns the index of the partition containing a. Both in Equation (3) and Equation (4), the effects set of an action or an event h is augmented with the set u(h), defined in Equation ( 5), in which (i) the value of δ J(h) is changed to its respective value defined by ∇(h) only if its value is different from the persist value κ, and (ii) the value of tk J(h) is reset to realign the ticks with the correct value of δ J(h) set by ∇(h) (this is because events are not constrained by the ticks). Equation ( 4) also adds n novel events tic j , defined in Equation ( 6), which represent the metronome of the system: the event tic j is fired when the value of the clock ck has just surpassed the value of tk j by the simulation delta ofEQUATIONI δ = I ∪ ∇(I) ∪ {⟨ck := 0⟩} ∪ m j=1 {⟨tkj := 0⟩} (2) A δ = a∈A {⟨pre(a) ∧ ⟨ck = tk J(a) ⟩, eff(a) ∪ u(a)⟩} (3) E δ = ε∈E {⟨pre(ε), eff (ε) ∪ u(ε)⟩} ∪ m j=1 {ticj} (4) u(h) = ∅ if ∇(h) = κ {⟨δ J(h) := ∇(h)⟩, ⟨tk J(h) := ck⟩} otherw.(5)EQUATIONFigure 2 : Components of the Π FLAT PDDL+ problem the planner δ e (i.e., we are in the falling edge) and, in the effects, it sets the timing (tk j ) in which the raising edge will happen again, taking into consideration the already passed simulation delta. Finally, in Equations ( 7) and ( 8), a new process t is added, whose job is to increase the value of the clock ck by the simulation delta δ e .It is worth noting that the FLAT translation yielding Π FLAT 500 is polynomial on the size of ⟨Π, K δ ⟩. Specifically, FLAT introduces 2m + 1 numerical variables (δ j , tk k for each j ∈ {1, ..., m} and ck), m events tic j , where m is the number of partitions of A ∪ E induced by J, and a single process, i.e., t. Additionally, the preconditions and effects 505 of actions/events are extended with at most 2 numeric conditions and effects. Also, it is easy to see that FLAT preserves the length of a plan exactly; as highlighted by (Nebel 2000) , this is a desired property when we talk about compilation from one planning problem into another.Theorem 1 (Soundness and Completeness of FLAT w.r.t. ⟨Π, K δ ⟩). Let ⟨Π, K δ ⟩ be a PDDLδ+ problem and let Π FLAT be the PDDL+ obtained by using FLAT. ⟨Π, K δ ⟩ admits a solution iff Π FLAT does so.Proof Sketch. (⇒) Let π t = ⟨π, t e ⟩ be a valid plan for 515 ⟨Π, K δ ⟩, and let π ′ t = ⟨π FLAT , t e ⟩ be the plan for Π FLAT constructed in such a way that: for each i-th time-stamped action ⟨a i , t i ⟩ in π, there exists an i-th time-stamped action ⟨a ′ i , t i ⟩ in π FLAT , where a ′ i ∈ A δ is the action a i ∈ A extended with the preconditions and effects introduced by FLAT.To prove that π ′ t is a valid plan for ⟨Π, K δ ⟩, we approach the proof modularly. Firstly, we note that the problem Π FLAT is an extended version of Π. Therefore, FLAT does not affect the original part of the problem and π ′ t achieves G. The important part to prove is that the actions generated 525 by the mapping above are applicable w.r.t. the novel variables. Let H and H ′ be the plan projections generated by π t and π ′ t , respectively. A key element is to prove that the discretisation variables δ m evolve in the same way in H and H ′ . It is worth noting that in the case of H, the assignments of δ m are explicitly kept within H, whereas in H ′ , they are variables that are part of the problem Π FLAT . Specifically, the δ m variables of H K change when an action (event) is applied (triggered) according to the updating rules R1-R2 of Definition 3, and remain unchanged in other cases. Similarly, the δ m ⊂ X δ variables of Π FLAT change whenever an action (event) from A δ (E δ ) is applied (triggered). Given the definitions of R1 and R2, along with the actions A δ and events E δ , it is evident that the δ m variables are synchronised across all STPs in both H and H ′ . Now, it remains to prove that the actions of π FLAT are applicable. Since FLAT does not affect F ∪ X of Π, the proof focuses only on the new variables {ck} ∪ n j=1 {δ j , tk j }. Additionally, it is important to note that for a given partition A j of A, each compiled action from A j only affects and is affected by tk j and δ j . Therefore, since the partitions of actions of A δ do not affect each other, we build the proof by examining a single partition and then generalise the result. So, for a given partition j, let T j K = ⟨T 1 , ..., T nj ⟩ (T j FLAT = ⟨T ′ 1 , ..., T ′ nj ⟩) be the sequence of STPs in H (H ′ ) associated with the application of the n j actions from the partition j. We prove by induction that the actions applied in T jFLAT are applicable. The case base (i = 1) trivially proves if t 1 = 0. If t 1 > 0, we leverage that, (i)I δ |= ⟨tk j = 0⟩ ∧ ⟨ck = 0⟩, (ii) H K (T 1 )[M j ] = H K (T 0 )[M j ] = ⟨0, δ 0 j ⟩ and then t 1 = s • δ 0 j and (iii) for each T ′ 0 ≤ T ′ ≤ T ′ 1 , H ′ s (T ′ )[δ j ] = δ 0 j .Combining these conditions, we obtain that in [0, t 1 ] the event tic j is triggered s = t 1 /δ 0 j times in the STPs T ′ = ⟨z • δ 0 j + δ e ⟩, where z ∈ {0, ..., s -1}. When z = s -1 and ck = (s -1) • δ 0 j + δ e , tic j sets tk j = ck + δ 0 j -δ e = s • δ 0 j . Such a value persists until t 1 is reached, so that H ′ s (T ′ 1 ) |= ⟨ck = tk j ⟩ |= pre(a ′ i ). For the induction step, we assume truly the statement for some 1 < i < n j and prove this for i + 1.If t i+1 = t i , it is easy to see that a ′ i+1 is applicable if a ′ i is too (in- ductive hypothesis). If t i+1 > t i , we leverage that, (i) H ′ s (T ′ i ) |= pre(a ′ i ) |= ⟨ck = tk i ⟩ (inductive hypothe- sis), (ii) H ′ K (T ′ i ) = ⟨t i , ∇(a i ) = δ i j ⟩ and (iii) for each T ′ i < T ′ ≤ T ′ i+1 , H ′ s (T ′ )[δ j ] = δ i j .Similarly to the case base, combining these conditions, we obtain that in[t i , t i+1 ] the event tic j is triggered s = (t i+1 -t i )/δ i j times in the STPs T ′ = ⟨t i +z •δ j +δ e , n ′ ⟩, where z ∈ {0, ..., s-1}, thus obtaining a state H ′ s (T i+1 ) |= ⟨ck = tk j ⟩ |= pre(a ′ i+1 ). (⇐)We can proceed in the opposite direction, and hence observing that, starting from a valid plan π ′ t = ⟨π ′ , ⟨0, t e ⟩⟩ for Π FLAT , we can create a valid plan π t = ⟨π, ⟨0, t e ⟩⟩ for ⟨Π, K δ ⟩. The validity of π t can be deduced by the validity of π ′ t and in particular by noting that each action in π ′ t implies that the corresponding action is applicable in π t therein.Since Π FLAT is an extension of Π, which does not alter the original problem, it is easy to see that any solution for Π FLAT is also a solution for Π. However, the converse is not true, as all plans with timed actions that are incompatible with K δ do not admit a corresponding valid one in Π FLAT .U -Kδ U -1δ E -1δ E -2δ E -KδCorollary 1 (Soundness of FLAT w.r.t. Π). Let ⟨Π, K δ ⟩ be 585 a PDDLδ+ problem and let Π FLAT be the PDDL+ obtained by using FLAT. Π FLAT admits a solution if Π does so.Our experimental analysis aims at assessing how the proposed encoding can affect the performance of PDDL+ 590 domain-independent planning engines. This is done by considering two sets of benchmarks. The first set focuses on the COOPROVERS, where the use of the proposed encoding is expected to deliver a significant performance boost due to the characteristics of the domain. The second set of ex-595 periments is performed on well-known PDDL+ benchmark domains with the aim of analysing how our approach behaves in the Unitary-Static setting (i.e., only one constant discretisation step). All benchmarks are available at https: //anonymous.4open.science/r/deltaExperiments-D585.Due to the nature of the proposed approach, we focus on planning engines that leverage on discretisation to solve PDDL+ problems. Therefore, we consider two state-of-theart domain-independent planning engines: ENHSP (Scala et al. 2016) and UPMURPHI (Della Penna, Magazzeni, and 605 Mercorio 2012). ENHSP incorporates a range of heuristics and search techniques, hence providing the ideal ground to compare them within the same infrastructure. UPMURPHI shed some lights into how a radically different approach to discretised PDDL+ can be affected by the proposed translations. In our analysis, we used the default A * search paired with the default AIBR heuristic (Scala et al. 2016) , the add heuristic (Scala, Haslum, and Thiébaux 2016) , and a traditional blind search. UPMURPHI is based on the planning via model-checking paradigm. It automatically translates discretised PDDL+ to a model-checking formulation, and then uses blind search to find a solution. Experiments are run on a 2.3 GHz Intel Xeon 6140M, with a 300 CPU-time seconds cut-off time, and 8 GB RAM.In the COOPROVERS domain model, choosing the right discretisation step is critical to efficiently generate a valid plan: larger discretisation can lead to draining the battery of the fastest robot. Indeed, to plan faster when the value of α becomes larger, one may consider using a larger discretisation step, proportional to α. But this approach can be problematic, as the nearest and fastest robot may not have the possibility to charge before its battery is drained. On the other hand, the use of a smaller discretisation step makes the search space deeper and requires more resources to be explored. Figure 3 shows the results achieved by the considered planning engines when a range of discretisation options are exploited: 1δ, the traditional approach in which there is a unique discretisation step to model the granularity of the agent and the environment, i.e., δ e = δ p = 1; 2δ, the approach where environment and agent are natively decoupled by the planner by using δ e = 1 and δ p = 3 (available only in ENHSP), and the proposed K δ approach. The K δ approach is run with δ e = 1 over the PDDL+ problems obtained by using the FLAT translation and exploiting the discretisation knowledge provided for the motivating example in the corresponding section. The ENHSP solver has been run with several heuristics (i.e., hadd, aibr, hmrp) and strategies (i.e., A * and GBFS), and we show in the plot the minimum run time among all these strategies for each α. It can be noted by the line chart how the presented approach better deals with the large value of α, allowing to always solve faster than the 2δ approach. The performance improvement is more pronounced when a blind search is used, as in the case of UP-MURPHI, where the improvements are noticeable already with small values of α. The displayed results confirm that the proposed approach can effectively support the reasoning of domain-independent planning engines in cases where dynamics evolving at different speeds are present in a single planning problem. Further, as a by-product of this work, we note that the newly introduced COOPROVERS domain can provide some interesting test-bed for the planning community, to assess aspects of the planning capabilities of domainindependent approaches that were not considered before. In these settings, we aim to understand if, on well-known benchmark instance: (i) the proposed approach can improve the performance of general domain-independent planning engines, and (ii) the proposed approach allows achieving performance that are comparable to those of a planning engine natively exploiting a dual discretisation. We consider the well-known benchmark domains of Baxter, Descent, HVAC, LinearCar, and Rover.Table 2 provides an overview of the results. Every approach is run using δ e = 0.1; 2δ and K δ discretise the agent's action with δ p = 1, the first natively on the planner side and the second via translation by setting J(h) = 1 and ∇(z) = 1 ∀z ∈ A ∪ E; finally, 1δ employs δ p = 0.1.Remarkably, the use of K δ allows all the considered planning systems to perform significantly better than when the standard 1δ techniques are in use. Often, this is not only reflected in better runtimes, but also in higher coverage. This strongly indicates that, even in domains where a single delta may seem to be appropriate, an intelligent use of multiple deltas can be beneficial; further, our approach can allow any planning engine to directly benefit from it. Finally, the comparison against the 2δ technique implemented in ENHSP shows that the use of the proposed reformulation of PDDL+ does not add a significant computational overhead. Of course, techniques that are encoded in a planning engine lead to better performance, but it is worth reminding that K δ gives more flexibility and the possibility to tailor the discretisation step for multiple dynamics.It is well-known that, in general, finding a suitable discretisation for a continuous system is a hard and challenging task (Della Penna, Magazzeni, and Mercorio 2012). On the one hand, a finer discretisation leads to a more accurate approximation of the continuous behaviour. On the other hand, a more coarse discretisation reduces the size of the search space and fosters solvability. This problem is, of course, exacerbated in approaches where multiple deltas need to be set, i.e. ENHSP or the solution proposed in this paper. However, it is worth noting that in many practical cases, it is easy to find suitable discretisation values, that can be implied by system constraints or by domain knowledge. When multiple agents or systems need to interact, an analysis of the greatest common divisor and of the minimum common multiple among considered delta values for the agents can shed some light into promising values to be used to ensure a 705 good approximation of the interaction points among agents. In extreme cases, where the application domain or the characteristics of the problem at hand do not easily allow to identify suitable discretisation values, the methodology proposed by Della Penna, Magazzeni, and Mercorio ( 2012) is to start 710 from a coarse discretisation and refine it until the approximation error is within an acceptable threshold. The overall plan-validate framework can support this approach, and has been extensively exploited in real-world applications of hybrid planning (Percassi, Scala, and Vallati 2023a) .Discretisation is a well-established approach to reason upon challenging hybrid PDDL+ problems. The vast majority of existing approaches are based on a single discretisation step, and ENHSP is the only approach that can leverage two dif-720 ferent discretisation steps in a domain-independent fashion. With the aim of taming complex PDDL+ problems where multiple deltas are needed to efficiently generate solutions, in this paper we presented a reformulation approach that allows any domain-independent planning engine to exploit 725 multiple discretisation steps. The formalised notion also allowed us to categorise different levels of discretisation control. The performed experimental analysis highlights the benefits of the discretisation knowledge K δ in problems characterised by the coexistence of different dynamics, and 730 also shows the capabilities of the approach on well-known PDDL+ benchmark domains. Our experimental analysis also indicates that the existing benchmarks for PDDL+ lack of variety in terms of modelled dynamics; our motivating example fills this gap, and the proposed approach can equip 735 existing planning engines with the means to solve this class of hybrid planning problems.As future work, we are interested in investigating approaches that can cover the whole range of discretisation control levels shown in Table 1 . We also plan to explore the 740 synergies that can be generated between multiple discretisation reformulations and domain-independent heuristics, to design models that can generate search spaces easier to be navigated by planning engines.We assume PDDL+ problems are event-deterministic, i.e., given a state where multiple events are triggered together, we can sequence them arbitrarily, always obtaining the same outcome(Fox and Long2006).The full PDDL+ formulation is available at https://anonymous. 4open.science/r/deltaExperiments-D585. 
 
 Appendix:  


Decision: We recommend to accept this paper. While there is not uniformity of opinion among reviewers according to headline scores, there is agreement that the work can be accepted, and recognition of the need to drive work in PDDL+ planning towards being suitable for practical use.

Reviews: review: strength_weakness: strength_weakness: see questions
questions: questions: 1. The authors argue that the appropriate discretization steps can often be derived from domain constraints, but it is unclear how or by whom the discretization step is set. I suggest dynamically adjusting the step during plan execution based on the partial plan. The authors are encouraged to comment on this aspect for clarity.
2. Considering that reasoning with discretized domains and planning may necessitate plan validation, it is suggested that the authors address using VAL to validate generated plans in their methodology.
3. The approach presented in the paper may benefit the DiNo planner; however, it is not included in the experimental results. The authors are encouraged to motivate the exclusion and discuss how their approach could benefit the DiNo planner.
strength_weakness: strength_weakness: The main idea is somewhat simplistic and the results show that the proposed approach (K_\delta) is comprehensively outperformed by the double discretization (2\delta) adopted bu ENHSP. 
Further, the paper does not specify how the values of \delta discretizations or other important parameters are selected. In its current form, the approach does seem like a handcrafted modification to existing PDDL+ domains which limits its applicability to solving novel PDDL+ problems. Having to directly modify the PDDL+ models and being outperformed by out-of-the-box ENHSP significantly limits the applicability of the proposed approach.
questions: questions: 1. is there a pre-processing script that can transform an existing PDDL+ problem into a dynamic planning-discretization PDDL+ problem?
2. Are all the multi-discretization parameters selected manually per domain/problem?
3. What is the concrete implementation of the Del function controlling the dynamics of the discretization steps? Does it need to be explicitly defined for each domain or problem? How can the function infer discretization steps from both the set of actions and events as well as the initial state?
4. Are all the discretization variables multiples of one of the smallest-valued discretization quantum?
5. PDDL+ models are supposed to be continuous by default, could the dynamic planning-discretized PDDL+ problem be (in principle) solved by non-discretization-based planners (e.g., SMTPlan+)?
strength_weakness: strength_weakness: The comments above describe the issues I have.
questions: questions: Can you comment on the question of whether mixed discretisation can lead to some plans being excluded because of the requirement that events must commute? I believe that the imposition of a discretisation is an added constraint that can make some plans no longer possible. How is that addressed in the completeness claim?