Optimization-based subdivision algorithm for reachable sets

Previous Article
JCD Home
This Issue
Next Article
A general framework for validated continuation of periodic orbits in systems of polynomial ODEs

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

Optimization-based subdivision algorithm for reachable sets

Wolfgang Riedl ^1, , Robert Baier ^2,, and Matthias Gerdts ^3,

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.

Keywords: Reachable sets, subdivision, optimal control, direct discretization, nonlinear systems, nonlinear optimization.

Mathematics Subject Classification: Primary: 93B03, 49M37; Secondary: 49M25, 49J53, 93C10.

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:

[1]	M. Althoff, Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars, PhD thesis, Fakultät für Elektrotechnik und Informationstechnik, Technische Universität München, Munich, Germany, 2010, URL http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20100715-963752-1-4. Google Scholar
[2]	J.-P. Aubin, A. M. Bayen and P. Saint-Pierre, Viability Theory. New Directions, 2nd edition, Springer, Heidelberg, 2011, First edition: J.-P. Aubin in Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 2009. doi: 10.1007/978-3-642-16684-6. Google Scholar
[3]	J.-P. Aubin, T. Bernado and P. Saint-Pierre, A viability approach to global climate change issues, in The Coupling of Climate and Economic Dynamics. Essays on Integrated Assessment (eds. A. Haurie and L. Viguier), vol. 22 of Advances in Global Change Research, Springer, Dordrecht–Berlin–Heidelberg–New York, 2005,113–143. doi: 10.1007/1-4020-3425-3_5. Google Scholar
[4]	J.-P. Aubin and A. Désilles, Traffic Networks as Information Systems. A Viability Approach, Mathematical Engineering, Springer-Verlag, Berlin, 2017. doi: 10.1007/978-3-642-54771-3. Google Scholar
[5]	R. Baier, I. A. Chahma and F. Lempio, Stability and convergence of Euler's method for stateconstrained differential inclusions, Special issue on “Variational Analysis and Optimization”, D. Dentcheva, J. Revalski (eds.), SIAM J. Optim., 18 (2007), 1004-1026. doi: 10.1137/060661867. Google Scholar
[6]	R. Baier and M. Gerdts, A computational method for non-convex reachable sets using optimal control, in Proceedings of the European Control Conference (ECC) 2009, Budapest (Hungary), August 23–26, 2009, European Union Control Association (EUCA), Budapest, 2009, 97-102, URL http://ieeexplore.ieee.org/document/7074386/. doi: 10.23919/ECC.2009.7074386. Google Scholar
[7]	R. Baier, M. Gerdts and I. Xausa, Approximation of reachable sets using optimal control algorithms, Numer. Algebra Control Optim., 3 (2013), 519-548. doi: 10.3934/naco.2013.3.519. Google Scholar
[8]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, with appendices by M. Falcone and P. Soravia, Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1. Google Scholar
[9]	W.-J. Beyn and J. Rieger, Numerical fixed grid methods for differential inclusions, Computing, 81 (2007), 91-106. doi: 10.1007/s00607-007-0240-4. Google Scholar
[10]	W.-J. Beyn and J. Rieger, The implicit Euler scheme for one-sided Lipschitz differential inclusions, Discrete Contin. Dyn. Syst. Ser. B, 14 (2010), 409-428. doi: 10.3934/dcdsb.2010.14.409. Google Scholar
[11]	M. Bodenschatz, Berechnung erreichbarer Mengen mit globalen Optimierungsverfahren [Calculation of Reachable Sets Using Global Optimization Methods], Diploma thesis, Department of Mathematics, University of Bayreuth, Bayreuth, Germany, 2014, URL http://num.math.uni-bayreuth.de/en/thesis/2014/Bodenschatz_Michael/. Google Scholar
[12]	O. Bokanowski, E. Bourgeois, A. Désilles and H. Zidani, HJBapproach for a multi-boost launcher trajectory optimization problem, in IFAC Proc., vol. 49-17, 20th IFAC Symposium on Automatic Control in Aerospace – ACA 2016, Aug 2016, Sherbrooke, Quebec, Canada., 2016,456–461. Google Scholar
[13]	C. Büskens and D. Wassel, The ESA NLP solver WORHP, in Modeling and Optimization in Space Engineering, vol. 73 of Springer Optim. Appl., Springer, New York, 2013, 85–110. doi: 10.1007/978-1-4614-4469-5_4. Google Scholar
[14]	I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161. Google Scholar
[15]	C. M. Chilan and B. A. Conway, A reachable set analysis method for generating near-optimal trajectories of constrained multiphase systems, J. Optim. Theory Appl., 167 (2015), 161-194. doi: 10.1007/s10957-014-0651-2. Google Scholar
[16]	J. L. Davy, Properties of the solution set of a generalized differential equation, Bull. Austral. Math. Soc., 6 (1972), 379-398. doi: 10.1017/S0004972700044646. Google Scholar
[17]	M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numer. Math., 75 (1997), 293-317. doi: 10.1007/s002110050240. Google Scholar
[18]	M. Dellnitz, A. Hohmann, O. Junge and M. Rumpf, Exploring invariant sets and invariant measures, Chaos, 7 (1997), 221-228. doi: 10.1063/1.166223. Google Scholar
[19]	M. Dellnitz, O. Junge, M. Post and B. Thiere, On target for Venus – set oriented computation of energy efficient low thrust trajectories, Celestial Mech. Dynam. Astronom., 95 (2006), 357-370. doi: 10.1007/s10569-006-9008-y. Google Scholar
[20]	A. Désilles, H. Zidani and E. Crück, Collision analysis for an UAV, in AIAA Guidance, Navigation, and Control Conference 2012 (GNC-12), 13–16 August 2012 in Minneapolis, Minnesota, American Institute of Aeronautics and Astronautics, 2012, 23 pages, URL http://arc.aiaa.org/doi/book/10.2514/MGNC12. Google Scholar
[21]	T. Donchev and E. Farkhi, Stability and Euler approximation of one-sided Lipschitz differential inclusions, SIAM J. Control Optim., 36 (1998), 780–796 (electronic). doi: 10.1137/S0363012995293694. Google Scholar
[22]	A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223. Google Scholar
[23]	A. L. Dontchev and F. Lempio, Difference methods for differential inclusions: A survey, SIAM Rev., 34 (1992), 263-294. doi: 10.1137/1034050. Google Scholar
[24]	M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, vol. 133 of Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), 2014. Google Scholar
[25]	H. Frankowska and F. Rampazzo, Filippov's and Filippov-Ważewski's theorems on closed domains, J. Differ. Equ., 161 (2000), 449-478. doi: 10.1006/jdeq.2000.3711. Google Scholar
[26]	M. Gerdts, OCPID-DAE1 – Optimal Control and Parameter Identification with Differential-Algebraic Equations of Index 1, 2013, URL http://www.optimal-control.de/. Google Scholar
[27]	M. Gerdts and M. Kunkel, A nonsmooth Newton's method for discretized optimal control problems with state and control constraints, J. Ind. Manag. Optim., 4 (2008), 247-270. doi: 10.3934/jimo.2008.4.247. Google Scholar
[28]	L. Grüne, Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization, vol. 1783 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, 2002. doi: 10.1007/b83677. Google Scholar
[29]	L. Grüne and T. Jahn, Computing reachable sets via barrier methods on SIMD architectures, in Proceedings of the 6th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2012) Held at the University of Vienna, Vienna, Austria, September 10–14, 2012 (eds. J. Eberhardsteiner, H. J. Böhm and F. G. Rammerstorfer), Vienna University of Technology, Vienna, Austria, 2012, 2076–2095, URL http://www.eccomas.org/spacehome/1/7/, Paper No. 1518, e-book. Google Scholar
[30]	E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations, vol. 31 of Springer Series in Computational Mathematics, 2nd edition, Springer-Verlag, Berlin, 2006, URL http://rd.springer.com/book/10.1007/3-540-30666-8. Google Scholar
[31]	J. D. Hunter, Matplotlib: A 2d graphics environment, Computing In Science & Engineering, 9 (2007), 90-95. Google Scholar
[32]	T. U. Jahn, A Feasibility Problem Approach for Reachable Set Approximation, PhD thesis, Fakultät für Mathematik, Physik und Informatik, Bayreuth, Germany, 2014, URL http://nbn-resolving.de/urn/resolver.pl?urn=urn:nbn:de:bvb:703-epub-2087-4. Google Scholar
[33]	O. Junge, Mengenorientierte Methoden zur numerischen Analyse dynamischer Systeme, PhD thesis, University of Paderborn, 2000, URL http://www.shaker.de/de/content/catalogue/index.asp?lang=de&ID=8&ISBN=978-3-8265-7081-0. Google Scholar
[34]	I. M. Mitchell, A. M. Bayen and C. J. Tomlin, A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games, IEEE Trans. Automat. Control, 50 (2005), 947-957. doi: 10.1109/TAC.2005.851439. Google Scholar
[35]	I. M. Mitchell and C. J. Tomlin, Overapproximating reachable sets by Hamilton-Jacobi projections, Special issue in honor of the sixtieth birthday of Stanley Osher, J. Sci. Comput., 19 (2003), 323-346. doi: 10.1023/A:1025364227563. Google Scholar
[36]	Persistence of Vision Pty. Ltd., Persistence of Vision Raytracer (Version 3.7). Computer Software, retrieved from http://www.povray.org/download/, 2004. Google Scholar
[37]	M. Rasmussen, J. Rieger and K. N. Webster, Approximation of reachable sets using optimal control and support vector machines, J. Comput. Appl. Math., 311 (2017), 68-83. doi: 10.1016/j.cam.2016.06.015. Google Scholar
[38]	G. Reiéig, Computing abstractions of nonlinear systems, IEEE Trans. Automat. Control, 56 (2011), 2583-2598. doi: 10.1109/TAC.1980.1102455. Google Scholar
[39]	W. Riedl, Optimization-based subdivision algorithm for reachable sets, Proc. Appl. Math. Mech., 14 (2014), 937-938. doi: 10.1002/pamm.201410449. Google Scholar
[40]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, vol. 317 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3. Google Scholar
[41]	E. Roxin, Stability in general control systems, J. Differ. Equ., 1 (1965), 115-150. doi: 10.1016/0022-0396(65)90015-X. Google Scholar
[42]	The Numerical Algorithms Group (NAG), The NAG Fortran Library, http://www.nag.com/. Google Scholar
[43]	V. Veliov, Second order discrete approximations to strongly convex differential inclusions, Systems Control Lett., 13 (1989), 263-269. doi: 10.1016/0167-6911(89)90073-X. Google Scholar
[44]	A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program. Ser. A, 106 (2006), 25-57. doi: 10.1007/s10107-004-0559-y. Google Scholar
[45]	P. R. Wolenski, The exponential formula for the reachable set of a Lipschitz differential inclusion, SIAM J. Control Optim., 28 (1990), 1148-1161. doi: 10.1137/0328062. Google Scholar
[46]	I. Xausa, Verification of Collision Avoidance Systems using Optimal Control and Sensitivity Analysis, PhD thesis, Fakultät für Luft- und Raumfahrttechnik, Universität der Bundeswehr München, Munich, Germany, 2015, URL http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:706-4394. Google Scholar

