Путь Дубина
Кратчайший путь с ограниченным радиусом поворота

В геометрии термин «путь Дубинса» обычно относится к кратчайшей кривой, которая соединяет две точки в двумерной евклидовой плоскости (т. е. плоскости xy ) с ограничением на кривизну пути и с предписанными начальными и конечными касательными к пути, а также предположением, что транспортное средство, движущееся по пути, может двигаться только вперед. Если транспортное средство также может двигаться назад, то путь следует кривой Ридса–Шеппа. [1]

Лестер Эли Дубинс (1920–2010) [2] доказал, используя инструменты анализа [3] , что любой такой путь будет состоять из сегментов максимальной кривизны и/или прямых линий. Другими словами, кратчайший путь будет получен путем соединения дуг окружностей максимальной кривизны и прямых линий.

Обсуждение

Дубинс доказал свой результат в 1957 году. В 1974 году Гарольд Х. Джонсон доказал результат Дубинса, применив принцип максимума Понтрягина . [4] В частности, Гарольд Х. Джонсон представил необходимые и достаточные условия для того, чтобы плоская кривая, которая имеет ограниченную кусочно-непрерывную кривизну и заданные начальные и конечные точки и направления, имела минимальную длину. В 1992 году тот же результат был показан снова с использованием принципа максимума Понтрягина. [5] Совсем недавно геометрическое доказательство с точки зрения теории кривых было предоставлено Дж. Айалой, Д. Кирзенблатом и Дж. Хайамом Рубинштейном. [6] Доказательство, характеризующее пути Дубинса в гомотопических классах, было предоставлено Дж. Айалой. [7]

Приложения

Путь Дубинса обычно используется в области робототехники и теории управления как способ планирования путей для колесных роботов, самолетов и подводных аппаратов. Существуют простые геометрические [8] и аналитические методы [9] для вычисления оптимального пути.

Например, в случае колесного робота простая кинематическая модель автомобиля (также известная как автомобиль Дубинса) для систем выглядит следующим образом: где — положение автомобиля, — направление, автомобиль движется с постоянной скоростью , а управление скоростью поворота ограничено. В этом случае максимальная скорость поворота соответствует некоторому минимальному радиусу поворота (и, что эквивалентно, максимальной кривизне). Заданные начальные и конечные касательные соответствуют начальному и конечному направлениям . Путь Дубинса дает кратчайший путь, соединяющий две ориентированные точки, который возможен для модели колесного робота. х ˙ = В потому что ⁡ ( θ ) у ˙ = В грех ⁡ ( θ ) θ ˙ = ты {\displaystyle {\begin{align}{\dot {x}}&=V\cos(\theta )\\{\dot {y}}&=V\sin(\theta )\\{\dot {\theta }}&=u\end{align}}} ( х , у ) {\displaystyle (x,y)} θ {\displaystyle \тета} В {\displaystyle V} ты {\displaystyle u}

Оптимальный тип пути можно описать с помощью аналогии с автомобилями, совершающими «поворот направо (R)», «поворот налево (L)» или едущими «прямо (S)». Оптимальный путь всегда будет по крайней мере одним из шести типов: RSR, RSL, LSR, LSL, RLR, LRL. Например, предположим, что для некоторых заданных начальных и конечных положений и касательных оптимальный путь имеет тип «RSR». Тогда это соответствует дуге поворота направо (R), за которой следует отрезок прямой линии (S), за которым следует еще одна дуга поворота направо (R). Движение по каждому отрезку в этой последовательности на соответствующую длину сформирует кратчайшую кривую, которая соединяет начальную точку A с конечной точкой B с желаемыми касательными в каждой конечной точке и которая не превышает заданной кривизны.

  • Путь RSL Дубинса
    Путь RSL Дубинса
  • Путь RSR Дубинса
    Путь RSR Дубинса
  • Путь LRL Дубинса
    Путь LRL Дубинса

Задача Дубинса об интервале

