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

• URL: http://arxiv.org/abs/2608.26314v1
• Date: Wed, 26 Aug 2026 18:46:17 GMT
• Title: Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation
• Abstract summary: This paper develops a propagation-based kinodynamic planner with deterministic finite-sample near-optimality guarantees.<n>We show that a forward tree of locally dispersive control commands contains a near-optimal trajectory at a certified tree size.<n>We implement the resulting search algorithm, Dispersive Forward Tree search (DFT*), as breadth-first expansion of the forward tree.
• Score: 15.03677748041754
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Graph Sparse Sampling: Breaking the Curse of the Horizon in Continuous MDP Planning [10.558515062670692]
  Planning under uncertainty in continuous domains is essential for autonomous systems.<n>Tree-based search methods such as Monte Carlo Tree Search (MCTS) remain popular.<n>We propose Graph Sparse Sampling (GSS), an online planning algorithm that shares sampled futures across many candidate decisions.
  arXiv  Detail & Related papers  (2026-07-06T17:36:28Z)
• BOWConnect: Parallel Bayesian Optimization over Windows with Learned Local Cost Maps for Sample-Efficient Kinodynamic Motion Planning [1.4499463058550681]
  This paper presents BOWConnect, a parallel kinodynamic motion planner.<n>It addresses three fundamental limitations of existing kinodynamic motion planners: sample inefficiency in high-dimensional state spaces, unreliable sampling, and poor performance in narrow spaces.<n>It integrates BOW as a learning-based exploration framework, enabling each worker to learn local maps and constraints to guide toward dynamically feasible and collision-free controls.
  arXiv  Detail & Related papers  (2026-06-25T17:11:33Z)
• Optimizing Trajectory-Trees in Belief Space: An Application from Model Predictive Control to Task and Motion Planning [12.236092368066332]
  This paper explores the benefits of computing arborescent trajectories (trajectory-trees) instead of commonly used sequential trajectories for partially observable robotic planning problems.<n>Unlike sequential trajectories, which model a single forward evolution of the system, trajectory-trees capture multiple possible contingencies.
  arXiv  Detail & Related papers  (2026-05-03T13:06:20Z)
• HAD: Combining Hierarchical Diffusion with Metric-Decoupled RL for End-to-End Driving [51.268878540511054]
  We propose HAD, an end-to-end planning framework with a Hierarchical Diffusion Policy.<n>We show that HAD achieves new state-of-the-art performance on both NAVSIM and HUGSIM.
  arXiv  Detail & Related papers  (2026-04-04T04:12:47Z)
• Para-B&B: Load-Balanced Deterministic Parallelization of Solving MIP [50.917107318582715]
  Mixed-integer programming (MIP) extends linear programming by incorporating both continuous and integer decision variables.<n>This paper presents the first fully open-source implementation of deterministic parallel branch-and-bound for HiGHS, a high-performance MIP solver.<n>Our approach introduces a novel data-parallel architecture ensuring strict determinism by replicating complete solver state across worker threads.
  arXiv  Detail & Related papers  (2026-02-10T14:17:53Z)
• Dynamic Parallel Tree Search for Efficient LLM Reasoning [102.16694475391665]
  Tree of Thoughts (ToT) enhances Large Language Model (LLM) reasoning by structuring problem-solving as a spanning tree.<n>We propose Dynamic Parallel Tree Search (DPTS), a novel parallelism framework that aims to dynamically optimize the reasoning path in inference.<n> Experiments on Qwen-2.5 and Llama-3 with Math500 and GSM8K datasets show that DPTS significantly improves efficiency by 2-4x on average.
  arXiv  Detail & Related papers  (2025-02-22T14:13:37Z)
• SCoTT: Strategic Chain-of-Thought Tasking for Wireless-Aware Robot Navigation in Digital Twins [78.53885607559958]
  We propose SCoTT, a wireless-aware path planning framework.<n>We show that SCoTT achieves path gains within 2% of DP-WA* while consistently generating shorter trajectories.<n>We also show the practical viability of our approach by deploying SCoTT as a ROS node within Gazebo simulations.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Sparsity-Constraint Optimization via Splicing Iteration [1.3622424109977902]
  We develop an algorithm named Sparsity-Constraint Optimization via sPlicing itEration (SCOPE) SCOPE converges effectively without tuning parameters. We apply SCOPE to solve quadratic optimization, learn sparse classifiers, and recover sparse Markov networks for binary variables. Our open-source Python package skscope based on C++ implementation is publicly available on GitHub.
  arXiv  Detail & Related papers  (2024-06-17T18:34:51Z)
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach [57.788675205519986]
  We learn high-quality traces from POMDP executions generated by any solver. We exploit data- and time-efficient Indu Logic Programming (ILP) to generate interpretable belief-based policy specifications. We show that learneds expressed in Answer Set Programming (ASP) yield performance superior to neural networks and similar to optimal handcrafted task-specifics within lower computational time.
  arXiv  Detail & Related papers  (2024-02-29T15:36:01Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search [12.457788665461312]
  We propose a hybrid solving planner that combines machine learning models and an optimal solver. We conduct experiments on realistic scenarios and show that GCN support enables substantial speedup and smoother scaling to harder problems.
  arXiv  Detail & Related papers  (2021-08-02T16:53:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.