УДК 517.977, 519.6, 004.02
MSC: 93B03, 93B40, 93B52, 49M30, 49N05
https://doi.org/10.21538/0134-4889-2025-31-2-fon-03
Работа выполнена при финансовой поддержке Минобрнауки РФ в рамках реализации программы Московского центра фундаментальной и прикладной математики по соглашению № 075-15-2022-284.
В статье рассматривается задача управления линейной системой дифференциальных уравнений при фазовых ограничениях и поточечных ограничениях на управляющие параметры. Такие задачи часто встречаются в приложениях из робототехники, в проблемах управления автономным движением на плоскости или в пространстве. Точное математическое решение в подобных задачах получить, как правило, не удается, а традиционные численные методы могут быть неэффективными из-за медленной скорости работы. В последние годы широкое распространение получили методы приближенного решения задач управления с фазовыми ограничениями при помощи случайных графов. Они показали высокую эффективность в случае с тривиальной динамикой управляемого объекта, когда возможно движение без инерции, по ломаным линиям. При этом задачи с так называемыми кинодинамическими ограничениями (когда динамика описывается нетривиальными дифференциальными уравнениями) до недавнего времени оставались нерешенными. Существенного продвижения в этой области удалось достичь за счет совмещения идей построения случайных графов и методов эллипсоидального оценивания, разработанных ранее академиком А.Б. Куржанским и его учениками. Данная статья продолжает исследования в этой области. Авторами предложена новая модификация ранее разработанных методов, которая позволит увеличить их эффективность, сделать подходящими для решения конкретных прикладных задач. Улучшение характеристик метода удалось достичь за счет выделения переменных, отвечающих за фазовые ограничения, и отдельной обработки таких переменных и оставшейся части вектора состояния.
Ключевые слова: оптимальное управление, фазовые ограничения, случайный граф, эллипсоидальное исчисление, эллипсоидальный синтез, множество достижимости
СПИСОК ЛИТЕРАТУРЫ
1. Казаков К.А., Семенов В.А. Обзор современных методов планирования движения // Труды ИСП РАН. 2016. Т. 28, № 4. С. 241–294. 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. P. 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. P. 846–894. https://doi.org/10.1177/0278364911406761
4. Shkolnik A., Walter M., Tedrake R. Reachability-guided sampling for planning under differential constraints // Proc. 2009 IEEE Int. Conf. on Robotics and Automat. (ICRA). 2009. P. 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 // Proc. 2015 IEEE Int. Conf. on Robotics and Automat. (ICRA). 2015. P. 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 // Proc. 2013 IEEE Conf. on Robotics and Automat. (ICRA). 2013. P. 5054–5061. https://doi.org/10.1109/ICRA.2013.6631299
7. Karaman S., Frazzoli E. Optimal kinodynamic motion planning using incremental sampling-based methods // Proc. of the 49th IEEE Conference on Decision and Control. 2010. P. 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. P. 378–400. https://doi.org/10.1177/02783640122067453
9. Точилин П.А., Паршиков М.В. Об использовании методов эллипсоидального оценивания в алгоритме поиска субоптимальных путей RRT* // Автоматика и телемеханика. 2024 № 2. С. 60–80. https://doi.org/10.31857/S0005231024020041
10. Zheng D., Tsiotras P. Accelerating kinodynamic RRT* through dimensionality reduction // Proc. 2021 IEEE/RSJ Int. Conf. on Intell. Robots and Systems (IROS). 2021. P. 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. P. 207–237. https://doi.org/10.1080/1055678021000012435
12. Kurzhanski A.B., Varaiya P. Dynamics and control of trajectory tubes. Theory and computation. BirkhЈauser, 2014. 445 p. https://doi.org/10.1007/978-3-319-10277-1
13. Филиппов А.Ф. Дифференциальные уравнения с разрывной правой частью. М.: Наука, 1985. 224 с.
Поступила 29.01.2025
После доработки 26.02.2025
Принята к публикации 3.03.2025
Опубликована онлайн 28.03.2025 (Online First 2025)
Точилин Павел Александрович
канд. физ.-мат. наук, доцент
факультет вычислительной математики и кибернетики
МГУ имени М.В. Ломоносова, г. Москва
e-mail: tochilin@cs.msu.ru
Паршиков Мирон Вячеславович
аспирант
факультет вычислительной математики и кибернетики
МГУ имени М.В. Ломоносова, г. Москва
e-mail: miron232734@gmail.com
Ссылка на статью: П.А. Точилин, М.В. Паршиков. О построении субоптимальных траекторий для линейной управляемой системы при фазовых ограничениях по части переменных // Тр. Ин-та математики и механики УрО РАН, 2025. Т. 31, № 2. С. 244–261
P.A. Tochilin, M.V. Parshikov. On the construction of suboptimal trajectories for a linear control system with state constraints on part of variables
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 (Online First 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
Cite this artile 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
