On the Use of Ellipsoidal Estimation Techniques in the RRT* Suboptimal Pathfinding Algorithm

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Acesso é pago ou somente para assinantes

Resumo

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

Sobre autores

P. Tochilin

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

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

M. Parshikov

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

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

Bibliografia

  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.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
Baixar

Declaração de direitos autorais © The Russian Academy of Sciences, 2024