# db-A*: Discontinuity-bounded Search for Kinodynamic Mobile Robot Motion Planning

arXiv: https://arxiv.org/abs/2203.11108 · HTML: https://mlsanity.com/paper/2203.11108/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Mar 2022.

## Built on by (most cited first, 2 of 2)

- [WinkTPG: An Execution Framework for Multi-Agent Path Finding Using Temporal Reasoning](https://mlsanity.com/paper/2508.01495/) (2025)
- [Accelerating db-A* for Kinodynamic Motion Planning Using Diffusion](https://mlsanity.com/paper/2503.05539/) (2025)

## Abstract (arXiv)

We consider time-optimal motion planning for dynamical systems that are translation-invariant, a property that holds for many mobile robots, such as differential-drives, cars, airplanes, and multirotors. Our key insight is that we can extend graph-search algorithms to the continuous case when used symbiotically with optimization. For the graph search, we introduce discontinuity-bounded A* (db-A*), a generalization of the A* algorithm that uses concepts and data structures from sampling-based planners. Db-A* reuses short trajectories, so-called motion primitives, as edges and allows a maximum user-specified discontinuity at the vertices. These trajectories are locally repaired with trajectory optimization, which also provides new improved motion primitives. Our novel kinodynamic motion planner, kMP-db-A*, has almost surely asymptotic optimal behavior and computes near-optimal solutions quickly. For our empirical validation, we provide the first benchmark that compares search-, sampling-, and optimization-based time-optimal motion planning on multiple dynamical systems in different settings. Compared to the baselines, kMP-db-A* consistently solves more problem instances, finds lower-cost initial solutions, and converges more quickly.