Abstract
Semi-Lagrangian schemes for the discretization of the dynamic programming principle are based on a time discretization projected on a state-space grid. The use of a structured grid makes this approach not feasible for high-dimensional problems due to the curse of dimensionality. Here, we present a new approach for infinite horizon optimal control problems where the value function is computed using radial basis functions by the Shepard moving least squares approximation method on scattered grids. We propose a new method to generate a scattered mesh driven by the dynamics and the selection of the shape parameter in the RBF using an optimization routine. This mesh will help to localize the problem and approximate the dynamic programming principle in high dimension. Error estimates for the value function are also provided. Numerical tests for high dimensional problems will show the effectiveness of the proposed method.
Introduction
In the field of optimal control, the Hamilton-Jacobi-Bellman (HJB) equation serves as the fundamental tool for determining the value function, which dictates the optimal policy for any given state. However, traditional numerical methods for solving HJB equations suffer from the "curse of dimensionality." As the number of state variables increases—particularly when controlling partial differential equations (PDEs) discretized into thousands of dimensions—the computational cost of grid-based methods grows exponentially. This paper introduces a mesh-free approach that leverages Radial Basis Functions (RBFs) and dynamics-aware scattered grids to overcome these limitations.
Methodology
The proposed framework integrates three core innovations to enable high-dimensional control.
Shepard’s Moving Least Squares
Instead of relying on a rigid grid, the method employs Shepard’s moving least squares approximation. This RBF-based technique acts as a partition of unity, allowing for the interpolation of the value function across scattered points. Unlike global RBF methods that require solving large, dense linear systems, Shepard’s method is computationally efficient, calculating a weighted average of local nodes.
Dynamics-Driven Mesh Generation
To avoid populating the entire high-dimensional state space, the authors utilize a "scouting" mechanism. By simulating the system's dynamics under various initial conditions and controls, the algorithm identifies the regions of the state space that are actually reachable. Approximation nodes are then placed exclusively along these trajectories, effectively localizing the problem to the relevant manifold.
Residual-Based Shape Parameter Optimization
A critical challenge in RBF approximation is selecting the shape parameter ($\sigma$), which controls the "flatness" or "spikiness" of the basis functions.
The authors propose an automated selection process where the HJB equation's residual—the degree to which the current approximation fails to satisfy the governing equation—is used as an error signal. An optimization routine then tunes $\sigma$ to minimize this residual, ensuring high approximation accuracy without manual intervention.
Experimental Validation
The effectiveness of the HJB-RBF approach was evaluated across several benchmark problems:
- 2D Eikonal Equation: Validated the scattered grid approach against analytical solutions for minimum-time problems.
- Bilinear Advection Equation: Demonstrated the ability to control a system discretized into 10,201 dimensions, a scale previously unreachable for HJB solvers.
- Nonlinear Heat Equation: Tested robustness on a 961-dimensional parabolic PDE, showing the method converges efficiently even with non-smooth initial conditions.
Key Insights
The success of this method hinges on the principle of localization. By allowing the system's own dynamics to dictate the grid placement, the "curse of dimensionality" is mitigated. Furthermore, the authors provide mathematical guarantees, proving that the Shepard-based operator remains a contraction mapping, ensuring the stability and convergence of the iterative solver.
Conclusion
The HJB-RBF approach represents a significant step forward in the numerical control of high-dimensional PDEs. By combining mesh-free interpolation with dynamics-driven sampling and automated parameter tuning, the method achieves practical performance on problems with tens of thousands of dimensions. Future research may explore coupling this technique with Model Order Reduction (MOR) to further enhance computational speed for complex industrial applications.
Summary updated