JaxPlan and GurobiPlan: Optimization Baselines for Replanning in Discrete and Mixed Discrete and Continuous Probabilistic Domains

Venue: icaps-conference_org_ICAPS_2024_Conference
Published: 2023-12-08 02:05:15

Abstract: Replanning methods that determinize a stochastic planning problem and replan at each action step have long been known to provide strong baseline (and even competition winning) solutions to discrete probabilistic planning problems.  Recent work has explored the extension of replanning methods to the case of mixed discrete and continuous probabilistic domains by leveraging MILP compilations of the RDDL specification language.  Other recent advances in probabilistic planning have explored the compilation of structured mixed discrete and continuous RDDL domains into a determinized computation graph that also lends itself to replanning via so-called planning by backpropagation methods.  However, to date, there has not been any comprehensive comparison of these recent optimization-based replanning methodologies to the state-of-the-art winner of the discrete probabilistic IPC 2011 and 2014 and runner-up in 2018 (PROST) and the winner of the mixed discrete-continuous probabilistic IPC 2023 (DiSProd). In this paper, we provide JaxPlan that has several extensive upgrades to both planning by backpropagation and its compact tensorized compilation from RDDL to a Jax computation graph with discrete relaxations and a sample average approximation.  We also provide the first detailed overview of a compilation of the RDDL language specification to Gurobi's Mixed Integer Nonlinear Programming (MINLP) solver that we term GurobiPlan.  We provide a comprehensive comparative analysis of JaxPlan and GurobiPlan with competition winning planners on 19 domains and a total of 155 instances to assess their performance across (a) different domains, (b) different instance sizes, and (c)  different time budgets.  We also release all code to reproduce the results along with the open-source planners we describe in this work.

