А.М. Майер, А.А. Галяев. Задача быстродействия обхода нескольких точек машиной Дубинса ... С. 42-61

УДК 517.977.5

MSC: 49XXX

DOI: 10.21538/0134-4889-2023-29-3-42-61

Работа выполнена при частичной поддержке РНФ (проект 23-19-00134).

Полный текст статьи (Full text)

В статье исследуется задача быстродействия последовательного обхода машиной Дубинса трех целевых точек на плоскости. Используется модель машины Дубинса для описания движения объекта в горизонтальной плоскости с постоянной скоростью и ограниченной маневренностью. Рассматривается как фиксированная, так и нефиксированная очередность обхода управляемым объектом целевых точек. Задача является дискретно-непрерывной и содержит три целевых множества. Сложность нахождения решения заключается в невозможности разбить рассматриваемую задачу на ряд двухточечных, так как необходимо учитывать информацию о всех целях для того, чтобы минимизировать время обхода. В исследовании сформулированы необходимые условия оптимальности, с помощью которых разработан алгоритм построения оптимальной траектории в дальней зоне. Получен явный вид оптимального программного управления, решена задача синтеза оптимального управления. Для задачи с фиксированной последовательностью обхода разработан алгоритм построения оптимальной траектории обхода трех и двух целевых точек. Проведено сравнение результатов работы двух алгоритмов. Наиболее интересные результаты моделирования траекторий при различных случаях взаимного расположения целевых точек представлены в статье графически. Для задачи с нефиксированной последовательностью обхода построен алгоритм решения и найдены границы областей, где меняется последовательность обхода точек.

Ключевые слова: машина Дубинса, задача быстродействия, оптимальная траектория, неподвижные цели, алгоритм обхода целей

СПИСОК ЛИТЕРАТУРЫ

1.   Ченцов А.Г., Ченцов А.А. Дискретно-непрерывная задача маршрутизации с условиями предшествования // Тр. Ин-та математики и механики УрО РАН. 2017. Т. 23, № 1. С. 275–292. doi: 10.21538/0134-4889-2017-23-1-275-292

2.   Тормагов Т.А., Генералов А.А., Шавин М.Ю., Рапопорт Л.Б. Задачи управления движением автономных колесных роботов в точном земледелии // Гироскопия и навигация. 2022. Т. 30, № 1 (116). C. 39-60. doi: 10.17285/0869-7035.0083

3.   Рогачев Г.Н., Рогачев Н.Г. Нечеткая оптимизация в задачах планирования перемещений роботизированных складских погрузчиков // Вестн. Самар. гос. техн. ун-та. Сер.: Техн. науки. 2018. № 1 (57). С. 18–30.

4.   Вагизов М.Р., Хабаров С.П. Расчет траектории движения БПЛА с учетом требования снижения его скорости в конечной точке // Информация и Космос. 2022. № 1. С. 122–128.

5.   Марков А.А. Несколько примеров решения особого рода задач о наибольших и наименьших величинах // Сообщ. Харьков. мат. общ. Сер. 2. 1889. Т. 1. № 2. С. 250–276.

6.   Isaacs R. Differential games. NY: John Wiley and Sons, 1965. 384 p.

7.   Dubins L.E. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents // American J. Math. 1957. Vol. 79 (3). P. 497–516. doi: 10.2307/2372560 

8.   Бердышев Ю.И. О задаче обхода нелинейной управляемой системой третьего порядка двух точек // Изв. Урал. гос. ун-та. Сер. 2. 2003. № 26. С. 24–33.

9.   Бердышев Ю.И. Нелинейные задачи последовательного управления и их приложение / УрО РАН. Екатеринбург, 2015. 193 с.

10.   Бердышев Ю.И. Задача последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференц. уравнения. 2002. Т. 38, № 11. С. 1451–1461.

11.   Chen Z., Shima T. Shortest Dubins paths through three points // Automatica. 2019. Vol. 105. P. 368–375. doi:10.1016/j.automatica.2019.04.007

