CS Paper Radar

Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation

Shashank A. Deshpande, Jonathan P. How

cs.RO math.OC ·submitted 2026-08-26 18:46 UTC · v1
code/data

Abstract

Steering-based planners require solutions to state-to-state boundary value problems, which can be inaccessible for nonlinear platforms. Forward propagation evades the steering requirement, but the finite-sample behavior of the associated planners remains uncharacterized and their implementations underperform in practice. This paper develops a propagation-based kinodynamic planner with deterministic finite-sample near-optimality guarantees. We work within the large class of differentially flat nonlinear systems and show that a forward tree of locally dispersive control commands contains a near-optimal trajectory at a certified tree size. We provide a general mechanism to construct dispersive command sets for control-affine systems, which are necessary to implement the search algorithm prescribed by the theory. We show that covering the certified trajectory class irrespective of cost provably demands a tree exponentially sized in the problem horizon, and present a cost-conditioned dominance pruning procedure that retains near-optimality at a tree size polynomial in the horizon. We implement the resulting search algorithm, Dispersive Forward Tree search (DFT*), as breadth-first expansion of the forward tree, which maps naturally onto parallel hardware. We design efficient dispersive samplers for the unicycle, the trailer car, and the quadrotor and evaluate challenging planning tasks for these platforms. DFT* delivers consistently competitive and often substantially better solution quality than state-of-the-art kinodynamic planners at comparable solution times on embedded-tier processors, accelerating further as parallel compute is scaled. We also implement DFT* in a receding-horizon loop to demonstrate real-time planning in dynamic environments at embedded-tier compute budgets.

Comment
28 pages. Code: https://github.com/croshank/DFTSearch

Closest papers

Nearest neighbours by meaning across the whole index.

Dispersive Tree Agreements for Multi-Robot Coordination

cs.RO cs.MAmath.OC ·2026-10-22 ·Shashank A. Deshpande, Blake T. Edwards, Jonathan P. How
similarity 0.67
Abstract · 18 pages, 5 figures, 7 tables

Multi-robot coordination of nonlinear systems is naturally formulated as joint-space optimal control subject to joint constraints. Existing methods that approach joint optimality remain largely centralized and offline, while decentralized, real-time counterparts target safe navigation without pursuing the joint optimum. This paper develops a decentralized, real-time planner that approaches the joint optimum as an anytime process. We extend a recent single-robot framework that searches dispersive trees of forward-propagated commands to coordinate a multi-robot team near-optimally. We first show that the inter-robot coupling can be effectively replaced by some local constraints, under which locally grown dispersive trees contain a near-optimal agreement. It is this structure that the robots pursue by a negotiation driven by decentralized column generation. In the quiescent limit, this negotiation is shown to settle on a near-optimal agreement. Our real-time protocol, WarpWeaver, runs the negotiation asynchronously over a receding horizon and closes on quiesced agreements even when deadlines cut it short. In simulation, WarpWeaver reduces total travel time by up to 22% against centralized offline planners on the Dynobench suite and by up to 16% against a decentralized real-time baseline, and outperforms a task-specific planner on networked navigation. Hardware experiments on six robots planning onboard demonstrate real-world implementability.

0.16

DynoFluxBench: Benchmarking Kinodynamic Space-Time Planners in Dynamic Environments

cs.RO ·2026-09-16 ·Franz Queißner, Andreas Orthey, Wolfgang Hönig
benchmark similarity 0.64
Abstract · 8 pages

Robots that leave structured, static environments must plan motions that are kinodynamically feasible and safe among moving obstacles. However, there are no dedicated benchmark frameworks that combine both aspects. To overcome this, we present DynoFluxBench, a framework to compare kinodynamic planners in known, dynamic environments with unbounded arrival time. To demonstrate its utility and establish strong baselines, we develop three dedicated planners, named ST-Db-RRT, ST-GBRRT, and KIST, that fuse kinodynamic and space-time methods, covering different kinodynamic search paradigms: ST-Db-RRT expands with randomly selected discontinuity-bounded motion primitives using trajectory optimization, whereas KIST and ST-GBRRT maintain a kinodynamically feasible tree with different heuristic guidance. We analyze the probabilistic completeness guarantees of those new planners in dynamic environments. Finally, we evaluate ST-Db-RRT, ST-GBRRT, and KIST using DynoFluxBench, showing that ST-Db-RRT reaches a first solution up to 32 times faster, while KIST and ST-GBRRT remain valuable where trajectory optimization is fragile. Videos and further analysis can be found at https://dynofluxbench.github.io/dynofluxbench/.

