Lax-Oleinik-Type Formulas and Efficient Algorithms for Certain High-Dimensional Optimal Control Problems

Abstract

Two of the main challenges in optimal control are solving problems with state-dependent running costs and developing efficient numerical solvers that are computationally tractable in high dimensions. In this paper, we provide analytical solutions to certain optimal control problems whose running cost depends on the state variable and with constraints on the control. We also provide Lax-Oleinik-type representation formulas for the corresponding Hamilton-Jacobi partial differential equations with state-dependent Hamiltonians. Additionally, we present an efficient, grid-free numerical solver based on our representation formulas, which is shown to scale linearly with the state dimension, and thus, to overcome the curse of dimensionality. Using existing optimization methods and the min-plus technique, we extend our numerical solvers to address more general classes of convex and nonconvex initial costs. We demonstrate the capabilities of our numerical solvers using implementations on a central processing unit (CPU) and a field-programmable gate array (FPGA). In several cases, our FPGA implementation obtains over a 10 times speedup compared to the CPU, which demonstrates the promising performance boosts FPGAs can achieve. Our numerical results show that our solvers have the potential to serve as a building block for solving broader classes of high-dimensional optimal control problems in real-time.

Keywords

Optimal control / Hamilton-Jacobi partial differential equations / Grid-free numerical methods / High dimensions / Field-programmable gate arrays (FPGAs)

References

[1.] Aĭpanov SA, Murzabekov ZN. Analytical solution of a linear quadratic optimal control problem with control value constraints on the value of the control. J. Comput. Syst. Sci. Int., 2014, 53: 84-91,

[2.] Akian, M., Bapat, R., Gaubert, S.: Max-plus algebra. In: Hogben, L. (ed) Handbook of Linear Algebra, vol. 39, pp. 10–14. Chapman and Hall/CRC, Boca Raton (2006)

[3.] Akian M, Gaubert S, Lakhoua A. The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis. SIAM J. Control. Optim., 2008, 47(2): 817-848,

[4.] Alla A, Falcone M, Saluzzi L. An efficient DP algorithm on a tree-structure for finite horizon optimal control problems. SIAM J. Sci. Comput., 2019, 41(4): A2384-A2406,

[5.] Alla A, Falcone M, Volkwein S. Error analysis for POD approximations of infinite horizon problems via the dynamic programming approach. SIAM J. Control. Optim., 2017, 55(5): 3091-3115,

[6.] Bachouch A, Huré C, Langrené N, Pham H. Deep neural networks algorithms for stochastic control problems on finite horizon: numerical applications. Methodol. Comput. Appl. Probab., 2022, 24(1): 143-178,

[7.] Bansal, S., Tomlin, C.: Deepreach: a deep learning approach to high-dimensional reachability. In: 2021 IEEE International Conference on Robotics and Automation (ICRA), Xi’an, China, 2021, pp. 1817–1824 (2021)

[8.] Bardi, M., Capuzzo-Dolcetta, I.: Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston (1997). https://doi.org/10.1007/978-0-8176-4755-1 (With appendices by Maurizio Falcone and Pierpaolo Soravia)

[9.] Bellman RE. . Adaptive Control Processes: a Guided Tour, 1961 Princeton Princeton University Press,

[10.] Bertsekas DP. . Reinforcement Learning and Optimal Control, 2019 Belmont Athena Scientific

[11.] Bokanowski O, Garcke J, Griebel M, Klompmaker I. An adaptive sparse grid semi-Lagrangian scheme for first order Hamilton-Jacobi Bellman equations. J. Sci. Comput., 2013, 55(3): 575-605,

[12.] Boyd S, Parikh N, Chu E, Peleato B, Eckstein J. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn., 2011, 3(1): 1-122,

[13.] Burachik RS, Kaya CY, Majeed SN. A duality approach for solving control-constrained linear-quadratic optimal control problems. SIAM J. Control. Optim., 2014, 52(3): 1423-1456,

[14.] Cannon, M., Liao, W., Kouvaritakis, B.: Efficient MPC optimization using Pontryagin’s minimum principle. In: Proceedings of the 45th IEEE Conference on Decision and Control, pp. 5459–5464 (2006). https://doi.org/10.1109/CDC.2006.377753

[15.] Chen, J., Zhan, W., Tomizuka, M.: Constrained iterative LQR for on-road autonomous driving motion planning. In: 2017 IEEE 20th International Conference on Intelligent Transportation Systems (ITSC), pp. 1–7 (2017). https://doi.org/10.1109/ITSC.2017.8317745