Main paper: 
 time management:: 
 We investigate how each method handles the allocated planning time, examining win rates versus the time per step size.These questions form the basis of our comprehensive evaluation, providing insights into the strengths and limitations of the considered methods across different dimensions.We begin with a detailed analysis of results and conclude with a summary of key performance observations at the end of the section.Normalized Performance Across Domains Following the procedures of the previous IPPC competition, for each instance we compute a normalized score as follows: a score of zero corresponds to the best average return of the noop and random policy, a score of one corresponds to the best average return across all baselines, and in general the normalized score of a return R is computed as score = (Rbase)/(bestbase) and clipped to [0, 1], where best is the best return, and base is the maximum of the no-op and random returns. The average score is averaged across all instances for each domain and baseline, and reported in Table 3 for the IPPC 2011 and 2014 domains, and Table 4 for the IPPC 2023 domains.On the IPPC 2011 and 2014 domains, we see that Gurobi-Plan achieves the best performance on the AcademicAdvising and CooperativeRecon domains. One possible explanation is that these domains require backwards sequential logical reasoning to identify the optimal path to the goal. For instance, to solve the AcademicAdvising problem, it is necessary to start from the desired course(s) the student wishes to pass (the goal), then pursue their direct prerequisites, the prerequisites of the prerequisites, and so forth. Complex logical constraints on state transitions in these domains renders it more difficult to discover the goal using forward search methods alone -on which JaxPlan and PROST are based. On the other hand, GurobiPlan does relatively poorly on domains where determinization is conjectured to be less effective. For instance, Navigation was designed to provide dead-ends when using most likely outcome determinization, which explains the particularly poor performance of Guro-biPlan on this domain.More generally, with a 5-second time limit per decision epoch, GurobiPlan outperforms JaxPlan on 8 out of the 12 0.00 ± 0.00 0.00 ± 0.00 0.00 ± 0.00 0.20 ± 0.39 0.00 ± 0.00 0.00 ± 0.00 0.00 ± 0.00 0.00 ± 0.00 0.00 ± 0.00 Reservoir 1.00 ± 0.00 1.00 ± 0.00 1.00 ± 0.00 0.99 ± 0.01 1.00 ± 0.01 1.00 ± 0.00 0.96 ± 0.04 0.96 ± 0.04 0.96 ± 0.04 UAV 0.02 ± 0.03 0.01 ± 0.02 0.01 ± 0.02 0.99 ± 0.00 0.98 ± 0.01 1.00 ± 0.00 0.97 ± 0.01 0.97 ± 0.01 0.97 ± 0.01 We surmise that the performance of JaxPlan on these do-mains (as well as CrossingTraffic and CooperativeRecon) is hindered by the presence of dead ends, i.e. terminal states 455 that when reached, render the goal state inaccessible during the remainder of the rollout (Guerin et al. 2012; Ng and Petrick 2022) . On the other hand, JaxPlan appears to Table 5 : List of hyper-parameters in JaxPlan that were tuned prior to evaluation, together with their corresponding ranges of possible values.do well when there are multiple high-reward actions available in each state, or at least the presence of a "corrective" action allowing the planner to move from a region of low to high reward, which we typically find in IPPC 2023 domains as we discuss next.On the IPPC 2023 domains, JaxPlan generally outperforms DiSProD. This new finding does not contradict the results of the IPC 2023 competition, where DiSProD only outperformed the straight-line implementation of JaxPlan, not the replanning approach used here. JaxPlan also significantly outperforms GurobiPlan, which fails to make progress on all domains, with the exception of the highly linear Reservoir and PowerGen domains. We suspect the poor performance on the nonlinear domains is at least partially explained by the piecewise linear approximation, which introduces a large number of auxiliary variables. One way to address this issue is to tune the parameters of the piecewise approximation (i.e. number of segments). Another explanation for the poor performance of GurobiPlan is the sparse goal-oriented nature of these problems in particular MountainCar and RaceCar (and to an extent MarsRover and UAV), where full horizon rollouts are required for identifying the goal state. JaxPlan (and its derivative DiSProD) are capable of efficiently planning over a long lookahead horizon within the allocated time budget, since their overall computation cost scales linearly with the rollout horizon.Instance Size Scalability Here, we conduct an evaluation to assess how each method effectively handles problems of increasing size, providing insights into scalability and performance under growing complexities. Across all domains, the scale of the problem systematically increases with the instance ID. Specifically, instance i exhibits a larger number of objects or a more intricate topology compared to instance i -1. This holds true for instances where i ∈ {2, ..., 10} in the case of IPPC 2011 and 2014, and i ∈ {2, .., 5} for IPPC 2023.To gauge performance, we measure the win rate against instance size for a given time-allocated budget. In essence, the win rate signifies the percentage of successes for each method on a particular instance across all domains. This evaluation metric is applied consistently for instances 1, 2, and so forth, with the measure being relative to the allocated execution time. The evaluation outlined above will be executed for three constant time allocation budgets. This strategic approach allows us to comprehensively measure how each method scales as the time allocated for a planning step size increases. The three time allocation budgets ensure a careful examination of scalability across various planning time constraints. Results are given in Figure 2 .The top row of Figures showcases the performance of Jax-Plan, GurobiPlan, and PROST across the domains of IPPC 2011 and 2014. In contrast, the bottom row illustrates the performance of JaxPlan, GurobiPlan, and DiSProD over the 2023 IPPC domains. For both rows, the leftmost In the results for the 2011 and 2014 IPPC domains, it is evident that PROST, as a highly tuned method tailored for discrete domains, achieves the highest win rate in the majority of cases. However, specific instances reveal that as the time budget increases, other methods manage to gain the upper hand. For example, in instance 1, GurobiPlan's performance surpasses other methods for step sizes 3 and 5 (see Figures 2b and 2c respectively ). An intriguing observation is that while GurobiPlan, as a MINLP method expressing discrete components explicitly, generally achieves better overall results than JaxPlan, there are instances, especially at larger sizes, where JaxPlan outperforms GurobiPlan. No-tably, in instance 9 and when allocated 5 seconds per step, JaxPlan achieves the best results (see Figure 2c ).Turning to the 2023 IPPC domains, JaxPlan stands out as clearly superior to GurobiPlan and DiSProD. It consistently achieves the best performance across all instance sizes and time budgets, as evidenced in Figures 2d, 2e, and 2f . This demonstrates JaxPlan's robustness and effectiveness in handling the challenges posed by the mixed discrete-continuous nature of the 2023 IPPC domains.Time Management and Anytime Performance Here, we evaluate each method according to its performance in relation to the allocated budget time. The assessment encompasses several time settings in increasing length, to comprehensively understand how each method adapts to varying time constraints.For every instance, each method underwent execution in three distinct settings, each with a different time budget. The allocation of time was determined on a per-instance basis and was linear with respect to both the horizon and the "stepbudget." Specifically, for a problem with a horizon T and a step-budget of h, the total allocated time for execution was T × h seconds per episode. The evaluation was conducted across three step sizes: 1 second per step, 3 seconds per step, and 5 seconds per step.Performance was quantified through the measurement of win rates, considering all instances across all domains. To maintain clarity and relevance, results from IPPC 2011 and 2014 were distinguished from those of IPPC 2023 due to variations in instance quantity and the methods used for comparison. This separation ensures a focused and controlled analysis of each iteration's results. The results are provided in Figure 3 .We can observe conclusive evidence supporting the assertion that PROST consistently achieves the best results across the domains of IPPC 2011 and 2014, while JaxPlan emerges as the top performer for IPPC 2023. This conclusion holds true across all allocated time step budgets, underscoring the reliability and consistency of these findings.Notably, an interesting observation from both Figures 3a and 3b is the stability of the win rate distribution among the methods across various time budgets. This consistency implies that the relative performance of each method remains proportionate across different time allocations. Moreover, it is worth noting that all methods demonstrate a capacity to leverage the increased time allocated per step to some degree. Surprisingly, no method establishes a significant lead over the others, indicating a collective adaptability to the additional computational resources provided.We now summarize our observations along key evaluation dimensions.• Discrete Domains (IPPC2011 & IPPC 2014):-PROST, being an optimized discrete MCTS method, performs best overall in purely discrete domains. -GurobiPlan outperforms JaxPlan on domains with heavy sequential, logical reasoning, but struggles on Probabilistically Interesting domains with avoidable probabilistic dead-ends (e.g., Navigation) that are known to provide a failure mode for deterministic replanners (Little and Thiébaux 2007) . -JaxPlan tends to work better in highly stochastic domains requiring reasoning about many concurrent 590 independent exogenous events where myopic, but stochastic outcome-aware policies can often work well (e.g., Wildfire, SysAdmin and GameOfLife).• Mixed Domains (IPPC2023):-JaxPlan (in replanning mode) performs best.-Gurobi's MINLP solver appears to significantly struggle with the horizon required to plan effectively in these challenging mixed discrete-continuous domains.• Instance Difficulty and Time Budget:-JaxPlan typically performs better relative to other 600 planners as the instance difficulty increases, particularly in the mixed discrete-continuous instances and very often in the discrete instances. -No planner clearly dominates the others as the planning time budget increases.605In this study, we introduced two distinct optimization-based replanning approaches, JaxPlan and GurobiPlan, designed to address the complexities of planning in mixed discretecontinuous stochastic environments, while also demonstrat-610 ing the ability to plan in purely discrete scenarios. Our evaluation encompassed a diverse spectrum of problems drawn from past planning competitions, covering both discrete and mixed discrete-continuous domains. In addition to assessing JaxPlan and GurobiPlan, we benchmarked them against the 615 winners of previous competitions, namely PROST and DiS-ProD, with the overarching goal of establishing baseline approaches and gaining insights into their performance across various scenarios. Notably, PROST excels in discrete domains, leveraging 620 optimized search-based methods. GurobiPlan, operating as an explicit MINLP method, outperforms JaxPlan in some discrete domains requiring heavy logical, sequential reasoning. However, JaxPlan demonstrated a remarkable ability to surpass GurobiPlan in many discrete instances, especially 625 those that were highly stochastic. A key highlight emerged from our evaluation of the mixed discrete-continuous 2023 IPPC domains, where JaxPlan emerged as the superior performer, consistently excelling across diverse instance sizes and time budgets. This performance underscores JaxPlan's 630 robustness across a range of problem and evaluation types.Our study positions JaxPlan and GurobiPlan as two unique optimization-based replanning baselines capable of addressing challenges across the spectrum of discrete, continuous, and mixed discrete-continuous problems. These 635 findings not only offer valuable insights into the strengths of each planning method, but also identify key challenges for further advances in the realm of probabilistic planning.https://ataitler.github.io/IPPC2023/ 
