# American Institute of Mathematical Sciences

doi: 10.3934/mcrf.2021015

## External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms

 Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16, S.Kovalevskaja street, Ekaterinburg, 620108, Russia

Received  February 2019 Revised  October 2019 Published  March 2021

We deal with the reachability problem for linear and bilinear discrete-time uncertain systems under integral non-quadratic constraints on additive input terms and set-valued constraints on initial states. The bilinearity is caused by an interval type uncertainty in coefficients of the system. Algorithms for constructing external parallelepiped-valued (shorter, polyhedral) estimates of reachable sets are presented. For linear time-invariant systems, two techniques for constructing touching external estimates with constant orientation matrices are described and compared. For time-dependant bilinear systems, parallelepiped-valued estimates are constructed. For bilinear systems with constant coefficients, nonconvex estimates are proposed in the form of unions of parallelepipeds. Evolution of all estimates is determined by systems of recurrence relations.

Citation: Elena K. Kostousova. External polyhedral estimates of reachable sets of discrete-time systems with integral bounds on additive terms. Mathematical Control & Related Fields, doi: 10.3934/mcrf.2021015
##### References:
 [1] R. Baier and T. Donchev, Discrete approximation of impulsive differential inclusions, Numer. Funct. Anal. Optim., 31 (2010), 653-678.  doi: 10.1080/01630563.2010.483878.  Google Scholar [2] V. A. Baturin, E. V. Goncharova, F. L. Pereira and J. B. Sousa, Measure-controlled dynamic systems: Polyhedral approximation of their reachable set boundary, Autom. Remote Control, 67 (2006), 350-360.  doi: 10.1134/S0005117906030027.  Google Scholar [3] F. L. Chernousko and D. Ya. Rokityanskii, Ellipsoidal bounds on reachable sets of dynamical systems with matrices subjected to uncertain perturbations, J. Optim. Theory Appl., 104 (2000), 1-19.  doi: 10.1023/A:1004687620019.  Google Scholar [4] T. F. Filippova, Estimates of reachable sets of impulsive control problems with special nonlinearity, AIP Conf. Proc., 1773 (2016), 100004. doi: 10.1063/1.4964998.  Google Scholar [5] T. F. Filippova, The HJB approach and state estimation for control systems with uncertainty, IFAC-PapersOnLine, 51 (2018), Issue 13, 7–12. doi: 10.1016/j.ifacol.2018.07.246.  Google Scholar [6] T. F. Filippova, Differential equations for ellipsoidal estimates of reachable sets for a class of control systems with nonlinearity and uncertainty, IFAC-PapersOnLine, 51 (2018), Issue 32,770–775. doi: 10.1016/j.ifacol.2018.11.452.  Google Scholar [7] A. Girard, C. Le Guernic and O. Maler, Efficient computation of reachable sets of linear time-invariant systems with inputs, in: Hybrid Systems: Computation and Control, Lecture Notes in Comput. Sci., 3927, Springer, Berlin, 2006,257–271. doi: 10.1007/11730637_21.  Google Scholar [8] K. G. Guseinov, O. Ozer, E. Akyar and V. N. Ushakov, The approximation of reachable sets of control systems with integral constraint on controls, NoDEA Nonlinear Differential Equations Appl., 14 (2007), 57-73.  doi: 10.1007/s00030-006-4036-6.  Google Scholar [9] M. I. Gusev, On convexity of reachable sets of a nonlinear system under integral constraints, IFAC-PapersOnLine 51 (2018), Issue 32,207–212. doi: 10.1016/j.ifacol.2018.11.382.  Google Scholar [10] L. Jaulin, M. Kieffer, O. Didrit and É. Walter, Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics, Springer-Verlag, London, 2001. doi: 10.1007/978-1-4471-0249-6.  Google Scholar [11] E. K. Kostousova, State estimation for dynamic systems via parallelotopes: Optimization and parallel computations, Optimiz. Methods and Software, 9 (1998), 269-306.  doi: 10.1080/10556789808805696.  Google Scholar [12] E. K. Kostousova, Outer polyhedral estimates for attainability sets of systems with bilinear uncertainty, J. Appl. Math. Mech., 66 (2002), 547–558. Erratum in: ibid., 66 (2002), 857. doi: 10.1016/S0021-8928(02)00073-4.  Google Scholar [13] E. K. Kostousova, Polyhedral estimates for attainability sets of linear multistage systems with integral constraints on the control (in Russian), Vychisl. Tekhnol., 8 (2003), no. 4, 55–74. Also available from: http://www.ict.nsc.ru/jct/content/t8n4/Kostousova.pdf. Google Scholar [14] E. K. Kostousova, On the boundedness of outer polyhedral estimates for reachable sets of linear systems, Comput. Math. Math. Phys., 48 (2008), 918–932. Erratum in: ibid., 48 (2008), 1915–1916. doi: 10.1134/S0965542508060043.  Google Scholar [15] E. K. Kostousova, State estimation for linear impulsive differential systems through polyhedral techniques, Discrete Contin. Dyn. Syst. (2009), Issue Suppl., 466–475. doi: 10.3934/proc.2009.2009.466.  Google Scholar [16] E. K. Kostousova, On polyhedral estimates for trajectory tubes of dynamical discrete-time systems with multiplicative uncertainty, Discrete Contin. Dyn. Syst. (2011), Issue Suppl., 864–873. doi: 10.3934/proc.2011.2011.864.  Google Scholar [17] E. K. Kostousova, On boundedness and unboundedness of polyhedral estimates for reachable sets of linear differential systems, Reliable Computing, 19 (2013), 26-44.   Google Scholar [18] E. K. Kostousova, External polyhedral estimates of reachable sets of linear and bilinear discrete-time systems with integral bounds on additive terms, in Proceedings of 2018 14th International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiys Conference), STAB, IEEE Xplore Digital Library, (2018), 1–4. doi: 10.1109/STAB.2018.8408370.  Google Scholar [19] V. M. Kuntsevich and A. B. Kurzhanski, Attainability domains for linear and some classes of nonlinear discrete systems and their control, J. Automation and Inform. Sci., 42 (2010), 1-18.  doi: 10.1615/JAutomatInfScien.v42.i1.10.  Google Scholar [20] A. B. Kurzhanski and A. N. Daryin, Dynamic programming for impulse controls, Annual Reviews in Control, 32 (2008), 213-227.  doi: 10.1016/j.arcontrol.2008.08.001.  Google Scholar [21] A. B. Kurzhanski and I. Vályi, Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Boston, 1997.  Google Scholar [22] A. B. Kurzhanski and P. Varaiya, Dynamics and Control of Trajectory Tubes, Theory and Computation, (Systems & Control: Foundations & Applications, Book 85), Birkhäuser/Springer, Cham, 2014. doi: 10.1007/978-3-319-10277-1.  Google Scholar [23] C. Le Guernic, Calcul Efficace de l'Ensemble Atteignable des Systèmes Linéaires avec Incertitudes, Master's thesis, Université Paris VII, 2005. Google Scholar [24] A. V. Lotov, Method for constructing an external polyhedral estimate of the trajectory tube for a nonlinear dynamic system, Doklady Mathematics, 95 (2017), 95-98.  doi: 10.1134/S1064562417010045.  Google Scholar [25] O. G. Matviychuk, Estimation techniques for bilinear control systems, IFAC-PapersOnLine, 51 (2018), Issue 32,877–882. doi: 10.1016/j.ifacol.2018.11.434.  Google Scholar [26] S. Mazurenko, Partial differential equation for evolution of star-shaped reachability domains of differential inclusions, Set-Valued Var. Anal., 24 (2016), 333-354.  doi: 10.1007/s11228-015-0345-4.  Google Scholar [27] B. T. Polyak, S. A. Nazin, C. Durieu and E. Walter, Ellipsoidal parameter or state estimation under model uncertainty, Automatica J. IFAC, 40 (2004), 1171-1179.  doi: 10.1016/j.automatica.2004.02.014.  Google Scholar [28] V. V. Sinyakov, Method for computing exterior and interior approximations to the reachability sets of bilinear differential systems, Differ. Equ., 51 (2015), 1097-1111.  doi: 10.1134/S0012266115080145.  Google Scholar [29] V. M. Veliov, On the relationship between continuous- and discrete-time control systems, CEJOR Cent. Eur. J. Oper. Res., 18 (2010), 511-523.  doi: 10.1007/s10100-010-0167-2.  Google Scholar

