From Kinematics to Dynamics: Learning to Refine Hybrid Plans for Physically Feasible Execution

1. Problem Statement

The paper addresses a critical gap in robotic planning: the discrepancy between hybrid temporal planning (which combines discrete logic with continuous constraints) and physical reality.

• The Core Issue: Existing hybrid planners (e.g., Scotty) typically model robot motion using first-order dynamics (velocity control, $\dot{x} = v$). This allows for tractable optimization (e.g., Second-Order Cone Programs - SOCP) but ignores second-order dynamics (acceleration control, $\ddot{x} = u$), such as bounded acceleration, drag, and inertia.
• The Consequence: A plan generated by a first-order planner often appears valid but is physically infeasible when executed by a real robot. The robot cannot instantaneously change velocity or accelerate infinitely, leading to actuator saturation, large tracking errors, and potential instability.
• The Challenge: Even if the high-level action sequence (the "skeleton") is fixed, refining the continuous trajectory to satisfy second-order constraints is a bi-level optimization problem. Existing planners cannot revise their first-order models to enforce these stricter physical constraints without breaking the discrete logic.

2. Methodology

The authors propose a neuro-symbolic refinement framework that bridges this gap using Reinforcement Learning (RL) to adjust a first-order plan into a physically feasible second-order trajectory.

A. Problem Formulation

The refinement task is cast as a Continuous-State and Action Markov Decision Process (CSA-MDP):

• Input: A "first-order feasible" hybrid grounded plan generated by an off-the-shelf planner (e.g., Scotty).
• Goal: Modify the continuous variables (specifically velocity bounds) to satisfy second-order dynamics while minimizing the increase in total execution time (makespan).
• State Representation ($S$): The plan is converted into a Graph ($G=(V, E)$) using a "Plan-to-Graph" module.
  • Nodes: Represent events (start/end of actions) with features like position, estimated velocity, time, and region constraints.
  • Edges: Represent transitions between events, encoding velocity bounds and duration constraints.
  • Processing: A Graph Neural Network (GNN) encodes spatial, temporal, and regional information into latent embeddings.
• Action Space ($A$): The RL agent outputs continuous scaling factors (between 0 and 1) to contract the velocity bounds for each motion segment.
  • Action: $a_t \in [0, 1]^{|E| \times 2}$, representing the percentage decrease in velocity limits for X and Y axes.
• Transition Dynamics:
  1. The agent proposes new velocity bounds.
  2. An SOCP solver computes the optimal trajectory (minimizing makespan) under these new bounds.
  3. Minimum-Time Validation (MTV) checks if the resulting trajectory satisfies second-order dynamics (acceleration limits, drag).
• Reward Function ($R$):
  • If SOCP fails: $-1$.
  • If SOCP succeeds but MTV fails (violation exists): A negative reward proportional to the "feasibility gap" (difference between assigned time and minimum physically possible time).
  • If both SOCP and MTV succeed: A positive reward based on the ratio of the original makespan to the refined makespan (encouraging efficiency).

B. Key Components

1. Minimum-Time Validation (MTV): A closed-form analytical method derived from optimal control theory. It calculates the minimum time ($t_{min}$) required to traverse a segment given non-linear second-order dynamics (including drag: $\dot{v} = u - \frac{1}{2}k v^2$). It determines if a segment is physically possible (Bang-Bang or Bang-Constant-Bang profiles).
2. Reinforcement Learning Algorithm: The authors use Proximal Policy Optimization (PPO). PPO is chosen because the optimization landscape (interaction between velocity bounds, SOCP solver, and MTV) is highly non-linear and non-differentiable, making gradient-based methods unsuitable.
3. Training Strategy: The clip ratio in PPO is decayed over time to allow for broad exploration initially and fine-grained exploitation later.

3. Key Contributions

1. CSA-MDP Formulation: The first formulation of plan refinement as a continuous-state/action MDP over a graph-based representation, enabling structured reasoning over temporal, spatial, and dynamical constraints.
2. Neuro-Symbolic Framework: An automated pipeline that integrates symbolic planning (hybrid planner), analytical validation (MTV), and neural learning (GNN + PPO) to transform infeasible first-order plans into physically valid second-order trajectories.
3. Empirical Validation: Demonstration that standard first-order planners produce plans that are 100% physically infeasible under second-order dynamics, and that the proposed refinement method recovers feasibility in 100% of cases.

4. Experimental Results

The method was evaluated across four domains: AUV-2D, NORM-AUV-2D (underwater), OnAir-Refuel (aerial), and Sailing.

• Feasibility Recovery:
  • Initial plans from the hybrid planner: 0% feasible under second-order dynamics.
  • Refined plans: 100% feasible.
• Makespan Efficiency:
  • The refinement process inevitably increases the total execution time (makespan) because first-order models underestimate the time needed for acceleration/deceleration.
  • Makespan Ratios: The refined plans took approximately 14% to 23% longer than the initial infeasible plans (e.g., 1.20x for AUV-2D, 1.23x for Norm-AUV-2D). This ratio represents a strict upper bound on the global optimum for the underlying Mixed-Integer Non-Linear Programming (MINLP) problem.
• Comparison with Baselines:
  • Compared against "Constant Contraction" baselines (uniformly reducing velocity by 10% or 0.5% per step).
  • The RL approach consistently achieved lower makespans than the baselines.
  • The RL agent reached feasible solutions significantly faster (fewer iterations) than the fine-grained baseline (0.5% reduction), which required ~17x more steps for marginal gains.
• Convergence: The episodic return showed consistent improvement across all domains, with the agent successfully learning to balance feasibility constraints with execution efficiency.

5. Significance and Future Work

• Bridging the Gap: This work provides a practical solution to the "reality gap" in robotics, allowing high-level symbolic planners to be used in real-world scenarios where physical dynamics (acceleration, drag) are critical.
• Scalability: By using a GNN to generalize across different plan structures, the method avoids re-solving the complex optimization problem from scratch for every new mission.
• Limitations & Future Directions:
  • Current assumptions include decoupled axes (X and Y dynamics treated independently) and disturbance-free environments.
  • Future work aims to handle coupled dynamics, time-window constraints, and activity duration variability to make the framework robust for complex, real-world multi-agent systems.

In summary, the paper presents a robust, learning-based refinement layer that ensures robotic plans are not just logically sound but also physically executable, effectively translating kinematic abstractions into dynamic reality.