0.32

Achieving Asymptotic Near-Optimality Without $δ$-Similarity

cs.RO ·2026-09-03 ·Michael Moncton, Eric Frew
similarity 0.64
Abstract · Submitted to IEEE RA-L

Sampling-based motion planning algorithms are a popular class of trajectory planning algorithm due to their speed in complex, high-dimensional environments and ability to handle kinodynamic constraints, specifically through the use of forward dynamics propagation. Many such planners claim to achieve asymptotic near-optimality by proving the almost sure sampling of trajectories that are close to an optimal trajectory in the state space, known as $δ$-similar trajectories. This paper shows that the proof behind asymptotic $δ$-similarity relies on an unstated assumption that $δ$-similar trajectory segments will always be kept once sampled. This assumption does not hold in general. A problematic case, referred to as ``crowding out,'' is described, where locally low-cost paths prevent trajectories that are $δ$-similar to the optimal trajectory from being added to the tree. It is shown, however, that asymptotic near-optimality guarantees can still be achieved without guarantees of $δ$-similar solution trajectories when crowding out is properly accounted for. An example environment and system are provided where crowding out is shown to occur, demonstrating a scenario where inductively sampling a $δ$-similar solution trajectory is impossible.

0.43

ST-pRRTC: Parallel Space-Time RRT-C with Adaptive Goal-Time Forests

cs.RO ·2026-09-24 ·Duo Zhang, Jintong Li, Junshan Huang, Jingjin Yu
similarity 0.63
Abstract

We propose ST-pRRTC, a GPU-parallel space- time RRT-Connect motion planner for problems with known obstacle trajectories and unspecified arrival time. Searching over many arrival times broadens temporal coverage but divides a finite planning budget among more backward trees. To address the challenge, ST-pRRTC builds a shared forward tree and an adaptive forest of backward goal-time trees. Its interval root formulation samples goal arrival times continuously and guarantees probabilistic completeness and asymptotic arrival- time optimality under the stated assumptions in a bounded time domain. The practical root recycling policy has no such guar- antees. It adapts a fixed number of backward trees, replacing later roots while retaining useful search progress. Experiments on three dynamic benchmarks show that both variants achieve lower mean first-solution times and earlier mean final arrivals than ST-RRT* and SI-RRT on problems solved by all compared methods. Further experiments demonstrate the benefit of recy- cling over broad arrival-time ranges. Real-robot demonstrations show root-recycling ST-pRRTC planning motions for a UR5e among moving Crazyflie quadrotors.

0.16

Scalable Robust MCTS with Anytime Deterministic Optimality Guarantees

cs.AI ·2026-10-11 ·Tomer Massas, Vadim Indelman
similarity 0.62
Abstract · 33 pages, including appendix

MDP planners often rely on nominal transition models that may differ from the true dynamics. Robust MDP planning accounts for this uncertainty through a set of admissible models, but doing so with limited online computation is challenging: the search tree grows exponentially with the horizon and each robust backup requires an additional optimization. Existing online robust methods remain limited in scale and offer at most probabilistic guarantees. We introduce, to the best of our knowledge, the first deterministic anytime guarantees for robust online MDP planning. We restrict computation to the sampled search tree while deterministically bounding the contribution of unsampled trajectories. For any fixed policy, we derive lower and upper bounds on the gap between its projected and true robust values under rectangular and non-rectangular uncertainty sets. Under rectangular uncertainty, we propagate these bounds through the robust Bellman operator to bound the optimal robust value. These bounds are computable from the current sampled tree, hold at every node, tighten as the sampled support expands, and converge to the robust values as full support is recovered. We develop CAR-MCTS, a bound-guided MCTS planner that uses these deterministic bounds to guide exploration, prune provably suboptimal branches, and terminate once the optimal root action is certified. The fixed-policy bounds also yield an anytime policy-evaluation mechanism that certifies the robust value of any policy, independent of how it was obtained. Experiments verify the deterministic bounds, their tightening under support expansion, substantial branch pruning, root-action certification, and convergence to the optimal robust policy. To our knowledge, this is the first scalable robust MCTS framework with anytime deterministic guarantees for both online planning and policy evaluation, without enumerating the full state space.