[16.] Chen J, Zhan W, Tomizuka M. Autonomous driving motion planning with constrained iterative LQR. IEEE Trans. Intell. Veh., 2019, 4(2): 244-254,

[17.] Chen M, Hu Q, Fisac JF, Akametalu K, Mackin C, Tomlin CJ. Reachability-based safety and goal satisfaction of unmanned aerial platoons on air highways. J. Guid. Control. Dyn., 2017, 40(6): 1360-1373,

[18.] Coupechoux, M., Darbon, J., Kèlif, J., Sigelle, M.: Optimal trajectories of a UAV base station using Lagrangian mechanics. In: IEEE INFOCOM 2019—IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 626–631 (2019)

[19.] Darbon J. On convex finite-dimensional variational methods in imaging sciences and Hamilton-Jacobi equations. SIAM J. Imag. Sci., 2015, 8(4): 2268-2293,

[20.] Darbon, J., Dower, P.M., Meng, T.: Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and Hamilton-Jacobi PDEs. Math. Control Signals Syst. 1–44 (2022)

[21.] Darbon J, Langlois GP, Meng T. Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures. Res. Math. Sci., 2020, 7(3): 20,

[22.] Darbon J, Meng T. On decomposition models in imaging sciences and multi-time Hamilton-Jacobi partial differential equations. SIAM J. Imag. Sci., 2020, 13(2): 971-1014,

[23.] Darbon J, Meng T. On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations. J. Comput. Phys., 2021, 425,

[24.] Darbon J, Meng T, Resmerita E. On Hamilton-Jacobi PDEs and image denoising models with certain nonadditive noise. J. Math. Imaging Vis., 2022, 64(4): 408-441,

[25.] Darbon J, Osher S. Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere. Res. Math. Sci., 2016, 3(19): 1-26,

[26.] Davis D, Yin W. Faster convergence rates of relaxed Peaceman-Rachford and ADMM under regularity assumptions. Math. Oper. Res., 2017, 42(3): 783-805,

[27.] Delahaye, D., Puechmorel, S., Tsiotras, P., Feron, E.: Mathematical models for aircraft trajectory design: a survey. In: Air Traffic Management and Systems, pp. 205–247. Springer Japan, Tokyo (2014)

[28.] Deng W, Yin W. On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput., 2016, 66(3): 889-916,

[29.] Denk, J., Schmidt, G.: Synthesis of a walking primitive database for a humanoid robot using optimal control techniques. In: Proceedings of IEEE-RAS International Conference on Humanoid Robots, pp. 319–326 (2001)

[30.] Djeridane, B., Lygeros, J.: Neural approximation of PDE solutions: an application to reachability computations. In: Proceedings of the 45th IEEE Conference on Decision and Control, pp. 3034–3039 (2006). https://doi.org/10.1109/CDC.2006.377184

[31.] Dolgov S, Kalise D, Kunisch KK. Tensor decomposition methods for high-dimensional Hamilton-Jacobi-Bellman equations. SIAM J. Sci. Comput., 2021, 43(3): A1625-A1650,

[32.] Dower, P.M., McEneaney, W.M., Cantoni, M.: Game representations for state constrained continuous time linear regulator problems. arXiv:1904.05552 (2019)

[33.] Dower, P.M., McEneaney, W.M., Zhang, H.: Max-plus fundamental solution semigroups for optimal control problems. In: 2015 Proceedings of the Conference on Control and Its Applications, pp. 368–375. SIAM (2015)

[34.] El Khoury, A., Lamiraux, F., Taïx, M.: Optimal motion planning for humanoid robots. In: 2013 IEEE International Conference on Robotics and Automation, pp. 3136–3141 (2013). https://doi.org/10.1109/ICRA.2013.6631013

[35.] Fallon M, Kuindersma S, Karumanchi S, Antone M, Schneider T, Dai H, D’Arpino CP, Deits R, DiCicco M, Fourie D, Koolen T, Marion P, Posa M, Valenzuela A, Yu K-T, Shah J, Iagnemma K, Tedrake R, Teller S. An architecture for online affordance-based perception and whole-body planning. J. Field Robot., 2015, 32(2): 229-254,

