Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations

DOI10.1007/S00245-018-9509-6MaRDI QIDQ2019982zbMATH OpenOpenAlexFDO

Authors Ivan Yegorov, Peter M. Dower

Publication date 22 April 2021

Published in Applied Mathematics and Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.03314

zbMATH Keywords

curse of dimensionalitydifferential gamesHamilton-Jacobi equationsoptimal controlmethod of characteristicsfeedback strategies

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Differential games and control (49N70) Hamilton-Jacobi equations (35F21) Optimality conditions for problems involving ordinary differential equations (49K15) Dynamic programming in optimal control and differential games (49L20) Viscosity solutions to Hamilton-Jacobi equations in optimal control and differential games (49L25) Finite difference methods for initial value and initial-boundary value problems involving PDEs (65M06) Numerical aspects of the method of characteristics for initial value and initial-boundary value problems involving PDEs (65M25) Numerical methods based on necessary conditions (49M05) Optimal feedback synthesis (49N35)

Abstract: This paper extends the considerations of the works [1, 2] regarding curse-of-dimensionality-free numerical approaches to solve certain types of Hamilton-Jacobi equations arising in optimal control problems, differential games and elsewhere. A rigorous formulation and justification for the extended Hopf-Lax formula of [2] is provided together with novel theoretical and practical discussions including useful recommendations. By using the method of characteristics, the solutions of some problem classes under convexity/concavity conditions on Hamiltonians (in particular, the solutions of Hamilton-Jacobi-Bellman equations in optimal control problems) are evaluated separately at different initial positions. This allows for the avoidance of the curse of dimensionality, as well as for choosing arbitrary computational regions. The corresponding feedback control strategies are obtained at selected positions without approximating the partial derivatives of the solutions. The results of numerical simulations demonstrate the high potential of the proposed techniques. It is also pointed out that, despite the indicated advantages, the related approaches still have a limited range of applicability, and their extensions to Hamilton-Jacobi-Isaacs equations in zero-sum two-player differential games are currently developed only for sufficiently narrow classes of control systems. That is why further extensions are worth investigating.

Recommendations

• Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations
• Algorithm for overcoming the curse of dimensionality for certain non-convex Hamilton-Jacobi equations, projections and differential games
• Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
• Stable numerical schemes for solving Hamilton-Jacobi-Bellman-Isaacs equations
• Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere

Cites work

• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 3168214 (Why is no real title available?)
• scientific article; zbMATH DE number 3862969 (Why is no real title available?)
• scientific article; zbMATH DE number 192835 (Why is no real title available?)
• scientific article; zbMATH DE number 3465097 (Why is no real title available?)
• scientific article; zbMATH DE number 3468574 (Why is no real title available?)
• scientific article; zbMATH DE number 3590092 (Why is no real title available?)
• scientific article; zbMATH DE number 1302349 (Why is no real title available?)
• scientific article; zbMATH DE number 1325009 (Why is no real title available?)
• scientific article; zbMATH DE number 706270 (Why is no real title available?)
• scientific article; zbMATH DE number 1173660 (Why is no real title available?)
• scientific article; zbMATH DE number 1181255 (Why is no real title available?)
• scientific article; zbMATH DE number 939851 (Why is no real title available?)
• scientific article; zbMATH DE number 2107361 (Why is no real title available?)
• scientific article; zbMATH DE number 3270165 (Why is no real title available?)
• scientific article; zbMATH DE number 3191476 (Why is no real title available?)
• A Curse-of-Dimensionality-Free Numerical Method for Solution of Certain HJB PDEs
• A Level Set Formulation for the Solution of the Dirichlet Problem for Hamilton–Jacobi Equations
• A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games
• Algorithm for overcoming the curse of dimensionality for time-dependent non-convex Hamilton-Jacobi equations arising from optimal control and differential games problems
• Algorithms for overcoming the curse of dimensionality for certain Hamilton-Jacobi equations arising in control theory and elsewhere
• An efficient data structure and accurate scheme to solve front propagation problems
• Controlled Markov processes and viscosity solutions
• Convergence Analysis for a Class of High-Order Semi-Lagrangian Advection Schemes
• Convergence rate for a curse-of-dimensionality-free method for a class of HJB PDEs
• Convex Analysis
• Differential Games
• Differential inclusions and optimal control
• Envelopes and nonconvex Hamilton-Jacobi equations
• Estimating error of the optimal grid design in the problems of nonlinear optimal control of prescribed duration
• Fast Semi-Lagrangian Schemes for the Eikonal Equation and Applications
• Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulations
• Generalized Hopf formulas for the nonautonomous Hamilton-Jacobi equation
• Geometry of optimal paths around focal singular surfaces in differential games
• High-Order Essentially Nonoscillatory Schemes for Hamilton–Jacobi Equations
• High-Order WENO Schemes for Hamilton--Jacobi Equations on Triangular Meshes
• Level set methods and dynamic implicit surfaces
• Max-plus methods for nonlinear control and estimation.
• Mitigating the curse of dimensionality: sparse grid characteristics method for optimal feedback control and HJB equations
• Model predictive control system design and implementation using \texttt{MATLAB}
• NUMERICAL METHODS FOR DIFFERENTIAL GAMES BASED ON PARTIAL DIFFERENTIAL EQUATIONS
• Numerical recipes. The art of scientific computing.
• Numerical solution of stochastic differential problems in the biosciences
• On the efficiency of optimal grid synthesis in optimal control problems with fixed terminal time
• On the structure of locally Lipschitz minimax solutions of the Hamilton-Jacobi-Bellman equation in terms of classical characteristics
• Optimal control and viscosity solutions of Hamilton-Jacobi-Bellman equations
• Probabilistic max-plus schemes for solving Hamilton-Jacobi-Bellman equations
• Reachability and Minimal Times for State Constrained Nonlinear Problems without Any Controllability Assumption
• The Existence of Value and Saddle Point in Games of Fixed Duration
• The Max-Plus Finite Element Method for Solving Deterministic Optimal Control Problems: Basic Properties and Convergence Analysis
• The method of characteristics for Hamilton-Jacobi equations and applications to dynamical optimization
• Two Approximations of Solutions of Hamilton-Jacobi Equations
• Weighted ENO Schemes for Hamilton--Jacobi Equations

Cited in

(15)

• On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton-Jacobi partial differential equations
• Robust Feedback Control of Nonlinear PDEs by Numerical Approximation of High-Dimensional Hamilton--Jacobi--Isaacs Equations
• Overcoming the curse of dimensionality for some Hamilton-Jacobi partial differential equations via neural network architectures
• A tree structure approach to reachability analysis
• Algorithms of data generation for deep learning and feedback design: a survey
• SympOCnet: Solving Optimal Control Problems with Applications to High-Dimensional Multiagent Path Planning Problems
• Neural network architectures using min-plus algebra for solving certain high-dimensional optimal control problems and Hamilton-Jacobi PDEs
• Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
• Adaptive deep learning for high-dimensional Hamilton-Jacobi-Bellman equations
• Reliable optimal controls for SEIR models in epidemiology
• scientific article; zbMATH DE number 7370565 (Why is no real title available?)
• Exploiting characteristics in stationary action problems
• Algorithm for Hamilton-Jacobi equations in density space via a generalized Hopf formula
• Algorithm for overcoming the curse of dimensionality for state-dependent Hamilton-Jacobi equations
• Tensor decomposition methods for high-dimensional Hamilton-Jacobi-Bellman equations

Describes a project that uses

Uses Software

• ToolboxLS
• ROC-HJ

This page was built for publication: Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019982)