12.   Isaiah P., Shima T. Motion planning algorithms for the Dubins travelling salesperson problem // Automatica. 2015. Vol. 53. P. 247–255. doi:10.1016/j.automatica.2014.12.041

13.   Пацко В.С., Федотов А.А. Аналитическое описание множества достижимости для машины Дубинса // Тр. Ин-та математики и механики УрО РАН. 2020. Т. 26, № 1. С. 182–197. doi: 10.21538/0134-4889-2020-26-1-182-197

14.   Бузиков М.Э., Галяев А.А. Алгоритмы вычисления оптимальной траектории перехвата подвижной цели машиной Дубинса // Материалы 14-й Мультиконференции по проблемам управления (МКПУ-2021, Дивноморское, Геленджик) / Южный федеральный университет. Ростов-на-Дону; Таганрог, 2021. Т. 1. С. 73–76.

15.   Buzikov M.E., Galyaev A.A. Minimum-time lateral interception of a moving target by a dubins car // Automatica. 2022. Vol. 135. doi: 10.1016/j.automatica.2021.109968

16.   Бузиков М.Э., Галяев А.А. Перехват подвижной цели машиной Дубинса за кратчайшее время // Автоматика и телемеханика. 2021. № 5. С. 3–19. doi: 10.31857/S0005231021050019

17.   Cockayne E.J., Hal G.W.C. Plane motion of a particle subject to curvature constraints // SIAM J. Control Optimi. 1975. Vol. 13 (1). P. 197–220. doi:10.1137/0313012

Поступила 18.03.2023

После доработки 2.06.2023

Принята к публикации 12.06.2023

Майер Алина Муратовна
математик
Институт проблем управления им. В.А. Трапезникова РАН
г. Москва
e-mail: atuova.a@mail.ru

Галяев Андрей Алексеевич
чл.-корр. РАН, д-р техн. наук
главный науч. сотрудник
Институт проблем управления им. В.А. Трапезникова РАН
г. Москва
e-mail: galaev@ipu.ru

Ссылка на статью: А.М. Майер, А.А. Галяев. Задача быстродействия обхода нескольких точек машиной Дубинса // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 42-61

English

A.M. Mayer, A.A. Galyaev. The time-optimal control problem of sequential traversal of several points by a Dubins car

A time-optimal control problem of sequential traversal of three target points on the plane by a Dubins car is considered. The Dubins car model is used to describe the motion of an object in a horizontal plane with a constant speed and limited maneuverability. Fixed and unfixed sequences of traversal of target points are considered. The problem is discrete-continuous and contains three target sets. The difficulty of finding a solution lies in the impossibility to divide the problem into a series of tasks with two target points since it is necessary to consider information about all target points to minimize the traversal time. Necessary optimality conditions are formulated and used to develop an algorithm for constructing an optimal trajectory in the far zone. An explicit form of an optimal program control is obtained, and the problem of optimal control synthesis is solved. For a problem with a fixed traversal sequence, an algorithm for constructing an optimal trajectory for visiting three and two target points is developed. The results of the two algorithms are compared. The most interesting results of trajectory modeling for various cases of mutual position of target points are presented graphically. For a problem with an unfixed traversal sequence, a solution algorithm is constructed and the boundaries of the regions where the traversal sequence changes are found.

Keywords: Dubins car, time-optimal control problem, optimal trajectory, fixed targets, target traversal algorithm

Received March 18, 2023

Revised June 2, 2023

Accepted June 12, 2023

Funding Agency: This work was partially supported by the Russian Science Foundation (project no. 23-19-00134).

Alina Muratovna Mayer, Institute of Control Sciences of the Russian Academy of Sciences, Moscow, 117997 Russia, e-mail: atuova.a@mail.ru

Andrey Alexeevich Galyaev, Dr. Eng. Sci., Prof., Corresponding Member RAS, Institute of Control Sciences of the Russian Academy of Sciences, Moscow, 117997 Russia, e-mail: galaev@ipu.ru

Cite this article as: A.M. Mayer, A.A. Galyaev. The time-optimal control problem of sequential traversal of several points by a Dubins car. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 42–61.

[References -> on the "English" button bottom right]