[36.] Feng, S., Whitman, E., Xinjilefu, X., Atkeson, C.G.: Optimization based full body control for the atlas robot. In: 2014 IEEE-RAS International Conference on Humanoid Robots, pp. 120–127 (2014). https://doi.org/10.1109/HUMANOIDS.2014.7041347

[37.] Fleming W, McEneaney W. A max-plus-based algorithm for a Hamilton-Jacobi-Bellman equation of nonlinear filtering. SIAM J. Control. Optim., 2000, 38(3): 683-710,

[38.] Fujiwara, K., Kajita, S., Harada, K., Kaneko, K., Morisawa, M., Kanehiro, F., Nakaoka, S., Hirukawa, H.: An optimal planning of falling motions of a humanoid robot. In: 2007 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 456–462 (2007). https://doi.org/10.1109/IROS.2007.4399327

[39.] Garcke J, Kröner A. Suboptimal feedback control of PDEs by solving HJB equations on adaptive sparse grids. J. Sci. Comput., 2017, 70(1): 1-28,

[40.] Gaubert, S., McEneaney, W., Qu, Z.: Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms. In: 2011 50th IEEE Conference on Decision and Control and European Control Conference, pp. 1054–1061. IEEE (2011)

[41.] Glowinski, R.: On alternating direction methods of multipliers: a historical perspective. In: Fitzgibbon, W., Kuznetsov, Y., Neittaanmäki, P., Pironneau, O. (eds) Modeling, Simulation and Optimization for Science and Technology. Computational Methods in Applied Sciences, vol. 34, pp. 59–82. Springer, Dordrecht (2014). https://doi.org/10.1007/978-94-017-9054-3_4

[42.] Han, J., Jentzen, A., E, W.: Solving high-dimensional partial differential equations using deep learning. Proc. Natl. Acad. Sci. 115(34), 8505–8510 (2018). https://doi.org/10.1073/pnas.1718942115

[43.] Hofer, M., Muehlebach, M., D’Andrea, R.: Application of an approximate model predictive control scheme on an unmanned aerial vehicle. In: 2016 IEEE International Conference on Robotics and Automation (ICRA), pp. 2952–2957 (2016). https://doi.org/10.1109/ICRA.2016.7487459

[44.] Horowitz, M.B., Damle, A., Burdick, J.W.: Linear Hamilton Jacobi Bellman equations in high dimensions. In: 53rd IEEE Conference on Decision and Control, pp. 5880–5887. IEEE (2014)

[45.] Hu C, Shu C-W. A discontinuous Galerkin finite element method for Hamilton-Jacobi equations. SIAM J. Sci. Comput., 1999, 21(2): 666-690,

[46.] Huré C, Pham H, Bachouch A, Langrené N. Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis. SIAM J. Numer. Anal., 2021, 59(1): 525-557,

[47.] Huré C, Pham H, Warin X. Deep backward schemes for high-dimensional nonlinear PDEs. Math. Comp., 2020, 89(324): 1547-1579,

[48.] Jaddu H. Spectral method for constrained linear-quadratic optimal control. Math. Comput. Simul., 2002, 58(2): 159-169,

[49.] Jiang, F., Chou, G., Chen, M., Tomlin, C.J.: Using neural networks to compute approximate and guaranteed feasible Hamilton-Jacobi-Bellman PDE solutions. arXiv:1611.03158 (2016)

[50.] Jiang G, Peng D. Weighted ENO schemes for Hamilton-Jacobi equations. SIAM J. Sci. Comput., 2000, 21(6): 2126-2143,

[51.] Jin L, Li S, Yu J, He J. Robot manipulator control using neural networks: a survey. Neurocomputing, 2018, 285: 23-34,

[52.] Jin P, Zhang Z, Kevrekidis IG, Karniadakis GE. Learning Poisson systems and trajectories of autonomous systems via Poisson neural networks. IEEE Trans. Neural Netw. Learn. Syst., 2022,

[53.] Jin P, Zhang Z, Zhu A, Tang Y, Karniadakis GE. SympNets: intrinsic structure-preserving symplectic networks for identifying Hamiltonian systems. Neural Netw., 2020, 132: 166-179,

[54.] Kalise D, Kundu S, Kunisch K. Robust feedback control of nonlinear PDEs by numerical approximation of high-dimensional Hamilton-Jacobi-Isaacs equations. SIAM J. Appl. Dyn. Syst., 2020, 19(2): 1496-1524,