: 
 the case of mixed discrete and continuous probabilistic domains by leveraging MILP compilations of the RDDL specification language. Other recent advances in probabilistic planning have explored the compilation of structured mixed discrete and continuous RDDL domains into a determinized computation graph that also lends itself to replanning via socalled planning by backpropagation methods. However, to date, there has not been any comprehensive comparison of these recent optimization-based replanning methodologies to the state-of-the-art winner of the discrete probabilistic IPC 2011 and 2014 and runner-up in 2018 (PROST) and the winner of the mixed discrete-continuous probabilistic IPC 2023 (DiSProd) . In this paper, we provide JaxPlan that has several extensive upgrades to both planning by backpropagation and its compact tensorized compilation from RDDL to 20 a Jax computation graph with discrete relaxations and a sample average approximation. We also provide the first detailed overview of a compilation of the RDDL language specification to Gurobi's Mixed Integer Nonlinear Programming (MINLP) solver that we term GurobiPlan. We provide a com-Stochastic planning addresses decision-making under uncertainty subject to probabilistic state transitions, and plays a major role in diverse fields such as robotics, artificial intelligence, and operations research. While historical emphasis in stochastic planning centered on discrete problems, recent years have witnessed a growing interest in continuous and mixed discrete-continuous problems due to their ability to accurately model a wide range of real-world scenarios with continuous time, space, and resources (Li and Williams 2011; Fernandez-Gonzalez, Williams, and Karpas 2018) .The International Planning Competition (IPC) (McDermott 2000; Coles et al. 2012; Vallati et al. 2015) , particu-larly its probabilistic track (IPPC), serves as a pivotal platform for evaluating stochastic planning systems. Replanning methods, historically prominent in control (Morari, Garcia, and Prett 1988) and planning (Hoffmann and Nebel 2001) , have demonstrated surprising efficacy in discrete probabilistic planning competitions. Notably, FF-Replan (Yoon, Fern, and Givan 2007) , the winner of the first IPPC in 2004, efficiently utilizes the deterministic planner FF (Hoffmann and Nebel 2001) to obtain plans based on determinized problem versions, effectively adapting to unexpected events during execution by replanning after each action is taken and the stochastically sampled next state is observed. In response to suggestions that all probabilistic planning might be effectively reduced to determinized replanning, Little and Thiebaux (2007) introduced a class of problems referred to as Probabilistically Interesting that could lead to suboptimal deterministic replanning behavior; this work influenced domain design in subsequent IPPCs as we highlight later.Since 2011, RDDL (Sanner et al. 2010 ) has been the standard description language for IPPCs, replacing PPDDL (Younes et al. 2005) . RDDL has the capacity to represent discrete and continuous components, with concurrency and exogenous and endogenous noise, while PPDDL is limited to only endogenous noise caused by stochastic action effects, and only a single action per time step. The IPPCs of 2011, 2014, and 2018 introduced only discrete problems and thus did not utilize the full expressive range of RDDL.The winners of the IPPCs over the years used a variety of methods, mainly revolving around the idea of replanning after each action is taken. PROST (Keller and Eyerich 2012) , the winner of IPPC 2011 and IPPC 2014, is a UCT based search method that leverages the structure of the problem, and knows to ignore actions if their effect does not have impact. SOGBOFA (Cui and Khardon 2016) , the runner up of IPPC 2018, is a symbolic gradient-based optimization method, that symbolically represents an approximation of the Q value function as a function of the action variables in order to perform gradient-based search over actions. DiSProD (Chatterjee et al. 2023) , the winner of IPPC 2023 mixed discrete-continuous competition, is a replanning method able to handle mixed problems by approximating the discrete components with a second order Taylor expansion. DiSProD is able to perform a gradient search forward and apply the first action in a rolling horizon scheme.The challenge of mixed discrete-continuous domains has been persistent for probabilistic planners, prompting dedicated focus in the 2023 IPPC. While determinization and replanning worked well in the discrete competition, it was interesting to see if these schemes are also effective in the mixed discrete-continuous case. The 2023 IPPC also introduced JaxPlan as a baseline method, evaluated in both straight-line planning mode (without replanning) and deep reactive policy mode.In this study, we evaluate PROST and DiSProD on the domains they previously won, alongside JaxPlan in a replanning mode with a comprehensive method description. Additionally, we introduce for the first time GurobiPlan, a novel replanning method based on compiling RDDL descriptions into mathematical optimization problems. Both GurobiPlan and JaxPlan undergo evaluation across all domains, providing insights into their capabilities in both purely discrete and mixed discrete-continuous domains.One of our core objectives in this paper is to establish replanning baselines for mixed discrete-continuous problems and to further evaluate how well they work in purely discrete scenarios. It is noteworthy that FF-Replan is excluded from our evaluation here due to its specificity to PPDDL and challenges in adapting to RDDL domains featuring concurrency or continuous components; this is attributed to the unbounded number of potential outcomes in the lifted RDDL specification (cf. RDDL domains like Wildfire) that PPDDL cannot model. Additionally, while the 2018 IPPC (Geißer 2019) introduced other PROST variants and methods such as SOGBOFA (Cui and Khardon 2016) , it introduced a variant of RDDL that has not been supported in the 2023 IPPC, which precludes comparative evaluation with JaxPlan or GurobiPlan that is the focus of this work.Markov Decision Process A Markov decision process (MDP) is a tuple (S, A, P, r, γ), where S is the state space, A is the action space, P is the next-state distribution, r is the single step reward function and γ is the discount factor. A plan is a sequence of actions a 1 , . . . a T , while a policy π is a mapping from states to actions. The goal of probabilistic planning is to find a sequence of actions that maximizes the cumulative expected reward over a planning horizonT max a1...a T E st∼P (st-1,at-1,•) T t=1 r(s t , a t ) s 1 = s . (1)Since the optimization problem above can be computationally intractable for long horizon, replanning approaches typically use a much shorter receding horizon T ′ ≪ T and solve (1) periodically starting from the current state s t at every decision epoch (or more generally, every k epochs).Planning-By-Backpropagation (PBBP) compiles a planning problem into a unrolled differentiable computational graph (Schulman et al. 2015) , thus enabling the direct calculation of return gradients with respect to action-fluents or policy parameters (Wu, Say, and Sanner 2017; Bueno et al. 2019; Patton et al. 2022) as illustrated conceptually in Figure 1 . Consider first a deterministic MDPs 0 + return s 1 a 0 r 0 s 2 a 1 r 1 s 3 a 2 r 2Figure 1 : A differentiable computation graph for an abstract MDP with a horizon of 3 decision time steps. Here, s t and a t denote the state and action variables, respectively. Red dotted arrows indicate the flow of gradients from the return objective t r t with respect to actions in the computation graph.with state transition model s t+1 = f (s t , a t ) and reward r(s t , a t ), where f and r are both differentiable functions. Trajectories s 1 , s 2 . . . s T can be forward sampled di-145 rectly from the model, and the gradients of the return ∇ a1,...a T V (a 1 , . . . a T , s 1 ) = ∇ a1,...a T T t=1 r(s t , a t ) can be used to update the actions by taking a gradient ascent. For stochastic problems, the reparameterization trick often allows rewriting the next-state distribution P (s t , a t , s t+1 ) 150 as a deterministic differentiable function f (s t , a t , ξ t ) of exogenous i.i.d. noise ξ t (Bueno et al. 2019) . However, we note that many discrete distributions such as Bernoulli do not support differentiable reparameterization.PROST (Keller and Eyerich 2012 ) is a planning system 155 rooted in the Upper Confidence Bounds applied to Trees (UCT) algorithm. PROST strategically traverses a search tree derived from a factored MDP, efficiently managing the branching factor of chance nodes to reduce the search space size. The algorithm employs a bias parameter that scales 160 with the expected reward of an optimal policy, contributing to convergence. A regret minimization strategy, derived from the UCB1 algorithm, is integrated to enhance performance. PROST also introduces a search depth limitation, prioritizing decisions with more immediate impacts on ex-165 pected rewards. Additionally, the algorithm excludes actions that lack influence under specific circumstances, leading to a streamlined branching factor. PROST also introduce reward locks for dead-ends and Q-value initialization to avoid random walks, based on a single outcome determinization of 170 the MDP.DiSProD (Chatterjee et al. 2023 ) is an on-line planner suitable for hybrid domains. Leveraging the stochastic computation graph paradigm, it builds a computation graph capturing an approximation of the distribution over future tra-175 jectories and rewards, conditioned on a probabilistic openloop policy. At each decision step, DiSProD performs a par-allel search over multiple policies, each optimizing the approximate cumulative reward by differentiating through the computation graph, and then uses the first action from the maximizing policy. DiSProD's novel innovation is its ability to handle mixed discrete-continuous domains by approximating the dynamics with second order Taylor expansions.Vectorized Computation Graphs Our proposed approach to PBBP in RDDL domains, called JaxPlan, leverages the JAX framework to compile the computation graph directly from the lifted RDDL domain description (Frostig, Johnson, and Leary 2018) . By working with the lifted problem, it is straightforward to vectorize the computation graph.To illustrate this, consider the conditional probability function cpf (?x, ?y) = sum {?z:type} values(?x, ?y, ?z), where ?x, ?y and ?z are free parameters. Working in a depthfirst fashion, the values(?x, ?y, ?z) fluent is compiled to a rank-3 tensor of dimensions equal to the number of objects corresponding to types ?x, ?y and ?z, respectively. Aggregations are compiled to their equivalent tensor operations over one or more axes of the argument (in the example above, a JAX sum operation over the last axis of values tensor). The vectorized just-in-time compilation of RDDL allows Jax-Plan to optimize action fluents over a long planning horizon while being efficient in both space and time.The novelty of JaxPlan is its ability to handle hybrid continuous-discrete state and action spaces. Specifically, suppose the state factors as s t = [s t,1 , . . . s t,n ] where s t,i = f i (Pa(s t,i )) is a function of the parents Pa of s t,i in the computation graph, which includes other state and action variables. At the core of its strategy, JaxPlan translates the conditional probability functions f i into differentiable relaxations, formalized as families of functions { fi,τ : τ > 0} indexed by some hyper-parameter τ . The variables st,i = fi,τ (Pa(s t,i )) and s1,i = s 1,i then define a differentiable relaxation of the original model.Given that Boolean logic in RDDL lacks inherent differentiability, it becomes essential to choose functions f i,τ that effectively approximate Boolean logic. The novel contribution of JaxPlan is to substitute Boolean operations with t-norms (Hájek 2013) . Specifically, a t-norm is a function T : [0, 1] 2 → [0, 1] that satisfies four properties: commutativity, monotonicity, associativity, and inclusion of the identity element. For a, b ∈ [0, 1], JaxPlan defines the axioms:• a ∧ b ≈ T (a, b) • ¬a ≈ 1 -a,from which other logical RDDL operations can be derived, e.g.:• a ∨ b ≡ ¬(¬a ∧ ¬b) ≈ 1 -T (1 -a, 1 -b) • a =⇒ b ≡ ¬a ∨ b ≈ 1 -T (a, 1 -b) • ∀{x 1 , x 2 , . . . x m } ≡ x 1 ∧ x 2 • • • ∧ x m ≈ T (x 1 , T (x 2 , T (. . . ))) Exact RDDL Operation Differentiable Relaxation a ∧ b T (a, b) ¬a 1 -a a ∨ b 1 -T (1 -a, 1 -b) a =⇒ b 1 -T (a, 1 -b) forall {?p:type} x(?p) ?p x(?p) exists {?p:type} x(?p) 1 -?p (1 -x(?p)) if c then a else b c × a + (1 -c) × b a > b sigmoid((a -b)τ ) a == b sech 2 ((b -a)/τ ) signum(x) tanh(x/τ ) argmax {?p:type} x(?p) |type| i=1 i × softmax(x/τ )[i] Bernoulli(p), Discrete(p) Gumbel-SoftmaxTable 1 : List of differentiable relaxations used in JaxPlan.•∃{x 1 , x 2 , . . . x m } ≡ ¬∀{¬x 1 , ¬x 2 , . . . ¬x m } ≈ 1 -230 T (1 -x 1 , T (1 -x 2 , T (. . . ))).For example, the product t-norm defines T (a, b) = a × b, which calculates the logical conjunction exactly when a and b are Boolean.In addition, JaxPlan approximates the conditional branch-235 ing statement such as "if c then a else b" asf (a, b, c) = c × a + (1 -c) × b,which is a differentiable function of its arguments. A popular choice for approximating relational operations, such as a > b, a < b and a == b is the logistic sigmoid approximation (Petersen et al. 2021) :240 a > b ≈ sigmoid((a -b)/τ ) a == b ≈ sech 2 ((b -a)/τ ),where τ refers to the temperature parameter.Finally, discrete distributions are approximately reparameterized using the Gumbel-Softmax trick (Jang, Gu, and Poole 2016) . Formally, samples z from a categorical distribution with density {p i } K i=1 can be approximated by sam-245 pling a vector ξ ∈ R K with i.i.d. Gumbel(0, 1) entries, and computing z = softmax((ξ + log p)/τ ) for a temperature hyper-parameter τ > 0.A more concrete description of the rewriting rules in Jax-Plan to facilitate automatic differentiation based on the prod-250 uct fuzzy logic is summarized in Table 1 . An interesting property of this set of relaxations is that as τ → ∞, the overall error in the model relaxation decreases to zero. However, in practice, there is a trade-off between high error in the gradient (for small τ ) and vanishing/sparse gradient (for 255 large τ ). Our empirical evaluation performs Bayesian hyperparameter optimization in order to determine the best overall value of τ for each problem instance, as discussed in a later section.Action Parameterization During optimization, the goal 260 of JaxPlan is to find optimal "soft" actions parameterized as logistic sigmoids, ãi = σ(θ i ) = 1/(1 + exp (-w × θ i )), by optimizing the real-valued parameters θ i using gradient ascent. Here, w is a general hyper-parameter that controls the overall sharpness of the approximation. At test time, since Boolean actions are required, the soft actions ãi are converted to "hard" actions a i by the rounding operation In order to ensure constraint satisfaction during optimization, JaxPlan projects the action parameters θ = [θ 1 , θ 2 , . . . θ N ] after each gradient ascent step to the feasible region as follows. First, the soft actions are sorted in descending order to obtain the order statistics ã(1) ≥ ã(2) , • • • ≥ ã(N) . Next, the B + 1-st largest action value determines the amount ∆ by which the soft actions needed to be shifted downwards to satisfy the constraint on the corresponding hard actions, i.e. ∆ = ã(B+1) -0.5. If ∆ > 0, then all soft action values are shifted downwards to obtain ã′ i = max(ã i -∆, 0). Finally, JaxPlan computes the new parameter θ ′ i by inverting the logistic sigmoid a i = 1, if ãi = σ(θ i ) > 0.5 0,θ ′ i = σ -1 (ã ′ i ).GurobiPlan is an alternative to JaxPlan that could perform better in discrete problems where the model relaxations as defined above could be inaccurate. In summary, this approach involves compiling the return maximization problem into a mixed-integer nonlinear program (MINLP). For example, if s t+1 = As t + Ba t and r(s t , a t ) = c • s t + d • a t for some appropriately sized matrices A, B and vectors c, d, and a compact (e.g. box-bounded) action space A the two-stage problem compiles to the mixed-integer linear program:max a1,a2∈A c • s 1 + d • a 1 + c • s 2 + d • a 2 s.t. s 2 = As 1 + Ba 1 .However, GurobiPlan leverages the state-of-the-art Gurobi optimizer to compile RDDL domains directly into MINLPs, which naturally handles a large subset of the nonlinear RDDL operations through piecewise-linear approximations (Gurobi Optimization, LLC 2023).Additionally, outcomes of relational operators, and some nonlinear functions, are expressed as indicator variables δ ∈ {0, 1} with suitable constraints imposed on them. For instance, we rewrite a ≥ b in terms of a binary variable δ, constrained as follows:δ = 1 =⇒ a -b ≥ 0 δ = 0 =⇒ a -b ≤ -ε,where ε is a small positive constant.Constraint Handling Another innovation of GurobiPlan 315 is the propagation of tight bounds on variables through interval arithmetic (Hickey, Ju, and Van Emden 2001) . To illustrate, for the expression s ′ = (s + a) 2 with s ∈ [0, 2] and a ∈ [0, 1], the sub-expression s + a is bounded in [0, 3], and thus s ′ ∈ [0, 9]. Action preconditions are compiled directly 320 as (possibly nonlinear) constraints on action-fluents using the rewriting rules described above. Together with the box constraints computed through interval arithmetic, and the constraints generated through the rewriting of relational or other operators as in Table 2 , this constitutes the constraint 325 set of the complete mixed-integer program.Stochastic Variables Stochastic variables are not directly compatible with the notion of mixed-integer programming, which is inherently deterministic in nature, thus some form of approximation is required. One option is the sample av-330 erage approximation, which would require a large sample size in practice and would therefore produce a large nonlinear program that is difficult to solve computationally (Kleywegt, Shapiro, and Homem-de Mello 2002). An alternative and much simpler approach, that is employed in the current 335 implementation of GurobiPlan, is to determinize stochastic samples by replacing them with their mean estimates. For example: b(?p) = Bernoulli(rate(?p)) → b(?p) = rate(?p) z(?p) = Normal(mean(?p), var(?p)) → z(?p) = mean(?p).A more complete list of rewriting rules employed by Guro-biPlan is summarized in Table 2 .Benchmark Problems The evaluation of JaxPlan and GurobiPlan encompasses the domains of IPPC 2011 (Coles et al. 2012) , 2014 (Vallati et al. 2015) , and 20231 . We note 345 that IPPC 2018 (Geißer 2019) was excluded due to unique, unsupported RDDL language components used exclusively in that iteration of the competition. The evaluation problems benchmark was thus comprised of the 12 domains from IPPC 2011 and IPPC 2014, each with 10 instances, and 7 do-350 mains from IPPC 2023, excluding the RecSim domain due to its excessively large combinatorial nature and since no method achieved results significantly better than random behaviour on it. This results in a total of 19 domains and 155 instances. All domains are summarized in the Appendix.Baselines In the case of IPPC 2011 and IPPC 2014, which were exclusively discrete competitions, we benchmarked the performance of JaxPlan and GurobiPlan against the winner of these two iterations, PROST (Keller and Eyerich 2012) . ous and mixed discrete-continuous domain components in the state and possibly action spaces. The winner, DiSProD (Chatterjee et al. 2023) , served as the benchmark for planner performance comparison for this set of problems. Complete raw unnormalized results for each evaluated method are pro-365 vided in the Appendix while this section specifically focuses on the aggregated comparative analysis of the planners on their applicable discrete and mixed discrete-continuous domains. To preempt perceived discrepencies in the the evaluation of JaxPlan vs. DisProd in this work vs. the 2023 IPPC, it is important to note that JaxPlan in this paper is run in replanning mode, whereas in the 2023 IPPC a straight-line plan (no replanning) and reactive policy versions were used.Additional Details All evaluations were executed on the IPPC 2023 simulation platform, pyRDDLGym (Taitler et al. 2022) . For PROST, we used the settings as employed in the IPPC 2014 competition, and for DiSProD we used the same settings as employed in the IPPC 2023 competition, except that we modified the algorithms to allow for the increased time budget. For the GurobiPlan and JaxPlan baselines, prior to evaluation, we performed tuning to identify the best hyper-parameter setting for each baseline method on each problem instance. The maximum time budget allowed for tuning was fixed at 2 × h hours, where h ∈ {1, 3, 5} was the maximum allowed time budget per decision epoch (in seconds). For GurobiPlan, we identified the receding horizon T ′ as the sole key hyperparameter, whereas for JaxPlan the 5 hyper-parameters and their ranges are defined in Table 5 . To identify the best hyper-parameter value for GurobiPlan, we ran a grid search on {1, 2, . . . 20, 22, 24 . . . 30, 35, 40}. To identify the best hyper-parameter value for JaxPlan efficiently within the time budget, we ran Gaussian-process Bayesian optimiza-tion (Snoek, Larochelle, and Adams 2012) , evaluating the average performance of each acquired hyper-parameter setting across 5 independent rollouts of the planner, with random seeds chosen to be different than those used at test time.Key Questions Our evaluation aims to address three key questions:1. Performance Across Domains: We explore how each method performs in each domain, averaging over the domain's instances. The results are normalized to a scale of [0,1]. 2. Scalability: We assess how each method fares as instances scale up in size, measured by win rate. 
 
 Appendix:  


