The article considers the problem of controlling a linear system of differential equations under state constraints and pointwise restrictions on control parameters. Such problems are often found in applications from robotics, in the field of controlling autonomous movement on a plane or in space. As a rule, it is not possible to obtain an exact mathematical solution to such problems, and traditional numerical methods may be ineffective due to their slow speed. In recent years, methods for approximating solutions of control problems with state constraints using random graphs have become widespread. They have shown high efficiency in the case of trivial dynamics of a controlled object when it is possible to move without inertia along broken lines. However, problems with so-called kinodynamic constraints (when dynamics are described by nontrivial differential equations) have remained unsolved until recently. Significant progress in this area has been achieved by combining the ideas of constructing random graphs and ellipsoidal estimation techniques developed earlier by academician A. B. Kurzhanski and his students. This article continues the research in this area. The authors propose a new modification of the previously developed methods, which increases its effectiveness and makes it suitable for solving specific applied problems. The improvement of the method's characteristics was achieved by allocating the variables responsible for state constraints and separately processing such variables and the remaining part of the state vector.
Keywords: optimal control, state constraints, random graph, ellipsoidal calculus, ellipsoidal synthesis, reachability set.
Received January 29, 2025
Revised February 26, 2025
Accepted March 3, 2025
Published online March 28, 2025
Funding Agency: The paper was published with the financial support of the Ministry of Education and Science of the Russian Federation as part of the program of the Moscow Center for Fundamental and Applied Mathematics under the agreement no. 075-15-2022-284.
Pavel Aleksandrovich Tochilin, Cand. Sci. (Phis.-Math), Faculty of Computational Mathematics and Cybernetics of the Lomonosov Moscow State University, Moscow, 119991 Russia, e-mail: tochilin@cs.msu.ru
Miron Vyacheslavovich Parshikov, PhD student, Faculty of Computational Mathematics and Cybernetics of the Lomonosov Moscow State University, Moscow, 119991 Russia, e-mail: miron232734@gmail.com
REFERENCES
1. Kazakov K.A., Semenov V.A. An overview of modern methods for motion planning. Proc. Inst. System Progr. RAS (Proc. of ISP RAS), 2016, vol. 28, no. 4, pp. 241–294 (in Russian).
https://doi.org/10.15514/ISPRAS-2016-28(4)-14
2. Paden B., Cap M., Yong S.Z., Yershov D., Frazzoli E. A survey of motion planning and control techniques for self-driving urban vehicles. IEEE Trans. Intell. Veh., 2016, vol. 1, no. 1, pp. 33–55.
https://doi.org/10.1109/TIV.2016.2578706
3. Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning. The Inter. J. Robot. Res., 2011, vol. 30, no. 7, pp. 846–894. https://doi.org/10.1177/0278364911406761
4. Shkolnik A., Walter M., Tedrake R. Reachability-guided sampling for planning under differential constraints. In: Proc. 2009 IEEE Int. Conf. on Robotics and Automat. (ICRA), 2009, pp. 2859–2865.
https://doi.org/10.1109/ROBOT.2009.5152874
5. Xie C., van der Berg J., Patil S., Abbeel P. Toward asymptotical optimal motion planning for kinodynamic systems using a two-point boundary value problem solver. In: Proc. 2015 IEEE Int. Conf. on Robotics and Automat. (ICRA), 2015, pp. 4187–4194. https://doi.org/10.1109/ICRA.2015.7139776
6. Webb D.J., van der Berg J. Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics. In: Proc. 2013 IEEE Int. Conf. on Robotics and Automat., (ICRA), 2013, pp. 5054–5061. https://doi.org/10.1109/ICRA.2013.6631299
7. Karaman S., Frazzoli E. Optimal kinodynamic motion planning using incremental sampling-based methods. In: Proc. 49th IEEE Conf. on Decision and Control (CDC), 2010, pp. 7681–7687. https://doi.org/10.1109/CDC.2010.5717430
8. LaValle S.M., Kuffner J.J. Randomized kinodynamic planning. Int. J. Robotics Res., 2001, vol. 20, no. 5, pp. 378–400. https://doi.org/10.1177/02783640122067453
9. Tochilin P.A., Parshikov M.V. On the use of ellipsoidal estimation techniques in the RRT* suboptimal pathfinding algorithm. Autom. Rem. Contr., 2024, vol. 85, no. 2, pp. 144–159. https://doi.org/10.31857/S0005117924020042
10. Zheng D., Tsiotras P. Accelerating kinodynamic RRT* through dimensionality reduction. In: Proc. 2021 IEEE/RSJ Int. Conf. on Intell. Robots and Systems (IROS), 2021, pp. 3674–3680. https://doi.org/10.1109/IROS51168.2021.9636754
11. Kurzhanski A.B., Varaiya P. On ellipsoidal techniques for reachability analysis. Part II: internal approximations, box-valued constraints. Optimiz. Methods and Software, 2002, vol. 17, pp. 207–237. https://doi.org/10.1080/1055678021000012435
12. Kurzhanski A., 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
13. Filippov A.F. Differential equations with discontinuous right-hand sides. Springer Dordrecht, 1988, 304 p. https://doi.org/10.1007/978-94-015-7793-9 . Original Russian text published in Filippov A. F. Differentsial’nyye uravneniya s razryvnoy pravoy chast’yu, Moscow, Nauka Publ., 1985, 225 p.
Cite this article as: P.A. Tochilin, M.V. Parshikov. On the construction of suboptimal trajectories for a linear control system with state constraints on part of variables. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2025, vol. 31, no. 2, pp. 244–261
