Email this article On the Use of Ellipsoidal Estimation Techniques in the RRT* Suboptimal Pathfinding Algorithm
- Authors: Tochilin P.A1, Parshikov M.V1
-
Affiliations:
- Issue: No 2 (2024)
- Pages: 60-80
- Section: Nonlinear systems
- URL: https://journals.rcsi.science/0005-2310/article/view/256145
- DOI: https://doi.org/10.31857/S0005231024020041
- EDN: https://elibrary.ru/UHSVVV
- ID: 256145
Cite item
Open Access
Access granted
Subscription Access
Abstract
Статья посвящена разработке алгоритма приближенного решения задачи быстродействия для системы обыкновенных дифференциальных уравнений при условии огибания неподвижных препятствий и при выполнении заданных поточечных ограничений на возможные значения управляющих параметров. Основная идея состоит в использовании модификации алгоритма поиска субоптимальных путей при помощи быстрорастущих случайных деревьев (RRT*). Наиболее сложная часть этого алгоритма состоит в поиске оптимальных траекторий для задач перевода системы из одной фиксированной позиции в другую, близкую к ней, без учета фазовых ограничений. Эту подзадачу предлагается решать при помощи методов эллипсоидального исчисления. Такой подход позволяет достаточно эффективно искать субоптимальные траектории как для линейных систем с большой размерностью фазового пространства, так и для систем с нелинейной динамикой. Последовательно разобраны алгоритмы как для линейного, так и для нелинейного случая. Приведены соответствующие примеры вычислений.
About the authors
P. A Tochilin
Email: tochilin@cs.msu.ru
M. V Parshikov
Email: miron232734@gmail.com
References
- Казаков К.А., Семенов В.А. Обзор современных методов планирования движения // Тр. ИСП РАН. 2016. Т. 28. № 4. С. 241–294.
- 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 Transactions on Intelligent Vehicles. 2016. V. 1. No. 1. P. 33–55.
- Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning // Int. J. Robot. Res. 2011. V. 30. No. 7. P. 846–894.
- Арутюнов А.В., Магарил-Ильяев Г.Г., Тихомиров В.М. Принцип максимума Понтрягина. М.: Факториал, 2006.
- Дубовицкий А.Я., Милютин А.А. Задачи на экстремум при наличии ограничений // ЖВМ и МФ. 1965. Т. 5. № 3. С. 395–453.
- Webb D.J., van der Berg J. Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics // Proc. of the IEEE Conf. on Robotics and Automation. 2013. P. 5054–5061.
- 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.
- LaValle S.M., Kuffner J.J. Randomized kinodynamic planning // Int. J. Robot. Res. 2001. V. 20. No. 5. P. 378–400.
- Shkolnik A., Walter M., Tedrake R. Reachability-guided sampling for planning under differential constraints // Proc. of the IEEE Conf. on Robotics and Automation. 2009. P. 2859–2865.
- Kurzhanski A.B., Varaiya P. On ellipsoidal techniques for reachability analysis. Part II: internal approximations, box-valued constraints // Optimization Methods and Software. 2002. V. 17. P. 207–237.
- Kurzhanski A.B., Varaiya P. Reachability analysis for uncertain systems — the ellipsoidal technique // Dynam. Contin. Discrete Impuls. Syst. Ser. B. 2002. V. 9. No. 3. P. 347–367.
- Kurzhanski A.B., Varaiya P. Dynamics and control of trajectory tubes. Theory and computation. Birkha¨user, 2014.
