Optimization-based subdivision algorithm for reachable sets

Title data

Riedl, Wolfgang ; Baier, Robert ; Gerdts, Matthias:
Optimization-based subdivision algorithm for reachable sets.
In: Journal of Computational Dynamics. Vol. 8 (2021) Issue 1 . - pp. 99-130.
ISSN 2158-2491
DOI: https://doi.org/10.3934/jcd.2021005

Related URLs

Project information

Abstract in another language

Reachable sets for nonlinear control systems can be computed via the use of solvers for optimal control problems. The paper presents a new improved variant which applies adaptive concepts similar to the framework of known subdivision techniques by Dellnitz/Hohmann. Using set properties of the nearest point projection, the convergence and rigorousness of the algorithm can be proved without the assumption of diffeomorphism on a nonlinear mapping. The adaptive method is demonstrated by two nonlinear academic examples and for a more complex robot model with box constraints for four states, two controls and five boundary conditions. In these examples adaptive and non-adaptive techniques as well as various discretization methods and optimization solvers are compared. The method also offers interesting features, like zooming into details of the reachable set, self-determination of the needed bounding box, easy parallelization and the use of different grid geometries. With the calculation of a 3d funnel in one of the examples, it is shown that the algorithm can also be used to approximate higher dimensional reachable sets and the resulting box collection may serve as a starting point for more sophisticated visualizations or algorithms.