[55.] Kalise D, Kunisch K. Polynomial approximation of high-dimensional Hamilton-Jacobi-Bellman equations and applications to feedback control of semilinear parabolic PDEs. SIAM J. Sci. Comput., 2018, 40(2): A629-A652,

[56.] Kang W, Wilcox LC. Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations. Comput. Optim. Appl., 2017, 68(2): 289-315,

[57.] Kastner, R., Matai, J., Neuendorffer, S.: Parallel Programming for FPGAs. arXiv:1805.03648v1 (2018)

[58.] Kim YH, Lewis FL, Dawson DM. Intelligent optimal control of robotic manipulators using neural networks. Automatica, 2000, 36(9): 1355-1364,

[59.] Kolokoltsov, V.N., Maslov, V.P.: Idempotent Analysis and Its Applications. Mathematics and Its Applications, vol. 401. Kluwer Academic Publishers Group, Dordrecht (1997). https://doi.org/10.1007/978-94-015-8901-7 (Translation of ıt Idempotent analysis and its application in optimal control (Russian), “Nauka” Moscow, 1994 [ MR1375021 (97d:49031)], Translated by V. E. Nazaikinskii, With an appendix by Pierre Del Moral)

[60.] Kuindersma S, Deits R, Fallon M, Valenzuela A, Dai H, Permenter F, Koolen T, Marion P, Tedrake R. Optimization-based locomotion planning, estimation, and control design for the atlas humanoid robot. Auton. Robot., 2016, 40(3): 429-455,

[61.] Kunisch K, Volkwein S, Xie L. HJB-POD-based feedback design for the optimal control of evolution problems. SIAM J. Appl. Dyn. Syst., 2004, 3(4): 701-722,

[62.] Lambrianides P, Gong Q, Venturi D. A new scalable algorithm for computational optimal control under uncertainty. J. Comput. Phys., 2020, 420,

[63.] Lee, D., Tomlin, C.J.: A computationally efficient Hamilton-Jacobi-based formula for state-constrained optimal control problems. arXiv:2106.13440 (2021)

[64.] Lee D, Tomlin CJ. A Hopf-Lax formula in Hamilton-Jacobi analysis of reach-avoid problems. IEEE Control Syst. Lett., 2021, 5(3): 1055-1060,

[65.] Lewis, F., Dawson, D., Abdallah, C.: Robot Manipulator Control: Theory and Practice. Control Engineering. Marcel Dekker Inc., New York (2004). https://books.google.com/books?id=BDS_PQAACAAJ

[66.] Li, A., Bansal, S., Giovanis, G., Tolani, V., Tomlin, C., Chen, M.: Generating robust supervision for learning-based visual navigation using Hamilton-Jacobi reachability. In: Bayen, A.M., Jadbabaie, A., Pappas, G., Parrilo, P.A., Recht, B., Tomlin, C., Zeilinger, M. (eds.) Proceedings of the 2nd Conference on Learning for Dynamics and Control, Proceedings of Machine Learning Research, vol. 120, pp. 500–510. PMLR, The Cloud (2020). http://proceedings.mlr.press/v120/li20a.html

[67.] Li, W., Todorov, E.: Iterative linear quadratic regulator design for nonlinear biological movement systems. In: 2004 International Conference on Informatics in Control, Automation and Robotics, pp. 222–229. Citeseer (2004)

[68.] Lin, F., Brandt, R.D.: An optimal control approach to robust control of robot manipulators. IEEE Trans. Robot. Automat. 14(1), 69–77 (1998). https://doi.org/10.1109/70.660845

[69.] Ma J, Cheng Z, Zhang X, Tomizuka M, Lee TH. Alternating direction method of multipliers for constrained iterative LQR in autonomous driving. IEEE Trans. Intell. Transp. Syst., 2022, 23: 23031-23042,

[70.] McEneaney W. A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J. Control. Optim., 2007, 46(4): 1239-1276,

[71.] McEneaney, W.M.: Max-Plus Methods for Nonlinear Control and Estimation. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston (2006)

[72.] McEneaney, W.M., Deshpande, A., Gaubert, S.: Curse-of-complexity attenuation in the curse-of-dimensionality-free method for HJB PDEs. In: 2008 American Control Conference, pp. 4684–4690. IEEE (2008)

[73.] McEneaney WM, Dower PM. The principle of least action and fundamental solutions of mass-spring and N \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$N$$\end{document}-body two-point boundary value problems. SIAM J. Control. Optim., 2015, 53(5): 2898-2933,