Задача Дубинса об интервале является ключевым вариантом задачи Дубинса о пути, где интервал направлений указан в начальной и конечной точках. Направление касательной к пути в начальной и конечной точках ограничено, чтобы лежать в пределах указанных интервалов. Можно решить это с помощью геометрического анализа [10] или с помощью принципа минимума Понтрягина [11] .

Ссылки

  1. ^ Ридс, JA; Шепп, LA (1990). «Оптимальные пути для автомобиля, который едет и вперед, и назад». Pacific Journal of Mathematics . 145 (2): 367–393 . doi : 10.2140/pjm.1990.145.367 .
  2. ^ "IN MEMORIAM Lester Eli Dubins Professor of Mathematics and Statistics, Emeritus UC Berkeley 1920–2010". Калифорнийский университет. Архивировано из оригинала 15 сентября 2011 года . Получено 26 мая 2012 года .
  3. ^ Дубинс, Л. Э. (июль 1957 г.). «О кривых минимальной длины с ограничением на среднюю кривизну и с заданными начальными и конечными положениями и касательными». American Journal of Mathematics . 79 (3): 497– 516. doi :10.2307/2372560. JSTOR  2372560.
  4. ^ Джонсон, Гарольд Х. (1974). «Применение принципа максимума к геометрии плоских кривых». Труды Американского математического общества . 44 (2): 432– 435. doi : 10.1090/S0002-9939-1974-0348631-6 . MR  0348631.
  5. ^ Буассона, Ж.-Д .; Сересо, А.; Леблон, К. (май 1992 г.). «Кратчайшие пути ограниченной кривизны на плоскости» (PDF) . Труды Международной конференции IEEE по робототехнике и автоматизации . Том 3. Пискатауэй, Нью-Джерси. С.  2315–2320 . doi :10.1109/ROBOT.1992.220117.
  6. ^ Айяла, Хосе; Кирзенблат, Дэвид; Рубинштейн, Хайам (2018). «Геометрический подход к кратчайшим ограниченным кривизным путям». Communications in Analysis and Geometry . 26 (4): 679– 697. arXiv : 1403.4899 . doi : 10.4310/CAG.2018.v26.n4.a1 .
  7. ^ Айала, Хосе (2015). «Минимизация длины ограниченных кривизненных путей в гомотопических классах». Топология и ее приложения . 193 : 140–151 . arXiv : 1403.4930 . doi : 10.1016/j.topol.2015.06.008 .
  8. ^ Аниси, Дэвид (июль 2003 г.). Оптимальное управление движением наземного транспортного средства (PDF) (Отчет). Шведское исследовательское оборонное агентство. 1650-1942.
  9. ^ Bui, Xuan-Nam; Boissonnat, J.-D .; Soueres, P.; Laumond, J.-P. (май 1994). «Синтез кратчайшего пути для неголономного робота Дубинса». Конференция IEEE по робототехнике и автоматизации . Том 1. Сан-Диего, Калифорния. С.  2–7 . doi :10.1109/ROBOT.1994.351019.
  10. ^ Маньям, Сатьянараяна; Ратинам, Сивакумар (2016). «О тесном ограничении оптимума коммивояжера Дубинса». Журнал динамических систем, измерений и управления . 140 (7): 071013. arXiv : 1506.08752 . doi : 10.1115/1.4039099. S2CID  16191780.
  11. ^ Маньям, Сатьянараяна Г.; Ратинам, Сивакумар; Касбир, Дэвид; Гарсия, Элой (2017). «Жесткое ограничение кратчайших путей Дубина через последовательность точек». Журнал интеллектуальных и робототехнических систем . 88 ( 2–4 ): 495–511 . doi :10.1007/s10846-016-0459-4. S2CID  30943273.
  • Кривые Дубинса, архив 2016-03-22 на Wayback Machine , из книги «Алгоритмы планирования» Стивена М. ЛаВаля
  • Изохроны для автомобиля Дубинса, демонстрация от проекта Wolfram Demonstrations Project
  • Реализация Python Reeds-Shepp с открытым исходным кодом, созданная Built Robotics
Взято с "https://en.wikipedia.org/w/index.php?title=Dubins_path&oldid=1263872554"