Anil V. Rao
Abstract
An algorithm is described to solve multiple-phase optimal control problems using a recently developed numerical method called the Gauss pseudospectral method. The algorithm is well suited for use in modern vectorized programming languages such as FORTRAN 95 and MATLAB. The algorithm discretizes the cost functional and the differential-algebraic equations in each phase of the optimal control problem. The phases are then connected using linkage conditions on the state and time. A large-scale nonlinear programming problem (NLP) arises from the discretization and the significant features of the NLP are described in detail. A particular reusable MATLAB implementation of the algorithm, called GPOPS, is applied to three classical optimal control problems to demonstrate its utility. The algorithm described in this article will provide researchers and engineers a useful software tool and a reference when it is desired to implement the Gauss pseudospectral method in other programming languages.
Supplemental Material
Available for Download
After publication two errors were found in the labeling of Figs. 2 and 4 of the article. In Fig. 2, the size of the main diagonal blocks should be labeled “(N +1)×(N +2).” In Fig. 4, column N + 2 of the main diagonal block was inadvertently omitted. This (N +2)th column should consist of all zero elements with the exception of the (N + 1,N + 2)th element which should contain a constant derivative.
Software for GPOPS, A MATLAB software for solving multiple-phase optimal control problems using the gauss pseudospectral method
- Balsa-Canto, E., Banga, J. R., Alonso, A. A., and Vassiliadis, V. S. 2001. Dynamic optimization of chemical and biochemical processes using restricted second-order information. Comput. Chem. Eng. 25, 4--6, 539--546.Google Scholar
Cross Ref
- Bate, R. R., Mueller, D. D., and White, J. E. 1971. Fundamentals of Astrodynamics. Dover Publications, New York, NY.Google Scholar
- Becerra, V. M. 2009. PSOPT Optimal Control Solver User Manual. University of Reading, Reading, U.K. http://www.psopt.org.Google Scholar
- Benson, D. A. 2004. A gauss pseudospectral transcription for optimal control. Ph.D. dissertation. MIT, Cambridge, MA.Google Scholar
- Benson, D. A., Huntington, G. T., Thorvaldsen, T. P., and Rao, A. V. 2006. Direct trajectory optimization and costate estimation via an orthogonal collocation method. J. Guid. Contr. Dynam. 29, 6, 1435--1440.Google ScholarCross Ref
- Betts, J. T. 1998. Survey of numerical methods for trajectory optimization. J. Guid. Contr. Dynam. 21, 3, 193--207.Google ScholarCross Ref
- Betts, J. T. 2001. Practical Methods for Optimal Control Using Nonlinear Programming. SIAM, Philadelphia, PA. Google ScholarDigital Library
- Betts, J. T. and Frank, P. D. 1994. A sparse nonlinear optimization algorithm. J. Optimiz. Theor. Appl. 82, 2, 193--207. Google ScholarDigital Library
- Betts, J. T. and Huffman, W. P. 1997. Sparse Optimal Control Software—SOCS, MEA-LR-085 Ed. Boeing Information and Support Services, Seattle, WA.Google Scholar
- Bryson, A. E. and Ho, Y.-C. 1975. Applied Optimal Control. Hemisphere Publishing, New York, NY.Google Scholar
- Byrd, R. H., Nocedal, J., and Waltz, R. 2006. KNITRO: An Integrated Package for Nonlinear Optimization. University of Colorado Boulder, CO, and Northwestern University, Evanston, IL.Google Scholar
- Canuto, C., Hussaini, M. Y., Quarteroni, A., and Zang, T. A. 1988. Spectral Methods in Fluid Dynamics. Spinger-Verlag, Heidelberg, Germany.Google Scholar
- Canuto, C. G., Hussaini, M. Y., Quarteroni, A., and Zang, T. A. 2007. Spectral Methods: Evolution to Complex Geometries and Applications to Fluid Dynamics. Spinger-Verlag, Heidelberg, Germany. Google ScholarCross Ref
- Cizniar, M., Fikar, M., and Latifi, M. A. 2006. Matlab dynamic optimization code dynopt user's guide. http://www.kirp.chtf.stuba.sk/fikar/research/dynopt/dynopt.htm.Google Scholar
- Curtis, A. R., Powell, M. J. D., and Reid, J. K. 1974. On the estimation of sparse Jacobian matrices. J. Inst. Math. Appl. 13, 1, 117--120.Google ScholarCross Ref
- Davis, P. and Rabinowitz, P. 1984. Methods of Numerical Integration. Academic Press, New York, NY.Google Scholar
- Don, W.-S. 2000. Pseudopack: A software for solving computational fluid dynamics problems. Tech. rep. Brown University, Providence, RI.Google Scholar
- Elnagar, G. and Kazemi, M. 1998. Pseudospectral chebyshev optimal control of constrained nonlinear dynamical systems. Computat. Optimiz. Appl. 11, 2, 195--217. Google ScholarDigital Library
- Elnagar, G., Kazemi, M., and Razzaghi, M. 1995. The pseudospectral legendre method for discretizing optimal control problems. IEEE Trans. Aut. Contr. 40, 10, 1793--1796.Google ScholarCross Ref
- Fahroo, F. and Ross, I. M. 2000. A spectral patching method for direct trajectory optimization. J. Astronaut. Sci. 48, 2--3, 269--286.Google Scholar
- Fahroo, F. and Ross, I. M. 2001. Costate estimation by a legendre pseudospectral method. J. Guid. Contr. Dynam. 24, 2, 270--277.Google ScholarCross Ref
- Fornberg, B. 1994. A review of pseudospectral methods for solving partial differential equations. Acta Numerica, 203--267.Google Scholar
- Fornberg, B. 1998. A Practical Guide to Pseudospectral Methods. Cambridge Monographs on Applied and Computational Mathematics. Cambridge University Press, Cambridge, U.K. New York, NY.Google Scholar
- Forth, S. A. 2006. An efficient overloaded implementation of forward mode automatic differentiation in matlab. ACM Trans. Math. Softw. 32, 2, 195--222. Google ScholarDigital Library
- Forth, S. A. and Edvall, M. M. 2007. User's Guide for MAD—A MATLAB Automatic Differentation Toolbox (TOMLAB/MAD) Version 1.4. TOMLAB Optimization, Inc., Pullman, WA.Google Scholar
- Gill, P. E., Murray, W., and Saunders, M. A. 2002. SNOPT: An sqp algorithm for large-scale constrained optimization. SIAM J. Optimiz. 12, 4, 979--1006. Google ScholarDigital Library
- Gill, P. E., Murray, W., and Saunders, M. A. 2006. User's Guide for SNOPT Version 7: Software for Large Scale Nonlinear Programming. Stanford University, Palo Alto, CA, and University of California, San Diego, La Jolla, CA.Google Scholar
- Goh, C. J. and Teo, K. L. 1988. Miser: A Fortran program for solving optimal control problems. Adv. Eng. Softw. 10, 2, 90--99. Google ScholarDigital Library
- Huntington, G. and Rao, A. V. 2007. A comparison of accuracy and computational efficiency of three pseudospectral methods. In Proceedings of Guidance, Navigation and Control Conference. American Institute of Aeronautics and Astrodynamics, Washington, DC.Google Scholar
- Huntington, G. T. 2007. Advancement and analysis of a gauss pseudospectral transcription for optimal control. Ph.D. dissertation. Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA.Google Scholar
- Huntington, G. T., Benson, D. A., and Rao, A. V. 2007. Design of optimal tetrahedral spacecraft formations. J. Astronaut. Sci. 55, 2, 141--169.Google ScholarCross Ref
- Huntington, G. T. and Rao, A. V. 2008a. A comparison of global and local collocation methods for optimal control. J. Guid. Contr. Dynam. 31, 2, 432--436.Google ScholarCross Ref
- Huntington, G. T. and Rao, A. V. 2008b. Optimal reconfiguration of spacecraft formations using the gauss pseudospecral method. J. Guid. Contr. Dynam. 31, 3, 689--698.Google ScholarCross Ref
- Jansch, C., Well, K. H., and Schnepper, K. 1994. GESOP—eine software umgebung zur simulation und optimierung. Proceedings des SFB.Google Scholar
- Jockenhovel, T. 2002. Optcontrolcentre, software package for dynamic optimization. http://OptControlCentre.com/.Google Scholar
- Kameswaran, S. and Biegler, L. T. 2008. Convergence rates for direct transcription of optimal control problems using collocation at Radau points. Comput. Optimiz. Appl. 41, 1(Sep.), 81--126. Google ScholarDigital Library
- Kirk, D. E. 2004. Optimal Control Theory: An Introduction. Dover Publications, New York, NY.Google Scholar
- Martins, J. R. R., Sturdza, P., and Alonso, J. J. 2003. The complex-step derivative approximation. ACM Trans. Math. Softw. 29, 3, 245--262. Google ScholarDigital Library
- Rao, A. V. 2003. Extension of a pseudospectral legendre method for solving non-sequential multiple-phase optimal control problems. In Proceedings of the AIAA Guidance, Navigation, and Control Conference, (Austin, TX). AIAA paper 2003-5634.Google ScholarCross Ref
- Ross, I. M. and Fahroo, F. 2001. User's Manual for DIDO 2001 α: A MATLAB Application for Solving Optimal Control Problems. Tech. rep. AAS-01-03. Department of Aeronautics and Astronautics, Naval Postgraduate School, Monterey, CA.Google Scholar
- Ross, I. M. and Fahroo, F. 2004a. Legendre pseudospectral approximations of optimal control problems. In New Trends in Nonlinear Dynamics and Control, and Their Applications, W. Kang, M. Xiao, and C. Borges, Eds. Lecture Notes in Control and Information Sciences, Vol. 295. Springer-Verlag, Heidelberg, Germany, 327--342.Google Scholar
- Ross, I. M. and Fahroo, F. 2004b. Pseudospectral knotting methods for solving optimal control problems. J. Guid. Contr. Dynam. 27, 3, 397--405.Google ScholarCross Ref
- Ross, I. M. and Fahroo, F. 2008a. Advances in pseusospectral methods. In Proceedings of the AIAA Guidance, Navigation, and Control Conference (Honolulu, HI). AIAA paper 2008-7309.Google Scholar
- Ross, I. M. and Fahroo, F. 2008b. Convergence of the costates do not imply convergence of the controls. J. Guid. Contr. Dynam. 31, 4, 1492--1497.Google ScholarCross Ref
- Rump, S. 2008. Intlab - interval laboratory. http://www.ti3.tu-harburg.de/rump/intlab/.Google Scholar
- Rutquist, P. and Edvall, M. 2008. PROPT: MATLAB Optimal Control Software. Tomlab Optimization, Inc. Pullman, WA.Google Scholar
- The Mathworks, Inc. 2008. MATLAB: A Language for Technical Computing. The Mathworks, Inc., Natick, MA.Google Scholar
- Trefethen, L. N. 2001. Spectral Methods in MATLAB. SIAM Press, Philadelphia, PA. Google ScholarDigital Library
- Vlases, W. G., Paris, S. W., Martens, M. J., and Hargraves, C. R. 1990. Optimal trajectories by implicit simulation. Tech. rep. WRDC-TR-90-3056. Boeing Aerospace and Electronics, Seattle, WA.Google Scholar
- Vlassenbroeck, J. and Doreen, R. V. 1988. A Chebyshev technique for solving nonlinear optimal control problems. IEEE Trans. Automat. Contr. 33, 4, 333--340.Google ScholarCross Ref
- von Stryk, O. 2000. User's Guide for DIRCOL (Version 2.1): A Direct Collocation Method for the Numerical Solution of Optimal Control Problems. Technical University, Munich, Germany.Google Scholar
- Weideman, J. A. C. and Reddy, S. C. 2000. A MATLAB differentiation matrix suite. ACM Trans. Math. Softw. 26, 4, 465--519. Google ScholarDigital Library
- Williams, P. 2004a. Application of pseudospectral methods for receding horizon control. J. Guid. Contr. Dynam. 27, 2, 310--314.Google ScholarCross Ref
- Williams, P. 2004b. Jacobi pseudospectral method for solving optimal control problems. J. Guid. Contr. Dynam. 27, 2, 293--297.Google ScholarCross Ref
- Williams, P. 2005. Hermite-Legendre-Gauss-Lobatto direct transcription methods in trajectory optimization. (AAS 05-131). Adv. Astronaut. Soci. 120, part 1, 465--484.Google Scholar
- Williams, P. 2008. User's Guide for DIRECT 2.0. Royal Melbourne Institute of Technology, Melbourne, Australia.Google Scholar
Index Terms
- Algorithm 902: GPOPS, A MATLAB software for solving multiple-phase optimal control problems using the gauss pseudospectral method
Recommendations
Corrigendum: Algorithm 902: GPOPS, a MATLAB software for solving multiple-phase optimal control problems using the gauss pseudospectral method
An algorithm is described to solve multiple-phase optimal control problems using a recently developed numerical method called the Gauss pseudospectral method. The algorithm is well suited for use in modern vectorized programming languages such as ...
Direct trajectory optimization and costate estimation of finite-horizon and infinite-horizon optimal control problems using a Radau pseudospectral method
A method is presented for direct trajectory optimization and costate estimation of finite-horizon and infinite-horizon optimal control problems using global collocation at Legendre-Gauss-Radau (LGR) points. A key feature of the method is that it ...
Brief paper: A unified framework for the numerical solution of optimal control problems using pseudospectral methods
A unified framework is presented for the numerical solution of optimal control problems using collocation at Legendre-Gauss (LG), Legendre-Gauss-Radau (LGR), and Legendre-Gauss-Lobatto (LGL) points. It is shown that the LG and LGR differentiation ...
Reviews
Leslie Stephen Jennings
Optimal control problems that consist of a number of state-connected phases, where the states of different phases may be different from each other, present a challenging computational problem. This paper shows how a finite dimensional optimization problem can be developed using a pseudo-spectral method to approximate the state and (continuous) control functions within each phase. Both states and controls are discretized. The authors successfully provide an educational paper on how their software, GPOPS, works. The actual pseudo-spectral approximation is a straightforward collocation at zeros of Legendre-Gauss polynomials for each phase. Most of the paper details how the various constraints are approximated within a phase and between phases, and the zero-nonzero structure of the resulting Jacobian matrices, which are needed for the optimization software. Links to automatic differentiation and simplifications for this process are discussed. Impressive results for three examples are presented, and the limitations of the method are noted. An extensive bibliography on both the pseudo-spectral method and optimal control software is included. Online Computing Reviews Service
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments