Paper deep dive
From Kinematics to Dynamics: Learning to Refine Hybrid Plans for Physically Feasible Execution
Lidor Erez, Shahaf S. Shperberg, Ayal Taitler
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 98%
Last extracted: 4/27/2026, 12:00:08 AM
Summary
The paper proposes a neuro-symbolic refinement framework to bridge the gap between first-order hybrid temporal planners and second-order physical execution in robotics. While traditional hybrid planners often use first-order (velocity-based) abstractions that fail to account for acceleration and drag constraints, this work introduces a Continuous-State and Action Markov Decision Process (CSA-MDP) to refine these plans. The framework uses a Graph Neural Network (GNN) to process a graph-based plan representation and a Proximal Policy Optimization (PPO) agent to adjust velocity bounds. The refinement is validated using a Minimum-Time Validation (MTV) method, which provides closed-form second-order feasibility analysis, ensuring the resulting trajectories are physically executable under real-world constraints.
Entities (7)
Relation Signals (5)
CSA-MDP → isusedfor → Plan Refinement
confidence 100% · We formulate the refinement task as a continuous-state and action Markov Decision Process (CSA-MDP).
PPO → optimizes → CSA-MDP
confidence 100% · We employ PPO to optimize the plan-refinement agent
GNN → processes → Plan Graph
confidence 100% · A Graph Neural Network (GNN) (Zhou et al. 2020) processes this graph
Hybrid Temporal Planner → uses → First-Order Dynamics
confidence 100% · While hybrid temporal planners attempt to address this challenge, they typically model motion using linear (first-order) dynamics
MTV → validates → Second-Order Dynamics
confidence 100% · The resulting trajectory is then validated for physical feasibility via MTV.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:In many robotic tasks, agents must traverse a sequence of spatial regions to complete a mission. Such problems are inherently mixed discrete-continuous: a high-level action sequence and a physically feasible continuous trajectory. The resulting trajectory and action sequence must also satisfy problem constraints such as deadlines, time windows, and velocity or acceleration limits. While hybrid temporal planners attempt to address this challenge, they typically model motion using linear (first-order) dynamics, which cannot guarantee that the resulting plan respects the robot's true physical constraints. Consequently, even when the high-level action sequence is fixed, producing a dynamically feasible trajectory becomes a bi-level optimization problem. We address this problem via reinforcement learning in continuous space. We define a Markov Decision Process that explicitly incorporates analytical second-order constraints and use it to refine first-order plans generated by a hybrid planner. Our results show that this approach can reliably recover physical feasibility and effectively bridge the gap between a planner's initial first-order trajectory and the dynamics required for real execution.
Tags
Links
- Source: https://arxiv.org/abs/2604.12474v2
- Canonical: https://arxiv.org/abs/2604.12474v2
Trouble viewing inline? Open PDF directly →
Full Text
44,197 characters extracted from source content.
Expand or collapse full text
From Kinematics to Dynamics: Learning to Refine Hybrid Plans for Physically Feasible Execution Lidor Erez1, Shahaf S. Shperberg2, Ayal Taitler1 Abstract In many robotic tasks, agents must traverse a sequence of spatial regions to complete a mission. Such problems are inherently mixed discrete-continuous: a high-level action sequence and a physically feasible continuous trajectory. The resulting trajectory and action sequence must also satisfy problem constraints such as deadlines, time windows, and velocity or acceleration limits. While hybrid temporal planners attempt to address this challenge, they typically model motion using linear (first-order) dynamics, which cannot guarantee that the resulting plan respects the robot’s true physical constraints. Consequently, even when the high-level action sequence is fixed, producing a dynamically feasible trajectory becomes a bi-level optimization problem. We address this problem via reinforcement learning in continuous space. We define a Markov Decision Process that explicitly incorporates analytical second-order constraints and use it to refine first-order plans generated by a hybrid planner. Our results show that this approach can reliably recover physical feasibility and effectively bridge the gap between a planner’s initial first-order trajectory and the dynamics required for real execution. Introduction Hybrid temporal planning aims to generate execution plans for robotic tasks that satisfy both discrete logical requirements and continuous numeric constraints governed by differential relations, together with temporal constraints. Temporal planners such as (Coles et al. 2012), (Fernández-González et al. 2018), and (Fernández-González et al. 2015) have demonstrated strong capabilities in handling complex temporal planning problems. Among these, the Scotty planner (Fernández-González et al. 2018) is a prominent approach that combines search over plan skeletons with trajectory optimization formulated as a mathematical program. In Scotty, the robotic system is modeled as a first-order integrator over the velocity x˙(t)=v(t), x(t)=v(t), (1) which enables the formulation of the resulting optimization problem as a Second Order Cone Program (SOCP) (Lobo et al. 1998). Additional hybrid planners include (Chen et al. 2021), which encodes mixed discrete-continuous planning for linear hybrid automata as a Mixed-Integer Linear Program (MILP), and (Denenberg and Coles 2019), which introduces linear over- and under-estimators to enable reasoning about nonlinear fluents within linear-dynamics planners. Despite their differences, these approaches share a common modeling assumption: they rely on first-order abstractions of system dynamics, where control inputs typically correspond to velocities and no continuity constraints on the inputs are enforced. While this assumption enables tractable optimization formulations such as SOCP or MILP, it fails to capture the second-order nonlinear dynamics that govern real robotic systems, including bounded accelerations and drag effects. Consequently, tracking these first-order plans with a low-level closed-loop controller inevitably induces actuator saturation, leading to large tracking errors and potential instability. In recent work, (Taitler et al. 2019) treat the plans produced by the mentioned planners as sequences of point-to-point motions and introduce Minimum-Time Validation (MTV), which provides a closed-form lower bound on the time required to move between two way-points under second-order dynamics. This bound makes it possible to identify way-point transitions whose assigned durations are physically unattainable, revealing portions of the plan that cannot be executed in reality. Yet, detecting violations is not sufficient: existing hybrid planners cannot revise a plan within their first-order models to enforce second-order feasibility. this work, we bridge this gap by introducing a neuro-symbolic refinement framework that combines hybrid planning, second-order validation, and reinforcement learning. Starting from a first-order-feasible hybrid plan generated by an off-the-shelf hybrid planner, we represent the temporal and spatial structure as a graph and formulate the refinement task as a continuous-state and action Markov Decision Process (CSA-MDP). A Graph Neural Network (GNN) (Zhou et al. 2020) processes this graph and proposes adjustments to the velocity bounds. An SOCP solver computes the corresponding motion parameters, and the updated trajectory is then validated for physical feasibility via MTV. This yields a closed-loop refinement mechanism capable of computing a feasible-guaranteed second-order trajectory without modifying symbolic preconditions, action ordering, or temporal constraints. The contributions of this work are as follows: • We formulate plan refinement as a CSA-MDP Process over a graph-based plan representation, enabling structured reasoning over temporal, spatial, and dynamical relationships and constraints. • We introduce the first refinement automated framework that transforms first-order feasible plans into physically valid trajectories by integrating closed-form second-order feasibility analysis with reinforcement learning. • We provide an empirical evaluation across multiple hybrid planning domains, demonstrating that first-order plans are physically infeasible under second-order dynamics, and that our refinement approach consistently achieves second-order feasibility. Background Material Markov Decision Process To enable a reinforcement learning (RL) approach for the trajectory repair problem, we formulate it within the standard framework of a CSA-MDP (Sutton and Barto 2018), defined as the tuple ⟨S,A,P,R,γ⟩ ,A,P,R,γ . Where SS denotes the state space that may be infinite, and the action space A⊆ℝnA ^n is continuous. The transition dynamics are described by a probability density p(s′|s,a)p(s |s,a), and the reward function is R:S×A→RR:S×A . An agent interacts with the environment through a stochastic policy π(a∣s)π(a s), which induces a distribution over actions given a state. The objective in RL is to find a policy π∗π^* that maximizes the expected discounted return: J(π)=π[∑t=0∞γtR(st,at)|s0=s].J(π)=E_π\! [ _t=0^∞γ^t\,R(s_t,a_t)\, |\,s_0=s ]. Proximal Policy Optimization In continuous-action settings, policy-gradient methods such as Proximal Policy Optimization (PPO) (Schulman et al. 2017) are widely used due to their stability and scalability. PPO iteratively updates the policy to maximize J(π)J(π) while constraining the deviation from previous policies via a clipped surrogate objective. Let πθ _θ denote the current policy and πθold _ _old the policy before the update. The probability ratio is defined as: rt(θ)=πθ(at∣st)πθold(at∣st).r_t(θ)= _θ(a_t s_t) _ _old(a_t s_t). (2) The clipped surrogate objective is given by: LCLIP(θ)=t[min(rt(θ)A^t,clip(rt(θ),1−ϵ,1+ϵ)A^t)],L^CLIP(θ)=E_t [ (r_t(θ) A_t,\;clip (r_t(θ),1-ε,1+ε ) A_t ) ], (3) where A^t A_t denotes the advantage estimate and ϵε is a hyperparameter controlling the trust region. In this work, we employ PPO to optimize the plan-refinement agent, enabling consistent learning within the continuous action space of our model. Optimal Control For single-trajectory verification and reward engineering, we consider a standard optimal control formulation in continuous time. The objective is to minimize a performance criterion subject to system dynamics, as well as control and state constraints, with given initial and terminal conditions. While our focus will be on solving the minimum-time problem, we present the general form of the optimization problem here for completeness: minimizeu,tf u,t_fminimize ∫t0tfl(x,u)t _t_0^t_fl (x,u )dt (4) subject to x˙(t)=f(x,u) x(t)=f (x,u ) x(t0)=x0 x(t_0)=x_0 x(tf)=xf x(t_f)=x_f Cuu(t)≤U C_uu(t)≤ U t≥t0 t≥ t_0 Cx(t)≤X Cx(t)≤ X t≥t0. t≥ t_0. Here x∈ℝnx ^n is the state vector, x˙∈ℝn x ^n is the derivative function of x(t)x(t) with respect to time t, and u∈ℝmu ^m is the control input to the system, all are functions of time. The function f(x,u)f (x,u ) is the system dynamics, and U and X give the component-wise constraints on the control and state vector, respectively. Problem Formulation Hybrid Planning Problem Hybrid planning concerns decision problems that combine discrete choices with the evolution of continuous system variables. Since our refinement pipeline begins with plans generated by a hybrid planner, we adopt a problem specification consistent with the formalism of such plans. However, since we model a second-order system where acceleration is directly controlled (in contrast to velocity-controlled first-order models), we introduce the following modifications: • P is the set of propositions that defines the discrete part of the system. • V=⟨X,XC⟩V= X,X_C where X is the set of real-valued continuous variables that are governed by a set of first-order differential equations denoted as X˙=x˙1,…,x˙n X=\ x_1,…, x_n\, and XCX_C is the set of constraints operating on these variables. • A is the set of durative activities. Each activity is associated with two time points: its start and its end. Each time point can have both discrete and continuous conditions that must be met simultaneously at that exact time point. Additionally, each action has an invariant condition that must hold throughout its execution, and continuous effects that modify the values of continuous variables X during its execution. • I=⟨x0,p0⟩I= x_0,\,p_0 is the initial state, a complete assignment over the propositional variables p0=p(0)p_0=p(0) and state variables x0=x(0)x_0=x(0) at the beginning of the process. • G=⟨XG,PG⟩G= X_G,\,P_G is the goal set specifications, consisting of continuous end-of-plan constraints XGX_G and propositional goals PGP_G which have to be satisfied at the end of the plan. As such, G is a partial assignment of P and X. • C=⟨U,UC⟩C= U,\,U_C where U is the vector of control variables (accelerations), and UCU_C is the set of constraints operating on these variables. • J denotes the optimization criterion, which in this work is the makespan (total execution time) of the plan. Definitions Definition 1 (Event). An event is the term used to describe the switch between control modes. Events correspond to the start and end points of durative activities. Definition 2 (Hybrid plan skeleton). The plan skeleton s is the ordered list of events s=(e0,e1,…,en)s=(e_0,e_1,…,e_n), which are the start and end happenings of the durative actions. Note that the plan skeleton is merely the order of events without the assignment of all continuous variables (including timers), which are not concurrent, and separated by at least an ϵε time constant (Fox and Long 2003). A plan skeleton and assignment of all the continuous variables and durations (timers) is a hybrid grounded plan. Definition 3 (Continuous Assignment). A continuous assignment m specifies the continuous control inputs associated with each event in the hybrid plan skeleton. Given a skeleton s=(e0,e1,…,en)s=(e_0,e_1,…,e_n), the continuous assignment is defined as m=m(e0),m(e1),…,m(en)m=\\,m(e_0),\,m(e_1),\,…,\,m(e_n)\,\ where m(ei)m(e_i) denotes the continuous assignment to the state variables in eie_i. Definition 4 (hybrid grounded plan). A hybrid grounded plan is defined as a tuple ⟨,ut:ℝ→ℝm⟩ ,u_t:R ^m where: • T is the activity schedule, which denotes when each activity should start. T is given by a list of triplets ⟨a,τs,d⟩ a, _s,d where a is an activity, τs _s the activity start time, d the activity duration. • ut:[0,T]→ℝmu_t:[0,T] ^m is the control trajectory, which assigns values to all the inputs (control variables) at every time point between 0 and T. A valid hybrid grounded plan is a hybrid plan that satisfies all the constraints of the problem, defined by the bounds on the continuous components of the system and the preconditions of the durative actions, and reaches the goal set. Constraint Refinement We formulate the refinement problem as a constrained optimization problem built upon the optimal control formulation proposed in (Taitler et al. 2019). Given a hybrid grounded plan, which was produced by an off-the-shelf hybrid planner, let s=(e0,e1,…,en)s=(e_0,e_1,…,e_n) denote its plan skeleton and (t0,t1,…,tn)(t_0,t_1,…,t_n) the corresponding timestamps. Each consecutive pair of events induces a transition interval Ii=[ti,ti+1],i∈0,…,n−1,I_i=[t_i,\,t_i+1], i∈\0,…,n-1\, with duration Δti=ti+1−ti t_i=t_i+1-t_i. For every interval IiI_i, MTV computes the minimum physically achievable traversal time tmin,it_ ,i under the non-linear second-order dynamics x˙1(t) x_1(t) =x2(t), =x_2(t), (5) x˙2(t) x_2(t) =u(t)−12kx22(t), =u(t)- 12k\,x_2^2(t), where x=[x1,x2]⊤x=[x_1,x_2] is the state vector, composed of the position and velocity respectively, u(t)u(t) is the acceleration control input, and k is a drag coefficient. A hybrid grounded plan is therefore physically feasible if Δti≥tmin,i∀i∈0,…,n−1. t_i≥ t_ ,i ∀ i∈\0,…,n-1\. In the refinement setting considered in this work, the discrete plan skeleton s remains fixed and only the continuous assignment is modified. Let M(s)M(s) denote the set of all continuous assignments compatible with the event sequence s. Each m∈M(s)m (s) induces timestamps (t0,t1,…,tn)(t_0,t_1,…,t_n) and corresponding interval durations Δti(m)\ t_i(m)\. The refinement problem can therefore be formulated as the following constrained optimization problem: minm∈M(S) _m (S) J(m) J(m) s.t. Δti(m)≥tmin,i(m),∀i∈0,…,n−1. t_i(m)≥ t_ ,i(m), ∀ i∈\0,…,n-1\. Where J is the objective function that the off-the-shelf hybrid planner is designed to minimize. The aim is to compute a continuous assignment for the fixed hybrid plan skeleton such that all intervals satisfy the MTV-derived second-order feasibility bounds, while preserving the discrete-event structure and limiting the increase in makespan T. Methodology We address the refinement problem introduced in the previous section by constructing a learning-based framework whose goal is to find a continuous assignment for the fixed hybrid plan skeleton that induces a physically feasible hybrid grounded plan that is also makespan-optimized. The refinement problem is cast as an CSA-MDP. The state is the graph G=(V,E)G=(V,E) describing the current plan. The policy outputs continuous scaling factors that adjust velocity bounds for all motion segments simultaneously. After applying the action, an SOCP solver, that is formulated as the one in (Fernández-González et al. 2018), minimizes the plan makespan subject to the new bounds and original temporal constraints. The resulting trajectory is evaluated using MTV to compute a reward. We employ RL, specifically PPO, because the optimization landscape defined by the interaction between velocity bounds, the SOCP solver, and the closed-form MTV validation is highly non-linear and non-differentiable. Specifically, the objective’s gradient is discontinuous at the switching surfaces between the optimal control regimes, making stochastic policy gradients a suitable choice for navigating this non-convex space without subgradient calculus. The final output comprises the refined plan and the valid second-order MTV motion profiles. The refinement process consists of four stages (Fig. 1). (I) We obtain a first-order-feasible hybrid grounded plan from a hybrid planner; (I) We convert this plan into a structured graph that captures the spatial, temporal, and dynamical relationships while respecting the fixed event sequence; (I) Each transition interval is evaluated using the closed-form MTV computation to identify violations of the second-order feasibility constraints. Finally, (IV) a reinforcement-learning agent iteratively proposes adjustments to velocity bounds; each is transformed into a candidate trajectory via an SOCP solver and validated again by MTV. This iterative loop terminates after a pre-defined finite horizon. To preserve MDP stationarity without explicitly encoding the remaining timestep in the state, the agent optimizes an infinite-horizon discounted objective. Figure 1: The refinement framework. A hybrid planner generates a first-order plan, which is converted to a graph. A GNN-based RL agent adjusts velocity bounds, and an SOCP solver generates a candidate trajectory validated by MTV. Plan-to-Graph Representation The hybrid grounded plan returned by the hybrid planner is transformed into a graph G=(V,E)G=(V,E) that serves as the state representation for our MDP formulation. Each event eie_i becomes a node vi∈Vv_i∈ V with attributes capturing its position, timestamp, dwell interval, and regional memberships. Edge Construction. Every two consecutive events (ei,ei+1)(e_i,e_i+1) are mapped to a directed edge (vi,vi+1)∈E(v_i,v_i+1)∈ E encoding the continuous constraints governing the transition between these events, including the segment duration, the velocity bounds assigned by the planner, and the maximum-norm constraint. Consecutive events with negligible spatial displacement, i.e., a durative activity that constrains the movement to remain static, are merged to avoid near-zero-length segments; durations are stored as a dwell-time attribute of the node vi+1v_i+1. Node Velocity Estimation. As first-order planners treat velocity as a control variable, node velocities are not directly provided. To fill in the missing values and obtain a second-order state representation, we estimate the velocity at each intermediate node vi∈Vv_i∈ V by taking a duration-weighted average of its incoming and outgoing segment velocities. Let Δti−1 t_i-1 and Δti t_i denote the durations of the consecutive events (vi−1,vi)(v_i-1,v_i) and (vi,vi+1)(v_i,v_i+1), and let vx(⋅)v_x(·) and vy(⋅)v_y(·) be their velocities along each axis. Then vi,vj=Δti−1vj(vi−1,vi)+Δtivj(vi,vi+1)Δti−1+Δti,j∈x,y.v_i,v_j= t_i-1\,v_j(v_i-1,v_i)+ t_i\,v_j(v_i,v_i+1) t_i-1+ t_i, j∈\x,y\. For the terminal node, we set vvx=0v_v_x=0 and vvy=0v_v_y=0. To preserve the direction of motion along the trajectory, we determine the sign of each velocity component based on the displacement between consecutive nodes. Specifically, for each intermediate node viv_i, we compute the differences between (vi,x,vi,y)(v_i,x,v_i,y) and (vi+1,x,vi+1,y)(v_i+1,x,v_i+1,y), and assign the final velocities as vi,vx=sign(vi+1,x−vi,x)⋅vi,vxv_i,v_x=sign(v_i+1,x-v_i,x)· v_i,v_x and vi,vy=sign(vi+1,y−vi,y)⋅vi,vyv_i,v_y=sign(v_i+1,y-v_i,y)· v_i,v_y. Graph-based State Representation. The graph is processed by a GNN that encodes spatial, temporal, and regional information into latent embeddings for the policy and value function. Each node v∈Vv∈ V is represented by 7 scalar features and a region embedding: v=(x,y,vx,vy,t,τlow,τhigh,enc),h_v=(x,y,v_x,v_y,t,\; _low, _high,\;r_enc), where τlow _low and τhigh _high denote the lower and upper bounds on the dwell time, respectively, and encr_enc denotes a learned region embedding. Region information is inherently heterogeneous; to enable uniform processing, all regions are encoded using a unified representation scheme. Circles and rectangles are parameterized as [cx,cy,rx,ry,type][c_x,c_y,r_x,r_y,1_type], while polygons are encoded using a Deep Sets (Zaheer et al. 2017) architecture to ensure permutation invariance across vertices. When multiple regions of the same type are present, their embeddings are averaged. When regions of different types are present, their embeddings are concatenated and passed through an intersection layer, ensuring that the resulting representation satisfies the requirement that each trajectory point satisfies all associated region constraints. Each edge (vi,vi+1)∈E(v_i,v_i+1)∈ E carries: (vi,vi+1)=(vxmin,vxmax,vymin,vymax,bnorm,dmin,dmax)h_(v_i,v_i+1)= aligned (&v_x ,\,v_x ,\;v_y ,\,v_y ,b_norm,d_ ,\,d_ ) aligned Here, vxmin,vxmax,vymin,vymaxv_x ,\,v_x ,\;v_y ,\,v_y are per-axis velocity bounds, bnormb_norm is the maximum velocity norm bound, and dmin,dmaxd_ ,\,d_ are the duration bounds of the durative activity. Minimum-Time Validation MTV is a feasibility analysis method designed to verify whether a continuous transition between two states can be executed under non-linear second-order dynamics (5) with bounded acceleration, bounded velocity, and quadratic drag (Taitler et al. 2019). A state is defined to be a vector of [x1,x2]⊤[x_1,x_2] where x1x_1 represents the position and x2x_2 represents the velocity of the agent. The problem is formulated as an optimal control problem as in (4), specifically a minimum-time optimal control problem defined as follows: minimizeu,tf u,t_fminimize ∫0tf1⋅t _0^t_f1· dt (6) subject to x˙1(t)=x2(t), x_1(t)=x_2(t), x˙2(t)=u(t)−12kx22(t), x_2(t)=u(t)- 12k\,x_2^2(t), |u(t)|≤U,|x2(t)|≤V,t≥t0, |u(t)|≤ U, |x_2(t)|≤ V, t≥ t_0, x1(t0)=x10,x2(t0)=x20, x_1(t_0)=x_10, x_2(t_0)=x_20, x1(tf)=x1f,x2(tf)=x2f. x_1(t_f)=x_1f, x_2(t_f)=x_2f. Here, U is the maximum acceleration, V the maximum allowable velocity, and k is a drag coefficient. Given the initial [x10,x20]⊤[x_10,x_20] and terminal states [x1f,x2f]⊤[x_1f,x_2f] , MTV computes the minimum physically achievable traversal time tmint_ for the segment. Intuitively, tmint_ represents the fastest motion permitted by the agent’s acceleration, velocity, and drag limits. If the planner assigns a duration d<tmind<t_ , the segment is physically impossible, even though it may appear consistent under a first-order model. MTV admits closed-form expressions for tmint_ , depending on whether the velocity bound V is reached. The resulting motion is either Bang-Constant-Bang or Bang-Bang. Bang-Constant-Bang (BCB). When the optimal motion reaches the velocity bound V, the solution takes a Bang-Constant-Bang (accelerate-cruise-decelerate) form. This occurs when V V <2Uk,Δxa+Δxd<x1f−x10, < 2Uk, x_a+ x_d<x_1f-x_10, (7) Δxa x_a =1kln(2kU−(x20k)22kU−(Vk)2), = 1k \! ( 2kU-(x_20k)^22kU-(Vk)^2 ), Δxd x_d =2kln(2kU+(Vk)2(2kU+k2Vx2f)2+2k3U(V−x2f)2). = 2k \! ( 2kU+(Vk)^2 (2kU+k^2Vx_2f)^2+2k^3U(V-x_2f)^2 ). The segment duration is the sum of three phases: Δt1 t_1 =12kUln(2kU−x20k2kU+x20k⋅2kU+Vk2kU−Vk), = 1 2kU \! ( 2kU-x_20k 2kU+x_20k· 2kU+Vk 2kU-Vk ), (8) Δt2 t_2 =x1f−x10−Δxa−ΔxdV, = x_1f-x_10- x_a- x_dV, Δt3 t_3 =2kUtan−1(2k3U(V−x2f)2kU+x2fk2V), = 2kU\, ^-1\! ( 2k^3U(V-x_2f)2kU+x_2fk^2V ), tmin t_ =Δt1+Δt2+Δt3. = t_1+ t_2+ t_3. Bang-Bang (B). If the velocity bound is not reached (the conditions in (7) do not hold), the optimal control is Bang-Bang (accelerate-decelerate). The peak velocity V~ V is the positive root of the quadratic aV~4+bV~2+c a V^4+b V^2+c =0,V~=−b+b2−4ac2a, =0, V= -b+ b^2-4ac2a, (9) and the minimum time is tmin t_ =12kUln(2kU−x20k2kU+x20k⋅2kU+V~k2kU−V~k) = 1 2kU \! ( 2kU-x_20k 2kU+x_20k· 2kU+ Vk 2kU- Vk ) (10) +2kUtan−1(2k3U(V~−x2f)2kU+x2fk2V~). + 2kU\, ^-1\! ( 2k^3U( V-x_2f)2kU+x_2fk^2 V ). Extension to 2D. Since there is no higher-order dynamic than two, and no external coupling force (Taitler et al. 2022), and in line with the standard assumptions made by common off-the-shelf hybrid planners (Fernández-González et al. 2018), we treat the two axes as decoupled, with the motion constrained by the axis requiring the longer duration. The shorter axis is automatically constrained by the longer axis, resulting in a BCB profile by definition. Consequently, the two-dimensional validation problem decomposes into two independent MTV computations. A segment is considered physically feasible only if both axes individually satisfy their respective dynamic bounds: tmin2D=maxtminx,tminy.t_ ^2D= \t_ ^x,\;t_ ^y\. Analytically, this decoupling constructs a conservative inner approximation of the dynamically feasible control space, guaranteeing strict satisfaction of the maximum-norm control constraints (‖u(t)‖≤U||u(t)||≤ U). While MTV is a powerful feasibility checker, it is strictly a validator: it cannot modify or repair a hybrid plan that violates second-order dynamics. In our framework, MTV quantifies the feasibility gap between the first-order hybrid plan and the true physical dynamics; this gap serves as the learning signal for our reinforcement-learning refinement method. CSA-MDP Formulation The refinement loop is modeled as a CSA-MDP: ⟨S,A,P,R,γ⟩ ,A,P,R,γ State space. Each state s∈Ss is the complete assignment of the continuous variables at the event points of the plan skeleton represented by a graph G=(V,E)G=(V,E) produced by the plan-to-graph conversion. Action space. The space of possible changes to the velocity bounds between the plan skeleton events is represented by a continuous matrix ∈[0,1]|E|×2a_t∈[0,1]^|E|× 2 produced by a sigmoid-squashed Gaussian policy: ∣st∼sigmoid((μ(st),σ(st))).a_t s_t (N(μ(s_t),σ(s_t))). Each row ,=(at,i,x,at,i,y)∈[0,1]2a_t,i=(a_t,i,x,a_t,i,y)∈[0,1]^2, associated with edge i∈Ei∈ E, specifies independent refinements to the velocity bounds along the x- and y-axes. Each entry of at,ia_t,i represents the percentage of decrease in velocity per axis. While this strictly monotonic contraction forces a conservative inner-approximation search, the parameterized GNN policy amortizes this optimization cost by generalizing across the training distribution. For each edge i∈Ei∈ E, let vx,t,max(i)v_x,t, ^(i) and vy,t,max(i)v_y,t, ^(i) denote its current velocity bounds at time t For each action component at,i,j∈[0,1]a_t,i,j∈[0,1] the update of the velocity bounds are as follows: vj,t+1,max(i)=at,i,j∗vj,t,max(i),vj,t+1,min(i)=−vj,t+1,max(i)v_j,t+1, ^(i)=a_t,i,j*v_j,t, ^(i), v_j,t+1, ^(i)=-v_j,t+1, ^(i) Transition dynamics. The transition function is defined as follows: if the SOCP solver returns a first-order feasible solution, the system transitions from sts_t to a new state st+1s_t+1. Otherwise, the system transitions to a terminal state sTs_T. This occurs when the RL agent has reduced the velocity beyond a point where further reductions no longer affect SOCP feasibility. Reward Function. The reward is defined based on the feasibility of the solution returned by the SOCP solver. If the SOCP solver fails to produce a feasible solution, no new continuous assignment is generated, the environment transitions to a terminal state, and the agent receives a reward of −1-1. If the SOCP solver produces a first-order feasible solution, a new continuous assignment m is associated with the hybrid plan skeleton. For each edge i, we evaluate second-order feasibility using MTV. Let Δti t_i denote the duration assigned by the SOCP for edge i, and let tmin(2)(i)t_ ^(2)(i) denote the minimum traversal time under second-order dynamics. We define the feasibility gap as gi=min(0,Δti−tmin(2)(i)),g_i= \! (0,\; t_i-t_ ^(2)(i) ), so that negative values indicate second-order violations. The corresponding per-edge reward is ri=gitmin(2)(i)r_i= g_it_ ^(2)(i) and the final immediate reward is rgap=∑i∈E1|E|rir_gap= _i∈ E 1|E|r_i. The agent receives this feasibility-gap reward only when the solution is first-order feasible but violates second-order dynamics. If the solution is also second-order feasible, meaning gi=0,∀i∈Eg_i=0,∀~i∈ E, the reward instead reflects the change in makespan relative to the initial plan. Let TplannerT_planner denote the makespan of the original hybrid plan and TSOCPT_SOCP the makespan after refinement. The reward in this case is defined as TplannerTSOCP T_plannerT_SOCP. Note that the feasibility-gap reward is non-positive, whereas the makespan-based reward is positive. Although this introduces a structural discontinuity exactly at the feasibility boundary, the stochasticity of the policy smoothly approximates the expected return J(π)J(π) for reliable policy gradient estimation. The final immediate reward per step function is then: rt r_t =−1,if SOCP is infeasible,rgap,if SOCP is feasible and∃i∈E:gi<0,TplannerTSOCP,if gi=0,∀i∈E. = cases-1,&if SOCP is infeasible,\\[6.0pt] r_gap,&if SOCP is feasible and~∃ i∈ E:\;g_i<0,\\[6.0pt] T_plannerT_SOCP,&if g_i=0,\ ∀ i∈ E. cases (11) Training Procedure In a continuous control problem, a known issue is how to slow down and constrain the learning to the current knowledge already obtained as learning progresses. This has been studied in various RL algorithms (Taitler and Shimkin 2017; Farsang and Szegletes 2021), and here we employ clip decay as the suitable remedy when using PPO (Farsang and Szegletes 2021). The clip ratio decay used in this work follows the linear schedule proposed by (Farsang and Szegletes 2021). Let K denote the total number of updates, k the current update, and ϵ0 _0 the initial PPO clip ratio. The decayed clip ratio is defined as: ϵk=K−kKϵ0. _k= K-kK\, _0. Since this schedule reduces the clip ratio from ϵ0 _0 to 0, which may overly restrict learning in later stages, we introduce a minimum bound ϵmin _ . The final update rule is therefore: ϵk=max(ϵmin,K−kKϵ0). _k= \! ( _ ,\; K-kK\, _0 ). All models were trained using a shared-encoder actor-critic PPO architecture with graph-based state encoding across 5 random seeds (see Table 1 for full hyperparameters). The network consists of three input encoders, a shared GNN, and separate actor and critic heads. The Region Encoder processes geometric features via parallel Linear(5,16)Linear(5,16) and Linear(2N,16)+ReLULinear(2N,16)+ReLU layers, followed by Linear(16,16)Linear(16,16) when multiple region types are present. The Node Encoder concatenates node and region features and maps them through Linear(23,32)Linear(23,32), while the Edge Encoder applies Linear(9,32)Linear(9,32) to edge features. These representations are concatenated and passed through a GNN with two message-passing layers, Linear(96,32)+TanhLinear(96,32)+Tanh and Linear(64,32)+TanhLinear(64,32)+Tanh, producing 32-dimensional node embeddings. The critic head applies mean pooling followed by Linear(32,32)+Tanh+Linear(32,1)Linear(32,32)+Tanh+Linear(32,1), while the actor head uses Linear(64,32)+Tanh+Linear(32,4)Linear(64,32)+Tanh+Linear(32,4) to output Gaussian policy parameters (see Fig. 2). Both heads use orthogonal initialization. Figure 2: Shared-encoder actor-critic architecture. Region, node, and edge features are encoded separately and concatenated before being processed by a message-passing GNN. The resulting node embeddings are used by separate actor and critic heads to produce Gaussian policy parameters and value estimates. Table 1: PPO Hyperparameters Hyperparameter Value Hyperparameter Value Learning Rate 10−410^-4 Target KL Div 0.015 Clip Ratio (ϵ0 _0) 0.2 Discount (γ) 0.99 Min Clip Ratio (ϵmin _ ) 0.05 GAE λ 0.95 Batch Size 16 Horizon 8 Entropy Coeff. 0.01 Rollout Size 64 Value Loss Coeff. 0.5 Epochs 1 Max Grad Norm 0.5 Episodes 15,000 Optimizer Adam Seeds 1,2,3,4,5 Experiments We evaluate our method across four hybrid planning domains. Three domains were originally used in the evaluation of Scotty (Fernández-González et al. 2018), and one domain originates from the 2023 International Planning Competition’s numeric track (Taitler et al. 2024). Each training job was allocated an NVIDIA L40 GPU, 3 vCPUs, and 8 GiB of RAM. Initial hybrid plans were generated using the off-the-shelf planner Scotty (Fernández-González et al. 2018). Second-order dynamics parameters were set to U=10U=10, V=10V=10, and k=0.05k=0.05, in alignment with (Taitler et al. 2019). AUV-Domains. The AUV-2D and Norm-AUV-2D domains model underwater sampling missions in which an autonomous underwater vehicle (AUV) must visit and sample from specified regions. The former does not impose maximum-norm velocity constraints, whereas the latter enforces such bounds, resulting in more restrictive dynamics. OnAir-Refuel. This domain models an aerial refueling mission involving a jet and a tanker. Since multi-agent dynamics are outside the scope of this work, we simplify the domain by forcing the tanker to move along a fixed straight-line path between two refueling regions. This yields an equivalent single-agent setting compatible with our framework. Sailing. The Sailing domain, from the 2023 IPC, models a vessel navigating between polygonal regions under wind-dependent motion. The domain also includes tight temporal constraints and region-based goals. We use this domain primarily to test refinement on a single-axis motion model while handling polygonal constraints, as motion disturbances are not part of the scope of this work. Baseline. We compare our method against a conservative baseline given by a constant contraction policy π(s)=a¯π(s)= a where a¯∈[0,1] a∈[0,1] is applied uniformly at each refinement step to the velocity bounds of all edges and both axes. We evaluate a¯∈0.9, 0.995 a∈\0.9,\,0.995\, corresponding to per-step reductions of 10% and 0.5%, respectively. More aggressive contraction reaches feasibility in fewer iterations but tends to produce more conservative, higher-makespan solutions, whereas finer contraction may yield tighter feasible solutions at the expense of additional iterations. Figure 3: Training curves across domains. The agent consistently improves its return and reaches a stable regime. Results Table 2 summarizes the performance of the refined solutions. Enforcing second-order dynamics renders all initial plans from the first-order planner physically infeasible (0% success). In contrast, our refinement framework recovers feasibility in 100% of cases, bridging the gap between symbolic planning and realizable execution. This comes at the cost of increased makespan (ratios >1>1), reflecting the underestimation inherent in first-order models. The resulting makespan thus provides a strict upper bound on the global optimum of the underlying MINLP. Fig. 3 reports the evolution of the average episodic return as a function of episodes across all evaluated domains. It also marks when the RL agent transitions into the physically feasible region and begins optimizing the hybrid plan’s makespan relative to the initial plan. Across all domains, the episodic return shows a clear upward trend, indicating consistent improvement of the refinement policy. In the Norm-AUV-2D and AUV-2D domains, the agent achieves near-monotonic return growth. In the Sailing domain, we observe fast convergence, reaching a stable plateau within the first 2,000 episodes. Finally, in the OnAir-Refuel domain, the return increases more gradually as refinement progresses. Fig. 4 reports the makespan achieved by our refinement method (blue, mean ± std) compared to constant baselines with uniform velocity contraction factors of 10% and 0.5% per step (orange and green, respectively), across all evaluated instances and domains. The refined solutions consistently achieve lower makespans than both baselines, demonstrating systematic improvements in execution efficiency. Notably, the finer-grained baseline (0.5%) yields only marginal improvement over the coarser 10% baseline, with an average makespan reduction of just 3.24% across domains, while requiring, on average, 1784.8% more refinement steps to reach feasibility. In contrast, our approach leverages a structured MDP formulation to perform segment-wise, physically informed adjustments, yielding more globally optimized, physically consistent solutions. Figure 4: Per-instance makespan comparison. Blue points show refined makespan with ±1± 1 std error bars. Orange and green markers denote the baseline makespan with a¯=0.9,0.995 a=\0.9,0.995\. Table 2: Performance statistics. We report the number of problem instances and the average makespan ratio of the final refined feasible solution relative to the initial infeasible plan. Values are mean ± std. dev. Initial plan feasibility was 0% for all domains; refined plan feasibility was 100%. Domain Instances Makespan Ratio Auv 2D 20 1.20±0.0081.20± 0.008 Norm Auv 2D 20 1.23±0.0061.23± 0.006 OnAir Refuel 10 1.15±0.0071.15± 0.007 Sailing 10 1.14±0.0061.14± 0.006 Conclusions and Future Work We addressed the gap between hybrid temporal planning under first-order dynamics and the physical feasibility requirements of second-order systems. Empirically, we demonstrated that all initial plans generated by an off-the-shelf hybrid planner are physically infeasible under second-order dynamics, highlighting the severity of the modeling gap. In contrast, our refinement approach recovers feasibility in all cases while maintaining competitive makespan performance, establishing the framework as an effective bridge between symbolic planning outputs and physically valid execution. However, the method assumes disturbance-free, decoupled dynamics and no time windows – assumptions that should be relaxed in realistic settings. Future work will consider problems with time-window constraints and extend the framework to timing-robust settings with coupled axes and variability in activity durations, further bridging the gap between planning and real-world execution. References J. Chen, B. C. Williams, and C. Fan (2021) Optimal mixed discrete-continuous planning for linear hybrid systems. In International Conference on Hybrid Systems: Computation and Control., p. 8:1–8:12. Cited by: Introduction. A. J. Coles, A. I. Coles, M. Fox, and D. Long (2012) COLIN: planning with continuous linear numeric change. Journal of Artificial Intelligence Research 44, p. 1–96. Cited by: Introduction. E. Denenberg and A. J. Coles (2019) Mixed discrete continuous non-linear planning through piecewise linear approximation. In International Conference on Automated Planning and Scheduling, p. 137–145. Cited by: Introduction. M. Farsang and L. Szegletes (2021) Decaying clipping range in proximal policy optimization. In International Symposium on Applied Computational Intelligence and Informatics, p. 521–526. Cited by: Training Procedure. E. Fernández-González, E. Karpas, and B. C. Williams (2015) Mixed discrete-continuous heuristic generative planning based on flow tubes. In International Joint Conference on Artificial Intelligence, p. 1565–1572. Cited by: Introduction. E. Fernández-González, B. C. Williams, and E. Karpas (2018) ScottyActivity: mixed discrete-continuous planning with convex optimization. Journal of Artificial Intelligence Research 62, p. 579–664. Cited by: Introduction, Minimum-Time Validation, Methodology, Experiments, Experiments. M. Fox and D. Long (2003) PDDL2.1: an extension to PDDL for expressing temporal planning domains. Journal of Artificial Intelligence Research 20, p. 61–124. Cited by: Definitions. M. S. Lobo, L. Vandenberghe, S. Boyd, and H. Lebret (1998) Applications of second-order cone programming. Linear algebra and its applications 284 (1-3), p. 193–228. Cited by: Introduction. J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov (2017) Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347. Cited by: Proximal Policy Optimization. R. S. Sutton and A. G. Barto (2018) Reinforcement learning: an introduction. MIT press. Cited by: Markov Decision Process. A. Taitler, R. Alford, J. Espasa, G. Behnke, D. Fišer, M. Gimelfarb, F. Pommerening, S. Sanner, E. Scala, D. Schreiber, J. Segovia-Aguas, and J. Seipp (2024) The 2023 international planning competition. AI Magazine 45 (2), p. 280–296. Cited by: Experiments. A. Taitler, I. Ioslovich, E. Karpas, and P. Gutman (2019) Minimum time optimal control of second order system with quadratic drag and state constraints. In Conference on Decision and Control, p. 523–528. Cited by: Introduction, Constraint Refinement, Minimum-Time Validation, Experiments. A. Taitler, I. Ioslovich, E. Karpas, and P. Gutman (2022) Time optimal control of a non-linear surface vehicle subject to disturbances. IFAC Journal of Systems and Control 21, p. 100195. External Links: ISSN 2468-6018, Document, Link Cited by: Minimum-Time Validation. A. Taitler and N. Shimkin (2017) Learning control for air hockey striking using deep reinforcement learning. In International Conference on Control, Artificial Intelligence, Robotics & Optimization, p. 22–27. Cited by: Training Procedure. M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. R. Salakhutdinov, and A. J. Smola (2017) Deep sets. Advances in neural information processing systems 30. Cited by: Plan-to-Graph Representation. J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun (2020) Graph neural networks: a review of methods and applications. AI open 1, p. 57–81. Cited by: Introduction.