Decision: The paper introduces two replanning approaches to probabilistic planning, presented as potential baselines in an evaluation setting.

The two approaches rely on distinct optimization settings and are clearly presented and interesting in themselves. The authors perform a comprehensive empirical study on IPC benchmarks and against winners of past competitions, identifying several insights regarding the performance of the proposed solvers.
Importantly, the authors identify key weaknesses in more established probabilistic planning algorithms that may be leveraged in driving future research in the area.

Reviews: review: strength_weakness: strength_weakness: I find that Figure 3 and the subsection "Time Management and Anytime Performance do not bring fundamentally new information with regard to Figure 2. It is certainly a different view on the same results, yet redundant in my opinion. Also, I felt that Figure 3 was maybe exaggeratedly made bigger to fill the space, but I might be wrong. I would have preferred instead more details about the JaxPlan and GurobiPlan planners, like for instance their pseudo-codes and formal definitions of their model transformations.
questions: questions: - "FF-Replan is excluded from our evaluation here due to its specificity to PPDDL and challenges in adapting to RDDL domains featuring concurrency or continuous components" => I am puzzled: since PPDDL is less expressive than RDDL, yielding less combinatorial action effects in general, I would expect RDDL planners to be more efficient than pure PPDDL planners. Also, there is no technical reason to prevent RDDL planners from being compared against PPDDL planners on the less expressive set of problems that can be expressed in PPDDL only (and eventually translated to RDDL). Can you please convince me of the opposite? The same argument holds for PROST which is mentioned afterwards in the same paragraph. (TL;DR : "if you can move mountains you can move molehills")

