# American Institute of Mathematical Sciences

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

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, 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] Robert Baier, Matthias Gerdts, Ilaria Xausa. Approximation of reachable sets using optimal control algorithms. Numerical Algebra, Control & Optimization, 2013, 3 (3) : 519-548. doi: 10.3934/naco.2013.3.519 [2] Roberta Fabbri, Sylvia Novo, Carmen Núñez, Rafael Obaya. Null controllable sets and reachable sets for nonautonomous linear control systems. Discrete & Continuous Dynamical Systems - S, 2016, 9 (4) : 1069-1094. doi: 10.3934/dcdss.2016042 [3] Dietmar Szolnoki. Set oriented methods for computing reachable sets and control sets. Discrete & Continuous Dynamical Systems - B, 2003, 3 (3) : 361-382. doi: 10.3934/dcdsb.2003.3.361 [4] Qun Lin, Ryan Loxton, Kok Lay Teo. The control parameterization method for nonlinear optimal control: A survey. Journal of Industrial & Management Optimization, 2014, 10 (1) : 275-309. doi: 10.3934/jimo.2014.10.275 [5] N. U. Ahmed. Existence of optimal output feedback control law for a class of uncertain infinite dimensional stochastic systems: A direct approach. Evolution Equations & Control Theory, 2012, 1 (2) : 235-250. doi: 10.3934/eect.2012.1.235 [6] Tayel Dabbous. Adaptive control of nonlinear systems using fuzzy systems. Journal of Industrial & Management Optimization, 2010, 6 (4) : 861-880. doi: 10.3934/jimo.2010.6.861 [7] Ellina Grigorieva, Evgenii Khailov. Optimal control of a nonlinear model of economic growth. Conference Publications, 2007, 2007 (Special) : 456-466. doi: 10.3934/proc.2007.2007.456 [8] Piermarco Cannarsa, Carlo Sinestrari. On a class of nonlinear time optimal control problems. Discrete & Continuous Dynamical Systems - A, 1995, 1 (2) : 285-300. doi: 10.3934/dcds.1995.1.285 [9] Ying Zhang, Changjun Yu, Yingtao Xu, Yanqin Bai. Minimizing almost smooth control variation in nonlinear optimal control problems. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1663-1683. doi: 10.3934/jimo.2019023 [10] Bin Li, Kok Lay Teo, Cheng-Chew Lim, Guang Ren Duan. An optimal PID controller design for nonlinear constrained optimal control problems. Discrete & Continuous Dynamical Systems - B, 2011, 16 (4) : 1101-1117. doi: 10.3934/dcdsb.2011.16.1101 [11] Valery Y. Glizer, Vladimir Turetsky, Emil Bashkansky. Statistical process control optimization with variable sampling interval and nonlinear expected loss. Journal of Industrial & Management Optimization, 2015, 11 (1) : 105-133. doi: 10.3934/jimo.2015.11.105 [12] M. Motta, C. Sartori. Exit time problems for nonlinear unbounded control systems. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 137-156. doi: 10.3934/dcds.1999.5.137 [13] Rohit Gupta, Farhad Jafari, Robert J. Kipka, Boris S. Mordukhovich. Linear openness and feedback stabilization of nonlinear control systems. Discrete & Continuous Dynamical Systems - S, 2018, 11 (6) : 1103-1119. doi: 10.3934/dcdss.2018063 [14] Chunjiang Qian, Wei Lin, Wenting Zha. Generalized homogeneous systems with applications to nonlinear control: A survey. Mathematical Control & Related Fields, 2015, 5 (3) : 585-611. doi: 10.3934/mcrf.2015.5.585 [15] Mikhail Gusev. On reachability analysis for nonlinear control systems with state constraints. Conference Publications, 2015, 2015 (special) : 579-587. doi: 10.3934/proc.2015.0579 [16] Xiao-Li Hu, Han-Fu Chen. Optimal Adaptive Regulation for Nonlinear Systems with Observation Noise. Journal of Industrial & Management Optimization, 2007, 3 (1) : 155-164. doi: 10.3934/jimo.2007.3.155 [17] Shuhong Chen, Zhong Tan. Optimal interior partial regularity for nonlinear elliptic systems. Discrete & Continuous Dynamical Systems - A, 2010, 27 (3) : 981-993. doi: 10.3934/dcds.2010.27.981 [18] Marcus Wagner. A direct method for the solution of an optimal control problem arising from image registration. Numerical Algebra, Control & Optimization, 2012, 2 (3) : 487-510. doi: 10.3934/naco.2012.2.487 [19] Max Gunzburger, Sung-Dae Yang, Wenxiang Zhu. Analysis and discretization of an optimal control problem for the forced Fisher equation. Discrete & Continuous Dynamical Systems - B, 2007, 8 (3) : 569-587. doi: 10.3934/dcdsb.2007.8.569 [20] Rong Liu, Feng-Qin Zhang, Yuming Chen. Optimal contraception control for a nonlinear population model with size structure and a separable mortality. Discrete & Continuous Dynamical Systems - B, 2016, 21 (10) : 3603-3618. doi: 10.3934/dcdsb.2016112

Impact Factor: