This paper presents a new onboard-implementable, real-time convex optimization-based powered-descent guidance algorithm for planetary pinpoint landing. Earlier work provided the theoretical basis of convexification, the equivalent representation of the fuel-optimal pinpoint landing trajectory optimization problem with nonconvex control constraints as a convex optimization problem. Once the trajectory optimization problem is convexified, interior-point method algorithms can be used to solve the problem to global optimality. Though having this guarantee of convergence motivated earlier convexification results, there were no real-time interior point method algorithms available for the computation of optimal trajectories on flight computers. This paper presents the first such algorithm developed for onboard use and flight-tested on a terrestrial rocket with the NASA Jet Propulsion Laboratory and the NASA Flight Opportunities Program in 2013. First, earlier convexification results are summarized and the resulting second-order cone-programming problem for fuel-optimal trajectory optimization is presented. Then, the proposed, fairly generic, second-order cone-programming interior point method algorithm is presented in detail with an overview of the customization process for real-time computations. Customization exploits a specific problem structure to increase the computational speed, which is shown to decrease run times by two to three orders of magnitude in many applications. A new convexification result for maximal-divert trajectories with active velocity constraints is also presented herein.

References

[1] Mendeck G. F. and Craig L. E., “Entry Guidance for the 2011 Mars Science Laboratory Mission,” AIAA Atmospheric Flight Mechanics Conference and Exhibit, AIAA Paper 2011-6639, 2011, pp. 8–11. doi:https://doi.org/10.2514/6.2011-6639 Google Scholar
[2] Steltzner A., “Overview of the Mars Science Laboratory Entry, Descent, and Landing System,” AIAA/AAS Spaceflight Mechanics Meeting, AAS Paper AAS 13-236, Kauai, HI, 2013. Google Scholar
[3] Way D. W., Powell R. W., Chen A., Steltzner A. D., San Martin A. M., Burkhart P. D. and Mendeck G. F., “Mars Science Laboratory: Entry, Descent, and Landing System Performance,” IEEE Aerospace Conference, Inst. of Electrical and Electronics Engineers Paper AERO.2007.352821, March 2006, pp. 1–19. doi:https://doi.org/10.1109/AERO.2007.352821 Google Scholar
[4] Ploen S., Açıkmeşe B. and Wolf A., “A Comparison of Powered Descent Guidance Laws for Mars Pinpoint Landing,” AIAA GNC Conference and Exhibit, AIAA Paper 2006-6676, 2006. doi:https://doi.org/10.2514/6.2006-6676 Google Scholar
[5] Eren U., Dueri D. and Açıkmeşe B., “Constrained Reachability and Controllability Sets for Planetary Precision Landing via Convex Optimization,” Journal of Guidance, Control, and Dynamics, Vol. 38, No. 11, 2015, pp. 2067–2083. Link Google Scholar
[6] Wolf A. A., Tooley J., Ploen S., Ivanov M., Acikmese B. and Gromov K., “Performance Trades for Mars Pinpoint Landing,” IEEE Aerospace Conference, Inst. of Electrical and Electronics Engineers Paper AERO.2006.1655793, 2006, pp. 1–0. doi:https://doi.org/10.1109/AERO.2006.1655793 Google Scholar
[7] Johnson A., Montgomery J. and Matthies L., “Vision Guided Landing of an Autonomous Helicopter in Hazardous Terrain,” Proceedings of IEEE International Conference on Robotics and Automation (ICRA), IEEE Publ., Piscataway, NJ, 2005, pp. 3966–3971. doi:https://doi.org/10.1109/ROBOT.2005.1570727 Google Scholar
[8] Açıkmeşe B. and Ploen S. R., “Convex Programming Approach to Powered Descent Guidance for Mars Landing,” Journal of Guidance, Control and Dynamics, Vol. 30, No. 5, 2007, pp. 1353–1366. doi:https://doi.org/10.2514/1.27553 Link Google Scholar
[9] Açıkmeşe B., Carson J. and Blackmore L., “Lossless Convexification of Non-Convex Control Bound and Pointing Constraints of the Soft Landing Optimal Control Problem,” IEEE Transactions on Control Systems Technology, Vol. 21, No. 6, 2013, pp. 2104–2113. doi:https://doi.org/10.1109/TCST.2012.2237346 IETTE2 1063-6536 Crossref Google Scholar
[10] Blackmore L., Açıkmeşe B. and Scharf D. P., “Minimum Landing Error Powered Descent Guidance for Mars Landing Using Convex Optimization,” Journal of Guidance, Control and Dynamics, Vol. 33, No. 4, 2010, pp. 1161–1171. doi:https://doi.org/10.2514/1.47202 Link Google Scholar
[11] Liu X. and Lu P., “Solving Nonconvex Optimal Control Problems by Convex Optimization,” Journal of Guidance, Control, and Dynamics, Vol. 37, No. 3, 2014, pp. 750–765. doi:https://doi.org/10.2514/1.62110 JGCODS 0731-5090 Link Google Scholar
[12] Meditch J. S., “On the Problem of Optimal Thrust Programming for a Lunar Soft Landing,” IEEE Transactions on Automatic Control, Vol. 9, No. 4, 1964, pp. 477–484. doi:https://doi.org/10.1109/TAC.1964.1105758 IETAA9 0018-9286 Crossref Google Scholar
[13] Klumpp A. R., “Apollo Lunar Descent Guidance,” Automatica, Vol. 10, No. 2, 1974, pp. 133–146. doi:https://doi.org/10.1016/0005-1098(74)90019-3 ATCAA9 0005-1098 Crossref Google Scholar
[14] Najson F. and Mease K. D., “Computationally Inexpensive Guidance Algorithm for Fuel-Efficient Terminal Descent,” Journal of Guidance, Control, and Dynamics, Vol. 29, No. 4, 2006, pp. 955–964. doi:https://doi.org/10.2514/1.17715 JGCODS 0731-5090 Link Google Scholar
[15] Topcu U., Casoliva J. and Mease K. D., “Minimum-Fuel Powered Descent for Mars Pinpoint Landing,” Journal of Spacecraft and Rockets, Vol. 44, No. 2, 2007, pp. 324–331. doi:https://doi.org/10.2514/1.25023 JSCRAG 0022-4650 Link Google Scholar
[16] Steinfeld B. A., Grant M. J., Matz D. A., Braun R. D. and Barton G. H., “Guidance, Navigation and Control System Performance Trades for Mars Pinpoint Landing,” Journal of Spacecraft and Rockets, Vol. 47, No. 1, 2010, pp. 188–198. doi:https://doi.org/10.2514/1.45779 JSCRAG 0022-4650 Link Google Scholar
[17] Açıkmeşe B. and Ploen S. R., “A Powered Descent Guidance Algorithm for Mars Pinpoint Landing,” AIAA GNC Conference and Exhibit, AIAA Paper 2005-6288, 2005. doi:https://doi.org/10.2514/6.2005-6288 Google Scholar
[18] Blackmore L., Açıkmeşe B. and Carson J. M., “Lossless Convexification of Control Constraints for a Class of Nonlinear Optimal Control Problems,” System and Control Letters, Vol. 61, No. 8, 2012, pp. 863–870. doi:https://doi.org/10.1016/j.sysconle.2012.04.010 Crossref Google Scholar
[19] Harris M. W. and Açıkmeşe B., “Maximum Divert for Planetary Landing Using Convex Optimization,” Journal of Optimization Theory and Applications, Vol. 162, No. 3, 2014, pp. 975–995. Crossref Google Scholar
[20] Nesterov Y. and Nemirovsky A., Interior-Point Polynomial Methods in Convex Programming, SIAM, Philadelphia, PA, 1994. Crossref Google Scholar
[21] Boyd S. and Vandenberghe L., Convex Optimization, Cambridge Univ. Press, Cambridge, England, 2004. Crossref Google Scholar
[22] Peng J., Roos C. and Terlaky T., Self-Regularity: A New Paradigm for Primal-Dual Interior-Point Algorithms, Princeton Series in Applied Mathematics, Univ. Press, Princeton, NJ, 2001. Google Scholar
[23] Mattingley J. and Boyd S., “CVXGEN: A Code Generator for Embedded Convex Optimization,” Optimization and Engineering, Vol. 13, No. 1, 2012, pp. 1–27. doi:https://doi.org/10.1007/s11081-011-9176-9 Crossref Google Scholar
[24] Dueri D., Zhang J. and Açıkmeşe B., “Automated Custom Code Generation for Embedded, Real-Time Second Order Cone Programming,” IFAC World Congress, IFAC Paper 1003.02736, 2014, pp. 1605–1612. doi:https://doi.org/10.3182/20140824-6-ZA-1003.02736 Google Scholar
[25] Mattingley J. and Boyd S., “Real-Time Convex Optimization in Signal Processing,” IEEE Signal Processing Magazine, Vol. 27, No. 3, 2010, pp. 50–61. doi:https://doi.org/10.1109/MSP.2010.936020 ISPRE6 1053-5888 Crossref Google Scholar
[26] Domahidi A., Chu E. and Boyd S., “ECOS: An SOCP Solver for Embedded Systems,” Proceedings European Control Conference, Inst. of Electrical and Electronics Paper 13936337, 2013, pp. 3071–3076. Google Scholar
[27] Frick D., Domahidi A. and Morari M., “Embedded Optimization for Mixed Logical Dynamical Systems,” Computers and Chemical Engineering, Vol. 72, Jan. 2015, pp. 21–33, A Tribute to Ignacio E. Grossmann. doi:https://doi.org/10.1016/j.compchemeng.2014.06.005 CCENDW 0098-1354 Crossref Google Scholar
[28] Açıkmeşe B., Aung M., Casoliva J., Mohan S., Johnson A., Scharf D., Masten D., Scotkin J., Wolf A. and Regehr M. W., “Flight Testing of Trajectories Computed by G-FOLD: Fuel Optimal Large Divert Guidance Algorithm for Planetary Landing,” AAS/AIAA Spaceflight Mechanics Meeting, AAS Paper 13-386, 2013. Google Scholar
[29] Scharf D. P., Regehr M. W., Dueri D., Açıkmeşe B., Vaughan G. M., Benito J., Ansari H., Aung M., Johnson A., Masten D., Nietfeld S., Casoliva J. and Mohan S., “ADAPT Demonstrations of Onboard Large-Divert Guidance with a VTVL Rocket,” IEEE Aerospace Conference, Inst. of Electrical and Electronics Engineers Paper AERO.2014.6836462, 2014. doi:https://doi.org/10.1109/AERO.2014.6836462 Google Scholar
[30] “JPL, Masten Space Systems, and University of Texas, First Flight Testing of Real-Time G-FOLD, Guidance for Fuel Optimal Large Divert, Validation,” 12 Aug. 2013, http://www.jpl.nasa.gov/news/news.php?release=2013-247. Google Scholar
[31] Scharf D., Açikmeşe B., Dueri D., Casoliva J. and Benito J., “Implementation and Experimental Demonstration of Onboard Powered Descent Guidance,” Journal of Guidance, Control, and Dynamics, 2015. JGCODS 0731-5090 Google Scholar
[32] Harris M. and Açıkmeşe B., “Lossless Convexification of Non-Convex Optimal Control Problems for State Constrained Linear Systems,” Automatica, Vol. 50, No. 9, 2014, pp. 2304–2311. doi:https://doi.org/10.1016/j.automatica.2014.06.008 ATCAA9 0005-1098 Crossref Google Scholar
[33] Pontryagin L. S., Boltyanskii V. G., Gamkrelidze V. G. and Mischenko E. F., The Mathematical Theory of Optimal Processes, Pergamon Press, Oxford, England, 1964. Google Scholar
[34] Berkovitz L. D., Optimal Control Theory, Springer–Verlag, New York, 1975. Google Scholar
[35] Milyutin A. and Osmolovskii N., Calculus of Variations and Optimal Control, American Mathematical Society, Providence, Rhode Island, 1998. Crossref Google Scholar
[36] JPL, Systems, M. S., and of Texas at Austin, U., “750 Meter Divert Xombie Test Flight for G-FOLD, Guidance for Fuel Optimal Large Divert, Validation,” Sept. 2013, http://www.jpl.nasa.gov/video/?id=1270 [retrieved April 2015]. Google Scholar
[37] Kim Y. and Mesbahi M., “Quadratically Constrained Attitude Control via Semidefinite Programming,” IEEE Transactions on Automatic Control, Vol. 49, No. 5, 2004, pp. 731–735. doi:https://doi.org/10.1109/TAC.2004.825959 IETAA9 0018-9286 Crossref Google Scholar
[38] Lee U. and Mesbahi M., “Constrained Consensus via Logarithmic Barrier Functions,” 50th IEEE Conference on Decision and Control and European Control Conference (CDC-ECC), Inst. of Electrical and Electronics Engineers Paper CDC.2011.6161496, 2011, pp. 3608–3613. doi:https://doi.org/10.1109/CDC.2011.6161496 Google Scholar
[39] Mehrotra S., “On the Implementation of a Primal-Dual Interior Point Method,” SIAM Journal on Optimization, Vol. 2, No. 4, 1992, pp. 575–601. doi:https://doi.org/10.1137/0802028 SJOPE8 1095-7189 Crossref Google Scholar
[40] Mehrotra S. and Sun J., “A Method of Analytic Centers for Quadratically Constrained Convex Quadratic Programs,” SIAM Journal on Numerical Analysis, Vol. 28, No. 2, 1991, pp. 529–544. doi:https://doi.org/10.1137/0728029 SJNAEQ 0036-1429 Crossref Google Scholar
[41] Karmarkar N., “A New Polynomial-Time Algorithm for Linear Programming,” Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, ACM, New York, 1984, pp. 302–311. doi:https://doi.org/10.1145/800057.808695 Google Scholar
[42] Wright S. J., Primal-Dual Interior-Point Methods, Vol. 54, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1997. Crossref Google Scholar
[43] Nocedal J. and Wright S. J., Numerical Optimization, edited by Mikosch T. V., Robinson S. M. and Resnick S. I., Springer Series in Operations Research, Springer, New York, 1999. Crossref Google Scholar
[44] Wang B., “Implementation of Interior Point Methods for Second Order Conic Optimization,” Master’s Thesis, McMaster Univ., Hamilton, ON, 2003. Google Scholar
[45] Vandenberghe L., “The CVXOPT Linear and Quadratic Cone Program Solvers,” 2010, http://www.seas.ucla.edu/vandenbe. Google Scholar
[46] Nesterov Y. and Nemirovski A., Interior Point Polynomial Algorithms in Convex Programming, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1994. Crossref Google Scholar
[47] Nesterov Y. E. and Todd M. J., “Self-Scaled Barriers and Interior-Point Methods for Convex Programming,” Mathematics of Operations Research, Vol. 22, No. 1, Feb. 1997, pp. 1–42. doi:https://doi.org/10.1287/moor.22.1.1 MOREDQ 0364-765X Crossref Google Scholar
[48] Hager W. W., “Updating the Inverse of a Matrix,” SIAM Review, Vol. 31, No. 2, June 1989, pp. 221–239. doi:https://doi.org/10.1137/1031049 Crossref Google Scholar
[49] Amestoy P. R., Davis T. A. and Duff I. S., “Algorithm 837: AMD, An Approximate Minimum Degree Ordering Algorithm,” ACM Transactions on Mathematical Software, Vol. 30, No. 3, Sept. 2004, pp. 381–388. doi:https://doi.org/10.1145/1024074 ACMSCU 0098-3500 Crossref Google Scholar
[50] Açıkmeşe B. and Blackmore L., “Lossless Convexification for a Class of Optimal Control Problems with Nonconvex Control Constraints,” Automatica, Vol. 47, No. 2, 2011, pp. 341–347. doi:https://doi.org/10.1016/j.automatica.2010.10.037 ATCAA9 0005-1098 Crossref Google Scholar
[51] Açıkmese B., Blackmore L., Scharf D. P. and Wolf A., “Enhancements on the Convex Programming Based Powered Descent Guidance Algorithm for Mars Landing,” AIAA/AAS Astrodynamics Specialist Conference, AAS Paper 2008-6426, 2008. doi:https://doi.org/10.2514/6.2008-6426 Google Scholar
[52] Tutuncu R. H., Toh K. C. and Todd M. J., “Solving Semidefinite-Quadratic-Linear Problems Using SDPT3,” Mathematical Programming, Vol. 95, No. 2, Feb. 2003, pp. 189–217. Crossref Google Scholar
[53] Sturm J., “Using SeDuMi 1.02, a MATLAB Toolbox for Optimization over Symmetric Cones,” Optimization Methods and Software, Vols. 11–12, 1999, pp. 625–653, Ver. 1.05. Crossref Google Scholar
[54] Scharf D., Ploen S. and Açikmeşe B., “Interpolation-Enhanced Powered Descent Guidance for Onboard Nominal, Off-Nominal, and Multi-X Scenarios,” AIAA Guidance, Navigation, and Control Conference, AIAA Paper 2015-0850, 2015. doi:https://doi.org/10.2514/6.2015-0850 Google Scholar

Journal of Guidance, Control, and Dynamics, volume 40 issue 2 cover

Volume 40, Number 2February 2017

Special Issue on Computational Guidance and Control

Metrics

Crossmark

Information

Copyright © 2016 by Behçet Açıkmeşe. Published by the American Institute of Aeronautics and Astronautics, Inc., with permission. Copies of this paper may be made for personal and internal use, on condition that the copier pay the per-copy fee to the Copyright Clearance Center (CCC). All requests for copying and permission to reprint should be submitted to CCC at www.copyright.com; employ the ISSN 0731-5090 (print) or 1533-3884 (online) to initiate your request.

Topics

Keywords

Acknowledgments

This research was supported in part by Jet Propulsion Laboratory (JPL), California Institute of Technology, Contract No. 1492781. Part of this research was performed at JPL, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. Parts of this research are funded by Office of Naval Research Grant No. N00014-14-1-0314 and National Science Foundation Grant No. CNS-1619729. The authors thank Tim Canham of JPL, who supported the runtime characterization on a flight processor. We are grateful for our collaborators Lars Blackmore of SpaceX; John M. Carson, David S. Bayard, and Jordi Casoliva of JPL; Stephen Boyd of Stanford University; Jacob Mattingley of Metamarkets; and Ping Lu of Iowa State for their valuable comments and insights. We would also like to thank the anonymous reviewers, whose comments were very useful in improving the quality of the paper.

Digital

Received16 May 2015
Accepted13 May 2016
Published online9 August 2016

Customized Real-Time Interior-Point Methods for Onboard Powered-Descent Guidance

Abstract

References

What's Popular

Metrics

Information