# American Institute of Mathematical Sciences

January  2021, 8(1): 99-130. doi: 10.3934/jcd.2021005

## Optimization-based subdivision algorithm for reachable sets

 1 Lehrstuhl für Ingenieurmathematik, Universität Bayreuth, 95440 Bayreuth, Germany 2 Lehrstuhl für Angewandte Mathematik, Universität Bayreuth, 95440 Bayreuth, Germany 3 Institut für Angewandte Mathematik und Wissenschaftliches Rechnen, Fakultät für Luft- und Raumfahrttechnik, Universität der Bundeswehr, 85577 Neubiberg/München, Germany

* Corresponding author.

Received  December 2016 Revised  September 2020 Published  October 2020

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.

Citation: Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
##### References:

show all references

##### References:
Reachable set of the bilinear problem for a full $33 \times 33$ grid
Reachable set of the bilinear problem, generated with (right) and without (left) the subdivision algorithm
First step of the subdivision algorithm. Choose an initial bounding box (left), solve the optimization problems to approximate the map $\mathcal{P}$ (middle) and select the boxes for the next step (right)
Selection of boxes for the next subdivision steps
Inner and outer approximation of the reachable set
Demonstration of reusability of the results within the subdivision algorithm
$B = [-1,1]$ covered by boxes (left) or by balls (right)
$B = [-1,1]^2$ covered by boxes (left) or by balls (right)
Kenderov problem using different discretization methods for the ODE-constraints with 16 timesteps each: Explicit Euler (left), implicit Euler (middle), implicit trapezoidal rule (right)
Kenderov problem using explicit Euler (left), implicit Euler (middle) and the implicit trapezoidal rule (right) with 261 timesteps each
Illustration of the robot from Ex. 4.3
Rough approximation of the reachable set of the robot problem
Finer approximation of the reachable set of the robot problem
Reachable set of the robot without the transformation in the objective function (left) and the transformed set using the same results and colorcode (right)
Objective function of the non-transformed robot problem (left) and the transformed version (right)
Approximated transformed reachable set of the robot with a less elaborate strategy for initial guesses
Reachable set of the robot problem, generated with Ipopt (left) and WORHP (right)
Robot model using a circular grid
Graphical (left) and computational (right) zoom on the example of the Kenderov Problem
Self-finding of the bounding box
Piecewise construction of the whole reachable set, by choosing new bounding boxes at locations containing target points from previous runs or cut off looking edges
Solution funnel of the bilinear problem for $T \in [0, 1]$. The plot only shows the slices at $t_i = \frac{1}{8} \cdot i,\; i\in \{0, 1, \dots, 8\}$ to make it easier to read (cpu-time 103 534s)
Final box collections of the solution funnel of the bilinear problem for $T \in [0, 1]$, rendered with POV-Ray
Comparison of the computational effort of the algorithm with (S) and without (N) using the subdivision algorithm for a few different grids
 Number of optimization problems Grid N S S/N 3 × 3 9 9 1 5 × 5 25 18 0.72 9 × 9 81 41 0.506 17 × 17 289 92 0.318 33 × 33 1 089 231 0.212 65 × 65 4 225 635 0.150 129 × 129 16 641 1948 0.119 257 × 257 66 049 6822 0.103 513 × 513 263 169 25477 0.097 1025 × 1025 1 050 625 98040 0.093 CPU time Grid N S S/N 3 × 3 0.13s 0.13s 1 5 × 5 0.35s 0.25s 0.714 9 × 9 1.2s 0.57s 0.475 17 × 17 4.3s 1.24s 0.288 33 × 33 16.12s 3.12s 0.194 65 × 65 62.74s 8.55s 0.136 129 × 129 253.53s 26.29s 0.104 257 × 257 1128.09s 92.63s 0.082 513 × 513 8234.45s 355.29s 0.043 1025 × 1025 94221.4s 1741.58s 0.018
 Number of optimization problems Grid N S S/N 3 × 3 9 9 1 5 × 5 25 18 0.72 9 × 9 81 41 0.506 17 × 17 289 92 0.318 33 × 33 1 089 231 0.212 65 × 65 4 225 635 0.150 129 × 129 16 641 1948 0.119 257 × 257 66 049 6822 0.103 513 × 513 263 169 25477 0.097 1025 × 1025 1 050 625 98040 0.093 CPU time Grid N S S/N 3 × 3 0.13s 0.13s 1 5 × 5 0.35s 0.25s 0.714 9 × 9 1.2s 0.57s 0.475 17 × 17 4.3s 1.24s 0.288 33 × 33 16.12s 3.12s 0.194 65 × 65 62.74s 8.55s 0.136 129 × 129 253.53s 26.29s 0.104 257 × 257 1128.09s 92.63s 0.082 513 × 513 8234.45s 355.29s 0.043 1025 × 1025 94221.4s 1741.58s 0.018
