Figure 1.
Reachable set of the bilinear problem for a full $ 33 \times 33 $ grid
- 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
| 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 |
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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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/. |
| [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. |
| [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. |
| [14] |
I. A. Chahma,
Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161.
|
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [22] |
A. L. Dontchev and E. M. Farkhi,
Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358.
doi: 10.1007/BF02241223. |
| [23] |
A. L. Dontchev and F. Lempio,
Difference methods for differential inclusions: A survey, SIAM Rev., 34 (1992), 263-294.
doi: 10.1137/1034050. |
| [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. |
| [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. |
| [26] |
M. Gerdts, OCPID-DAE1 – Optimal Control and Parameter Identification with Differential-Algebraic Equations of Index 1, 2013, URL http://www.optimal-control.de/. |
| [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. |
| [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. |
| [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. |
| [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. |
| [31] |
J. D. Hunter,
Matplotlib: A 2d graphics environment, Computing In Science & Engineering, 9 (2007), 90-95.
|
| [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. |
| [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. |
| [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. |
| [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. |
| [36] |
Persistence of Vision Pty. Ltd., Persistence of Vision Raytracer (Version 3.7). Computer Software, retrieved from http://www.povray.org/download/, 2004. |
| [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. |
| [38] |
G. Reiéig,
Computing abstractions of nonlinear systems, IEEE Trans. Automat. Control, 56 (2011), 2583-2598.
doi: 10.1109/TAC.1980.1102455. |
| [39] |
W. Riedl,
Optimization-based subdivision algorithm for reachable sets, Proc. Appl. Math. Mech., 14 (2014), 937-938.
doi: 10.1002/pamm.201410449. |
| [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. |
| [41] |
E. Roxin,
Stability in general control systems, J. Differ. Equ., 1 (1965), 115-150.
doi: 10.1016/0022-0396(65)90015-X. |
| [42] |
The Numerical Algorithms Group (NAG), The NAG Fortran Library, http://www.nag.com/. |
| [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. |
| [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. |
| [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. |
| [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. |
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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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/. |
| [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. |
| [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. |
| [14] |
I. A. Chahma,
Set-valued discrete approximation of state-constrained differential inclusions, Bayreuth. Math. Schr., 67 (2003), 3-161.
|
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [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. |
| [22] |
A. L. Dontchev and E. M. Farkhi,
Error estimates for discretized differential inclusions, Computing, 41 (1989), 349-358.
doi: 10.1007/BF02241223. |
| [23] |
A. L. Dontchev and F. Lempio,
Difference methods for differential inclusions: A survey, SIAM Rev., 34 (1992), 263-294.
doi: 10.1137/1034050. |
| [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. |
| [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. |
| [26] |
M. Gerdts, OCPID-DAE1 – Optimal Control and Parameter Identification with Differential-Algebraic Equations of Index 1, 2013, URL http://www.optimal-control.de/. |
| [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. |
| [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. |
| [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. |
| [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. |
| [31] |
J. D. Hunter,
Matplotlib: A 2d graphics environment, Computing In Science & Engineering, 9 (2007), 90-95.
|
| [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. |
| [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. |
| [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. |
| [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. |
| [36] |
Persistence of Vision Pty. Ltd., Persistence of Vision Raytracer (Version 3.7). Computer Software, retrieved from http://www.povray.org/download/, 2004. |
| [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. |
| [38] |
G. Reiéig,
Computing abstractions of nonlinear systems, IEEE Trans. Automat. Control, 56 (2011), 2583-2598.
doi: 10.1109/TAC.1980.1102455. |
| [39] |
W. Riedl,
Optimization-based subdivision algorithm for reachable sets, Proc. Appl. Math. Mech., 14 (2014), 937-938.
doi: 10.1002/pamm.201410449. |
| [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. |
| [41] |
E. Roxin,
Stability in general control systems, J. Differ. Equ., 1 (1965), 115-150.
doi: 10.1016/0022-0396(65)90015-X. |
| [42] |
The Numerical Algorithms Group (NAG), The NAG Fortran Library, http://www.nag.com/. |
| [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. |
| [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. |
| [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. |
| [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. |
Figure 2.
Reachable set of the bilinear problem, generated with (right) and without (left) the subdivision algorithm
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)
Figure 4.
Selection of boxes for the next subdivision steps
Figure 5.
Inner and outer approximation of the reachable set
Figure 6.
Demonstration of reusability of the results within the subdivision algorithm
Figure 7.
$ B = [-1,1] $ covered by boxes (left) or by balls (right)
Figure 8.
$ B = [-1,1]^2 $ covered by boxes (left) or by balls (right)
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)
Figure 10.
Kenderov problem using explicit Euler (left), implicit Euler (middle) and the implicit trapezoidal rule (right) with 261 timesteps each
Figure 11.
Illustration of the robot from Ex. 4.3
Figure 12.
Rough approximation of the reachable set of the robot problem
Figure 13.
Finer approximation of the reachable set of the robot problem
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)
Figure 15.
Objective function of the non-transformed robot problem (left) and the transformed version (right)
Figure 16.
Approximated transformed reachable set of the robot with a less elaborate strategy for initial guesses
Figure 17.
Reachable set of the robot problem, generated with Ipopt (left) and WORHP (right)
Figure 18.
Robot model using a circular grid
Figure 19.
Graphical (left) and computational (right) zoom on the example of the Kenderov Problem
Figure 20.
Self-finding of the bounding box
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
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)
Figure 23.
Final box collections of the solution funnel of the bilinear problem for $ T \in [0, 1] $ , rendered with POV-Ray
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 |
| 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 |
| 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 and 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 and 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 and 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 and 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 and Control Theory, 2012, 1 (2) : 235-250. doi: 10.3934/eect.2012.1.235 |
| [6] |
Canghua Jiang, Cheng Jin, Ming Yu, Zongqi Xu. Direct optimal control for time-delay systems via a lifted multiple shooting algorithm. Journal of Industrial and Management Optimization, 2022, 18 (5) : 3771-3786. doi: 10.3934/jimo.2021135 |
| [7] |
Tayel Dabbous. Adaptive control of nonlinear systems using fuzzy systems. Journal of Industrial and Management Optimization, 2010, 6 (4) : 861-880. doi: 10.3934/jimo.2010.6.861 |
| [8] |
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 |
| [9] |
Piermarco Cannarsa, Carlo Sinestrari. On a class of nonlinear time optimal control problems. Discrete and Continuous Dynamical Systems, 1995, 1 (2) : 285-300. doi: 10.3934/dcds.1995.1.285 |
| [10] |
Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control and Related Fields, 2021, 11 (3) : 625-641. doi: 10.3934/mcrf.2021015 |
| [11] |
Bin Li, Kok Lay Teo, Cheng-Chew Lim, Guang Ren Duan. An optimal PID controller design for nonlinear constrained optimal control problems. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1101-1117. doi: 10.3934/dcdsb.2011.16.1101 |
| [12] |
Ying Zhang, Changjun Yu, Yingtao Xu, Yanqin Bai. Minimizing almost smooth control variation in nonlinear optimal control problems. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1663-1683. doi: 10.3934/jimo.2019023 |
| [13] |
Valery Y. Glizer, Vladimir Turetsky, Emil Bashkansky. Statistical process control optimization with variable sampling interval and nonlinear expected loss. Journal of Industrial and Management Optimization, 2015, 11 (1) : 105-133. doi: 10.3934/jimo.2015.11.105 |
| [14] |
Xiao-Li Hu, Han-Fu Chen. Optimal Adaptive Regulation for Nonlinear Systems with Observation Noise. Journal of Industrial and Management Optimization, 2007, 3 (1) : 155-164. doi: 10.3934/jimo.2007.3.155 |
| [15] |
Shuhong Chen, Zhong Tan. Optimal interior partial regularity for nonlinear elliptic systems. Discrete and Continuous Dynamical Systems, 2010, 27 (3) : 981-993. doi: 10.3934/dcds.2010.27.981 |
| [16] |
M. Motta, C. Sartori. Exit time problems for nonlinear unbounded control systems. Discrete and Continuous Dynamical Systems, 1999, 5 (1) : 137-156. doi: 10.3934/dcds.1999.5.137 |
| [17] |
Rohit Gupta, Farhad Jafari, Robert J. Kipka, Boris S. Mordukhovich. Linear openness and feedback stabilization of nonlinear control systems. Discrete and Continuous Dynamical Systems - S, 2018, 11 (6) : 1103-1119. doi: 10.3934/dcdss.2018063 |
| [18] |
Chunjiang Qian, Wei Lin, Wenting Zha. Generalized homogeneous systems with applications to nonlinear control: A survey. Mathematical Control and Related Fields, 2015, 5 (3) : 585-611. doi: 10.3934/mcrf.2015.5.585 |
| [19] |
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 |
| [20] |
Max Gunzburger, Sung-Dae Yang, Wenxiang Zhu. Analysis and discretization of an optimal control problem for the forced Fisher equation. Discrete and Continuous Dynamical Systems - B, 2007, 8 (3) : 569-587. doi: 10.3934/dcdsb.2007.8.569 |
Impact Factor:
Tools
Metrics
Other articles
by authors
[Back to Top]