show all references

References:

[1]	M. Althoff, Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars, PhD thesis, Fakultät für Elektrotechnik und Informationstechnik, Technische Universität München, Munich, Germany, 2010, URL http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:91-diss-20100715-963752-1-4. Google Scholar
[2]	J.-P. Aubin, A. M. Bayen and P. Saint-Pierre, Viability Theory. New Directions, 2nd edition, Springer, Heidelberg, 2011, First edition: J.-P. Aubin in Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 2009. doi: 10.1007/978-3-642-16684-6. Google Scholar
[3]	J.-P. Aubin, T. Bernado and P. Saint-Pierre, A viability approach to global climate change issues, in The Coupling of Climate and Economic Dynamics. Essays on Integrated Assessment (eds. A. Haurie and L. Viguier), vol. 22 of Advances in Global Change Research, Springer, Dordrecht–Berlin–Heidelberg–New York, 2005,113–143. doi: 10.1007/1-4020-3425-3_5. Google Scholar
[4]	J.-P. Aubin and A. Désilles, Traffic Networks as Information Systems. A Viability Approach, Mathematical Engineering, Springer-Verlag, Berlin, 2017. doi: 10.1007/978-3-642-54771-3. Google Scholar
[5]	R. Baier, I. A. Chahma and F. Lempio, Stability and convergence of Euler's method for stateconstrained differential inclusions, Special issue on “Variational Analysis and Optimization”, D. Dentcheva, J. Revalski (eds.), SIAM J. Optim., 18 (2007), 1004-1026. doi: 10.1137/060661867. Google Scholar
[6]	R. Baier and M. Gerdts, A computational method for non-convex reachable sets using optimal control, in Proceedings of the European Control Conference (ECC) 2009, Budapest (Hungary), August 23–26, 2009, European Union Control Association (EUCA), Budapest, 2009, 97-102, URL http://ieeexplore.ieee.org/document/7074386/. doi: 10.23919/ECC.2009.7074386. Google Scholar
[7]	R. Baier, M. Gerdts and I. Xausa, Approximation of reachable sets using optimal control algorithms, Numer. Algebra Control Optim., 3 (2013), 519-548. doi: 10.3934/naco.2013.3.519. Google Scholar
[8]	M. Bardi and I. Capuzzo-Dolcetta, Optimal Control and Viscosity Solutions of Hamilton-Jacobi-Bellman Equations, with appendices by M. Falcone and P. Soravia, Systems & Control: Foundations & Applications, Birkhäuser Boston Inc., Boston, MA, 1997. doi: 10.1007/978-0-8176-4755-1. Google Scholar
[9]	W.-J. Beyn and J. Rieger, Numerical fixed grid methods for differential inclusions, Computing, 81 (2007), 91-106. doi: 10.1007/s00607-007-0240-4. Google Scholar
[10]	W.-J. Beyn and J. Rieger, The implicit Euler scheme for one-sided Lipschitz differential inclusions, Discrete Contin. Dyn. Syst. Ser. B, 14 (2010), 409-428. doi: 10.3934/dcdsb.2010.14.409. Google Scholar
[11]	M. Bodenschatz, Berechnung erreichbarer Mengen mit globalen Optimierungsverfahren [Calculation of Reachable Sets Using Global Optimization Methods], Diploma thesis, Department of Mathematics, University of Bayreuth, Bayreuth, Germany, 2014, URL http://num.math.uni-bayreuth.de/en/thesis/2014/Bodenschatz_Michael/. Google Scholar
[12]	O. Bokanowski, E. Bourgeois, A. Désilles and H. Zidani, HJBapproach for a multi-boost launcher trajectory optimization problem, in IFAC Proc., vol. 49-17, 20th IFAC Symposium on Automatic Control in Aerospace – ACA 2016, Aug 2016, Sherbrooke, Quebec, Canada., 2016,456–461. Google Scholar
[13]	C. Büskens and D. Wassel, The ESA NLP solver WORHP, in Modeling and Optimization in Space Engineering, vol. 73 of Springer Optim. Appl., Springer, New York, 2013, 85–110. doi: 10.1007/978-1-4614-4469-5_4. Google Scholar
[14]	I. A. Chahma, Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161. Google Scholar
[15]	C. M. Chilan and B. A. Conway, A reachable set analysis method for generating near-optimal trajectories of constrained multiphase systems, J. Optim. Theory Appl., 167 (2015), 161-194. doi: 10.1007/s10957-014-0651-2. Google Scholar
[16]	J. L. Davy, Properties of the solution set of a generalized differential equation, Bull. Austral. Math. Soc., 6 (1972), 379-398. doi: 10.1017/S0004972700044646. Google Scholar
[17]	M. Dellnitz and A. Hohmann, A subdivision algorithm for the computation of unstable manifolds and global attractors, Numer. Math., 75 (1997), 293-317. doi: 10.1007/s002110050240. Google Scholar
[18]	M. Dellnitz, A. Hohmann, O. Junge and M. Rumpf, Exploring invariant sets and invariant measures, Chaos, 7 (1997), 221-228. doi: 10.1063/1.166223. Google Scholar
[19]	M. Dellnitz, O. Junge, M. Post and B. Thiere, On target for Venus – set oriented computation of energy efficient low thrust trajectories, Celestial Mech. Dynam. Astronom., 95 (2006), 357-370. doi: 10.1007/s10569-006-9008-y. Google Scholar
[20]	A. Désilles, H. Zidani and E. Crück, Collision analysis for an UAV, in AIAA Guidance, Navigation, and Control Conference 2012 (GNC-12), 13–16 August 2012 in Minneapolis, Minnesota, American Institute of Aeronautics and Astronautics, 2012, 23 pages, URL http://arc.aiaa.org/doi/book/10.2514/MGNC12. Google Scholar
[21]	T. Donchev and E. Farkhi, Stability and Euler approximation of one-sided Lipschitz differential inclusions, SIAM J. Control Optim., 36 (1998), 780–796 (electronic). doi: 10.1137/S0363012995293694. Google Scholar
[22]	A. L. Dontchev and E. M. Farkhi, Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358. doi: 10.1007/BF02241223. Google Scholar
[23]	A. L. Dontchev and F. Lempio, Difference methods for differential inclusions: A survey, SIAM Rev., 34 (1992), 263-294. doi: 10.1137/1034050. Google Scholar
[24]	M. Falcone and R. Ferretti, Semi-Lagrangian Approximation Schemes for Linear and Hamilton-Jacobi Equations, vol. 133 of Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM), 2014. Google Scholar
[25]	H. Frankowska and F. Rampazzo, Filippov's and Filippov-Ważewski's theorems on closed domains, J. Differ. Equ., 161 (2000), 449-478. doi: 10.1006/jdeq.2000.3711. Google Scholar
[26]	M. Gerdts, OCPID-DAE1 – Optimal Control and Parameter Identification with Differential-Algebraic Equations of Index 1, 2013, URL http://www.optimal-control.de/. Google Scholar
[27]	M. Gerdts and M. Kunkel, A nonsmooth Newton's method for discretized optimal control problems with state and control constraints, J. Ind. Manag. Optim., 4 (2008), 247-270. doi: 10.3934/jimo.2008.4.247. Google Scholar
[28]	L. Grüne, Asymptotic Behavior of Dynamical and Control Systems under Perturbation and Discretization, vol. 1783 of Lecture Notes in Mathematics, Springer-Verlag, Berlin, 2002. doi: 10.1007/b83677. Google Scholar
[29]	L. Grüne and T. Jahn, Computing reachable sets via barrier methods on SIMD architectures, in Proceedings of the 6th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS 2012) Held at the University of Vienna, Vienna, Austria, September 10–14, 2012 (eds. J. Eberhardsteiner, H. J. Böhm and F. G. Rammerstorfer), Vienna University of Technology, Vienna, Austria, 2012, 2076–2095, URL http://www.eccomas.org/spacehome/1/7/, Paper No. 1518, e-book. Google Scholar
[30]	E. Hairer, C. Lubich and G. Wanner, Geometric Numerical Integration. Structure-Preserving Algorithms for Ordinary Differential Equations, vol. 31 of Springer Series in Computational Mathematics, 2nd edition, Springer-Verlag, Berlin, 2006, URL http://rd.springer.com/book/10.1007/3-540-30666-8. Google Scholar
[31]	J. D. Hunter, Matplotlib: A 2d graphics environment, Computing In Science & Engineering, 9 (2007), 90-95. Google Scholar
[32]	T. U. Jahn, A Feasibility Problem Approach for Reachable Set Approximation, PhD thesis, Fakultät für Mathematik, Physik und Informatik, Bayreuth, Germany, 2014, URL http://nbn-resolving.de/urn/resolver.pl?urn=urn:nbn:de:bvb:703-epub-2087-4. Google Scholar
[33]	O. Junge, Mengenorientierte Methoden zur numerischen Analyse dynamischer Systeme, PhD thesis, University of Paderborn, 2000, URL http://www.shaker.de/de/content/catalogue/index.asp?lang=de&ID=8&ISBN=978-3-8265-7081-0. Google Scholar
[34]	I. M. Mitchell, A. M. Bayen and C. J. Tomlin, A time-dependent Hamilton-Jacobi formulation of reachable sets for continuous dynamic games, IEEE Trans. Automat. Control, 50 (2005), 947-957. doi: 10.1109/TAC.2005.851439. Google Scholar
[35]	I. M. Mitchell and C. J. Tomlin, Overapproximating reachable sets by Hamilton-Jacobi projections, Special issue in honor of the sixtieth birthday of Stanley Osher, J. Sci. Comput., 19 (2003), 323-346. doi: 10.1023/A:1025364227563. Google Scholar
[36]	Persistence of Vision Pty. Ltd., Persistence of Vision Raytracer (Version 3.7). Computer Software, retrieved from http://www.povray.org/download/, 2004. Google Scholar
[37]	M. Rasmussen, J. Rieger and K. N. Webster, Approximation of reachable sets using optimal control and support vector machines, J. Comput. Appl. Math., 311 (2017), 68-83. doi: 10.1016/j.cam.2016.06.015. Google Scholar
[38]	G. Reiéig, Computing abstractions of nonlinear systems, IEEE Trans. Automat. Control, 56 (2011), 2583-2598. doi: 10.1109/TAC.1980.1102455. Google Scholar
[39]	W. Riedl, Optimization-based subdivision algorithm for reachable sets, Proc. Appl. Math. Mech., 14 (2014), 937-938. doi: 10.1002/pamm.201410449. Google Scholar
[40]	R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, vol. 317 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1998. doi: 10.1007/978-3-642-02431-3. Google Scholar
[41]	E. Roxin, Stability in general control systems, J. Differ. Equ., 1 (1965), 115-150. doi: 10.1016/0022-0396(65)90015-X. Google Scholar
[42]	The Numerical Algorithms Group (NAG), The NAG Fortran Library, http://www.nag.com/. Google Scholar
[43]	V. Veliov, Second order discrete approximations to strongly convex differential inclusions, Systems Control Lett., 13 (1989), 263-269. doi: 10.1016/0167-6911(89)90073-X. Google Scholar
[44]	A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program. Ser. A, 106 (2006), 25-57. doi: 10.1007/s10107-004-0559-y. Google Scholar
[45]	P. R. Wolenski, The exponential formula for the reachable set of a Lipschitz differential inclusion, SIAM J. Control Optim., 28 (1990), 1148-1161. doi: 10.1137/0328062. Google Scholar
[46]	I. Xausa, Verification of Collision Avoidance Systems using Optimal Control and Sensitivity Analysis, PhD thesis, Fakultät für Luft- und Raumfahrttechnik, Universität der Bundeswehr München, Munich, Germany, 2015, URL http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:706-4394. Google Scholar

