ОБ ИСПОЛЬЗОВАНИИ МЕТОДОВ ЭЛЛИПСОИДАЛЬНОГО ОЦЕНИВАНИЯ В АЛГОРИТМЕ ПОИСКА СУБОПТИМАЛЬНЫХ ПУТЕЙ RRT*

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Статья посвящена разработке алгоритма приближенного решения задачи быстродействия для системы обыкновенных дифференциальных уравнений при условии огибания неподвижных препятствий и при выполнении заданных поточечных ограничений на возможные значения управляющих параметров. Основная идея состоит в использовании модификации алгоритма поиска субоптимальных путей при помощи быстрорастущих случайных деревьев (RRT*). Наиболее сложная часть этого алгоритма состоит в поиске оптимальных траекторий для задач перевода системы из одной фиксированной позиции в другую, близкую к ней, без учета фазовых ограничений. Эту подзадачу предлагается решать при помощи методов эллипсоидального исчисления. Такой подход позволяет достаточно эффективно искать субоптимальные траектории как для линейных систем с большой размерностью фазового пространства, так и для систем с нелинейной динамикой. Последовательно разобраны алгоритмы как для линейного, так и для нелинейного случая. Приведены соответствующие примеры вычислений.

Об авторах

П. А ТОЧИЛИН

Московский государственный университет им. М.В. Ломоносова; Институт проблем управления им. В.А. Трапезникова РАН

Email: tochilin@cs.msu.ru
канд. физ.-мат. наук Москва

М. В ПАРШИКОВ

Московский государственный университет им. М.В. Ломоносова

Email: miron232734@gmail.com
канд. физ.-мат. наук

Список литературы

  1. Казаков К.А., Семенов В.А. Обзор современных методов планирования движения // Тр. ИСП РАН. 2016. Т. 28. № 4. С. 241–294.
  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 Transactions on Intelligent Vehicles. 2016. V. 1. No. 1. P. 33–55.
  3. Karaman S., Frazzoli E. Sampling-based algorithms for optimal motion planning // Int. J. Robot. Res. 2011. V. 30. No. 7. P. 846–894.
  4. Арутюнов А.В., Магарил-Ильяев Г.Г., Тихомиров В.М. Принцип максимума Понтрягина. М.: Факториал, 2006.
  5. Дубовицкий А.Я., Милютин А.А. Задачи на экстремум при наличии ограничений // ЖВМ и МФ. 1965. Т. 5. № 3. С. 395–453.
  6. 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.
  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.
  8. LaValle S.M., Kuffner J.J. Randomized kinodynamic planning // Int. J. Robot. Res. 2001. V. 20. No. 5. P. 378–400.
  9. 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.
  10. 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.
  11. 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.
  12. Kurzhanski A.B., Varaiya P. Dynamics and control of trajectory tubes. Theory and computation. Birkha¨user, 2014.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2024