2015/05/15 by Kris Hauser, Hauser, Kris, Yilun Zhou +1 · 5 citations
Computer Science · Engineering · #Robotic Path Planning Algorithms #Robotics and Sensor-Based Localization #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.1505.04098
This paper presents an equivalence between feasible kinodynamic planning and optimal kinodynamic planning, in that any optimal planning problem can be transformed into a series of feasible planning problems in a state-cost space whose solutions approach the optimum. This transformation gives rise to a meta-algorithm that produces an asymptotically optimal planner, given any feasible kinodynamic planner as a subroutine. The meta-algorithm is proven to be asymptotically optimal, and a formula is derived relating expected running time and solution suboptimality. It is directly applicable to a wide range of optimal planning problems because it does not resort to the use of steering functions or numerical boundary-value problem solvers. On a set of benchmark problems, it is demonstrated to perform, using the EST and RRT algorithms as subroutines, at a superior or comparable level to related planners.