Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and Hamilton–Jacobi PDEs

  • Original Article
  • Published:
Mathematics of Control, Signals, and Systems Aims and scope Submit manuscript

Abstract

Solving high-dimensional optimal control problems and corresponding Hamilton–Jacobi PDEs are important but challenging problems in control engineering. In this paper, we propose two abstract neural network architectures which are, respectively, used to compute the value function and the optimal control for certain class of high-dimensional optimal control problems. We provide the mathematical analysis for the two abstract architectures. We also show several numerical results computed using the deep neural network implementations of these abstract architectures. A preliminary implementation of our proposed neural network architecture on FPGAs shows promising speedup compared to CPUs. This work paves the way to leverage efficient dedicated hardware designed for neural networks to solve high-dimensional optimal control problems and Hamilton–Jacobi PDEs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13
Fig. 14
Fig. 15
Fig. 16
Fig. 17
Fig. 18

Similar content being viewed by others

References

  1. Aggarwal CC et al (2018) Neural networks and deep learning. Springer 10:978

    Google Scholar 

  2. Akian M, Bapat R, Gaubert S (2006) Max-plus algebra. Handbook of linear algebra 39

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

    Article  MathSciNet  MATH  Google Scholar 

  4. Albi G, Bicego S, Kalise D (2021) Gradient-augmented supervised learning of optimal feedback laws using state-dependent riccati equations. Preprint arXiv:2103.04091

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  7. Anastassi AA (2014) Constructing Runge-Kutta methods with the use of artificial neural networks. Neural Comput Appl 25(1):229–236

    Article  Google Scholar 

  8. Bachouch A, Huré C, Langrené N, Pham H (2018) Deep neural networks algorithms for stochastic control problems on finite horizon: numerical applications. Preprint arXiv:1812.05916

  9. Balasubramaniam P, Abdul Samath J, Kumaresan N, Vincent Antony Kumar A (2006) Solution of matrix Riccati differential equation for the linear quadratic singular system using neural networks. Appl Math Comput 182(2):1832–1839. https://doi.org/10.1016/j.amc.2006.06.020

    Article  MathSciNet  MATH  Google Scholar 

  10. Balasubramaniam P, Vincent Antony Kumar A (2009) Solution of matrix Riccati differential equation for nonlinear singular system using genetic programming. Genet Programm Evol Mach 10(1):71–89. https://doi.org/10.1007/s10710-008-9072-z

    Article  Google Scholar 

  11. Banerjee K, Georganas E, Kalamkar D, Ziv B, Segal E, Anderson C, Heinecke A (2019) Optimizing deep learning RNN topologies on Intel architecture. Supercomput Front Innov 6(3)

  12. Bansal S, Tomlin C (2020) Deepreach: a deep learning approach to high-dimensional reachability. Preprint arXiv:2011.02082

  13. Bardi M, Capuzzo-Dolcetta I (1997) Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations. Systems & Control: Foundations & Applications. Birkhäuser Boston, Inc., Boston, MA . https://doi.org/10.1007/978-0-8176-4755-1. With appendices by Maurizio Falcone and Pierpaolo Soravia

  14. Bardi M, Da Lio F (1997) On the Bellman equation for some unbounded control problems. NoDEA Nonlinear Differ Equ Appl 4(4):491–510. https://doi.org/10.1007/s000300050027

    Article  MathSciNet  MATH  Google Scholar 

  15. Beck C, Becker S, Cheridito P, Jentzen A, Neufeld A (2019) Deep splitting method for parabolic PDEs. Preprint arXiv:1907.03452

  16. Beck C, Becker S, Grohs P, Jaafari N, Jentzen A (2018) Solving stochastic differential equations and Kolmogorov equations by means of deep learning. Preprint arXiv:1806.00421

  17. Beck C, Weinan E, Jentzen A (2019) Machine learning approximation algorithms for high-dimensional fully nonlinear partial differential equations and second-order backward stochastic differential equations. J Nonlinear Sci 29(4):1563–1619

  18. Bellman RE (1961) Adaptive control processes: a guided tour. Princeton university press

  19. Berg J, Nyström K (2018) A unified deep artificial neural network approach to partial differential equations in complex geometries. Neurocomputing 317:28–41. https://doi.org/10.1016/j.neucom.2018.06.056

    Article  Google Scholar 

  20. Bertsekas DP (2019) Reinforcement learning and optimal control. Athena Scientific, Belmont, Massachusetts

    Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  22. Boyd S, Parikh N, Chu E, Peleato B, Eckstein J (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3(1):1–122. https://doi.org/10.1561/2200000016

    Article  MATH  Google Scholar 

  23. Bucy R (1967) Global theory of the Riccati equation. J Comput Syst Sci 1(4):349–361. https://doi.org/10.1016/S0022-0000(67)80025-4

    Article  MathSciNet  MATH  Google Scholar 

  24. Butcher JC (2016) Numerical methods for ordinary differential equations. Wiley

  25. Cannarsa P, Sinestrari C (2004) Semiconcave functions, Hamilton-Jacobi equations, and optimal control, Progress in Nonlinear Differential Equations and their Applications, vol 58. Birkhäuser Boston Inc, Boston

    MATH  Google Scholar 

  26. Chan-Wai-Nam Q, Mikael J, Warin X (2019) Machine learning for semi linear PDEs. J Sci Comput 79(3):1667–1712

    Article  MathSciNet  MATH  Google Scholar 

  27. Chen M, Hu Q, Fisac JF, Akametalu K, Mackin C, Tomlin CJ (2017) Reachability-based safety and goal satisfaction of unmanned aerial platoons on air highways. J Guid Control Dyn 40(6):1360–1373. https://doi.org/10.2514/1.G000774

    Article  Google Scholar 

  28. Chen T, Chen H (1993) Approximations of continuous functionals by neural networks with application to dynamic systems. IEEE Trans Neural Netw 4(6):910–918. https://doi.org/10.1109/72.286886

    Article  Google Scholar 

  29. Chen T, van Gelder J, van de Ven B, Amitonov SV, de Wilde B, Euler HCR, Broersma H, Bobbert PA, Zwanenburg FA, van der Wiel WG (2020) Classification with a disordered dopant-atom network in silicon. Nature 577(7790):341–345

    Article  Google Scholar 

  30. Cheng T, Lewis FL (2006) Fixed-final time constrained optimal control of nonlinear systems using neural network HJB approach. In: Proceedings of the 45th IEEE conference on decision and control, pp 3016–3021. https://doi.org/10.1109/CDC.2006.377523

  31. Coupechoux M, Darbon J, Kélif J, Sigelle M (2019) 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. https://doi.org/10.1109/INFCOMW.2019.8845287

  32. Darbon J (2015) On convex finite-dimensional variational methods in imaging sciences and Hamilton-Jacobi equations. SIAM J Imag Sci 8(4):2268–2293. https://doi.org/10.1137/130944163

    Article  MathSciNet  MATH  Google Scholar 

  33. Darbon J, Langlois GP, Meng T (2020) Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures. Res Math Sci 7(3):20. https://doi.org/10.1007/s40687-020-00215-6

    Article  MathSciNet  MATH  Google Scholar 

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

  35. Darbon J, Meng T (2021) On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations. J Comput Phys 425:109907. https://doi.org/10.1016/j.jcp.2020.109907

    Article  MathSciNet  MATH  Google Scholar 

  36. Darbon J, Osher S (2016) Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere. Res Math Sci 3(1):19. https://doi.org/10.1186/s40687-016-0068-7

    Article  MathSciNet  MATH  Google Scholar 

  37. Davison E, Maki M (1973) The numerical solution of the matrix Riccati differential equation. IEEE Trans Autom Control 18(1):71–73

    Article  MATH  Google Scholar 

  38. Delahaye D, Puechmorel S, Tsiotras P, Feron E (2014) Mathematical models for aircraft trajectory design: A survey. In: Air traffic management and systems, Springer Japan, Tokyo, pp 205–247

  39. Denk J, Schmidt G (2001) 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

  40. Deshpande AS (2011) Max-plus representation for the fundamental solution of the time-varying differential Riccati equation. Automatica 47(8):1667–1676. https://doi.org/10.1016/j.automatica.2011.05.009

    Article  MathSciNet  MATH  Google Scholar 

  41. Dissanayake MWMG, Phan-Thien N (1994) Neural-network-based approximations for solving partial differential equations. Commun Numer Methods Eng 10(3):195–201. https://doi.org/10.1002/cnm.1640100303

    Article  MATH  Google Scholar 

  42. Djeridane B, Lygeros J (2006) Neural approximation of PDE solutions: An application to reachability computations. In: Proceedings of the 45th IEEE conference on decision and control, pp 3034–3039 . https://doi.org/10.1109/CDC.2006.377184

  43. Dockhorn T (2019) A discussion on solving partial differential equations using neural networks. Preprint arXiv:1904.07200

  44. Dolgov S, Kalise D, Kunisch K (2019) A tensor decomposition approach for high-dimensional Hamilton-Jacobi-Bellman equations. Preprint arXiv:1908.01533

  45. Dower P, McEneaney W, Cantoni M (2016) A dynamic game approximation for a linear regulator problem with a log-barrier state constraint. In: Proc. 22nd international symposium on mathematical theory of networks and systems, pp 297–304

  46. Dower PM, McEneaney WM (2015) A max-plus dual space fundamental solution for a class of operator differential Riccati equations. SIAM J Control Optim 53(2):969–1002. https://doi.org/10.1137/120879312

    Article  MathSciNet  MATH  Google Scholar 

  47. Dower PM, McEneaney WM, Cantoni M (2016) A game representation for state constrained linear regulator problems. In: 2016 IEEE 55th conference on decision and control (CDC), pp 1074–1079. https://doi.org/10.1109/CDC.2016.7798410

  48. Dower PM, McEneaney WM, Zhang H (2015) Max-plus fundamental solution semigroups for optimal control problems. In: 2015 proceedings of the conference on control and its applications. SIAM, pp 368–375

  49. Dower PM, Zhang H (2015) A new fundamental solution for differential Riccati equations arising in L2-gain analysis. In: 2015 5th Australian control conference (AUCC), pp 65–68

  50. El Khoury A, Lamiraux F, Taïx M (2013) Optimal motion planning for humanoid robots. In: 2013 IEEE international conference on robotics and automation, pp 3136–3141. https://doi.org/10.1109/ICRA.2013.6631013

  51. Fallon M, Kuindersma S, Karumanchi S, Antone M, Schneider T, Dai H, D’Arpino CP, Deits R, DiCicco M, Fourie D et al (2015) An architecture for online affordance-based perception and whole-body planning. J Field Robot 32(2):229–254

    Article  Google Scholar 

  52. Farabet C, LeCun Y, Kavukcuoglu K, Culurciello E, Martini B, Akselrod P, Talay S (2011) Large-scale FPGA-based convolutional networks. In: Bekkerman R, Bilenko M, Langford J (eds) Scaling up machine learning: parallel and distributed approaches. Cambridge University Press

  53. Farabet C, Poulet C, Han J, LeCun Y (2009) CNP: An FPGA-based processor for convolutional networks. In: International conference on field programmable logic and applications. IEEE, Prague

  54. Farabet C, Poulet C, LeCun Y (2009) An FPGA-based stream processor for embedded real-time vision with convolutional networks. In: 2009 IEEE 12th international conference on computer vision workshops, ICCV Workshops. IEEE Computer Society, Los Alamitos, CA, USA, pp 878–885. https://doi.org/10.1109/ICCVW.2009.5457611

  55. Farimani AB, Gomes J, Pande VS (2017) Deep Learning the Physics of Transport Phenomena. arXiv e-prints

  56. Feng S, Whitman E, Xinjilefu X, Atkeson CG (2014) Optimization based full body control for the atlas robot. In: 2014 IEEE-RAS international conference on humanoid robots, pp 120–127. https://doi.org/10.1109/HUMANOIDS.2014.7041347

  57. Feng L, Brandt RD (1998) An optimal control approach to robust control of robot manipulators. IEEE Trans Robot Autom 14(1):69–77. https://doi.org/10.1109/70.660845

    Article  Google Scholar 

  58. Fleming W, McEneaney W (2000) A max-plus-based algorithm for a Hamilton-Jacobi-Bellman equation of nonlinear filtering. SIAM J Control Optim 38(3):683–710. https://doi.org/10.1137/S0363012998332433

    Article  MathSciNet  MATH  Google Scholar 

  59. Fujii M, Takahashi A, Takahashi M (2019) Asymptotic expansion as prior knowledge in deep learning method for high dimensional BSDEs. Asia-Pacific Finan Markets 26(3):391–408. https://doi.org/10.1007/s10690-019-09271-7

    Article  MATH  Google Scholar 

  60. Fujiwara K, Kajita S, Harada K, Kaneko K, Morisawa M, Kanehiro F, Nakaoka S, Hirukawa H (2007) An optimal planning of falling motions of a humanoid robot. In: 2007 IEEE/RSJ international conference on intelligent robots and systems, pp 456–462. https://doi.org/10.1109/IROS.2007.4399327

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

    Article  MathSciNet  MATH  Google Scholar 

  62. Gaubert S, McEneaney W, Qu Z (2011) 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. IEEE, pp 1054–1061

  63. Glowinski R (2014) On alternating direction methods of multipliers: a historical perspective. Springer, Dordrecht, pp 59–82. https://doi.org/10.1007/978-94-017-9054-3_4

  64. Grüne L, Schaller M, Schiela A (2020) Exponential sensitivity and turnpike analysis for linear quadratic optimal control of general evolution equations. J Differ Equa 268(12):7311–7341. https://doi.org/10.1016/j.jde.2019.11.064

    Article  MathSciNet  MATH  Google Scholar 

  65. Grohs P, Jentzen A, Salimova D (2019) Deep neural network approximations for Monte Carlo algorithms. Preprint arXiv:1908.10828

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

  67. Han J, Zhang L, E W (2019) Solving many-electron Schrödinger equation using deep neural networks. J Comput Phys:108929

  68. He K, Zhang X, Ren S, Sun J (2016) Deep residual learning for image recognition. In: Proceedings of the IEEE conference on computer vision and pattern recognition (CVPR)

  69. Hirjibehedin C (2020) Evolution of circuits for machine learning. Nature 577:320–321. https://doi.org/10.1038/d41586-020-00002-x

    Article  Google Scholar 

  70. Hofer M, Muehlebach M, D’Andrea R (2016) 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 . https://doi.org/10.1109/ICRA.2016.7487459

  71. Hornik K (1991) Approximation capabilities of multilayer feedforward networks. Neural Netw 4(2):251–257. https://doi.org/10.1016/0893-6080(91)90009-T

    Article  MathSciNet  Google Scholar 

  72. Horowitz MB, Damle A, Burdick JW (2014) Linear Hamilton Jacobi Bellman equations in high dimensions. In: 53rd IEEE conference on decision and control. IEEE, pp 5880–5887

  73. Hsieh JT, Zhao S, Eismann S, Mirabella L, Ermon S (2019) Learning neural PDE solvers with convergence guarantees. In: International conference on learning representations

  74. Hu C, Shu C (1999) A discontinuous Galerkin finite element method for Hamilton-Jacobi equations. SIAM J Sci Comput 21(2):666–690. https://doi.org/10.1137/S1064827598337282

    Article  MathSciNet  MATH  Google Scholar 

  75. Huré C, Pham H, Bachouch A, Langrené N (2018) Deep neural networks algorithms for stochastic control problems on finite horizon, part I: convergence analysis. Preprint arXiv:1812.04300

  76. Huré C, Pham H, Warin X (2019) Some machine learning schemes for high-dimensional nonlinear PDEs. Preprint arXiv:1902.01599

  77. Jiang F, Chou G, Chen M, Tomlin CJ (2016) Using neural networks to compute approximate and guaranteed feasible Hamilton-Jacobi-Bellman PDE solutions. Preprint arXiv:1611.03158

  78. Jiang G, Peng D (2000) Weighted ENO schemes for Hamilton-Jacobi equations. SIAM J Sci Comput 21(6):2126–2143. https://doi.org/10.1137/S106482759732455X

    Article  MathSciNet  MATH  Google Scholar 

  79. Jianyu L, Siwei L, Yingjian Q, Yaping H (2003) Numerical solution of elliptic partial differential equation using radial basis function neural networks. Neural Netw 16(5–6):729–734

    Article  Google Scholar 

  80. Jin L, Li S, Yu J, He J (2018) Robot manipulator control using neural networks: a survey. Neurocomputing 285:23–34. https://doi.org/10.1016/j.neucom.2018.01.002

    Article  Google Scholar 

  81. Jin P, Zhang Z, Kevrekidis IG, Karniadakis GE (2020) Learning poisson systems and trajectories of autonomous systems via Poisson neural networks. IEEE Trans Neural Netw Learn Syst. https://doi.org/10.1109/TNNLS.2022.3148734

  82. Jin P, Zhang Z, Zhu A, Tang Y, Karniadakis GE (2020) SympNets:intrinsic structure-preserving symplectic networks for identifying Hamiltonian systems. Neural Netw 132:166–179. https://doi.org/10.1016/j.neunet.2020.08.017

    Article  MATH  Google Scholar 

  83. Jouppi NP, Young C, Patil N, Patterson D, Agrawal G, Bajwa R, Bates S, Bhatia S, Boden N, Borchers A, et al (2017) In-datacenter performance analysis of a tensor processing unit. In: Proceedings of the 44th Annual international symposium on computer architecture, ISCA ’17. Association for Computing Machinery, New York, NY, USA, p 1–12. https://doi.org/10.1145/3079856.3080246

  84. Kalise D, Kundu S, Kunisch K (2019) Robust feedback control of nonlinear PDEs by numerical approximation of high-dimensional Hamilton-Jacobi-Isaacs equations. Preprint arXiv:1905.06276

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

    Article  MathSciNet  MATH  Google Scholar 

  86. Kamali M (2015) A Study on Solution of Matrix Riccati Differential Equations Using Ant Colony Programming and Simulink. Institut Sains Matematik, Fakulti Sains, Universiti Malaya. https://books.google.com/books?id=0D8_nQAACAAJ

  87. Kang W, Gong Q (2020) Neural network approximations of compositional functions with applications to dynamical systems. Preprint arXiv:2012.01698

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

    Article  MathSciNet  MATH  Google Scholar 

  89. Kastner R, Matai J, Neuendorffer S (2018) Parallel Programming for FPGAs. ArXiv e-prints

  90. Kenney C, Leipnik R (1985) Numerical integration of the differential matrix Riccati equation. IEEE Trans Autom Control 30(10):962–970

    Article  MathSciNet  MATH  Google Scholar 

  91. Khoo Y, Lu J, Ying L (2017) Solving parametric PDE problems with artificial neural networks. Preprint arXiv:1707.03351

  92. Khoo Y, Lu J, Ying L (2019) Solving for high-dimensional committor functions using artificial neural networks. Res Math Sci 6(1):1

    Article  MathSciNet  MATH  Google Scholar 

  93. Kidger P, Lyons T (2020) Universal approximation with deep narrow networks. In: Abernethy J, Agarwal S (eds) Proceedings of thirty third conference on learning theory, Proceedings of machine learning research. PMLR,vol 125, pp 2306–2327. http://proceedings.mlr.press/v125/kidger20a.html

  94. Kim YH, Lewis FL, Dawson DM (2000) Intelligent optimal control of robotic manipulators using neural networks. Automatica 36(9):1355–1364. https://doi.org/10.1016/S0005-1098(00)00045-5

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  Google Scholar 

  96. Kundu A, Srinivasan S, Qin EC, Kalamkar D, Mellempudi NK, Das D, Banerjee K, Kaul B, Dubey P (2019) K-tanh: Hardware efficient activations for deep learning. arXiv:1909.07729

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

    Article  MathSciNet  MATH  Google Scholar 

  98. Lagaris IE, Likas A, Fotiadis DI (1998) Artificial neural networks for solving ordinary and partial differential equations. IEEE Trans Neural Netw 9(5):987–1000. https://doi.org/10.1109/72.712178

    Article  Google Scholar 

  99. Lagaris IE, Likas AC, Papageorgiou DG (2000) Neural-network methods for boundary value problems with irregular boundaries. IEEE Trans Neural Netw 11(5):1041–1049. https://doi.org/10.1109/72.870037

    Article  Google Scholar 

  100. Lambrianides P, Gong Q, Venturi D (2019) A new scalable algorithm for computational optimal control under uncertainty. Preprint arXiv:1909.07960

  101. LeCun Y (2019) 1.1 deep learning hardware: Past, present, and future. In: 2019 IEEE international solid- state circuits conference—(ISSCC), pp 12–19 . https://doi.org/10.1109/ISSCC.2019.8662396

  102. Lee D, Tomlin CJ (2021) A Hopf-Lax formula in Hamilton-Jacobi analysis of reach-avoid problems. IEEE Control Syst Lett 5(3):1055–1060. https://doi.org/10.1109/LCSYS.2020.3009933

    Article  MathSciNet  Google Scholar 

  103. Lee H, Kang IS (1990) Neural algorithm for solving differential equations. J Comput Phys 91(1):110–131

    Article  MathSciNet  MATH  Google Scholar 

  104. Leshno M, Lin VY, Pinkus A, Schocken S (1993) Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural Netw 6(6):861–867. https://doi.org/10.1016/S0893-6080(05)80131-5

    Article  Google Scholar 

  105. Levin JJ (1959) On the matrix Riccati equation. Proc Am Math Soc 10:519–524. https://doi.org/10.2307/2033645

    Article  MathSciNet  MATH  Google Scholar 

  106. Lewis F, Dawson D, Abdallah C (2004) Robot manipulator control: theory and practice. Control engineering. Marcel Dekker. https://books.google.com/books?id=BDS_PQAACAAJ

  107. Li A, Bansal S, Giovanis G, Tolani V, Tomlin C, Chen M (2020) Generating robust supervision for learning-based visual navigation using Hamilton-Jacobi reachability. In: Bayen AM, Jadbabaie A, Pappas G, Parrilo PA, Recht B, Tomlin C, Zeilinger M (eds) Proceedings of the 2nd conference on learning for dynamics and control, Proceedings of machine learning research. PMLR, THe Cloud, vol 120, pp 500–510. http://proceedings.mlr.press/v120/li20a.html

  108. Long Z, Lu Y, Dong B (2019) PDE-net 2.0: learning PDEs from data with a numeric-symbolic hybrid deep network. J Comput Phys 399:108925. https://doi.org/10.1016/j.jcp.2019.108925

    Article  MathSciNet  MATH  Google Scholar 

  109. Long Z, Lu Y, Ma X, Dong B (2017) PDE-net: Learning PDEs from data. Preprint arXiv:1710.09668

  110. Lu L, Jin P, Karniadakis GE (2019) Deeponet: Learning nonlinear operators for identifying differential equations based on the universal approximation theorem of operators. Preprint arXiv:1910.03193

  111. Lye KO, Mishra S, Ray D (2019) Deep learning observables in computational fluid dynamics. Preprint arXiv:1903.03040

  112. McEneaney W (2006) Max-plus methods for nonlinear control and estimation. Springer

  113. McEneaney W (2007) A curse-of-dimensionality-free numerical method for solution of certain HJB PDEs. SIAM J Control Optim 46(4):1239–1276. https://doi.org/10.1137/040610830

    Article  MathSciNet  MATH  Google Scholar 

  114. McEneaney WM (2008) A new fundamental solution for differential Riccati equations arising in control. Automatica 44(4):920–936. https://doi.org/10.1016/j.automatica.2007.08.019

    Article  MathSciNet  MATH  Google Scholar 

  115. McEneaney WM, Deshpande A, Gaubert S (2008) Curse-of-complexity attenuation in the curse-of-dimensionality-free method for HJB PDEs. In: 2008 American control conference. IEEE, pp 4684–4690

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

    Article  MathSciNet  MATH  Google Scholar 

  117. McFall KS, Mahan JR (2009) Artificial neural network method for solution of boundary value problems with exact satisfaction of arbitrary boundary conditions. IEEE Trans Neural Netw 20(8):1221–1233. https://doi.org/10.1109/TNN.2009.2020735

    Article  Google Scholar 

  118. Meade A, Fernandez A (1994) The numerical solution of linear ordinary differential equations by feedforward neural networks. Math Comput Model 19(12):1–25. https://doi.org/10.1016/0895-7177(94)90095-7

    Article  MathSciNet  MATH  Google Scholar 

  119. Meng X, Karniadakis GE (2019) A composite neural network that learns from multi-fidelity data: Application to function approximation and inverse PDE problems. J Comput Phys 401:109020

  120. Meng X, Li Z, Zhang D, Karniadakis GE (2019) PPINN: Parareal physics-informed neural network for time-dependent PDEs. Comput Methods Appl Mech Eng 370:113250

  121. van Milligen BP, Tribaldos V, Jiménez JA (1995) Neural network differential equation and plasma equilibrium solver. Phys Rev Lett 75:3594–3597. https://doi.org/10.1103/PhysRevLett.75.3594

    Article  Google Scholar 

  122. Nakamura-Zimmerer T, Gong Q, Kang W (2019) Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations. Preprint arXiv:1907.05317

  123. Nakamura-Zimmerer T, Gong Q, Kang W (2021) QRnet: Optimal regulator design with LQR-augmented neural networks. IEEE Control Syst Lett 5(4):1303–1308. https://doi.org/10.1109/LCSYS.2020.3034415

    Article  MathSciNet  Google Scholar 

  124. Niarchos KN, Lygeros J (2006) A neural approximation to continuous time reachability computations. In: Proceedings of the 45th IEEE conference on decision and control, pp 6313–6318 . https://doi.org/10.1109/CDC.2006.377358

  125. Osher S, Shu C (1991) High-order essentially nonoscillatory schemes for Hamilton-Jacobi equations. SIAM J Numer Anal 28(4):907–922. https://doi.org/10.1137/0728049

    Article  MathSciNet  MATH  Google Scholar 

  126. Pang G, Lu L, Karniadakis GE (2019) fPINNs: Fractional physics-informed neural networks. SIAM J Sci Comput 41(4):A2603–A2626

    Article  MathSciNet  MATH  Google Scholar 

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

  128. Pham H, Pham H, Warin X (2019) Neural networks-based backward scheme for fully nonlinear PDEs. Preprint arXiv:1908.00412

  129. Raissi M (2018) Deep hidden physics models: Deep learning of nonlinear partial differential equations. J. Mach Learn Res 19(1):932–955

    MathSciNet  MATH  Google Scholar 

  130. Raissi M (2018) Forward-backward stochastic neural networks: Deep learning of high-dimensional partial differential equations. Preprint arXiv:1804.07010

  131. Raissi M, Perdikaris P, Karniadakis G (2019) Physics-informed neural networks: A deep learning framework for solving forward and inverse problems involving nonlinear partial differential equations. J Comput Phys 378:686–707. https://doi.org/10.1016/j.jcp.2018.10.045

    Article  MathSciNet  MATH  Google Scholar 

  132. Raissi M, Perdikaris P, Karniadakis GE (2017) Physics informed deep learning (part i): Data-driven solutions of nonlinear partial differential equations. arXiv preprint arXiv:1711.10561

  133. Raissi M, Perdikaris P, Karniadakis GE (2017) Physics informed deep learning (part ii): Data-driven discovery of nonlinear partial differential equations. Preprint arXiv:1711.10566

  134. Reisinger C, Zhang Y (2019) Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems. Preprint arXiv:1903.06652

  135. Rossi F, Conan-Guez B (2005) Functional multi-layer perceptron: a non-linear tool for functional data analysis. Neural Netw 18(1):45–60. https://doi.org/10.1016/j.neunet.2004.07.001

    Article  MATH  Google Scholar 

  136. Royo VR, Tomlin C (2016) Recursive regression with neural networks: Approximating the HJI PDE solution. Preprint arXiv:1611.02739

  137. Rucco A, Sujit PB, Aguiar AP, de Sousa JB, Pereira FL (2018) Optimal rendezvous trajectory for unmanned aerial-ground vehicles. IEEE Trans Aerosp Electron Syst 54(2):834–847. https://doi.org/10.1109/TAES.2017.2767958

    Article  Google Scholar 

  138. Rudd K, Muro GD, Ferrari S (2014) A constrained backpropagation approach for the adaptive solution of partial differential equations. IEEE Trans Neural Netw Learn Syst 25(3):571–584. https://doi.org/10.1109/TNNLS.2013.2277601

    Article  Google Scholar 

  139. Samath JA, Selvaraju N (2010) Solution of matrix Riccati differential equation for nonlinear singular system using neural networks. Int J Comput Appl 1(29):49–55. https://doi.org/10.5120/575-181

    Article  Google Scholar 

  140. Sirignano J, Spiliopoulos K (2018) DGM: A deep learning algorithm for solving partial differential equations. J Comput Phys 375:1339–1364. https://doi.org/10.1016/j.jcp.2018.08.029

    Article  MathSciNet  MATH  Google Scholar 

  141. Subbotin AI (1996) Minimax solutions of first-order partial differential equations. Russ Math Surv 51(2):283–313. https://doi.org/10.1070/RM1996v051n02ABEH002773

    Article  MathSciNet  MATH  Google Scholar 

  142. Tang W, Shan T, Dang X, Li M, Yang F, Xu S, Wu J (2017) Study on a Poisson’s equation solver based on deep learning technique. In: 2017 IEEE electrical design of advanced packaging and systems symposium (EDAPS), pp 1–3. https://doi.org/10.1109/EDAPS.2017.8277017

  143. Tassa Y, Erez T (2007) Least squares solutions of the HJB equation with neural network value-function approximators. IEEE Trans Neural Netw 18(4):1031–1041. https://doi.org/10.1109/TNN.2007.899249

    Article  Google Scholar 

  144. Todorov E (2009) Efficient computation of optimal actions. Proc Natl Acad Sci 106(28):11478–11483

    Article  MATH  Google Scholar 

  145. Uchiyama T, Sonehara N (1993) Solving inverse problems in nonlinear PDEs by recurrent neural networks. In: IEEE international conference on neural networks. IEEE, pp 99–102

  146. E W (2017) A proposal on machine learning via dynamical systems. Commun Math Stat 5(1):1–11. https://doi.org/10.1007/s40304-017-0103-z

  147. E W, Han J, Jentzen A (2017) Deep learning-based numerical methods for high-dimensional parabolic partial differential equations and backward stochastic differential equations. Commun Math Stat 5(4):349–380. https://doi.org/10.1007/s40304-017-0117-

  148. E W, Han J, Li Q (2019) A mean-field optimal control formulation of deep learning. Res Math Sci 6(1):41. https://doi.org/10.1007/s40687-018-0172-y

  149. E W, Yu B (2018) The deep Ritz method: a deep learning-based numerical algorithmfor solving variational problems. Commun Math Stat 6(1):1–12

  150. Yadav N, Yadav A, Kumar M (2015) An introduction to neural network methods for differential equations. Springer briefs in applied sciences and technology. Springer, Dordrecht. https://doi.org/10.1007/978-94-017-9816-7

  151. Wang Y, Yong J (2014) A deterministic affine-quadratic optimal control problem. ESAIM COCV 20(3):633–661. https://doi.org/10.1051/cocv/2013078

  152. Yang L, Zhang D, Karniadakis GE (2018) Physics-informed generative adversarial networks for stochastic differential equations. SIAM J Sci Comput 42(1):A292–A317

  153. Yang Y, Perdikaris P (2019) Adversarial uncertainty quantification in physics-informed neural networks. J Comput Phys 394:136–152

    Article  MathSciNet  MATH  Google Scholar 

  154. Yegorov I, Dower PM (2017) Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton–Jacobi equations. Appl Math Optim:1–49

  155. Yong J, Zhou XY (1999) Stochastic controls, Applications of Mathematics (New York), vol 43. Springer, New York . https://doi.org/10.1007/978-1-4612-1466-3. Hamiltonian systems and HJB equations

  156. Zaslavski AJ (2015) Turnpike theory of continuous-time linear optimal control problems. Springer. https://doi.org/10.1007/978-3-319-19141-6

  157. Zhang D, Guo L, Karniadakis GE (2019) Learning in modal space: solving time-dependent stochastic PDEs using physics-informed neural networks. SIAM J Sci Comput 42(2):A639–A665

  158. Zhang D, Lu L, Guo L, Karniadakis GE (2019) Quantifying total uncertainty in physics-informed neural networks for solving forward and inverse stochastic problems. J Comput Phys 397:108850

    Article  MathSciNet  MATH  Google Scholar 

  159. Zhou XY (1990) Maximum principle, dynamic programming, and their connection in deterministic control. J Optim Theory Appl 65(2):363–373. https://doi.org/10.1007/BF01102352

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

This research is supported by AFOSR MURI FA9550-20-1-0358. The authors also thank the Xilinx Center of Excellence at the University of Illinois, Urbana-Champaign UIUC, for providing access to Xilinx Alveo boards and computing resources.

Author information

Authors and Affiliations

  1. Division of Applied Mathematics, Brown University, Providence, USA

    Jérôme Darbon

  2. Department of Electrical and Electronic Engineering, The University of Melbourne, Melbourne, Australia

    Peter M. Dower

  3. Department of Mathematics, UCLA, Los Angeles, USA

    Tingwei Meng

Authors
  1. Jérôme Darbon
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Peter M. Dower
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tingwei Meng
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jérôme Darbon.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Research supported by AFOSR MURI FA9550-20-1-0358.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

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. 35, 1–44 (2023). https://doi.org/10.1007/s00498-022-00333-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00498-022-00333-2

Keywords

Search

Navigation