Reachability-Augmented Dual Dynamic Programming for Optimal Path Parameterization

Yunan Wang, Jizhou Yan, Chuxiong Hu, and Zeyang Li · 2026

Read Reachability-Augmented Dual Dynamic Programming for Optimal Path Parameterization by Yunan Wang, Jizhou Yan, Chuxiong Hu, and Zeyang Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-19089.txt.

Introduction

Yunan Wang and three colleagues propose reachability-augmented dual dynamic programming for planning trajectories along a path under motion constraints. Classical dual dynamic programming assumes complete recourse; the new method uses backward reachable sets instead, building value cuts and trial paths only inside them. The authors prove global optimality for convex problems and KKT convergence for non-convex ones, with versions for second- and third-order cases. Experiments show objective values matching convex baselines while cutting time by 28.6 times for second-order and 5.8 times for third-order problems.

Catalog record

CREATORYunan Wang, Jizhou Yan, Chuxiong Hu, and Zeyang Li
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE124212
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.19089

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Reachability-Augmented Dual Dynamic Programming for Optimal Path Parameterization Yunan Wang, Jizhou Yan, Chuxiong Hu, and Zeyang Li Abstract Optimal path parameterization (OPP) is a fundamental problem for planning trajectories along a prescribed geometric path under kinodynamic constraints and task-dependent objectives. While time-optimal path parameterization (TOPP) minimizes traversal time, its saturating states and controls may induce vibration and tracking errors, which can be mitigated by introducing smoothness objectives. However, a key capability gap remains in OPP: feasibility guarantees, general-objective optimality certificates, and computational efficiency are difficult to achieve simultaneously in a unified framework, especially for third-order OPP (OPP3) with non-convex constraints. This paper proposes reachability-augmented dual dynamic programming (RDDP), a state-grid-free and objective-aware dynamic programming (DP) framework for OPP. The key idea is to replace the relatively complete recourse assumption used in classical dual DP (DDP) with OPP-specific backward reachable sets, and then generate both value-function cuts and trial trajectories only inside these reachable sets. For convex and non-convex OPP, we prove global optimality and Karush-Kuhn-Tucker convergence of RDDP under OPP-specific conditions, respectively. Efficient instantiations are developed for second-order OPP (OPP2) and OPP3. Experiments show that RDDP achieves objective values comparable to convex-optimization baselines while reducing computation time by 28.6 times for OPP2 and 5.8 times for OPP3. RDDP also achieves faster convergence than grid-based DP. Compared with reachability-analysis methods, RDDP retains the reachability mechanism while replacing local maximum-control propagation with value-function-guided control selection, thereby enabling objectives beyond traversal time. In summary, RDDP addresses a key capability gap in OPP by unifying certifiable general-objective optimization, reachability-based feasibility preservation, and online-compatible low-dimensional DP computation in a single OPP framework. I Introduction Optimal path parameterization (OPP) is a fundamental problem in robotics and optimal control. It aims to find an optimal time parameterization of a given geometric path under kinodynamic constraints and task-dependent objectives. Originating from the study in the 1980s [ 1 , 2 , 3 ] , OPP has been widely applied in various robotic systems, such as manipulators [ 4 , 5 , 6 ] , humanoid robots [ 7 , 8 ] , and manufacturing systems [ 9 , 10 ] . When the objective is to minimize the traversal time, OPP reduces to the well-known time-optimal path parameterization (TOPP) problem [ 7 ] . According to the Pontryagin’s maximum principle (PMP) [ 11 ] , the optimal control of TOPP is bang-singular-bang, which pushes the velocity, acceleration, torque, and jerk constraints to their limits. Despite the high motion efficiency, such constraint-saturating trajectories might induce undesirable behaviors such as vibration and tracking error in some scenarios. By trading traversal time with task-dependent criteria such as energy consumption and smoothness [ 4 , 12 ] , general objectives can smooth the motion profile while maintaining high motion efficiency. Our real-world experiment provides one example of this tradeoff: compared with pure TOPP, the time-thermal objective increases the traversal time by only 0.15% while reducing the normalized total variation of feedback acceleration by 87.7%. For online robotic applications, an ideal OPP solver should satisfy four requirements simultaneously: 1. Feasibility : The solver should guarantee the feasibility of the generated trajectory under state and mixed state-control constraints, which are essential for the safety and reliability of robotic systems. 2. General-objective optimality : The solver should provide appropriate optimality certificates for general objectives. 3. Efficiency : The solver should be computationally efficient enough for online motion generation. 4. High-order capability : The solver should be able to handle higher-order systems, especially third-order OPP (OPP3) which involves non-convex jerk constraints. To the best of the authors’ knowledge, it remains challenging to simultaneously achieve all the above properties within a unified framework. This key capability gap is particularly pronounced for OPP3 due to non-convexity. TABLE I : Comparison of different classes of OPP solvers. Method Order Objective Scope Optimality Feasibility Efficiency NI [ 13 ] 2 ✗ (Time only) ✓ (Global) ✓ High CO [ 4 , 8 ] 2 ✓ (General) ✓ (Global) ✓ Low DP [ 3 ] 2 ✓ (General) ✓ (Grid-optimal) ✓ Medium RA [ 7 ] 2 ✗ (Time only) ✓ (Global, without zero-inertia points) ✓ High RDDP (Ours) 2 ✓ (General) ✓ (Global) ✓ Medium–High NI [ 14 ] 3 ✗ (Time only) ✗ ✗ N/A CO [ 5 , 9 ] 3 ✓ (General) ✓ (KKT convergence) ✓ Low DP [ 3 ] 3 ✓ (General) ✓ (Grid-optimal) ✓ Extremely Low Greedy DP [ 12 ] 3 ✓ (General) ✗ ✗ Medium RA [ 15 ] 3 ✗ (Time only) ✓ (Empirically near optimal) ✓ High RDDP (Ours) 3 ✓ (General) ✓ (KKT convergence) ✓ Medium I-A Related Works I-A 1 OPP solvers The study of OPP, including TOPP, can be categorized into three main classes: numerical integration (NI), convex optimization (CO), and dynamic programming (DP). In this paper, we classify the recently developed reachability analysis (RA) approaches as DP methods, as they involve the backward propagation of reachable sets in a DP manner. As the earliest approaches to TOPP [ 2 ] , NI methods exploit the bang-singular-bang structure of the optimal control induced by PMP and reduce the decision space to a binary choice between maximum- and minimum-control arcs. As a result, NI methods are highly efficient for TOPP2, where time-optimality is guaranteed by the consistent maximum property of the optimal solution. Despite numerical instability issues induced by the dynamic singularity [ 16 ] , some robust TOPP2-NI implementations have been developed [ 13 ] . However, a complete extension of NI methods to TOPP3 is still lacking [ 14 ] . NI methods also do not naturally extend to general-objective OPP, as the bang-singular-bang structure no longer holds. This reveals the objective-agnostic nature of NI methods. CO approaches provide the strongest generic optimality certificates among existing OPP solvers. The standard optimization formulations for second-order OPP (OPP2) and OPP3 were established in [ 4 ] and [ 5 ] , respectively. These formulations are highly expressive [ 8 ] . For convex OPP, CO methods can guarantee global optimality; for non-convex OPP, CO methods can obtain Karush-Kuhn-Tucker (KKT) solutions based on the sequential convex programming (SCP) framework [ 17 ] . For online applications with long paths, recent advances have further guaranteed the feasibility of the windowing process for non-convex OPP3 [ 9 ] . As a result, CO approaches satisfy three of the requirements stated above, i.e., optimality, feasibility, and high-order capability. However, the main limitation of CO methods lies in their computational efficiency, especially for OPP3 which involves non-convex third-order constraints. Although OPP is often used as a low-level motion planning module that must be repeatedly solved with short latency, the considered optimization problems can involve thousands of decision variables and constraints. Such large-scale non-convex optimization problems remain computationally expensive for online OPP applications. The above observation motivates the study of DP methods. Instead of solving the full large-scale optimization problem in OPP, DP methods decompose it into a sequence of low-dimensional subproblems. Standard DP methods discretize the state space into grid points at each parameter point [ 3 ] . Based on Bellman’s principle of optimality (BPO) [ 18 ] , DP methods generate the optimal grid sequence under general objectives based on the

Read the complete text