Figure 1. Reachable set of the bilinear problem for a full $ 33 \times 33 $ grid

Download full-size image

Download as PowerPoint slide

Figure 2. Reachable set of the bilinear problem, generated with (right) and without (left) the subdivision algorithm

Download full-size image

Download as PowerPoint slide

Figure 3. 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)

Download full-size image

Download as PowerPoint slide

Figure 4. Selection of boxes for the next subdivision steps

Download full-size image

Download as PowerPoint slide

Figure 5. Inner and outer approximation of the reachable set

Download full-size image

Download as PowerPoint slide

Figure 6. Demonstration of reusability of the results within the subdivision algorithm

Download full-size image

Download as PowerPoint slide

Figure 7. $ B = [-1,1] $ covered by boxes (left) or by balls (right)

Download full-size image

Download as PowerPoint slide

Figure 8. $ B = [-1,1]^2 $ covered by boxes (left) or by balls (right)

Download full-size image

Download as PowerPoint slide

Figure 9. Kenderov problem using different discretization methods for the ODE-constraints with 16 timesteps each: Explicit Euler (left), implicit Euler (middle), implicit trapezoidal rule (right)

Download full-size image

Download as PowerPoint slide

Figure 10. Kenderov problem using explicit Euler (left), implicit Euler (middle) and the implicit trapezoidal rule (right) with 261 timesteps each

