# A Local Ordered Upwind Method for Hamilton-Jacobi and Isaacs Equations

@article{Cacace2011ALO, title={A Local Ordered Upwind Method for Hamilton-Jacobi and Isaacs Equations}, author={Simone Cacace and Emiliano Cristiani and Maurizio Falcone}, journal={IFAC Proceedings Volumes}, year={2011}, volume={44}, pages={6800-6805} }

Abstract We present a generalization of the Fast Marching (FM) method for the numerical solution of a class of Hamilton-Jacobi equations, including Hamilton-Jacobi-Bellman and Hamilton-Jacobi-Isaacs equations. The method is able to compute an approximation of the viscosity solution concentrating the computations only in a small evolving trial region, as the original FM method. The main novelty is that the size of the trial region does not depend on the dynamics. We compare the new method with… Expand

#### 15 Citations

A Patchy Dynamic Programming Scheme for a Class of Hamilton-Jacobi-Bellman Equations

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2012

A new algorithm for the solution of Hamilton--Jacobi--Bellman equations related to optimal control problems is presented that has the advantage that every subdomain is invariant with respect to the optimal dynamics, and then the solution can be computed independently in each subdomain. Expand

Reconstruction of Independent Sub-domains for a class of Hamilton Jacobi Equations and its Application to Parallel Computing

- Mathematics
- 2014

A previous knowledge of the domains of dependence of an Hamilton Jacobi equation can be useful in its study and approximation. Information of this nature are, in general, difficult to obtain directly… Expand

Recent Results in the Approximation of Nonlinear Optimal Control Problems

- Mathematics, Computer Science
- LSSC
- 2013

This survey paper presents recent advances for the numerical solution of Hamilton-Jacobi-Bellman equations related to optimal control problems and illustrates here some of these techniques: patchy domain decomposition, fast marching and fast sweeping and an acceleration method based on the coupling between value and policy iteration. Expand

Hybrid massively parallel fast sweeping method for static Hamilton-Jacobi equations

- Computer Science
- J. Comput. Phys.
- 2016

This work presents a multilevel, hybrid parallel algorithm that combines the desirable traits of two distinct parallel methods and demonstrates its effectiveness on a set of example problems including optimal control, dynamic games, and seismic wave propagation. Expand

Can Local Single-Pass Methods Solve Any Stationary Hamilton-Jacobi-Bellman Equation?

- Mathematics, Computer Science
- SIAM J. Sci. Comput.
- 2014

It is shown that the construction of a local single-pass method for general Hamilton--Jacobi equations is very hard, if not impossible, Nevertheless, some special classes of problems can actually be solved, making localSingle-pass methods very useful from a p... Expand

Viscosity Solution of Bellman-Isaacs Equation Arising in Non-linear Uncertain Object Control

- Mathematics
- 2016

Abstract The problem of optimal control for a class of non-linear objects with uncontrolled bounded disturbances is formulated in the sense of a differential game. In case of problems with quadratic… Expand

Robust Feedback Control of Nonlinear PDEs by Numerical Approximation of High-Dimensional Hamilton-Jacobi-Isaacs Equations

- Mathematics, Computer Science
- SIAM J. Appl. Dyn. Syst.
- 2020

The proposed design yields a feedback controller achieving optimal stabilization and disturbance rejection properties, along with providing a modelling framework for the robust control of PDEs under parametric uncertainties. Expand

Sequential/parallel reusability study on solving Hamilton-Jacobi-Bellman equations. (Etude de la réutilisabilité séquentielle/parallèle pour la résolution des équations Hamilton-Jacobi-Bellman)

- Computer Science
- 2015

This thesis dissertation is multidisciplinary by designing a reusable parallel numerical library for solving Hamilton-Jacobi-Bellman equations and proposes code abstraction allowing algorithmic and data genericity while trying to keep a maintainable and performant code potentially parallelizable. Expand

Optimal Control with Budget Constraints and Resets

- Mathematics, Computer Science
- SIAM J. Control. Optim.
- 2015

