Abstract
The solution of minimum-time feedback optimal control problems is generally achieved using the dynamic programming approach, in which the value function must be computed on numerical grids with a very large number of points. Classical numerical strategies, such as value iteration (VI) or policy iteration (PI) methods, become very inefficient if the number of grid points is large. This is a strong limitation to their use in real-world applications. To address this problem, the authors present a novel multilevel framework, where classical VI and PI are embedded in a full-approximation storage (FAS) scheme. In fact, the authors will show that VI and PI have excellent smoothing properties, a fact that makes them very suitable for use in multilevel frameworks. Moreover, a new smoother is developed by accelerating VI using Anderson’s extrapolation technique. The effectiveness of our new scheme is demonstrated by several numerical experiments.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Jurdjevic V, Geometric Control Theory, Cambridge University Press, Cambridge, 1996.
Lee E B and Markus L, Foundations of Optimal Control Theory, Wiley, New York, 1967.
Sussmann H J and Willems J C, 300 years of optimal control: From the brachystochrone to the maximum principle, IEEE Control Systems, 1997, 17: 32–44.
Bellman R, Dynamic Programming, Princeton University Press, Princeton, 1957.
Bardi M and Dolcetta I C, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, Birkhäuser, Basel, 1997.
Guo B and Wu T T, Numerical solution to optimal feedback control by dynamic programming approach: A local approximation algorithm, Journal of Systems Science and Complexity, 2017, 30(4): 782–802.
Chai L and Qian C, State feedback stabilization for a class of nonlinear time-delay systems via dynamic linear controllers, Journal of Systems Science and Complexity, 2014, 27(3): 453–462.
Falcone M and Ferretti R, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, Vol. 133, SIAM, 2014.
Howard R A, Dynamic programming, Manage. Sci., 1966, 12(5): 317–348.
Pollatschek M and Avi-Itzhak B, Algorithms for stochastic games with geometrical interpretation, Manage. Sci., 1969, 15(7): 399–415.
Puterman M L and Brumelle S L, On the convergence of policy iteration in stationary dynamic programming, Math. Oper. Res., 1979, 4(1): 60–69.
Alla A, Falcone M, and Kalise D, An efficient policy iteration algorithm for dynamic programming equations, SIAM J. Sci. Comput., 2015, 37(1): A181–A200.
Cacace S, Cristiani E, Falcone M, et al., A patchy dynamic programming scheme for a class of Hamilton-Jacobi-Bellman equations, SIAM J. Sci. Comput., 2012, 34(5): A2625–A2649.
Camilli F, Falcone M, Lanucara P, et al., A domain decomposition method for Bellman equations, Contemp. Math., 1994, 180: 477–477.
Festa A, Reconstruction of independent sub-domains for a class of Hamilton-Jacobi equations and application to parallel computing, ESAIM: Math. Model. Num., 2016, 50(4): 1223–1240.
Alla A, Haasdonk B, and Schmidt A, Feedback control of parametrized pdes via model order reduction and dynamic programming principle, Adv. Comput. Math., 2020, 46(1): 1–28.
Sun B, Tao Z Z, and Wang Y Y, Dynamic programming viscosity solution approach and its applications to optimal control problems, Mathematics Applied to Engineering, Modelling, and Social Issues, Springer, 2019, 363–420.
Sun B and Guo B Z, Convergence of an upwind finite-difference scheme for Hamilton-Jacobi-Bellman equation in optimal control, IEEE Transactions on Automatic Control, 2015, 60(11): 3012–3017.
Alla A, Fabrini G, and Falcone M, Coupling MPC and DP methods for an efficient solution of optimal control problems, IFIP Conference on System Modeling and Optimization, Springer, 2015, 68–77.
Fabrini G, Falcone M, and Volkwein S, Coupling MPC and HJB for the computation of POD-based feedback laws, European Conference on Numerical Mathematics and Advanced Applications, Springer, 2017, 941–949.
Annunziato M, Borzi A, Nobile F, et al., On the connection between the Hamilton-Jacobi-Bellman and the Fokker-Planck control frameworks, J. Appl. Math, 2014, 5(16): 2476–2484.
Anderson D, Iterative procedures for nonlinear integral equations, J. Assoc. Comput. Mach., 1965, 12: 547–560.
Walker H F and Ni P, Anderson acceleration for fixed-point iterations, SIAM J. Numer. Anal., 2011, 49(4): 1715–1735.
Walker H F, Anderson acceleration: Algorithms and implementations, WPI Math. Sciences Dept. Report MS-6-15-50, 2011.
Saad Y, Numerical Methods for Large Eigenvalue Problems, Manchester University Press, Manchester, UK, 1992.
Toth A and Kelley C, Convergence analysis for Anderson acceleration, SIAM J. Numer. Anal., 2015, 53(2): 805–819.
Hoppe R H, Multi-grid methods for Hamilton-Jacobi-Bellman equations, Numer. Math., 1986, 49(2–3): 239–254.
Han D and Wan J W, Multigrid methods for second order Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Bellman-Isaacs equations, SIAM J. Sci. Comput., 2013, 35(5): S323–S344.
Akian M and Detournay S, Multigrid methods for two-player zero-sum stochastic games, Numer. Linear Algebra Appl., 2012, 19(2): 313–342.
Hackbusch W, Multi-Grid Methods and Applications, Springer, New York, 2003.
Borzì A, Introduction to Multigrid Methods, Lecture Notes, 2011.
Fleming W and Rishel R, Deterministic and Sthochastic Optimal Control, Springer Verlag, New York, 1975.
Bardi M and Falcone M, An approximation scheme for the minimum time function, SIAM J. Control Optim., 1990, 28(4): 950–965.
Falcone M, Numerical solution of dynamic programming equations, Optimal Control and Viscosity Solutions of HJB Equations, Birkhäuser, Berlin, 1997.
Santos M S and Rust J, Convergence properties of policy iteration, SIAM J. Control Optim., 2004, 42(6): 2094–2115.
Gander W, Gander M J, and Kwok F, Scientific Computing — An Introduction Using Maple and Matlab, Vol. 11, Springer Science & Business, 2014.
Ulbrich M, Semismooth Newton Methods for Variational Inequalities and Constrained Optimization Problems in Function Spaces, SIAM, Philadelphia, PA, 2011.
Henson V E, Multigrid methods for nonlinear problems: An overview, Tech. rep., Lawrence Livermore National Lab., CA (US), 2002.
Borzì A, Ciaramella G, and Sprengel M, Formulation and Numerical Solution of Quantum Control Problems, SIAM, Philadelphia, PA, 2017.
Chen Y, Hou T, and Yi N, Variational discretization for optimal control problems governed by parabolic equations, Journal of Systems Science and Complexity, 2013, 26(6): 902–924.
Tang Y and Chen Y, Variational discretization for parabolic optimal control problems with control constraints, Journal of Systems Science and Complexity, 2012, 25(5): 880–895.
Gubisch M and Volkwein S, Proper orthogonal decomposition for linear-quadratic optimal control, Model Reduction and Approximation: Theory and Algorithms, SIAM, Philadelphia, PA, 2017.
Author information
Authors and Affiliations
Corresponding authors
Additional information
This paper was recommended for publication by Editor LIU Kang-Zhi.
Rights and permissions
About this article
Cite this article
Ciaramella, G., Fabrini, G. Multilevel Techniques for the Solution of HJB Minimum-Time Control Problems. J Syst Sci Complex 34, 2069–2091 (2021). https://doi.org/10.1007/s11424-021-0253-7
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11424-021-0253-7