- "b(?p) = Bernoulli(rate(?p)) -> b(?p) = rate(?p)" => does it mean that the b boolean variable becomes a float variable after the mean estimate transformation?

- "The maximum time budget allowed for tuning was fixed at 2 × h hours, where h in {1, 3, 5} was the maximum allowed time budget per decision epoch (in seconds)" => I'm lost: are we speaking about hours or about seconds?

- When Gurobi is used in the literature to solve scheduling problems, each variable is usually indexed by time. Is it the same of the MINLP model used by GurobiPlan?

- JaxPlan appears to perform not so well in probabilistically interesting domains (e.g. AcademicAdvising and TriangleTireworld) whereas its JAX encoding handles probability distributions. How do you explain this? Is it due to a too loose approximation of the probability distributions as the Gumbel-Sotfmax transformation?

- "JaxPlan typically performs better relative to other planners as the instance difficulty increases" => The claim being made also for IPPC 2011 and 2014 domains, I don't see how Figure 2/(a)-(c) supports this statement. Can you please elaborate?


=== General comments ===

- "PROST also introduce [...]" => introduceS

- "DiSProD’s novel innovation" => "novel" and "innovation" are redundant

- "JaxPlan achieves the best performance on Wildfire, while results on GameOfLife and SysAdmin are comparable to PROST." => well, honestly, not really for GameOfLife...
strength_weakness: strength_weakness: The only real problem I had with the paper was the presentation of graphical data.  Overlaying the legend on top of the graphs themselves obscures the plots in confusing ways.  See for example Figure 3.a, where it appears as though the Win Rate does not sum to 1.00.  That is an artifact of a bad layout, not a problem with the data or the plot itself.
As a suggestion: in the second full paragraph in the second column on p. 7, consider replacing the term "Figures" with "graphs."
questions: questions: 1.  What challenges for further advances are identified (or implied) by the results presented here?
strength_weakness: strength_weakness: I see no weaknesses in the paper, but I do have some minor comments and points for consideration, as well as some minor writing issues and typos.