show all references

##### References:
 [1] R. Baier and T. Donchev, Discrete approximation of impulsive differential inclusions, Numer. Funct. Anal. Optim., 31 (2010), 653-678.  doi: 10.1080/01630563.2010.483878.  Google Scholar [2] V. A. Baturin, E. V. Goncharova, F. L. Pereira and J. B. Sousa, Measure-controlled dynamic systems: Polyhedral approximation of their reachable set boundary, Autom. Remote Control, 67 (2006), 350-360.  doi: 10.1134/S0005117906030027.  Google Scholar [3] F. L. Chernousko and D. Ya. Rokityanskii, Ellipsoidal bounds on reachable sets of dynamical systems with matrices subjected to uncertain perturbations, J. Optim. Theory Appl., 104 (2000), 1-19.  doi: 10.1023/A:1004687620019.  Google Scholar [4] T. F. Filippova, Estimates of reachable sets of impulsive control problems with special nonlinearity, AIP Conf. Proc., 1773 (2016), 100004. doi: 10.1063/1.4964998.  Google Scholar [5] T. F. Filippova, The HJB approach and state estimation for control systems with uncertainty, IFAC-PapersOnLine, 51 (2018), Issue 13, 7–12. doi: 10.1016/j.ifacol.2018.07.246.  Google Scholar [6] T. F. Filippova, Differential equations for ellipsoidal estimates of reachable sets for a class of control systems with nonlinearity and uncertainty, IFAC-PapersOnLine, 51 (2018), Issue 32,770–775. doi: 10.1016/j.ifacol.2018.11.452.  Google Scholar [7] A. Girard, C. Le Guernic and O. Maler, Efficient computation of reachable sets of linear time-invariant systems with inputs, in: Hybrid Systems: Computation and Control, Lecture Notes in Comput. Sci., 3927, Springer, Berlin, 2006,257–271. doi: 10.1007/11730637_21.  Google Scholar [8] K. G. Guseinov, O. Ozer, E. Akyar and V. N. Ushakov, The approximation of reachable sets of control systems with integral constraint on controls, NoDEA Nonlinear Differential Equations Appl., 14 (2007), 57-73.  doi: 10.1007/s00030-006-4036-6.  Google Scholar [9] M. I. Gusev, On convexity of reachable sets of a nonlinear system under integral constraints, IFAC-PapersOnLine 51 (2018), Issue 32,207–212. doi: 10.1016/j.ifacol.2018.11.382.  Google Scholar [10] L. Jaulin, M. Kieffer, O. Didrit and É. Walter, Applied Interval Analysis: With Examples in Parameter and State Estimation, Robust Control and Robotics, Springer-Verlag, London, 2001. doi: 10.1007/978-1-4471-0249-6.  Google Scholar [11] E. K. Kostousova, State estimation for dynamic systems via parallelotopes: Optimization and parallel computations, Optimiz. Methods and Software, 9 (1998), 269-306.  doi: 10.1080/10556789808805696.  Google Scholar [12] E. K. Kostousova, Outer polyhedral estimates for attainability sets of systems with bilinear uncertainty, J. Appl. Math. Mech., 66 (2002), 547–558. Erratum in: ibid., 66 (2002), 857. doi: 10.1016/S0021-8928(02)00073-4.  Google Scholar [13] E. K. Kostousova, Polyhedral estimates for attainability sets of linear multistage systems with integral constraints on the control (in Russian), Vychisl. Tekhnol., 8 (2003), no. 4, 55–74. Also available from: http://www.ict.nsc.ru/jct/content/t8n4/Kostousova.pdf. Google Scholar [14] E. K. Kostousova, On the boundedness of outer polyhedral estimates for reachable sets of linear systems, Comput. Math. Math. Phys., 48 (2008), 918–932. Erratum in: ibid., 48 (2008), 1915–1916. doi: 10.1134/S0965542508060043.  Google Scholar [15] E. K. Kostousova, State estimation for linear impulsive differential systems through polyhedral techniques, Discrete Contin. Dyn. Syst. (2009), Issue Suppl., 466–475. doi: 10.3934/proc.2009.2009.466.  Google Scholar [16] E. K. Kostousova, On polyhedral estimates for trajectory tubes of dynamical discrete-time systems with multiplicative uncertainty, Discrete Contin. Dyn. Syst. (2011), Issue Suppl., 864–873. doi: 10.3934/proc.2011.2011.864.  Google Scholar [17] E. K. Kostousova, On boundedness and unboundedness of polyhedral estimates for reachable sets of linear differential systems, Reliable Computing, 19 (2013), 26-44.   Google Scholar [18] E. K. Kostousova, External polyhedral estimates of reachable sets of linear and bilinear discrete-time systems with integral bounds on additive terms, in Proceedings of 2018 14th International Conference Stability and Oscillations of Nonlinear Control Systems (Pyatnitskiys Conference), STAB, IEEE Xplore Digital Library, (2018), 1–4. doi: 10.1109/STAB.2018.8408370.  Google Scholar [19] V. M. Kuntsevich and A. B. Kurzhanski, Attainability domains for linear and some classes of nonlinear discrete systems and their control, J. Automation and Inform. Sci., 42 (2010), 1-18.  doi: 10.1615/JAutomatInfScien.v42.i1.10.  Google Scholar [20] A. B. Kurzhanski and A. N. Daryin, Dynamic programming for impulse controls, Annual Reviews in Control, 32 (2008), 213-227.  doi: 10.1016/j.arcontrol.2008.08.001.  Google Scholar [21] A. B. Kurzhanski and I. Vályi, Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Boston, 1997.  Google Scholar [22] A. B. Kurzhanski and P. Varaiya, Dynamics and Control of Trajectory Tubes, Theory and Computation, (Systems & Control: Foundations & Applications, Book 85), Birkhäuser/Springer, Cham, 2014. doi: 10.1007/978-3-319-10277-1.  Google Scholar [23] C. Le Guernic, Calcul Efficace de l'Ensemble Atteignable des Systèmes Linéaires avec Incertitudes, Master's thesis, Université Paris VII, 2005. Google Scholar [24] A. V. Lotov, Method for constructing an external polyhedral estimate of the trajectory tube for a nonlinear dynamic system, Doklady Mathematics, 95 (2017), 95-98.  doi: 10.1134/S1064562417010045.  Google Scholar [25] O. G. Matviychuk, Estimation techniques for bilinear control systems, IFAC-PapersOnLine, 51 (2018), Issue 32,877–882. doi: 10.1016/j.ifacol.2018.11.434.  Google Scholar [26] S. Mazurenko, Partial differential equation for evolution of star-shaped reachability domains of differential inclusions, Set-Valued Var. Anal., 24 (2016), 333-354.  doi: 10.1007/s11228-015-0345-4.  Google Scholar [27] B. T. Polyak, S. A. Nazin, C. Durieu and E. Walter, Ellipsoidal parameter or state estimation under model uncertainty, Automatica J. IFAC, 40 (2004), 1171-1179.  doi: 10.1016/j.automatica.2004.02.014.  Google Scholar [28] V. V. Sinyakov, Method for computing exterior and interior approximations to the reachability sets of bilinear differential systems, Differ. Equ., 51 (2015), 1097-1111.  doi: 10.1134/S0012266115080145.  Google Scholar [29] V. M. Veliov, On the relationship between continuous- and discrete-time control systems, CEJOR Cent. Eur. J. Oper. Res., 18 (2010), 511-523.  doi: 10.1007/s10100-010-0167-2.  Google Scholar
