# 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] Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021015 [2] Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399 [3] Marita Holtmannspötter, Arnd Rösch, Boris Vexler. A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021014 [4] Tobias Geiger, Daniel Wachsmuth, Gerd Wachsmuth. Optimal control of ODEs with state suprema. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021012 [5] Yanqin Fang, Jihui Zhang. Multiplicity of solutions for the nonlinear Schrödinger-Maxwell system. Communications on Pure & Applied Analysis, 2011, 10 (4) : 1267-1279. doi: 10.3934/cpaa.2011.10.1267 [6] Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017 [7] Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933 [8] Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185 [9] Manoel J. Dos Santos, Baowei Feng, Dilberto S. Almeida Júnior, Mauro L. Santos. Global and exponential attractors for a nonlinear porous elastic system with delay term. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2805-2828. doi: 10.3934/dcdsb.2020206 [10] Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1649-1672. doi: 10.3934/dcdss.2020448 [11] Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1693-1716. doi: 10.3934/dcdss.2020450 [12] Amit Goswami, Sushila Rathore, Jagdev Singh, Devendra Kumar. Analytical study of fractional nonlinear Schrödinger equation with harmonic oscillator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021021 [13] Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 [14] Lorenzo Freddi. Optimal control of the transmission rate in compartmental epidemics. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021007 [15] Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems - A, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 [16] Emma D'Aniello, Saber Elaydi. The structure of $\omega$-limit sets of asymptotically non-autonomous discrete dynamical systems. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 903-915. doi: 10.3934/dcdsb.2019195 [17] Irena PawŃow, Wojciech M. Zajączkowski. Global regular solutions to three-dimensional thermo-visco-elasticity with nonlinear temperature-dependent specific heat. Communications on Pure & Applied Analysis, 2017, 16 (4) : 1331-1372. doi: 10.3934/cpaa.2017065 [18] Xiaoming Wang. Quasi-periodic solutions for a class of second order differential equations with a nonlinear damping term. Discrete & Continuous Dynamical Systems - S, 2017, 10 (3) : 543-556. doi: 10.3934/dcdss.2017027 [19] Hong Yi, Chunlai Mu, Guangyu Xu, Pan Dai. A blow-up result for the chemotaxis system with nonlinear signal production and logistic source. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2537-2559. doi: 10.3934/dcdsb.2020194 [20] Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

Impact Factor: