TY - JOUR
T1 - Asymptotically optimal planning by feasible kinodynamic planning in a state-cost space
AU - Hauser, Kris
AU - Zhou, Yilun
N1 - Funding Information:
This work was partially supported by the National Science Foundation under Award 1218534. The work of Y. Zhou was partially supported by a Pratt Engineering Undergraduate Research Fellowship.
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2016/12
Y1 - 2016/12
N2 - 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 yields 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 expansive space tree (EST) and rapidly-exploring random tree (RRT) algorithms as subroutines, at a level that is superior or comparable to related planners.
AB - 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 yields 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 expansive space tree (EST) and rapidly-exploring random tree (RRT) algorithms as subroutines, at a level that is superior or comparable to related planners.
KW - Motion planning
KW - nonlinear control systems
KW - trajectory optimization
UR - http://www.scopus.com/inward/record.url?scp=84991052050&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84991052050&partnerID=8YFLogxK
U2 - 10.1109/TRO.2016.2602363
DO - 10.1109/TRO.2016.2602363
M3 - Article
AN - SCOPUS:84991052050
VL - 32
SP - 1431
EP - 1443
JO - IEEE Transactions on Robotics
JF - IEEE Transactions on Robotics
SN - 1552-3098
IS - 6
M1 - 7588078
ER -