Computational times for generating parts of the reachable set with the shown boxes
 Box Times (with subdivision) Times (without subdivision) [-1.1, 0.4]×[-0.5, 0.5] 7.49 s 18.21 s [ 0.4, 1.9]×[-0.5, 0.5] 7.00 s 17.58 s [-1.1, 0.4]×[ 0.5, 1.5] 9.35 s 18.12 s [ 0.4, 1.9]×[ 0.5, 1.5] 10.55 s 18.69 s
 Box Times (with subdivision) Times (without subdivision) [-1.1, 0.4]×[-0.5, 0.5] 7.49 s 18.21 s [ 0.4, 1.9]×[-0.5, 0.5] 7.00 s 17.58 s [-1.1, 0.4]×[ 0.5, 1.5] 9.35 s 18.12 s [ 0.4, 1.9]×[ 0.5, 1.5] 10.55 s 18.69 s
 [1] Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462 [2] Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115 [3] Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $L^2-$norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077 [4] Andrew Comech, Scipio Cuccagna. On asymptotic stability of ground states of some systems of nonlinear Schrödinger equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1225-1270. doi: 10.3934/dcds.2020316 [5] Amira M. Boughoufala, Ahmed Y. Abdallah. Attractors for FitzHugh-Nagumo lattice systems with almost periodic nonlinear parts. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1549-1563. doi: 10.3934/dcdsb.2020172 [6] Pierluigi Colli, Gianni Gilardi, Jürgen Sprekels. Deep quench approximation and optimal control of general Cahn–Hilliard systems with fractional operators and double obstacle potentials. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 243-271. doi: 10.3934/dcdss.2020213 [7] Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019 [8] Maoding Zhen, Binlin Zhang, Vicenţiu D. Rădulescu. Normalized solutions for nonlinear coupled fractional systems: Low and high perturbations in the attractive case. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020379 [9] Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436 [10] Jonathan J. Wylie, Robert M. Miura, Huaxiong Huang. Systems of coupled diffusion equations with degenerate nonlinear source terms: Linear stability and traveling waves. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 561-569. doi: 10.3934/dcds.2009.23.561 [11] Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380 [12] Lars Grüne, Matthias A. Müller, Christopher M. Kellett, Steven R. Weller. Strict dissipativity for discrete time discounted optimal control problems. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020046 [13] Hai Huang, Xianlong Fu. Optimal control problems for a neutral integro-differential system with infinite delay. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020107 [14] Vaibhav Mehandiratta, Mani Mehra, Günter Leugering. Fractional optimal control problems on a star graph: Optimality system and numerical solution. Mathematical Control & Related Fields, 2021, 11 (1) : 189-209. doi: 10.3934/mcrf.2020033 [15] Christian Clason, Vu Huu Nhu, Arnd Rösch. Optimal control of a non-smooth quasilinear elliptic equation. Mathematical Control & Related Fields, 2020  doi: 10.3934/mcrf.2020052 [16] Hongbo Guan, Yong Yang, Huiqing Zhu. A nonuniform anisotropic FEM for elliptic boundary layer optimal control problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1711-1722. doi: 10.3934/dcdsb.2020179 [17] Thomas Bartsch, Tian Xu. Strongly localized semiclassical states for nonlinear Dirac equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 29-60. doi: 10.3934/dcds.2020297 [18] Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272 [19] Eduard Feireisl, Elisabetta Rocca, Giulio Schimperna, Arghir Zarnescu. Weak sequential stability for a nonlinear model of nematic electrolytes. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 219-241. doi: 10.3934/dcdss.2020366 [20] D. R. Michiel Renger, Johannes Zimmer. Orthogonality of fluxes in general nonlinear reaction networks. Discrete & Continuous Dynamical Systems - S, 2021, 14 (1) : 205-217. doi: 10.3934/dcdss.2020346

Impact Factor:

## Tools

Article outline

Figures and Tables