[74.] McEneaney WM, Kluberg LJ. Convergence rate for a curse-of-dimensionality-free method for a class of HJB PDEs. SIAM J. Control. Optim., 2009, 48(5): 3052-3079,

[75.] Nakamura-Zimmerer T, Gong Q, Kang W. Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations. SIAM J. Sci. Comput., 2021, 43(2): A1221-A1247,

[76.] Nakamura-Zimmerer T, Gong Q, Kang W. QRnet: optimal regulator design with LQR-augmented neural networks. IEEE Control Syst. Lett., 2021, 5(4): 1303-1308,

[77.] Niarchos, K.N., Lygeros, J.: A neural approximation to continuous time reachability computations. In: Proceedings of the 45th IEEE Conference on Decision and Control, pp. 6313–6318 (2006). https://doi.org/10.1109/CDC.2006.377358

[78.] Onken D, Nurbekyan L, Li X, Fung SW, Osher S, Ruthotto L. A neural network approach for high-dimensional optimal control applied to multiagent path finding. IEEE Trans. Control Syst. Technol., 2022,

[79.] Osher S, Shu C-W. High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J. Numer. Anal., 1991, 28(4): 907-922,

[80.] Park JH, Han S, Kwon WH. LQ tracking controls with fixed terminal states and their application to receding horizon controls. Syst. Control Lett., 2008, 57(9): 772-777,

[81.] Parzani, C., Puechmorel, S.: On a Hamilton-Jacobi-Bellman approach for coordinated optimal aircraft trajectories planning. In: CCC 2017 36th Chinese Control Conference (CCC), Dalian, China, pp. 353–358. IEEE (2017). https://doi.org/10.23919/ChiCC.2017.8027369. https://hal-enac.archives-ouvertes.fr/hal-01340565

[82.] Prakash, S.K.: Managing HBM’s Bandwidth in Multi-die FPGAs Using Overlay NoCs. Master’s thesis, University of Waterloo (2021)

[83.] Reisinger, C., Zhang, Y.: Rectified deep neural networks overcome the curse of dimensionality for non-smooth value functions in zero-sum games of nonlinear stiff systems. Anal. Appl. (Singap.) 18(6), 951–999 (2020). https://doi.org/10.1142/S0219530520500116

[84.] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 317. Springer, Berlin (1998). https://doi.org/10.1007/978-3-642-02431-3

[85.] Royo, V.R., Tomlin, C.: Recursive regression with neural networks: approximating the HJI PDE solution. arXiv:1611.02739 (2016)

[86.] Rucco A, Sujit PB, Aguiar AP, de Sousa JB, Pereira FL. Optimal rendezvous trajectory for unmanned aerial-ground vehicles. IEEE Trans. Aerosp. Electron. Syst., 2018, 54(2): 834-847,

[87.] Russo, D.: Adaptation of High Performance and High Capacity Reconfigurable Systems to OpenCL Programming Environments. Master’s thesis, Universitat Politècnica de València (2020)

[88.] Sideris, A., Bobrow, J.E.: An efficient sequential linear quadratic algorithm for solving nonlinear optimal control problems. In: Proceedings of the 2005, American Control Conference, vol. 4, pp. 2275–2280. IEEE (2005). https://doi.org/10.1109/ACC.2005.1470308

[89.] Sirignano J, Spiliopoulos K. DGM: a deep learning algorithm for solving partial differential equations. J. Comput. Phys., 2018, 375: 1339-1364,

[90.] Todorov E. Efficient computation of optimal actions. Proc. Natl. Acad. Sci., 2009, 106(28): 11478-11483,

[91.] Yegorov I , Dower PM. Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations. Appl. Math. Optim., 2021, 83: 1-49,

[92.] Zhang H, Dower PM. A max-plus based fundamental solution for a class of discrete time linear regulator problems. Linear Algebra Appl., 2015, 471: 693-729,

[93.] Zhou M, Han J, Lu J. Actor-critic method for high dimensional static Hamilton-Jacobi-Bellman partial differential equations based on neural networks. SIAM J. Sci. Comput., 2021, 43(6): A4043-A4066,

Funding

Air Force Office of Scientific Research(AFOSR MURI FA9550-20-1-0358); U.S. Department of Energy(DOE-MMICS SEA-CROGS DE-SC0023191); U.S. Department of Defense(SMART Scholarship)