Advances in the direct computation of Lyapunov functions using convex optimization make it possible to efficiently evaluate regions of attraction for smooth non-linear systems. Here we present a feedback motion-planning algorithm which uses rigorously computed stability regions to build a sparse tree of LQR-stabilized trajectories. The region of attraction of this non-linear feedback policy “probabilistically covers” the entire controllable subset of state space, verifying that all initial conditions that are capable of reaching the goal will reach the goal. We numerically investigate the properties of this systematic non-linear feedback design algorithm on simple non-linear systems, prove the property of probabilistic coverage, and discuss extensions and implementation details of the basic algorithm.
Anderson, B.D.O. and Moore, J.B. ( 1990). Optimal control: linear quadratic methods. Upper Saddle River, NJ, Prentice Hall.
2.
Atkeson, C.G. and Stephens, B. ( 2008). Random sampling of states in dynamic programming. In Advances in Neural Information Processing Systems 20, Platt JC and Koller D and Singer Yand Roweis S (eds), Cambridge, MA: MIT Press. pp. 33-40.
3.
Betts, J.T. ( 2001). Practical Methods for Optimal Control Using Nonlinear Programming (Advances in Design and Control). Philadelphia, PA, Society for Industrial and Applied Mathematics.
4.
Branicky, M. and Curtiss, M. ( 2002). Nonlinear and hybrid control via RRTs. Proceedings International Symposium on Mathematical Theory of Networks and Systems.
5.
Burridge, R.R., Rizzi, A.A. and Koditschek, D.E. ( 1999). Sequential composition of dynamically dexterous robot behaviors. The International Journal of Robotics Research , 18(6): 534-555.
6.
Chesi, G. ( 2009). Estimating the domain of attraction for non-polynomial systems via LMI optimizations. Automatica, 45(6): 1536-1541.
7.
Franzè, G., Casavola, A., Famularo, D. and Garone, E. ( 2009). An off-line MPC strategy for nonlinear systems based on SOS programming. Nonlinear Model Predictive Control, Magni, L., Raimondo, D. M. and Allgower, F. (eds) (Lecture Notes in Control and Information Sciences, Vol. 384). Berlin, Springer, pp. 491-499.
8.
Frazzoli, E., Dahleh, M.A. and Feron, E. ( 2002). Real-time motion planning for agile autonomous vehicles . Journal of Guidance, Control, and Dynamics, 25(1): 116-129.
9.
Gill, P.E., Murray, W. and Saunders, M.A. ( 2005). SNOPT: An SQP algorithm for large-scale constrained optimization . SIAM Review, 47(1): 99-131.
10.
Goebel, R., Prieur, C. and Teel, A.R. ( 2009). Smooth patchy control Lyapunov functions. Automatica, 45: 675-683.
11.
Gollu, N. and Rodrigues, L. ( 2007). Control of large angle attitude maneuvers for rigid bodies using sum of squares. American Control Conference , 2007 (ACC ’07), July, pp. 3156-3161.
12.
Johansen, T.A. ( 2000). Computation of Lyapunov functions for smooth nonlinear systems using convex optimization. Automatica, 36(11): 1617-1626.
13.
Kavraki, L., Svestka, P., Latombe, J. and Overmars, M. ( 1996). Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation , 12(4): 566-580.
Kuffner, J., Nishiwaki, K., Kagami, S., Inaba, M. and Inoue, H. ( 2001). Motion planning for humanoid robots under obstacle and dynamic balance constraints. Proceedings of the IEEE International Conference on Robotics and Automation, pp. 692-698.
16.
LaValle, S. and Kuffner, J. ( 2000). Rapidly-exploring random trees: Progress and prospects . Proceedings of the Workshop on the Algorithmic Foundations of Robotics.
17.
LaValle, S.M. ( 2006). Planning Algorithms. Cambridge, Cambridge University Press.
18.
Mason, M. ( 1985). The mechanics of manipulation. Proceedings of the IEEE International Conference on Robotics and Automation , pp. 544-548.
19.
Megretski, A.SPOT: Systems Polynomial Optimization Tools. http://web.mit.edu/ameg/www./ .
20.
Megretski, A. and Rantzer, A. ( 1997). System analysis via integral quadratic constraints. IEEE Transactions on Automatic Control, 42(6): 819-830.
21.
Mitchell, I.M. and Templeton, J.A. ( 2005). A toolbox of Hamilton-Jacobi solvers for analysis of nondeterministic continuous and hybrid systems. Proceedings of Hybrid Systems Computation and Control.
22.
Nesterov, Y. and Nemirovskii, A. ( 1995). Interior-Point Polynomial Algorithms in Convex Programming , SIAM Review36(4): 682-683.
23.
Papachristodoulou, A., Peet, M.M. and Lall, S. ( 2009). Analysis of polynomial systems with time delays via the sum of squares decomposition. IEEE Transactions on Automatic Control, 54(5): 1058-1064.
24.
Papachristodoulou, A. and Prajna, S. ( 2002). On the construction of Lyapunov functions using the sum of squares decomposition. Proceedings of the 41st IEEE Conference on Decision and Control.
25.
Parrilo, P.A. ( 2000). Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD Thesis, California Institute of Technology.
26.
Peterfreund, N. and Baram, Y. ( 1998). Convergence analysis of nonlinear dynamical systems by nested Lyapunov functions. IEEE Transactions on Automatic Control, 43(8): 1179-1184.
27.
Prajna, S., Papachristodoulou, A., Seiler, P. and Parrilo, P.A. ( 2004a). SOSTOOLS Sum of Squares Optimization Toolbox for MATLAB: User’s Guide, version 2.00.
28.
Prajna, S., Parrilo, P. and Rantzer, A. ( 2004b). Nonlinear control synthesis by convex optimization. IEEE Transactions on Automatic Control, 49(2): 310-314.
29.
Prajna, S. and Rantzer, A. ( 2007). Convex programs for temporal verification of nonlinear dynamical systems. SIAM Journal on Control and Optimization , 46(3): 999-1021.
30.
Rantzer, A. ( 2001). A dual to Lyapunov’s stability theorem. Systems and Control Letters, 42(3): 161-168.
31.
Reist, P. and Tedrake, R. ( 2010). Simulation-based LQR-trees with input and state constraints . Proceedings of the International Conference on Robotics and Automation (ICRA), (in press).
32.
Shkolnik, A. and Tedrake, R. ( 2009). Path planning in 1000+ dimensions using a task-space Voronoi bias. Proceedings of the IEEE/RAS International Conference on Robotics and Automation (ICRA).
33.
Slotine, J.-J. E. and Li, W. ( 1990). Applied Nonlinear Control. Upper Saddle River, NJ, Prentice Hall.
34.
Tan, W. and Packard, A. ( 2008). Stability region analysis using polynomial and composite polynomial Lyapunov functions and sum-of-squares programming. IEEE Transactions on Automatic Control, 53(2): 565-571.
35.
Tedrake, R. ( 2009). LQR-Trees: Feedback motion planning on sparse randomized trees. Proceedings of Robotics: Science and Systems (RSS), p. 8.
36.
Tomlin, C.J., Mitchell, I.M., Bayen, A.M. and Oishi, M.K.M. ( 2005). Computational techniques for the verification and control of hybrid systems. Multidisciplinary Methods for Analysis Optimization and Control of Complex Systems (Mathematics in Industry). Berlin, Springer, pp. 151-175.
37.
Topcu, U., Packard, A. and Seiler, P. ( 2008). Local stability analysis using simulations and sum-of-squares programming. Automatica, 44(10): 2669-2675.