Download full-size image

Download as PowerPoint slide

Figure 11. Illustration of the robot from Ex. 4.3

Download full-size image

Download as PowerPoint slide

Figure 12. Rough approximation of the reachable set of the robot problem

Download full-size image

Download as PowerPoint slide

Figure 13. Finer approximation of the reachable set of the robot problem

Download full-size image

Download as PowerPoint slide

Figure 14. Reachable set of the robot without the transformation in the objective function (left) and the transformed set using the same results and colorcode (right)

Download full-size image

Download as PowerPoint slide

Figure 15. Objective function of the non-transformed robot problem (left) and the transformed version (right)

Download full-size image

Download as PowerPoint slide

Figure 16. Approximated transformed reachable set of the robot with a less elaborate strategy for initial guesses

Download full-size image

Download as PowerPoint slide

Figure 17. Reachable set of the robot problem, generated with Ipopt (left) and WORHP (right)

Download full-size image

Download as PowerPoint slide

Figure 18. Robot model using a circular grid

Download full-size image

Download as PowerPoint slide

Figure 19. Graphical (left) and computational (right) zoom on the example of the Kenderov Problem

Download full-size image

Download as PowerPoint slide

Figure 20. Self-finding of the bounding box

Download full-size image

Download as PowerPoint slide

Figure 21. 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

Download full-size image

Download as PowerPoint slide

Figure 22. 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)

Download full-size image

Download as PowerPoint slide

Figure 23. Final box collections of the solution funnel of the bilinear problem for $ T \in [0, 1] $, rendered with POV-Ray

Download full-size image

Download as PowerPoint slide

Table 1. 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

Download as excel

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

Table 2. 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

Download as excel

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

Metrics

Other articles
by authors

on AIMS
Wolfgang Riedl Robert Baier Matthias Gerdts
on Google Scholar
Wolfgang Riedl Robert Baier Matthias Gerdts

Impact Factor:

Tools

Article outline

Figures and Tables

Impact Factor:

Tools

Figures and Tables

Impact Factor:

Tools

Metrics

Other articles
by authors

on AIMS
Wolfgang Riedl Robert Baier Matthias Gerdts
on Google Scholar
Wolfgang Riedl Robert Baier Matthias Gerdts

[Back to Top]