An iterative algorithm for solving discrete and continuous control problems constrained by a fixed budget of some resource, which may be renewed upon entering a preferred subset of the state space with a full/instantaneous budget reset on the preferred subset. Expand

Nonmonotonic Front Propagation on Weighted Graphs With Applications in Image Processing and High-Dimensional Data Classification

- Mathematics, Computer Science
- IEEE Journal of Selected Topics in Signal Processing
- 2017

This paper introduces several significant improvements: A simplified and explicit representation of a front on a weighted graph, a new formulation of the level set equation on weighted graphs considering both time-dependent and stationary versions of this equation in the case of signed velocities, and an efficient algorithm that generalized the fast marching to graphs with signed veloities. Expand

#### References

SHOWING 1-10 OF 19 REFERENCES

A Fast Marching Method for Hamilton-Jacobi Equations Modeling Monotone Front Propagations

- Mathematics, Computer Science
- J. Sci. Comput.
- 2009

The new method, named Buffered Fast Marching (BFM), is based on a semi-Lagrangian discretization and is suitable for Hamilton- Jacobi equations modeling monotonically advancing fronts, including Hamilton-Jacobi-Bellman and Hamilton-jacobi-Isaacs equations which arise in the framework of optimal control problems and differential games. Expand

Ordered Upwind Methods for Static Hamilton-Jacobi Equations: Theory and Algorithms

- Mathematics, Computer Science
- SIAM J. Numer. Anal.
- 2003

A family of fast ordered upwind methods for approximating solutions to a wide class of static Hamilton-Jacobi equations with Dirichlet boundary conditions with complexity O(M log M), where M is the total number of points in the domain. Expand

An efficient algorithm for Hamilton–Jacobi equations in high dimension

- Mathematics
- 2004

In this paper we develop a new version of the semi-Lagrangian algorithm for first order Hamilton–Jacobi equations. This implementation is well suited to deal with problems in high dimension, i.e. in… Expand

Fast Sweeping Algorithms for a Class of Hamilton-Jacobi Equations

- Mathematics, Computer Science
- SIAM J. Numer. Anal.
- 2003

A Godunov-type numerical flux is derived for the class of strictly convex, homogeneous Hamiltonians that includes H(p,q) and it is shown that convergence after a few iterations, even in rather difficult cases, is indicated. Expand

A fast sweeping method for Eikonal equations

- Mathematics, Computer Science
- Math. Comput.
- 2005

Monotonicity and stability properties of the fast sweeping algorithm are proven and it is shown that 2 n Gauss-Seidel iterations is enough for the distance function in n dimensions. Expand

A Non-Monotone Fast Marching Scheme for a Hamilton-Jacobi Equation Modelling Dislocation Dynamics

- Mathematics
- 2006

In this paper we introduce an extension of the Fast Marching Method introduced by Sethian [6] for the eikonal equation modelling front evolutions in normal direction. The new scheme can deal with a… Expand

Fast Semi-Lagrangian Schemes for the Eikonal Equation and Applications

- Mathematics, Computer Science
- SIAM J. Numer. Anal.
- 2007

A fast version of the semi-Lagrangian algorithm for front propagation is introduced and it is shown that the new algorithm converges to the viscosity solution of the problem and its complexity is O(N \log N_{nb})$, as it is for the fast marching method based on finite difference. Expand

Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations

- Mathematics
- 1997

Preface.- Basic notations.- Outline of the main ideas on a model problem.- Continuous viscosity solutions of Hamilton-Jacobi equations.- Optimal control problems with continuous value functions:… Expand

A fast marching level set method for monotonically advancing fronts.

- Medicine, Computer Science
- Proceedings of the National Academy of Sciences of the United States of America
- 1996

A fast marching level set method is presented for monotonically advancing fronts, which leads to an extremely fast scheme for solving the Eikonal equation. Level set methods are numerical techniques… Expand

Efficient algorithms for globally optimal trajectories

- Mathematics
- Proceedings of 1994 33rd IEEE Conference on Decision and Control
- 1994

Presents serial and parallel algorithms for solving a system of equations that arises from the discretization of the Hamilton-Jacobi equation associated to a trajectory optimization problem of the… Expand