×

An introduction to trajectory optimization: how to do your own direct collocation. (English) Zbl 1474.37131

Summary: This paper is an introductory tutorial for numerical trajectory optimization with a focus on direct collocation methods. These methods are relatively simple to understand and effectively solve a wide variety of trajectory optimization problems. Throughout the paper we illustrate each new set of concepts by working through a sequence of four example problems. We start by using trapezoidal collocation to solve a simple one-dimensional toy problem and work up to using Hermite-Simpson collocation to compute the optimal gait for a bipedal walking robot. Along the way, we cover basic debugging strategies and guidelines for posing well-behaved optimization problems. The paper concludes with a short overview of other methods for trajectory optimization. We also provide an electronic supplement that contains well-documented MATLAB code for all examples and methods presented. Our primary goal is to provide the reader with the resources necessary to understand and successfully implement their own direct collocation methods.

MSC:

37N35 Dynamical systems in control
37M05 Simulation of dynamical systems
37C35 Orbit growth in dynamical systems
70B15 Kinematics of mechanisms and robots
93C85 Automated systems (robots, etc.) in control theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Agrawal, S. Shen, and M. V. D. Panne, {\it Diverse motion variations for physics-based character animation}, in Proceedings of the 12th ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’13, ACM, New York, 2013, pp. 37-44, .
[2] V. M. Becerra, {\it PSOPT Optimal Control Solver User Manual}, 2011, .
[3] D. A. Benson, G. T. Huntington, T. P. Thorvaldsen, and A. V. Rao, {\it Direct trajectory optimization and costate estimation via an orthogonal collocation method}, J. Guidance Control Dynam., 29 (2006), pp. 1435-1440, .
[4] J.-P. Berrut and L. N. Trefethen, {\it Barycentric Lagrange interpolation}, SIAM Rev., 46 (2004), pp. 501-517, . · Zbl 1061.65006
[5] J. T. Betts, {\it Survey of numerical methods for trajectory optimization}, J. Guidance Control Dynam., 21 (1998), pp. 193-207. · Zbl 1158.49303
[6] J. T. Betts, {\it Practical Methods for Optimal Control and Estimation Using Nonlinear Programming}, SIAM, Philadelphia, PA, 2010, . · Zbl 1189.49001
[7] J. T. Betts, {\it SOS: Sparse Optimization Suite-User’s Guide}, 2013, .
[8] P. A. Bhounsule, J. Cortell, A. Grewal, B. Hendriksen, J. G. D. Karssen, C. Paul, and A. Ruina, {\it Low-bandwidth reflex-based control for lower power walking: \(65\) km on a single battery charge}, Internat. J. Robotics Res., 33 (2014), pp. 1305-1321, .
[9] P. A. Bhounsule, J. Cortell, A. Grewal, B. Hendriksen, J. G. D. Karssen, C. Paul, and A. Ruina, {\it MULTIMEDIA EXTENSION #1. Low-bandwidth reflex-based control for lower power walking: 65 km on a single battery charge}, Internat. J. Robotics Res., 2014, , .
[10] L. T. Biegler and V. M. Zavala, {\it Large-scale nonlinear programming using IPOPT: An integrating framework for enterprise-wide dynamic optimization}, Comput. Chem. Engrg., 33 (2009), pp. 575-582, .
[11] A. E. Bryson and Y.-C. Ho, {\it Applied Optimal Control}, Taylor & Francis, London, 1975.
[12] E. Catto, {\it Box \(2\) D User Manual}, 2013, .
[13] B. C. Chevallereau, G. Abba, Y. Aoustin, F. Plestan, E. R. Westervelt, C. Canudas-De Wit, and J. W. Grizzle, {\it RABBIT: A testbed for advanced control theory}, IEEE Control Systems Mag., 23 (2003), pp. 57-79, .
[14] E. Coumans, {\it Bullet Physics SDK Manual}, 2015, .
[15] C. L. Darby, D. Garg, and A. V. Rao, {\it Costate estimation using multiple-interval pseudospectral methods}, J. Spacecraft Rockets, 48 (2011), pp. 856-866, , .
[16] C. L. Darby, W. W. Hagar, and A. V. Rao, {\it An hp-adaptive pseudospectral method for solving optimal control problems}, Optim. Control Appl. Methods, 32 (2011), pp. 476-502, . · Zbl 1266.49066
[17] T. A. Driscoll, N. Hale, and L. N. Trefethen, {\it Chebfun Guide}, 1st ed., Pafnuty Publications, Oxford, 2014.
[18] G. Elnagar, M. A. Kazemi, and M. Razzaghi, {\it The pseudospectral Legendre method for discretizing optimal control problems}, IEEE Trans. Automat. Control, 40 (1995), pp. 1793-1796. · Zbl 0863.49016
[19] G. N. Elnagar and M. A. Kazemi, {\it Pseudospectral Chebyshev optimal control of constrained nonlinear dynamical systems}, Comput. Optim. Appl., 217 (1998), pp. 195-217, . · Zbl 0914.93024
[20] B. Fornberg, {\it A Practical Guide to Pseudospectral Methods}, Cambridge University Press, Cambridge, UK, 1996. · Zbl 0844.65084
[21] C. C. Francolin, D. A. Benson, W. W. Hager, and A. V. Rao, {\it Costate estimation in optimal control using integral Gaussian quadrature orthogonal collocation methods}, Optim. Control Appl. Methods, 36 (2015), pp. 381-397. · Zbl 1329.49045
[22] D. Garg, W. W. Hager, and A. V. Rao, {\it Gauss pseudospectral method for solving infinite-horizon optimal control problems}, in AIAA Guidance, Navigation, and Control Conference, AIAA, 2010, pp. 1-9.
[23] D. Garg, M. Patterson, and W. Hager, {\it An overview of three pseudospectral methods for the numerical solution of optimal control problems}, Adv. Astronaut. Sci., 135 (2009), pp. 1-17, .
[24] D. Garg, M. Patterson, W. W. Hager, A. V. Rao, D. A. Benson, and G. T. Huntington, {\it A unified framework for the numerical solution of optimal control problems using pseudospectral methods}, Automatica, 46 (2010), pp. 1843-1851, . · Zbl 1219.49028
[25] P. E. Gill, W. Murray, and M. A. Saunders, {\it User’s Guide for SNOPT Version 7: Software for Large-Scale Nonlinear Programming}, 2006, .
[26] G. H. Golub and J. H. Welsch, {\it Calculation of Gauss quadrature rules}, Math. Comp., 23 (1968), pp. 221-230, . · Zbl 0179.21901
[27] J. W. Grizzle, J. Hurst, B. Morris, H. W. Park, and K. Sreenath, {\it MABEL, a new robotic bipedal walker and runner}, in Proceedings of the 2008 American Control Conference, IEEE, 2009, pp. 2030-2036, .
[28] N. Hale and A. Townsend, {\it Fast and accurate computation of Gauss-Legendre and Gauss-Jacobi quadrature nodes and weights}, SIAM J. Sci. Comput., 35 (2013), pp. A652-A674, . · Zbl 1270.65017
[29] C. R. Hargraves and S. W. Paris, {\it Direct trajectory optimization using nonlinear programming and collocation}, AIAA J. Guidance, 10 (1987), pp. 338-342, . · Zbl 0634.65052
[30] A. L. Herman and B. A. Conway, {\it Direct optimization using collocation based on high-order Gauss-Lobatto quadrature rules}, AIAA J. Guidance Control Dynam., 19 (1996), pp. 522-529, . · Zbl 0866.65044
[31] D. H. Jacobson and D. Q. Mayne, {\it Differential Dynamic Programming}, Elsevier, New York, 1970. · Zbl 0223.49022
[32] G. Klein and J.-P. Berrut, {\it Linear barycentric rational quadrature}, BIT, 52 (2012), pp. 407-424, . · Zbl 1247.65033
[33] D. P. Laurie, {\it Computation of Gauss-type quadrature formulas}, J. Comput. Appl. Math., 127 (2001), pp. 201-217, . · Zbl 0980.65021
[34] L. Liu, M. V. D. Panne, and K. Yin, {\it Guided learning of control graphs for physics-based characters}, ACM Trans. Graphics, 35 (2016), art. 29, .
[35] D. G. Luenberger and Y. Ye, {\it Linear and Nonlinear Programming}, 3rd ed., Springer, New York, 2008. · Zbl 1207.90003
[36] Y. Ma, F. Borrelli, B. Hencey, B. Coffey, S. Bengea, and P. Haves, {\it Model predictive control for the operation of building cooling systems}, IEEE Trans. Control Systems Technol., 20 (2012), pp. 796-803, .
[37] Mathworks, {\it MATLAB Optimization Toolbox}, 2014, .
[38] Mathworks, {\it MATLAB Symbolic Toolbox}, 2014, .
[39] D. Mayne, {\it A second-order gradient method for determining optimal trajectories of non-linear discrete-time systems}, Internat. J. Control, 3 (1966), pp. 85-95, .
[40] I. Mordatch, E. Todorov, and Z. Popović, {\it Discovery of complex behaviors through contact-invariant optimization}, ACM Trans. Graphics, 31 (2012), art. 43, .
[41] D. M. Murray and S. J. Yakowitz, {\it Differential dynamic programming and Newton’s method for discrete optimal control problems}, J. Optim. Theory Appl., 43 (1984), pp. 395-414, . · Zbl 0518.49020
[42] A. Ng, {\it Reinforcement Learning and Control}, Machine Learning, Stanford CS 229 Lecture Notes, Stanford University, 2012, .
[43] H. W. Park, K. Sreenath, A. Ramezani, and J. W. Grizzle, {\it Switching control design for accommodating large step-down disturbances in bipedal robot walking}, Proceedings IEEE International Conference on Robotics and Automation, 2012, pp. 45-50, .
[44] S. V. Parter, {\it On the Legendre-Gauss-Lobatto Points and Weights}, J. Scientific Computing, 14 (1999), pp. 347-355. · Zbl 0959.65113
[45] M. A. Patterson and A. V. Rao, {\it GPOPS II: A MATLAB software for solving multiple-phase optimal control problems using hp-adaptive Gaussian quadrature collocation methods and sparse nonlinear programming}, ACM Trans. Math. Software, 39 (2013), art. 1, .
[46] X. B. Peng, G. Berseth, and M. van de Panne, {\it Dynamic terrain traversal skills using reinforcement learning}, ACM Trans. Graph., 34 (2015), art. 80, .
[47] M. Posa, S. Kuindersma, and R. Tedrake, {\it Optimization and stabilization of trajectories for constrained dynamical systems}, in Proceedings of the 2016 IEEE International Conference on Robotics and Automation, IEEE, 2016, pp. 1366-1373, .
[48] M. Posa and R. Tedrake, {\it Direct trajectory optimization of rigid body dynamical systems through contact}, in Algorithmic Foundations of Robotics X, Springer Tracts in Adv. Robotics 86, Springer, Berlin, Heidelberg, 2013, pp. 527-542.
[49] J. Pratt, {\it Virtual model control: An intuitive approach for bipedal locomotion}, Internat. J. Robotics Res., 20 (2001), pp. 129-143, .
[50] W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, {\it Numerical Recipes in C}, 2nd ed., Cambridge University Press, Cambridge, UK, 1992. · Zbl 0778.65003
[51] A. Rao, {\it A survey of numerical methods for optimal control}, Adv. Astronaut. Sci., 135 (2009), pp. 497-528, .
[52] I. M. Ross, {\it DIDO}, 2001, .
[53] I. M. Ross and F. Fahroo, {\it Legendre pseudospectral approximations of optimal control problems}, in New Trends in Nonlinear Dynamics and Control and Their Applications, Lect. Notes Control Inf. Sci. 295, Springer, Berlin, 2003, pp. 327-342, . · Zbl 1203.49025
[54] C. O. Saglam and K. Byl, {\it Robust policies via meshing for metastable rough terrain walking}, in Proceedings of Robotics: Science and Systems, Berkeley, CA, 2014, .
[55] M. Srinivasan and A. Ruina, {\it Computer optimization of a minimal biped model discovers walking and running}, Nature, 439 (2006), pp. 72-75, .
[56] SymPy Development Team, {\it SymPy: Python library for symbolic mathematics}, 2016, .
[57] T. W. Tee and L. N. Trefethen, {\it A rational spectral collocation method with adaptively transformed Chebyshev grid points}, SIAM J. Sci. Comput., 28 (2006), pp. 1798-1811, . · Zbl 1123.65105
[58] L. N. Trefethen, {\it Approximation Theory and Approximation Practice}, SIAM, Philadelphia, 2013. · Zbl 1264.41001
[59] V. A. Tucker, {\it Energetic cost of locomotion in animals}, Comparative Biochem. Physiol., 34 (1970), pp. 841-846, .
[60] C. D. Twigg and D. L. James, {\it Many-worlds browsing for control of multibody dynamics}, ACM Trans. Graphics, 26 (2007), art. 14, .
[61] C. D. Twigg and D. L. James, {\it Backward steps in rigid body simulation}, ACM Trans. Graphics, 27 (2008), art. 25, .
[62] J. Vlassenbroeck and R. V. Dooren, {\it A Chebyshev technique for solving nonlinear optimal control problems}, IEEE Trans. Automat. Control, 33 (1988), pp. 333-340, . · Zbl 0643.49027
[63] O. von Stryk, {\it User’s guide for DIRCOL: A Direct Collocation Method for the Numerical Solution of Optimal Control pPblems}, Lehrstuhl für Höhere Mathematik und Numerische, 1999, .
[64] A. Wächter and L. T. Biegler, {\it On the implementation of primal-dual interior point filter line search algorithm for large-scale nonlinear programming}, Math. Program., 106 (2006), pp. 25-57, . · Zbl 1134.90542
[65] H. Wang and S. Xiang, {\it On the convergence rate of Legendre approximation}, Math. Comp., 81 (2011), pp. 861-877. · Zbl 1242.41016
[66] E. R. Westervelt, J. W. Grizzle, and D. E. Koditschek, {\it Hybrid zero dynamics of planar biped walkers}, IEEE Trans. Automat. Control, 48 (2003), pp. 42-56, . · Zbl 1364.70015
[67] T. Yang, E. R. Westervelt, A. Serrani, and J. P. Schmiedeler, {\it A framework for the control of stable aperiodic walking in underactuated planar bipeds}, Autonomous Robots, 27 (2009), pp. 277-290, .
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.