The evasion problem under uncertainty is considered for discrete-time systems with an initially linear structure and state constraints, where controls u, U, and v act; u and v enter additively, and U enters into the system matrix. In the considered control synthesis problem, which we call the enhanced evasion problem, the aim of v is either to avoid the trajectory to hit a given terminal set at a given final moment, as well as a sequence of sets specified at previous moments, or to violate at least one of the state constraints, whatever the admissible realizations of u and U. The presence of U introduces nonlinearity into the systems and leads to bilinear type systems. It is assumed that the terminal and intermediate sets are parallelepipeds, the controls u and v are constrained by parallelotope-valued constraints, U by interval constraints, and the state constraints are specified in the form of zones. A polyhedral method for synthesizing controls v is developed using polyhedral (parallelepiped-valued) tubes, which can be found from recurrence relations using explicit formulas. To obtain a solution to the problem under consideration, a solution to an auxiliary one-step polyhedral evasion problem with bilinearity is found. Its connections with the problems of interval analysis concerning the so-called sets of quantifier solutions to interval equations are noted. Examples illustrating the efficiency of the method are given.
Keywords: uncertain systems, evasion problem, control synthesis, bilinear systems, state constraints, polyhedral methods, parallelepipeds, interval analysis
Received February 4, 2025
Revised March 14, 2025
Accepted March 17, 2025
Elena Kirillovna Kostousova, Dr. Phys.-Math. Sci., Krasovskii Institute of Mathematics and Mechanics of the Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, e-mail: kek@imm.uran.ru
REFERENCES
1. Krasovskii N.N., Subbotin A.I. Game-theoretical control problems. NY, Springer, 1988, 517 p. ISBN: 978-1-4612-8318-8 .
2. Kurzhanski A., Vályi I. Ellipsoidal calculus for estimation and control. Boston, Birkhäuser, 1996, 321 p. ISBN: 978-0-8176-3699-9 .
3. Kurzhanski A.B., Varaiya P. Dynamics and control of trajectory tubes: theory and computation. Boston, Birkhäuser, 2014, 445 p. https://doi.org/10.1007/978-3-319-10277-1
4. Kurzhanski A.B., Daryin A.N. Dynamic programming for impulse feedback and fast controls: The linear systems case. London, Springer, 2020, 275 p. https://doi.org/10.1007/978-1-4471-7437-0
5. Ushakov V.N., Tarasyev A.M., Ushakov A.V. Minimax differential game with a fixed end moment. Mat. Teor. Igr Pril., 2024, vol. 16, no. 3, pp. 77–112 (in Russian).
6. Kurzhanski A.B., Mitchell I.M., Varaiya P. Control synthesis for state constrained systems and obstacle problems. IFAC Proceedings Volumes (IFAC-PapersOnline). 2004, vol. 37, no. 13, pp. 657–662. https://doi.org/10.1016/S1474-6670(17)31299-5
7. Ananyev B.I., Gusev M.I., Filippova T.F. Upravleniye i otsenivaniye sostoyaniy dinamicheskikh sistem s neopredelennost’yu [Control and estimation of states of dynamic systems with uncertainty]. Novosibirsk, Izd-vo SO RAN, 2018, 193 p. ISBN: 978-5-7692-1624-4 .
8. Althoff M., Frehse G., Girard A. Set propagation techniques for reachability analysis. Annu. Rev. Control. Robotics Auton. Syst., 2021, vol. 4, pp. 369–395. https://doi.org/10.1146/annurev-control-071420-081941
9. Patsko V., Kumkov S.I., Turova V. Pursuit-evasion games. In: Basar T., Zaccour G. (eds.) Handbook of dynamic game theory. Cham, Springer, 2018, pp. 951–1038. https://doi.org/10.1007/978-3-319-44374-4_30
10. Chernous’ko F.L. Otsenivanie fazovogo sostoyaniya dinamicheskikh sistem. Metod ellipsoidov [Estimation of phase state of dynamic systems: the ellipsoid method]. Moscow, Nauka Publ., 1988, 319 p.
11. Kurzhanskiy A.A., Varaiya P. Reach set computation and control synthesis for discrete-time dynamical systems with disturbances. Automatica, 2011, vol. 47, no. 7, pp. 1414–1426. https://doi.org/10.1016/j.automatica.2011.02.009
12. Chernousko F.L., Rokityanskii D.Ya. Ellipsoidal bounds on reachable sets of dynamical systems with matrices subjected to uncertain perturbations. J. Optimiz. Theory Appl., 2000, vol. 104, no. 1, pp. 1–19. https://doi.org/10.1023/A:1004687620019
13. Filippova T.F. HJB-inequalities in estimating reachable sets of a control system under uncertainty. Ural Math. J., 2022, vol. 8, no. 1, pp. 34–42. https://doi.org/10.15826/umj.2022.1.004
14. Vicino A., Zappa G. Sequential approximation of feasible parameter sets for identification with set membership uncertainty. IEEE Trans. Autom. Control, 1996, vol. 41, no. 6, pp. 774–785. https://doi.org/10.1109/9.506230
15. Kostousova E.K. On the polyhedral method of solving problems of control strategy synthesis. Proc. Steklov Inst. Math. (Suppl. 1), 2016, vol. 292, suppl. 1, pp. S140–S155. https://doi.org/10.1134/S0081543816020127
16. Martynov K., Botkin N.D., Turova V.L., Diepolder J. Quick construction of dangerous disturbances in conflict control problems. Annals of the International Society of Dynamic Games, vol. 17, pp. 3–24, Cham, Birkhäuser, 2020. https://doi.org/10.1007/978-3-030-56534-3_1
17. Sinyakov V., Girard A. Abstraction of continuous-time systems based on feedback controllers and mixed monotonicity. IEEE Trans. Autom. Control, 2023, vol. 68, no. 8, pp. 4508–4522. https://doi.org/10.1109/TAC.2022.3205423
18. Kostousova E.K. On polyhedral control synthesis for dynamical discrete-time systems under uncertainties and state constraints. Discr. Cont. Dynam. Syst., 2018, vol. 38, no. 12, pp. 6149–6162. https://doi.org/10.3934/dcds.2018153
19. Kostousova E.K. On solving terminal approach and evasion problems for linear discrete-time systems under state constraints. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2024, vol. 34, no. 2, pp. 204–221. https://doi.org/10.35634/vm240203
20. Kostousova E.K. On a control synthesis in an enhanced evasion problem for linear discrete-time systems. Trudy Inst. Mat. Mekh. UrO RAN, 2023, vol. 29, no. 1, pp. 111–126 (in Russian). https://doi.org/10.21538/0134-4889-2023-29-1-111-126
21. Martynov K., Botkin N., Turova V., Diepolder J. Real-time control of aircraft take-off in windshear. Part I: Aircraft model and control schemes. In: Proc. 25th Mediterranean Confer. on Control and Automation (MED 2017). Valletta, Malta, IEEE Xplore Digital Library, 2017, pp. 277–284. https://doi.org/10.1109/MED.2017.7984131
22. Kostousova E.K. Parallel computations for estimating attainability domains and informational sets of linear systems. In: Sb. Nauch. Trudov Algoritmy i programmnye sredstva parallelnykh vychisleniy, Ekaterinburg, Izd-vo UrO RAN, 1999, no. 3, pp. 107–126 (in Russian).
23. Shary S.P. Konechnomernyi interval’nyi analiz [Finite-dimensional interval analysis]. Novosibirsk, 2024, 671 p. Available at: http://www.nsc.ru/interval/Library/InteBooks/SharyBook.pdf .
24. Nikol’skii M.S. Some optimal control problems associated with Richardson’s arms race model. Comput. Math. Model., 2015, vol. 26, no. 1, pp. 52–60. https://doi.org/10.1007/s10598-014-9256-8
25. Patsko V.S., Ushakov V.N. Antagonistic differential games. Bol’shaya rossiyskaya entsiklopediya: nauchno-obrazovatel’nyy portal, 2023 (in Russian).
Available at: https://bigenc.ru/c/antagonisticheskie-differentsial-nye-igry-4c1915 .
Cite this article as: E.K. Kostousova. On the polyhedral method of control synthesis for an enhanced evasion problem for discrete-time systems with bilinearity and state constraints. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 2, pp. 125–140.
