Search papers, labs, and topics across Lattice.
This paper introduces Dispersive Forward Tree search (DFT*), a novel kinodynamic planner that provides deterministic finite-sample near-optimality guarantees for steering-based planners facing nonlinear platforms. By constructing a forward tree of locally dispersive control commands, the authors demonstrate that DFT* can efficiently cover a certified trajectory class while maintaining polynomial tree size in relation to the problem horizon, significantly improving solution quality over existing kinodynamic planners. The approach is validated through practical implementations on various platforms, showcasing its superior performance in real-time planning tasks under embedded compute constraints.
DFT* achieves near-optimal planning in nonlinear systems with a polynomial-sized search tree, outperforming traditional methods in both quality and efficiency.
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.
