@inproceedings{e87057bb359447fab7f9a4b5eca54156,
title = "An Adaptive Multi-Level Max-Plus Method for Deterministic Optimal Control Problems",
abstract = "We introduce a new numerical method to approximate the solution of a finite horizon deterministic optimal control problem. We exploit two Hamilton-Jacobi-Bellman PDE, arising by considering the dynamics in forward and backward time. This allows us to compute a neighborhood of the set of optimal trajectories, in order to reduce the search space. The solutions of both PDE are successively approximated by max-plus linear combinations of appropriate basis functions, using a hierarchy of finer and finer grids. We show that the sequence of approximate value functions obtained in this way does converge to the viscosity solution of the HJB equation in a neighborhood of optimal trajectories. Then, under certain regularity assumptions, we show that the number of arithmetic operations needed to compute an approximate optimal solution of a d-dimensional problem, up to a precision ε, is bounded by O(Cd|log ε|), for some constant C > 1, whereas ordinary grid-based methods have a complexity in O(1/εad) for some constant a > 0.",
keywords = "Hamilton-Jacobi-Bellman PDE, Optimal control, curse-of-dimensionality, dynamic programming, max-plus algebra",
author = "Marianne Akian and St{\'e}phane Gaubert and Shanqing Liu",
note = "Publisher Copyright: Copyright {\textcopyright} 2023 The Authors. This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/); 22nd IFAC World Congress ; Conference date: 09-07-2023 Through 14-07-2023",
year = "2023",
month = jul,
day = "1",
doi = "10.1016/j.ifacol.2023.10.628",
language = "English",
series = "IFAC-PapersOnLine",
publisher = "Elsevier B.V.",
number = "2",
pages = "7448--7455",
editor = "Hideaki Ishii and Yoshio Ebihara and Jun-ichi Imura and Masaki Yamakita",
booktitle = "IFAC-PapersOnLine",
edition = "2",
}