Lax-Oleinik-type formulas and efficient algorithms for certain high-dimensional optimal control problems
arXiv:2109.14849
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 dimension. 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.
References in corpus (18)
- DGM: A deep learning algorithm for solving partial differential equations
- Solving high-dimensional partial differential equations using deep learning
- The max-plus finite element method for solving deterministic optimal control problems: basic properties and convergence analysis
- Deep neural networks algorithms for stochastic control problems on finite horizon: convergence analysis
- On some neural network architectures that can represent viscosity solutions of certain high dimensional Hamilton--Jacobi partial differential equations
- Reachability-Based Safety and Goal Satisfaction of Unmanned Aerial Platoons on Air Highways
- Actor-Critic Method for High Dimensional Static Hamilton--Jacobi--Bellman Partial Differential Equations based on Neural Networks
- Curse of dimensionality reduction in max-plus based approximation methods: theoretical estimates and improved pruning algorithms
- Perspectives on characteristics based curse-of-dimensionality-free numerical approaches for solving Hamilton-Jacobi equations
- QRnet: optimal regulator design with LQR-augmented neural networks
- Rectified deep neural networks overcome the curse of dimensionality for nonsmooth value functions in zero-sum games of nonlinear stiff systems
- A new scalable algorithm for computational optimal control under uncertainty
- Deep neural networks algorithms for stochastic control problems on finite horizon: numerical applications
- Using Neural Networks to Compute Approximate and Guaranteed Feasible Hamilton-Jacobi-Bellman PDE Solutions
- Alternating Direction Method of Multipliers for Constrained Iterative LQR in Autonomous Driving
- Deep backward schemes for high-dimensional nonlinear PDEs
- Game representations for state constrained continuous time linear regulator problems
- A Computationally Efficient Hamilton-Jacobi-based Formula for State-Constrained Optimal Control Problems