Optimal Sampling-Based Planning for Linear-Quadratic Kinodynamic Systems

Authors

Gustavo Goretkin, Alejandro Perez, Robert Platt Jr., George Konidaris

Year

2013

Conference Paper

Algorithm

LQR-RRT*

Source

IEEE International Conference on Robotics and Automation

Identifiers

DOI 10.1109/ICRA.2013.6630907

Abstract¶

We propose a new method for applying RRT* to kinodynamic motion planning problems by using finite-horizon linear quadratic regulation (LQR) to measure cost and to extend the tree. First, we introduce the method in the context of arbitrary affine dynamical systems with quadratic costs. For these systems, the algorithm is shown to converge to optimal solutions almost surely. Second, we extend the algorithm to non-linear systems with non-quadratic costs, and demonstrate its performance experimentally.

Summary¶

Adapts RRT* to kinodynamic planning by using finite-horizon LQR as both the cost metric and steering method in state-time space. The paper proves almost-sure convergence to optimal solutions for affine dynamics with quadratic costs, then extends the method by local linearization to nonlinear systems and demonstrates it on constrained examples such as pendulum swing-up.