arXiv:2608.26314cs.ROmath.OC2026-08

提出一种可证明近优的前向树规划算法,解决非线性系统运动规划难题。

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

论文配图:Dispersive Forward Tree Search for Optimal Control: Coverage, Complexity, and Computation
图 1 · 摘自论文原文
  • 基于局部发散控制指令构建前向搜索树,保证在有限样本下近似最优
  • 在规划时长内,树规模指数增长可覆盖所有轨迹;成本条件剪枝后多项式规模仍近优
  • 适用于无人车、无人机等复杂平台,可在嵌入式设备上实时运行

基于推进的规划器避免了状态到状态边值问题的求解需求,但其有限样本行为未被充分刻画,实际实现性能不佳。本文针对微分平坦的非线性系统,提出一种具有确定性有限样本近优性保证的传播式运动规划方法。通过构造控制仿射系统的发散控制集,构建包含近优轨迹的前向树,证明无论代价如何,覆盖该类轨迹需指数级树大小;提出成本条件主导剪枝策略,使树规模仅需多项式增长即可保持近优性。实现的DFT*算法以广度优先方式扩展前向树,天然适配并行硬件。为单车、拖车、四旋翼设计高效发散采样器,在这些平台上的挑战性任务中,DFT*在嵌入式处理器上与先进算法相当甚至更优,且随并行计算扩展加速。进一步将其用于滚动时域框架,实现在嵌入式算力下的动态环境实时规划。

原文摘要 · Abstract (English)

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.

运动规划非线性系统实时控制并行计算

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。