# T*varepsilon -- Bounded-Suboptimal Efficient Motion Planning for Minimum-Time Planar Curvature-Constrained Systems

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 31 references that are in the map.
- First posted on arXiv 4 Apr 2022.

## Builds on (most cited first, 6 of 6)

- [Generalized Lazy Search for Robot Motion Planning: Interleaving Search and Edge Evaluation via Event-based Toggles](https://mlsanity.com/paper/1904.02795/) (2019)
- [A Unifying Formalism for Shortest Path Problems with Expensive Edge Evaluations via Lazy Best-First Search over Paths with Edge Selectors](https://mlsanity.com/paper/1603.03490/) (2016)
- [Asymptotically near-optimal RRT for fast, high-quality, motion planning](https://mlsanity.com/paper/1308.0189/) (2013)
- [The Provable Virtue of Laziness in Motion Planning](https://mlsanity.com/paper/1710.04101/) (2017)
- [Rapid Path Planning for Dubins Vehicles under Environmental Currents](https://mlsanity.com/paper/1909.04105/) (2019)
- [Tstar-Lite: A Fast Time-Risk Optimal Motion Planning Algorithm for Multi-Speed Autonomous Vehicles](https://mlsanity.com/paper/2008.13048/) (2020)

## Abstract (arXiv)

We consider the problem of finding collision-free paths for curvature-constrained systems in the presence of obstacles while minimizing execution time. Specifically, we focus on the setting where a planar system can travel at some range of speeds with unbounded acceleration. This setting can model many systems, such as fixed-wing drones. Unfortunately, planning for such systems might require evaluating many (local) time-optimal transitions connecting two close-by configurations, which is computationally expensive. Existing methods either pre-compute all such transitions in a preprocessing stage or use heuristics to speed up the search, thus foregoing any guarantees on solution quality. Our key insight is that computing all the time-optimal transitions is both~(i)~computationally expensive and~(ii)~unnecessary for many problem instances. We show that by finding bounded-suboptimal solutions (solutions whose cost is bounded by 1+varepsilon times the cost of the optimal solution for any user-provided varepsilon) and not time-optimal solutions, one can dramatically reduce the number of time-optimal transitions used. We demonstrate using empirical evaluation that our planning framework can reduce the runtime by several orders of magnitude compared to the state-of-the-art while still providing guarantees on the quality of the solution.