LQR-trees: Feedback motion planning on sparse randomized trees

Recent advances in the direct computation of Lyapunov functions using convex optimization make it possible to efficiently evaluate regions of stability for smooth nonlinear systems. Here we present a feedback motion planning algorithm which uses these results to efficiently combine locally-valid linear quadratic regulator (LQR) controllers into a nonlinear feedback policy which probabilistically covers the reachable area of a (bounded) state space with a region of stability, certifying that all initial conditions that are capable of reaching the goal will stabilize to the goal. We demonstrate the performance of this systematic nonlinear feedback control design algorithm on the model underactuated systems and discuss the potential for control of more complicated control problems like bipedal walking.