# American Institute of Mathematical Sciences

• Previous Article
Modeling the pressure distribution in a spatially averaged cerebral capillary network
• MCRF Home
• This Issue
• Next Article
A priori error estimates for the space-time finite element discretization of an optimal control problem governed by a coupled linear PDE-ODE system
September  2021, 11(3): 625-641. 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  September 2021 Early access  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 and Related Fields, 2021, 11 (3) : 625-641. 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [17] E. K. Kostousova, On boundedness and unboundedness of polyhedral estimates for reachable sets of linear differential systems, Reliable Computing, 19 (2013), 26-44. [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. [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. [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. [21] A. B. Kurzhanski and I. Vályi, Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Boston, 1997. [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. [23] C. Le Guernic, Calcul Efficace de l'Ensemble Atteignable des Systèmes Linéaires avec Incertitudes, Master's thesis, Université Paris VII, 2005. [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. [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. [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. [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. [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. [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.

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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [17] E. K. Kostousova, On boundedness and unboundedness of polyhedral estimates for reachable sets of linear differential systems, Reliable Computing, 19 (2013), 26-44. [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. [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. [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. [21] A. B. Kurzhanski and I. Vályi, Ellipsoidal Calculus for Estimation and Control, Birkhäuser, Boston, 1997. [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. [23] C. Le Guernic, Calcul Efficace de l'Ensemble Atteignable des Systèmes Linéaires avec Incertitudes, Master's thesis, Université Paris VII, 2005. [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. [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. [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. [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. [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. [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.
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] Elena K. Kostousova. On polyhedral control synthesis for dynamical discrete-time systems under uncertainties and state constraints. Discrete and Continuous Dynamical Systems, 2018, 38 (12) : 6149-6162. doi: 10.3934/dcds.2018153 [2] Elena K. Kostousova. On polyhedral estimates for trajectory tubes of dynamical discrete-time systems with multiplicative uncertainty. Conference Publications, 2011, 2011 (Special) : 864-873. doi: 10.3934/proc.2011.2011.864 [3] Elena K. Kostousova. On control synthesis for uncertain dynamical discrete-time systems through polyhedral techniques. Conference Publications, 2015, 2015 (special) : 723-732. doi: 10.3934/proc.2015.0723 [4] Yuefen Chen, Yuanguo Zhu. Indefinite LQ optimal control with process state inequality constraints for discrete-time uncertain systems. Journal of Industrial and Management Optimization, 2018, 14 (3) : 913-930. doi: 10.3934/jimo.2017082 [5] Byungik Kahng, Miguel Mendes. The characterization of maximal invariant sets of non-linear discrete-time control dynamical systems. Conference Publications, 2013, 2013 (special) : 393-406. doi: 10.3934/proc.2013.2013.393 [6] 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 [7] Peter Giesl, Zachary Langhorne, Carlos Argáez, Sigurdur Hafstein. Computing complete Lyapunov functions for discrete-time dynamical systems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (1) : 299-336. doi: 10.3934/dcdsb.2020331 [8] Vladimir Răsvan. On the central stability zone for linear discrete-time Hamiltonian systems. Conference Publications, 2003, 2003 (Special) : 734-741. doi: 10.3934/proc.2003.2003.734 [9] Sofian De Clercq, Koen De Turck, Bart Steyaert, Herwig Bruneel. Frame-bound priority scheduling in discrete-time queueing systems. Journal of Industrial and Management Optimization, 2011, 7 (3) : 767-788. doi: 10.3934/jimo.2011.7.767 [10] Xiang Xie, Honglei Xu, Xinming Cheng, Yilun Yu. Improved results on exponential stability of discrete-time switched delay systems. Discrete and Continuous Dynamical Systems - B, 2017, 22 (1) : 199-208. doi: 10.3934/dcdsb.2017010 [11] Haijun Sun, Xinquan Zhang. Guaranteed cost control of discrete-time switched saturated systems. Discrete and Continuous Dynamical Systems - B, 2021, 26 (8) : 4515-4522. doi: 10.3934/dcdsb.2020300 [12] Andrii Mironchenko, Hiroshi Ito. Characterizations of integral input-to-state stability for bilinear systems in infinite dimensions. Mathematical Control and Related Fields, 2016, 6 (3) : 447-466. doi: 10.3934/mcrf.2016011 [13] Chuandong Li, Fali Ma, Tingwen Huang. 2-D analysis based iterative learning control for linear discrete-time systems with time delay. Journal of Industrial and Management Optimization, 2011, 7 (1) : 175-181. doi: 10.3934/jimo.2011.7.175 [14] Ran Dong, Xuerong Mao. Asymptotic stabilization of continuous-time periodic stochastic systems by feedback control based on periodic discrete-time observations. Mathematical Control and Related Fields, 2020, 10 (4) : 715-734. doi: 10.3934/mcrf.2020017 [15] Qingling Zhang, Guoliang Wang, Wanquan Liu, Yi Zhang. Stabilization of discrete-time Markovian jump systems with partially unknown transition probabilities. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1197-1211. doi: 10.3934/dcdsb.2011.16.1197 [16] Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. Permanence and universal classification of discrete-time competitive systems via the carrying simplex. Discrete and Continuous Dynamical Systems, 2020, 40 (3) : 1621-1663. doi: 10.3934/dcds.2020088 [17] Xi Zhu, Meixia Li, Chunfa Li. Consensus in discrete-time multi-agent systems with uncertain topologies and random delays governed by a Markov chain. Discrete and Continuous Dynamical Systems - B, 2020, 25 (12) : 4535-4551. doi: 10.3934/dcdsb.2020111 [18] Zhongkui Li, Zhisheng Duan, Guanrong Chen. Consensus of discrete-time linear multi-agent systems with observer-type protocols. Discrete and Continuous Dynamical Systems - B, 2011, 16 (2) : 489-505. doi: 10.3934/dcdsb.2011.16.489 [19] Deepak Kumar, Ahmad Jazlan, Victor Sreeram, Roberto Togneri. Partial fraction expansion based frequency weighted model reduction for discrete-time systems. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 329-337. doi: 10.3934/naco.2016015 [20] Huan Su, Pengfei Wang, Xiaohua Ding. Stability analysis for discrete-time coupled systems with multi-diffusion by graph-theoretic approach and its application. Discrete and Continuous Dynamical Systems - B, 2016, 21 (1) : 253-269. doi: 10.3934/dcdsb.2016.21.253

2020 Impact Factor: 1.284