0.28

Pareto-Optimal Entropy-Regularized Trajectory Optimization

cs.RO eess.SY ·2026-10-06 ·Dimitrios S. Georgiou, Augustinos D. Saravanos, Evangelos A. Theodorou
similarity 0.61
Abstract · 9 pages, 3 figures

Trajectory optimization (TO) under nonlinear dynamics, actuation limits and collision avoidance constraints is a fundamental problem in robotics, albeit especially challenging due to its highly non-convex nature. For this setting, Differential Dynamic Programming (DDP) is an efficient second-order shooting method, yet its local structure renders it vulnerable to suboptimal basins. Sampling-augmented variants mitigate this susceptibility through stochastic exploration, but often sample only around the few trajectories they retain for reoptimization, based solely on their cost which restricts exploration breadth. We introduce Pareto-Optimal Entropy-Regularized DDP (PER-DDP), an entropy-regularized population framework derived from the free-energy/relative-entropy inequality. Our method combines prior-guided sampling that shapes exploration around each retained trajectory, with expanded rollout evaluations that probe these sampling policies beyond the few retained candidates, and Pareto filtering for preserving task-constraint alternatives across iterations. This decouples sampling effort from the optimization population size and broadens exploration without sacrificing the second-order structure that makes DDP effective. Across multiple systems and hundreds of environments, PER-DDP achieves higher success rates than state-of-the-art sampling-augmented TO methods and finds reliable solutions in environments beyond the reach of all baselines.

0.31

Some Modifications to Our End-to-End UAV Planner

cs.RO ·2026-08-16 ·Junjie Lu, Bailing Tian
similarity 0.61
Abstract

The one-stage planner YOPO maps a single depth image and the robot state directly to a set of candidate trajectories, trained by backpropagating through differentiable trajectory costs. This yields dense, geometrically informative supervision, but inherits the pathologies of soft-constrained optimization: the safety cost competes with the smoothness and goal-reaching terms, is non-convex across homotopy classes, and the single-piece polynomial is limited in expressiveness. In this report, we summarize several effective modifications. We adopt a two-piece MINCO parameterization, trading time for smoothness without altering the trajectory's spatial profile. We further lift YOPO's multi-modal prediction to span distinct homotopy classes, treating each motion primitive as a homotopy anchor that confines the trajectory to a feasible basin - without explicit safe-flight-corridor construction or front-end search. For dynamic feasibility, we impose barrier penalties on velocity and acceleration together with a curvature-dependent speed limit whose gradient acts only on the velocity, producing an adaptive-speed behavior that decelerates in cluttered regions or sharp turns. We replace score regression with a ranking loss, preventing small score errors from reordering the candidate set. These yield richer trajectory representations, safer obstacle avoidance, and more direct flight paths.

0.04

MeshSIPP: Efficient Lattice Planning in Dynamic Environment

cs.AI cs.RO ·2026-10-07 ·Marat Agranovskiy, Konstantin Yakovlev
benchmarktheory similarity 0.60
Abstract

Autonomous navigation in dynamic environments requires computing spatiotemporal trajectories that satisfy non-holonomic motion constraints. When the trajectories of the moving obstacles are predictable or known, a promising approach is to rely on the combination of state lattices constructed from precomputed feasible motion primitives and Safe Interval Path Planning -- a search-based algorithm with strong theoretical guarantees. While this approach yields feasible paths, the rich primitive sets needed for smooth navigation induce a large branching factor, which becomes costly when coupled with time-dependent obstacle intervals. To this end, we present MeshSIPP, an efficient planner that removes the computational bottleneck by exploiting the fact that many primitives sweep the same regions and can therefore be validated together. MeshSIPP propagates primitives as spatial bundles, screens them with lightweight bounding-interval checks, and defers the expensive exact departure-time search until a primitive reaches its terminal state. A time-aware pruning rule additionally discards redundant space-time branches early in the search. We prove that the resulting search is complete and optimal. Extensive experiments over more than 6,000 benchmark instances and real-time ROS~2 simulations show that MeshSIPP achieves up to a 3$\times$ speedup over state-of-the-art spatiotemporal planners.

0.18