Algorithm for Simulating the Optimal Movement of a Complex Dynamic System Oleksandr Lysenko1, Elena Tachynina2, Sergiy Ponomarenko1 and Oleksandr Guida3 1 National Technical University of Ukraine "Ihor Sikorsky Kyiv Polytechnic Institute", 37 Beresteyskyi Prospect, Kyiv, 03056, Ukraine 2 National Aviation University, 1 Lubomyra Huzara avenue, Kyiv, 03058, Ukraine 3 V. I. Vernadsky Tavria National University, 33 John McCain str, Kyiv, 01042, Ukraine Abstract The work is devoted to the development of the structure of the algorithm for modeling the optimal movement of complex dynamic systems (SDS) along a branched trajectory. Complex systems are called systems consisting of separate subsystems, the flight trajectories of which differ and are called branched. Branched trajectories should consist of trajectory segments, the first of which will be common to the entire SDS, and the other trajectory branches will be different, as each subsystem moves to its goal along its own trajectory segment. The proposed algorithm makes it possible to optimize such trajectories in real time and to carry out operational correction of SDS trajectories in the event of the occurrence of unpredictable influencing factors. It is known that the effectiveness of the SDS functioning between structural transformations depends on the coordinates of the mutual location and speed of each subsystem and the choice of optimal moments of time for structural transformations. The efficiency of determining these parameters during the flight is fundamentally important. The necessary conditions for the optimality of the trajectory of the SDS movement are found, which are universal for problems with any finite number of trajectory branches. The implementation of the proposed conditions will allow to reduce the number of computational procedures in the control calculations in conditions of uncertainty of the initial conditions. These conditions are the methodological basis for the development of computational algorithms for modeling the optimal trajectories of the SDS movement. The necessary optimality conditions have a clear physical meaning and are technological and user-friendly. The results of the research presented in the article are important and relevant for the construction of the laws of trajectory control of existing and prospective SDS Keywords 1 Optimal control, complex dynamic systems, branched trajectories, mathematical modeling, algorithmic support 1. Relevance of the topic Modern achievements in the creation of complex mechanical objects, communication and data transmission systems, and high-performance on-board computers open the way to the design of complex technical systems of the new generation, capable of solving a single technical problem without mechanical communication and only on the basis of information exchange between individual subsystems of such objects. Examples of such systems are complex dynamic systems (CDS). These include dynamic systems consisting of separate subsystems (sets of objects) that interact with each other in flight. And the synthesis of motion control of each subsystem is coordinated. At the same time, the subsystems can function together or separately. Their separation takes place according to separate commands, which are given in a strictly defined spatial position of each subsystem and at given moments of time. 14th International Scientific and Practical Conference from Programming UkrPROG’2024, May 14-15, 2024, Kyiv, Ukraine * Corresponding author. † These authors contributed equally. lysenko_home@ukr.net (O. Lysenko); tachinina5@gmail.com (E. Tachynina); sol_@ukr.net (S. Ponomarenko); guydasg@ukr.net (O. H. Guida) 0000-0002-7276-9279 (O. Lysenko); 0000-0001-7081-0576 (E. Tachynina); 0000-0001-5512-3778 (S. Ponomarenko); 0000-0002-2019-2615 (O. Guida) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings Examples of modern SDS are reusable air-launched aerospace systems (ASS) and groups of unmanned aerial vehicles (UAVs) that form "flying sensor networks" or swarms (robotic sensor networks) based on wireless telecommunication systems. In the scientific literature, it is customary to call the trajectories of complex dynamic systems branched, since they consist of the initial section of the joint movement of the entire system and sections of individual movement of individual subsystems of the SDS along separate branches of the trajectory. It was established [1, 2] that the effectiveness of the operation of the SDS between structural transformations depends on the coordinates of the mutual location and speed of each subsystem and the choice of optimal moments of time for structural transformations. The efficiency of determining these parameters during the flight is fundamentally important. Therefore, the task of operational construction of the optimal branched trajectory of the SDS movement during the flight is key and is recognized as relevant in the world both from the scientific and practical points of view [1, 2, 5]. 2. Analysis of the state of the issue The mathematical theory of impulse differential equations with a discontinuous right-hand side is used to solve the problem of optimal control of the SDS on branched trajectories [4]. The concept of "disruptive system" is generalizing and covers a significant class of dynamic objects: with impulse influence, with discontinuities, multi-stage, with relay control, with intermediate conditions, composite, etc. Mathematical models of discontinuous systems are mainly described by differential equations with discontinuous (piecewise continuous) right-hand parts. The theory of discontinuous dynamic systems and methods of finding optimal solutions for such systems were developed by such researchers as L. S. Pontryagin, V. G. Boltyansky, R. V. Gamkrelidze, and M. M. Krasovsky, V. A. Troitskyi, V. I. Utkin. For specific types of discontinuous systems, theoretical and applied results were obtained in the works of V. A. Bodner, L. T. Ashchepkov, B. F. Krotov, Bryson Ho Yu Shea, A. M. Samoilenko, N. A. Perestyuk, A. A. Aslanyan, O. I. Lysenko and other authors. The peculiarity of the theoretical results of these authors is that they formulated optimal control problem statements in terms of discontinuous systems and proposed optimal solutions for specific dynamic systems with the presence of the main element (main subsystem) of the SDS. In their works, the overdetermination method, or the method of linear time transformations, was used to create mathematical models of discontinuous systems. In such a statement, the task of managing the SDS was formulated as the task of managing a discontinuous system with a selected priority element, in relation to which the theory of discontinuous systems was applied for individual components. The consequence of this formulation of the problem was an increase in the size of the state vector and the control vector of the discontinuous system. Their number increased in proportion to the number of branches of the SDS trajectory. And the formulation of the problem of finding the optimal branched trajectory for the entire SDS (holistic, generalized formulation of the problem) was not considered. To date, the theoretical solutions obtained by previous researchers have not been put to practical use, and there are no design solutions for synthesizing the trajectories of the SDS movement in real time. This is explained by the complexity of the mathematical models themselves and the methods of their multiple solution, since the use of an abstract-formal description of the optimization problems of branched SDS trajectories leads to an increase in the dimension of the state vector and the dimension of the control vector of the discontinuous system. And this dimension increases in proportion to the number of branches of the trajectory. The increase in the dimension of the entire problem leads to the impossibility of practical implementation of the algorithm of operational optimization of branched trajectories in the on-board computer. Also, no applied studies were conducted, which would be based on an adequate physical understanding of the "scheme" of the movement of the SDS along the branches of the trajectory. Therefore, the results of the practical verification of the mechanism for building optimal branched trajectories according to an arbitrary scheme with the possibility of organizing operational computational procedures are currently unknown. As a result, the actually existing SDS of the type "air launch" and "flying sensor networks" do not fully realize their potential of technical capabilities due to the fact that large-scale methods and models are used to control them. The solution to this problem requires the construction of sufficient conditions for the optimality of the branched trajectories of the SDS movement. Moreover, these requirements should be formulated in a form convenient for implementation on a real time scale (for operational synthesis of trajectories). In this regard, solving the problem of operational synthesis of optimal branched trajectories of movement and operational optimization of the SDS traffic management process on existing on-board computing devices is an urgent scientific and technical need. And, the research carried out in this article is relevant for trajectory control systems of modern and promising SDS [3, 5, 6]. 2.1. Presentation of the main material The SDS is a collection of dynamic subsystems, which in the process of movement can be combined into groups for joint movement, separate for the purpose of independent maneuvering, and exert a mutual influence on the dynamics of movement [1, 3]. Let's consider an example of the movement of a hypothetical SDS according to the scheme shown in Figure 1 Figure 1: Scheme of a branched trajectory At the moment of time t1, four subsystems in a single block begin to move, during which at the moment of time t3, two auxiliary subsystems are separated from the original unit, which end their movement at the moments of time t4 and t5. At the moment of time t6, the third auxiliary subsystem is separated, the movement of which ends at the moment of time t8. At time t7, the fourth subsystem is connected to the subsystem that started moving at time t2. After the end of the joint movement at time t9, the subsystems are uncoupled and carry out independent maneuvering, which ends at time t10 and t11. The trajectory of the analyzed SDS belongs to the branched class. Let's set the efficiency criterion taking into account the nature of the movement of the subsystems along all the branches of the trajectory. It is necessary to simulate the optimal trajectory of the SDS movement according to the given criterion. When solving such tasks, branched trajectories of varying complexity are possible. Currently, optimality conditions of only partial schemes of branched trajectories are formulated. Let us formulate in terms of the theory of optimal control the sufficient conditions for the existence of optimal control of the SDS of an arbitrary scheme. Consider the simplest branched trajectories, the time diagrams of which are presented in Figure 2. The equations describing the movement of the SDS along the trajectory with separation and grouping [3, 5] have the form (Figure 2, a, б): . Figure 2: Time diagram of the simplest branched trajectory (a – with separation; 2 – with grouping). 1 x  1 f  1 x , 1 u  , t  t 0 , t1  ;  11 12 f  11 x, 11 u ; 12 x , 12 u  , t  t1 , t12  ; x    (1)  1 f  11 x , 11 u  , t  t12 , t11  ; 11 11 x  12 f  12 x , 12 u ; 11 x , 11 u  , t   t 0 , t12  ; (2) where 1 x  t   R , 1 u  t   R l , l u  t    l ( l  1, 1 1, 1 2 ). n m We will write the vector criterion of the quality of the functioning of the SDS in an adaptive form: I  S ( 1 x (t 0 ), t 0 ; 1 x (t1 ), t1 ; 11 x (t12 ), 12 x (t12 ), t12 ; 11 x (t11 ), t11 )  I1  I11  I1 (3 ) 1 12 3 I1   1  1 x, 1 u  dt , I12   12  12 x, 12 u; 11 x, 11 u  dt; 0 1 12 11 I11    1 12 11  12 x , 12 u ; 11 x , 11 u  dt  12  11  11 x , 11 u  dt . The optimality criteria corresponds to the Bilets form, according to which the function S() physically reflects the requirements for the movement parameters of individual subsystems. Such parameters are the values of the coordinates at the beginning and end of each branch of the trajectory, as well as the values of the moments of time of the structural transformations of the SDS. The integral members of the criterion set requirements for the nature of the movement of the subsystem along the corresponding branches of the trajectory. The mutual influence of the subsystem in the time interval t1 , t12  is reflected in equation (1) and (2) and in the partial integral terms I11 , I12 . The equations describing the criteria and dynamics of movement of subsystems that are grouped (Figure 2, b) have the same form as for a system with separation, and differ only in that t11  t12  t1  t0 . Omitting the proof [1], we formulate the theorem taking into account the two systems shown in Figure 2. The equations 1 u  t  t  t 0 , t1  , 11 u  t  t  t1 , t11  , 12 u  t  t  t1 , t12  , of the phase coordinate vectors 1 x(t0 ), 1 x(t1 ), 11 x(t12 ), 12 x(t12 ), 11 x(t11 ) and the moment of time t0 , t1 , t11 , t12 should be chosen such that the functional I assumes the smallest possible value. Theorem Let 1 x(t ), 1 u  t  t  t0 , t1  ; 11 u  t  , 12 x(t ), 12 u  t  t  t1 , t12  ; 11 x(t11 ) , 11 u  t  t  t12 , t11  , be admissible processes. The optimality of processes requires the existence of solutions 1   t  t  t0 , t1  , 11 12   t  , 12   t  t  t1 , t12  , 11   t  t  t12 , t11  such connected vector equations:   H /  x  0, 1 1 1 12 11   H 1112 /  11 x  H 12 / 11 x  0, (4) 12   H /  x  H 12 / 12 x  0, 12 11 12   H /  x  0 11 11 11 such that fair conditions: transversality for connected functions and Hamiltonians S / 1 x (t0 )   ( 1) 1  (tˆ0 )  0, S / t0   (1)  H1  0, (5)  S / 1i x (ti )   ( 1) 1i  (tˆ1i )  0 (i  1, 2), S / t11   (1)  H11  0;  jump for conjugate functions and Hamiltonians  S / 1 x (t1 )   ( 1)  1  (tˆ1 )  11 12  (tˆ1 )  12  (tˆ1 )   0, H  H   S / t1   (1) 1 12  H12   0, (6) 11   S / 11 x (t12 )   ( 1)  11 12  (tˆ12 )  11  (tˆ12 )   0, H   S / t12   (1) 12 11   H12  H11   0;  The minimum of the Hamiltonians at the instant of time t   t h , t1  for the equations l u  t    l will have the following form: H 1   min H l  . l u ( t ) (l  1, h  0; l  11, h  12); (7) The minimum of the linear combination of Hamiltonians at the instants of time t   t1 , t12  for equations l u  t    l (l=11, 12) will have the following form: H1112   H12    min H1112  . 11 u ( t ),12 u ( t )  H12  . 11 u ( t ),12 u ( t )  (8) where H l ()   l ()  l  T l f () (l  1, 11, 12) , H1112 ()  12 11  11  11 f (). 12 T 12 Here the sign  means optimality of variables and parameters; symbol  . means that the expression is determined at optimal values of variables and parameters, except  ; parameter β takes the value 1 or 2, respectively: 1 - for a scheme with division; 2 – for a scheme with grouping, Figure 2; Note that for mechanical systems, the condition for a jump along the n-th phase coordinate, which denotes the mass, has the form [5-7] 11  0, 12  0, 11  12  1. The proof of the theorem can be carried out according to the method described in [1] if the SDS is resolved as a system with a variable structure and size of the state vector. According to the stated theorem, considering a complex branched trajectory as a collection of simple ones, we formulate the structure of the algorithm for modeling the optimal movement of the SDS. For the optimality of a branched trajectory of an arbitrary scheme, the existence of a solution of the associated vector equations in the time intervals between the moments tN (start-current of movement), tR (separation), tG (grouping), tK (end of the subsystems movement) M L   H /  x  l L  H /  x  0, q q L (9) where L is the index of the section of the branched trajectory; M, q are, respectively, the number of subsystems, the dynamic properties of which depend on the phase coordinates of the L-th section, and the indices of the sections of the branched trajectory through which these subsystems move. The following conditions apply to such equations: tˆN  ˆ1 tˆK  ˆ2 1) transversality in moments and S /  L x ( i )   ( 1) L  (ˆi )  0 (i  1, 2), i (10)   P S /  i   (1) i H L   H  ,ˆ 0  H   ,ˆ  0  0, (11)  i i  where P is the number of subsystems, the dynamic properties of which change at the moment of the start or end of the movement of the subsystem moving along the L-th section of the trajectory; v is indexes of sections of the branched trajectory through which these subsystems are moved; 2) a jump in moments tˆR  ˆ1 and tˆG  ˆ2 associated with the division of a subsystem moving along the L-th section into r subsystems, or the grouping of r-subsystems into a subsystem that moves along the L-th section of a branched trajectory, R S /  L xi ( i )   (1) L  j (ˆi )  (1)i   q  j (ˆi )  0 , ( j  1, n  1; i  1, 2), i (12) q R S /  L xn ( i )   ( 1) L n (ˆi )  ( 1)i    q q n (ˆi )  0, i (13) q R  q  0,   q  1 (i  1, 2); q   r P S /  i   ( 1) i H L  ( 1)i  H q   H   ,ˆ  0  H   ,ˆ  0  0, (14)   i i q  where q are the indices of the sections of the branched trajectory along which the subsystems move after division or before grouping; Р is the number of subsystems that do not participate in division or grouping, but change dynamic properties at time points tR and tG;   is the indices of sections of the branched trajectory through which the specified subsystems are moved. A phase coordinate L xn (t ) that describes the change in mass. The condition for a jump on the μ-th section of a branched trajectory at the moment of time tˆS , that coincides with the moment of structural transformations in the SDS that do not belong to the μ-th section, but affect it, has the form S /   x(tS )     (tˆS  0)    (tˆS  0)  0; (15) 3) the minimum of the linear combination of Hamiltonians at the moments of time between tˆN , tˆR , tˆG , tˆK L L  Hq = min  Hq q L q uÎWq q L, q u , (16) where  is the number of subsystems that have mutually influencing control in the specified time intervals; q  is the indices of the sections of the branched trajectory along which these subsystems move. The formulated rule is a methodological basis for the synthesis of computational algorithms that allow modeling optimal trajectories of movement of various SDS. The program for modeling optimal branched trajectories can become a part of the mathematical support of the system of automated design of prospective SDS. 3. An example of the structure of the algorithm for modeling the optimal movement of a dynamic system component along a trajectory branch According to the given scheme of the branched trajectory (Figure 1), we will make its time diagram (Figure 3). On this diagram, the moments of time at which structural transformations corresponding to the pattern of movement of the SDS take place are located in a sequential order. In addition, the belonging of these moments to the corresponding moments of time is noted: t N , t R , tG , t K . The crossed-out arrow marks the sections of the trajectory along which the subsystems interact with each other. Figure 3: Time diagram of a branched trajectory The additive optimality criterion is determined by the terminal part S() , and the sum of partial tb integral criteria I i   i ()dt (i  1,15) ; a  b, ( a  1,11 ; b  1,11) , recorded for each section of  ta the trajectory branch (Figure 3). The terminal part depends on the coordinates of the subsystems at the instants of time and these instants of time. Partial integral criteria correspond to areas located between adjacent points of the SDS transformation. The movement of subsystems along the branches of the trajectory is described by the equations x  f () , where f () is a function that depends on the controls and coordinates of the subsystem, as well as on the controls and coordinates of interacting subsystems (at the sections with crossed arrows). According to the rule for trajectory optimality (Figure 3), it is necessary to solve 15 coupled vector equations of type (3) satisfying 39 conditions of type (4)-(9). Vector equations are compiled according to the data in the table.1, and optimality conditions (constraints) are given by tables 2 and 3. Sequences of numbers corresponding to the beginning and end of the branch or its section are used as indices of the branch or its section (Figure 3). Table 1 Minimization condition (3) L M q 1, 2′ 0 — 2′, 3 1 2, 3′ 2′, 3’ 1 2′, 3 3, 4 0 — 3, 6 0 — 3′, 5′ 1 3, 5 3, 5 1 3′, 5′ 5′, 7 0 — 6, 7 0 — 6, 7′ 0 — 7′, 8 1 7, 8′ 7, 8’ 1 7′, 8 8′, 9 0 — 9, 10 0 — 9, 11 0 — Table 2 Minimization condition (9) Interval  q  [t1, t2] 1 1, 2′ [t2, t3] 2 2′, 3; 2, 3′ [t3, t4] 1 3, 4 [t3, t5] 2 3, 5; 3′, 5′ [t3, t6] 1 3, 6 [t5, t7] 1 5′, 7 [t6, t7] 1 6, 7 [t6, t7] 1 6, 7′ [t7, t8] 2 7′, 8; 7, 8′ [t8, t9] 1 8′, 9 [t9, t10] 1 9, 10 [t9, t11] 1 9, 11 To complete the solution of the problem of modeling the optimal branched trajectory, it is necessary to supplement the listed differential equations of motion of the subsystems along the branches of the trajectory with algebraic equations of constraints. The data in Tables 1-3 are the initial information that allows you to proceed to the application of standard subroutines for solving ordinary differential equations under algebraic constraints and thereby practically complete the solution of the problem of modeling the optimal trajectory of the SDS. Note that the sequence of time moments t1  t2  ...  t11 in the problem with free time is given based on physical considerations and is approximate. If, as a result of solving the problem, it is violated (a change in the sequence of trajectory branches is allowed by the physical content of the task), then it is necessary to repeat the calculations for a new, refined sequence of time moments. Table 3 The condition of the transversality of the jump at the moment of time ti Equation t1 t2 t3 t4 t5 (4) L=1, 2′; i=1 L=2, 3′; i=1 — L=3, 4; i=2 L=3, 5; i=2 (5) L=1, 2′; i=1; P=0 L=2, 3′; i=1; — L=3, 4; i=2; L=3, 5; i=2; P=1; v=1, 3 P=0 P=1; v=3′, 7 (6) — — L=2, 3′; i=1; — — r=3; q′=3,6; 3,4; 3, 5 (7) — — L=2′, 3; i=1; — — r=3; q′=3, 6; 3, 5; 3, 4; P′=1; v′=2, 5′ (8) — =1, 3 =2, 5′ — =3′, 7 t6 t7 t8 t9 t10 t11 — — L=7′, 8; i=2 — L=9, 10; i=2 L=9, 11; i=2 — — L=7′, 8; P=1 — L=9, 10; i=2 L=9, 11; i=2 v=7, 9 L=3, 6; i=1; r=2; L=7, 8′; i=2; r=2; — L=8′, 9; i=1; — — q′=6, 7′; 6, 7 q′=6, 7; 5′, 7 r=2; q`=9, 10; 9, 11 L=3, 6; i=1; r=2; L=7, 8′; i=2; r=2; — L=8′, 9; i=1; — — q′=6, 7′; 6, 7 q′=6, 7; 5′, 7; r=2; q′=9, 10; P′=1; v=6, 8 9, 11; P′=0 — =6, 8 =7, 9 — It should be noted that the task of optimizing a branched trajectory with various forms of constraints using known methods [3] can be reduced to the type proposed in this article. 4. Conclusion 1. The structure of the algorithm for modeling the optimal movement of the SDS along branched trajectories is developed. The algorithm allows in real time to optimize the branched trajectories of movement for the realization of the target assignment of the SDS and to perform operative correction of the movement trajectories of sub-systems in the event of occurrence of critical factors of influence unforeseen at the previous stage. 2. The developed sufficient conditions of optimality are universal for planning trajectories with any limited number of trajectory branches and various mathematical models of SDS. This makes it possible to significantly reduce computational costs when calculating optimal control in conditions of uncertainty of the initial conditions for structural transformations of the SDS and stitching of trajectories. 3. The necessary optimality conditions have a clear physical meaning and are technological and convenient for practical use. 4. The results of the research can be considered as a methodological basis for the construction of the laws of trajectory control of existing and prospective SDS. References [1] Lysenko O. I., Tachynina O. M., Ponomarenko S. O. & Guida O. G. (2023) Theory of optimal branched trajectories: monograph. Kyiv: Ihor Sikorsky Kyiv Polytechnic Institute, 2023. 260 p. URL: https://ela.kpi.ua/handle/123456789/52094 [in Ukrainian] [2] Tachinina, O. & Lysenko, O., (2020). Methods for the Synthesis of Optimal Control of Deterministic Compound Dynamical Systems With Branch. У: Handbook of Research on Artificial Intelligence Applications in the Aviation and Aerospace Industries. IGI Global. p. 323–351. URL: doi.org/10.4018/978-1-7998-1415-3.ch014 [3] Tachinina, O., Lysenko, O., Romanchenko, I., Novikov, V. & Sushyn, I., (2023). Using Krotov’s Functions for the Prompt Synthesis Trajectory of Intelligent Info-communication Robot. У: Studies in Systems, Decision and Control. Cham: Springer Nature Switzerland. p. 255–283. URL: doi.org/10.1007/978-3-031-43579-9_6 [4] Impulse differential equations with multi-valued and discontinuous right-hand side: Monograph / N.A. Perestyuk, V.A. Plotnikov, A.M. Samoilenko, N.V. Violinist - K., 2007. - 427 p. [5] Alekseeva, I. V., Lysenko, O. I. & Tachinina, O. M., (2020). Necessary optimality conditions of control of stochastic compound dynamic system in case of full in-formation about state vector. Mathematical machines and systems. 4, 136–147. URL: doi.org/10.34121/1028-9763-2020-4-136- 147 [6] Lysenko, O. I., Tachinina, O. M. & Alekseeva, I. V., (2018). Algorithm of Optimal Control of UAV Group. Electronics and Control Systems. 2(56). URL: doi.org/10.18372/1990- 5548.56.12945 [7] GiuntI, M. & Mazzola, C., (2012). Dynamical Systems on Monoids: Toward a General Theory of Deterministic Systems and Motion: Methods, Models, Simulations And Approaches Towards A General Theory of Change.World Scientific. p. 173-185. URL: doi.org/10.1142/9789814383332_0012