# Minor Comments and Points of Consideration:

C1. I was wondering if the approaches of Wu, Say and Sanner (2017) and Bueno et al. (2019) wouldn't be a nice addition to your experiments (see my question Q1). I think these approaches you could be used in some of the benchmarks (domains and problems) used in the paper.
- https://github.com/wuga214/PAPER_NIPS17_ScalablePlanning_Tensorflow
- https://github.com/thiagopbueno/tf-plan
- https://github.com/thiagopbueno/tf-mdp

C2. Furthermore, personally, I think it would be good (and interesting) to see the results of the straight-line implementation of JaxPlan in the experiments, so we would be able to see how the "novel" JaxPlan (proposed in the paper) has improved compared to the straight-line implementation of JaxPlan.

# Writing Issues and Typos:

W1. "Mixed Discrete and Continuous" -> "Mixed Discrete-Continuous".
W2. "runner up -> "runner-up".
W3. "UCT" -> "Upper Confidence Tree (UCT)".
W4. "Q value" -> "Q-value".
W5. "DiSProD is able to perform a gradient search forward and ..." -> "DiSProD is able to perform a forward gradient-based search and ...".
W6. In Markov Decision Process (MDP), when you say "... solve (1) periodically starting from the current state ...", you mean Equation 1, is that correct?
W7. "i.e." -> "i.e.,".
questions: questions: Q1. As I mentioned in my comment C1, I found myself wondering why you haven't included the approaches of Wu, Say and Sanner (2017) and Bueno et al. (2019) in your empirical evaluation. Is there any reason for that? Please, clarify that.

Q2. You evaluate and assess the approaches in terms of performance, scalability, and time management, but why haven't you considered evaluating the quality of the solution as part of your empirical evaluation? 

Q3. Is there any room to improve the proposed approaches JaxPlan and GurobiPlan? You mention that the findings in the paper provide and show the advantages and disadvantages of each of the evaluated approaches, but you don't mention the possible advances that could be made to improve the evaluated approaches. Please, try to address that in your response/rebuttal (and also in the paper).