Touching external estimates for $\mathcal{X}[\cdot]$ and $\mathcal{X}[N]$ from $\mathfrak{P}^{1+}$ (figures (a), (b)) and ${\hat {\mathfrak{P}}}^{2+}$ (figures (c), (d)) in Example 1
External estimates for $\mathcal{X}[\cdot]$ and $\mathcal{X}[N]$ in Example 2
External estimates for $\mathcal{Y}[N]$ for three cases in Example 3: $\mathcal{P}^{II+}{[N]}$ from Theorem 5.2 (dashed lines), $\mathcal{P}^{+, {\rm mod}}{[N]}$ from (49) (solid thick lines), and estimates in the form of unions (48) of several parallelepipeds, not intersections as in previous figures
 [1] Tadeusz Kaczorek, Andrzej Ruszewski. Analysis of the fractional descriptor discrete-time linear systems by the use of the shuffle algorithm. Journal of Computational Dynamics, 2021  doi: 10.3934/jcd.2021007 [2] 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 [3] Horst R. Thieme. Discrete-time dynamics of structured populations via Feller kernels. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021082 [4] Elimhan N. Mahmudov. Second order discrete time-varying and time-invariant linear continuous systems and Kalman type conditions. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021010 [5] Alberto Bressan, Ke Han, Franco Rampazzo. On the control of non holonomic systems by active constraints. Discrete & Continuous Dynamical Systems, 2013, 33 (8) : 3329-3353. doi: 10.3934/dcds.2013.33.3329 [6] Manuel de León, Víctor M. Jiménez, Manuel Lainz. Contact Hamiltonian and Lagrangian systems with nonholonomic constraints. Journal of Geometric Mechanics, 2021, 13 (1) : 25-53. doi: 10.3934/jgm.2021001 [7] Yuri Fedorov, Božidar Jovanović. Continuous and discrete Neumann systems on Stiefel varieties as matrix generalizations of the Jacobi–Mumford systems. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2559-2599. doi: 10.3934/dcds.2020375 [8] Vandana Sharma. Global existence and uniform estimates of solutions to reaction diffusion systems with mass transport type boundary conditions. Communications on Pure & Applied Analysis, 2021, 20 (3) : 955-974. doi: 10.3934/cpaa.2021001 [9] Wei-Jian Bo, Guo Lin, Shigui Ruan. Traveling wave solutions for time periodic reaction-diffusion systems. Discrete & Continuous Dynamical Systems, 2018, 38 (9) : 4329-4351. doi: 10.3934/dcds.2018189 [10] Tianhu Yu, Jinde Cao, Chuangxia Huang. Finite-time cluster synchronization of coupled dynamical systems with impulsive effects. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3595-3620. doi: 10.3934/dcdsb.2020248 [11] Yue Qi, Xiaolin Li, Su Zhang. Optimizing 3-objective portfolio selection with equality constraints and analyzing the effect of varying constraints on the efficient sets. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1531-1556. doi: 10.3934/jimo.2020033 [12] Xiongxiong Bao, Wan-Tong Li. Existence and stability of generalized transition waves for time-dependent reaction-diffusion systems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (7) : 3621-3641. doi: 10.3934/dcdsb.2020249 [13] Peng Zhang, Yongquan Zeng, Guotai Chi. Time-consistent multiperiod mean semivariance portfolio selection with the real constraints. Journal of Industrial & Management Optimization, 2021, 17 (4) : 1663-1680. doi: 10.3934/jimo.2020039 [14] Wenmin Gong, Guangcun Lu. On coupled Dirac systems. Discrete & Continuous Dynamical Systems, 2017, 37 (8) : 4329-4346. doi: 10.3934/dcds.2017185 [15] Mauricio Achigar. Extensions of expansive dynamical systems. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3093-3108. doi: 10.3934/dcds.2020399 [16] 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 [17] Bingru Zhang, Chuanye Gu, Jueyou Li. Distributed convex optimization with coupling constraints over time-varying directed graphs†. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2119-2138. doi: 10.3934/jimo.2020061 [18] María J. Garrido-Atienza, Bohdan Maslowski, Jana  Šnupárková. Semilinear stochastic equations with bilinear fractional noise. Discrete & Continuous Dynamical Systems - B, 2016, 21 (9) : 3075-3094. doi: 10.3934/dcdsb.2016088 [19] Haiyan Wang. Existence and nonexistence of positive radial solutions for quasilinear systems. Conference Publications, 2009, 2009 (Special) : 810-817. doi: 10.3934/proc.2009.2009.810 [20] Tuvi Etzion, Alexander Vardy. On $q$-analogs of Steiner systems and covering designs. Advances in Mathematics of Communications, 2011, 5 (2) : 161-176. doi: 10.3934/amc.2011.5.161

2019 Impact Factor: 0.857

## Tools

Article outline

Figures and Tables

[Back to Top]