ntvНаучно-технический вестник информационных технологий, механики и оптикиScientific and Technical Journal of Information Technologies, Mechanics and Optics2226-14942500-0373Университет ИТМО10.17586/2226-1494-2022-22-1-167-178ntv-292Research ArticleМАТЕМАТИЧЕСКОЕ И КОМПЬЮТЕРНОЕ МОДЕЛИРОВАНИЕMODELING AND SIMULATIONПостроение на базе задачи машины Дубинса опорных траекторий движения объектов с учетом постоянных внешних воздействийConstruction of movement trajectories for objects based on the Dubins car problem, taking into account constant external influenceshttps://orcid.org/0000-0003-1337-0150ХабаровС. П.KhabarovS. P.

Хабаров Сергей Петрович — кандидат технических наук, доцент, доцент

sc 57220744173

Санкт-Петербург, 194021

Sergey P. Khabarov — PhD, Associate Professor, Associate Professor

sc 57220744173

Saint Petersburg, 194021

Serg.Habarov@mail.ruhttps://orcid.org/0000-0001-6501-5789ШилкинаМ. Л.ShilkinaM. L.

Шилкина Мария Львовна — кандидат технических наук, доцент, доцент

sc 57246047100

Санкт-Петербург, 194021

Maria L. Shilkina — PhD, Associate Professor, Associate Professor

sc 57246047100

Saint Petersburg, 194021

mchernobay@inbox.ruСанкт-Петербургский государственный лесотехнический университет им. С.М. КироваРоссияSt. Petersburg State Forest Technical UniversityRussian Federation202217122024221167178Copyright © Хабаров С.П., Шилкина М.Л., 20242024Хабаров С.П., Шилкина М.Л.Khabarov S.P., Shilkina M.L.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://ntv.elpub.ru/jour/article/view/292

Предмет исследования. Рассмотрен основанный на решении задачи машины Дубинса подход к формированию опорных траекторий движения подвижных объектов (судов, беспилотников) из начальной в заданную конечную конфигурацию. Движение происходит за минимальное время с учетом ограниченной управляемости объектов по угловым скоростям и действия на них постоянных по величине и направлению внешних возмущений. Метод. Предложено вместо аналитического исследования прямой и сопряженной систем, вытекающих из принципа максимума Понтрягина, и оставаясь в парадигме задачи машины Дубинса, воспользоваться простым перебором возможных типов траекторий с целью определения среди них наилучшей по быстродействию. Для каждой траектории расчет точек переключения управления на траектории производится на основе минимизации разности расстояния между координатами конечной заданной точки и точки, в которую траектория приходит в зависимости от выбора параметров двух промежуточных точек переключения управления. Основные результаты. Решена задача поиска наилучшей по быстродействию траектории движения объекта из одной точки в другую с использованием подхода Дубинса, причем для обеих точек заданы их координаты и курсовые углы. Все расчеты произведены с учетом искажающих траекторию постоянных по величине и направлению внешних воздействий. Задача поиска кривых Дубинса сводится к поиску параметров двух промежуточных точек, в которых происходит смена управления. Рассмотрены возможные варианты смены управлений с учетом имеющихся ограничений. Вычислены длины траекторий движения и выбрана наилучшая по времени прохождения. Предложенный метод рассматривает нескольких допустимых по ограничениям траекторий, учитывающих влияние внешнего воздействия, из которых перебором выбирается оптимальная. Наличие нескольких допустимых траекторий дает преимущества при выборе траектории в зависимости от окружающей обстановки. Практическая значимость. Вместо решения задачи нелинейной оптимизации принципа максимума Понтрягина использован простой перебор возможных типов траекторий с целью определения среди них наилучшей по быстродействию. Поиск каждой из возможных траекторий выполняется из условия минимизации невязки аналитического решения и краевого условия на конце траектории. При поиске возможных траекторий учтены ограничения на управление, влияние постоянных по величине и направлению внешних воздействий и постоянство значения управления на каждом участке траектории. Выполнение данных ограничений позволяет правильно моделировать движение судна. Физически ограничения на управление (радиус поворота) связаны с тем, что не все значения угла поворота руля реализуемы на практике. Ограничения могут быть связаны не только с величиной радиуса поворота, но и с географическими особенностями конкретной местности: для беспилотных летательных аппаратов — здания и рельеф, а для судов — береговая линия, мели, острова и другие. В связи с этим может оказаться, что найденное оптимальное по быстродействию решение не может быть реализуемым на практике. Тогда предложенный в работе метод предоставляет возможность выбора другой траектории среди менее оптимальных по быстродействию.

The paper considers an approach in terms of optimal speed problem for Dubins cars to the formation of control trajectories of moving objects (airplanes, ships), that have control restrictions, under external influences that are constant in magnitude and direction and constant control values at each part of the trajectory. Instead of solving the Pontryagin maximum principle, it is proposed to use a simple comparison of possible control strategies in order to determine the best among them in terms of speed. For each strategy, the calculation of control switching points on the trajectory is based on minimizing the difference between the specified coordinates of the endpoint and the coordinates of the point at which the trajectory comes, depending on the choice of the parameters of two intermediate control switching points. The problem of finding the best speed trajectory for an object from one point to another is solved using the Dubins approach, and their coordinates and heading angles are given for both points. All calculations were carried out taking into account wind and water disturbances, which are constant in magnitude and direction and distort the trajectory. The problem of finding the Dubins paths is reduced to finding the parameters of two intermediate points at which the control changes. Different possibilities for changing controls are considered, taking into account the existing restrictions. The lengths of the trajectories are calculated and the best travel time is selected. The proposed method considers several trajectories acceptable in terms of constraints, taking into account the external influences, from which the optimal path is selected by comparison. Having multiple feasible strategies is beneficial when choosing a trajectory depending on the environment. Instead of solving the problem of nonlinear optimization of the Pontryagin maximum principle, a simple comparison of possible control strategies is used in order to determine the best among them in terms of speed, each of the possible strategies is sought from the condition of minimizing the residual of the analytical solution and the boundary condition at the end of the trajectory. When searching for possible trajectories, control constraints, the influence of external influences, that are constant in magnitude and direction, and the constancy of the control value at each part of the trajectory are taken into account. And all these factors make it possible to sufficiently and adequately simulate the movement of the ship. Physically, restrictions on control (turning radius) are associated with a limited steering angle. Restrictions can be associated not only with restrictions on the turning radius, but also with geographical features of a specific area: for unmanned aerial vehicles this may be due to the buildings and terrain, and for ships this may be due to the coastline, shoals, islands, etc. In this regard, it may turn out that the solution found optimal in terms of speed cannot be realizable in practice. Then the method proposed in the work has the ability to choose another trajectory among the less optimal in terms of speed.

кривая Дубинсаалгоритмыоптимальное управлениенавигация по путевым точкамбеспилотные летательные аппаратыкратчайший путьоптимизацияDubins pathalgorithmsoptimal controlwaypoint navigationunmanned aerial vehiclesshortest pathoptimizationReferencesКумков С.И., Пацко В.С., Пятко С.Г., Федотов А.А. Построение множества разрешимости в задаче проводки самолета при ветровом возмущении // Труды Института математики и механики УрО РАН. 2005. Т. 11. № 1. С. 149–159.Kumkov S.I., Patcko V.S., Piatko S.G., Fedotov A.A. Construction of the solvability set for guiding an aircraft under wind disturbance. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2005, vol. 11, no. 1, pp. 149–159. (in Russian)Dubins L.E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents // American Journal of Mathematics. 1957. V. 79. N 3. P. 497–516. https://doi.org/10.2307/2372560Dubins L.E. On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents. American Journal of Mathematics, 1957, vol. 79, no. 3, pp. 497–516. https://doi.org/10.2307/2372560Вагизов М.Р., Хабаров С.П. Алгоритм формирования гладких программных траекторий движения БПЛА // Информация и космос. 2021. № 2. С. 122–130.Vagizov M.R., Khabarov S.P. Algorithm for the formation of smooth programmed trajectories of UAV motion. Information and Space, 2021, no. 2, pp. 122–130. (in Russian)Хабаров С.П., Шилкина М.Л. Геометрический подход к решению задачи для машин Дубинса при формировании программных траекторий движения // Научно-технический вестник информационных технологий, механики и оптики. 2021. Т. 21. № 5. С. 653–663. https://doi.org/10.17586/2226-1494-2021-21-5-653-663Khabarov S.P., Shilkina M.L. geometric approach to the solution of the dubins car problem in the formation of program trajectories. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2021, vol. 21, no. 5, pp. 653–663. (in Russian). https://doi.org/10.17586/2226-1494-2021-21-5-653-663Хабаров С.П., Шилкина М.Л. Формирование программных траекторий движения БПЛА с учетом ограничений на их управляемость // Цифровые технологии в лесном секторе: Материалы II Всероссийской научно-технической конференции-вебинара. Санкт-Петербург, 2021. С. 141–143.Khabarov S.P., Shilkina M.L. Building programmed motion trajectories for unmanned aircraft with control restrictions. Proc. of the 2nd All-Russian Scientific and Technical Conference-Webinar “Digital Technologies in the Forestry Sector”. St. Petersburg, 2021, pp. 141–143. (in Russian)Пацко В.С., Федотов А.А. Аналитическое описание множества достижимости для машины Дубинса // Труды Института математики и механики УРО РАН. 2020. Т. 26. № 1. С. 182–197. https://doi.org/10.21538/0134-4889-2020-26-1-182-197Patsko V.S., Fedotov A.A. Analytic description of a reachable set for the Dubins car. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2020, vol. 26, no. 1, pp. 182–197. (in Russian). https://doi.org/10.21538/0134-4889-2020-26-1-182-197Patsko V.S., Fedotov A.A. Three-dimensional reachable set at instant for the Dubins car: Properties of extremal motions // Proc. of the 60th Israel Annual Conference on Aerospace Sciences, (IACAS). 2020. P. 1033–1049.Patsko V.S., Fedotov A.A. Three-dimensional reachable set at instant for the Dubins car: Properties of extremal motions. Proc. 60th Israel Annual Conference on Aerospace Sciences, (IACAS), 2020, pp. 1033– 1049.Patsko V.S., Fedotov A.A. Reachable set for Dubins car and its application to observation problem with incomplete information // Proc. of the 27th Mediterranean Conference on Control and Automation, (MED 2019). 2019 P. 489–494. https://doi.org/10.1109/MED.2019.8798511Patsko V.S., Fedotov A.A. Reachable set for Dubins car and its application to observation problem with incomplete information. Proc. of the 27th Mediterranean Conference on Control and Automation, (MED 2019), 2019, pp. 489–494. https://doi.org/10.1109/MED.2019.8798511Рогачев Г.Н. Использование генетического алгоритма с отсечением по времени в задаче синтеза программного регулятора для машины Дубинса // Вестник Самарского государственного технического университета. Серия: Технические науки. 2011. № 3(31). С. 27–32.Rogachev G.N. Synthesis of the open-loop regulator for dubins’ car by anytime genetic algorithm. Vestnik of Samara State Technical University. Technical Sciences Series, 2011, no. 3(31), pp. 27–32. (in Russian)Buzikov M.E., Galyaev A.A. Time-optimal interception of a moving target by a Dubins car // Automation and Remote Control. 2021. V. 82. N 5. P. 745–758. https://doi.org/10.1134/S0005117921050015Buzikov M.E., Galyaev A.A. Time-optimal interception of a moving target by a Dubins car. Automation and Remote Control, 2021, vol. 82, no. 5, pp. 745–758. https://doi.org/10.1134/S0005117921050015Ветчинкин А.С., Стариченков А.Л. Формирование траектории сближения морских подвижных объектов // Морские интеллектуальные технологии. 2020. № 1-1(47). С. 113–117. https://doi.org/10.37220/MIT.2020.47.1.014Vetchinkin A.S., Starichenkov A.L. Formati on of the trajectory of convergence of marine mobile objects. Marine Intellectual Technologies, 2020, no. 1-1 (47), pp. 113–117. (in Russian). https://doi.org/10.37220/MIT.2020.47.1.014Silverberg L., Xu D. Dubins waypoint navigation of small-class unmanned aerial // Open Journal of Optimization. 2019. V. 8. N 2. P. 59–72. https://doi.org/10.4236/ojop.2019.82006Silverberg L., Xu D. Dubins waypoint navigation of small-class unmanned aerial. Open Journal of Optimization, 2019, vol. 8, no. 2, pp. 59–72. https://doi.org/10.4236/ojop.2019.82006Savla K., Frazzoli E., Bullo F. Traveling salesperson problems for the Dubins vehicle // IEEE Transactions on Automatic Control. 2008. V. 53. N 6. P. 1378–1391. https://doi.org/10.1109/TAC.2008.925814Savla K., Frazzoli E., Bullo F. Traveling salesperson problems for the Dubins vehicle. IEEE Transactions on Automatic Control, 2008, vol. 53, no. 6, pp. 1378–1391. https://doi.org/10.1109/TAC.2008.925814Parlangeli G., Indiveri G. Dubins inspired 2D smooth paths with bounded curvature and curvature // IFAC Proceedings Volumes. 2010 V. 43. N 16. P. 252–257. https://doi.org/10.3182/20100906-3-IT-2019.00045Parlangeli G., Indiveri G. Dubins inspired 2D smooth paths with bounded curvature and curvature. IFAC Proceedings Volumes, 2010, vol. 43, no. 16, pp. 252–257. https://doi.org/10.3182/20100906-3-IT-2019.00045Cai W., Zhang M., Zheng Y.R. Task assignment and path planning for multiple autonomous underwater vehicles using 3D Dubins curves // Sensors. 2017. V. 17. N 7. P. 1607. https://doi.org/10.3390/s17071607Cai W., Zhang M., Zheng Y.R. Task assignment and path planning for multiple autonomous underwater vehicles using 3D Dubins curves. Sensors, 2017, vol. 17, no. 7, pp. 1607. https://doi.org/10.3390/s17071607Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Redundant servicing of a flow of heterogeneous requests critical to the total waiting time During the multi-path passage of a sequence of info-communication nodes // Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2020. V. 12563. P. 100–112. https://doi.org/10.1007/978-3-030-66471-8_9Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S.V. Redundant servicing of a flow of heterogeneous requests critical to the total waiting time During the multi-path passage of a sequence of info-communication nodes. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2020, vol. 12563, pp. 100–112. https://doi.org/10.1007/978-3-030-66471-8_9Bogatyrev S.V., Bogatyrev A.V., Bogatyrev V.A. Priority maintenance with replication of wait-critical requests // Proc. of the 2021 Wave Electronics and its Application in Information and Telecommunication Systems (WECONF). 2021. P. 9470640. https://doi.org/10.1109/WECONF51603.2021.9470640Bogatyrev S.V., Bogatyrev A.V., Bogatyrev V.A. Priority maintenance with replication of wait-critical requests. Proc. of the 2021 Wave Electronics and its Application in Information and Telecommunication Systems (WECONF), 2021, pp. 9470640. https://doi.org/10.1109/WECONF51603.2021.9470640LaValle S.M. Planning Algorithms. Cambridge University Press, 2006. 1023 p. https://doi.org/10.1017/CBO9780511546877LaValle S.M. Planning Algorithms. Cambridge University Press, 2006, 1023 p. https://doi.org/10.1017/CBO9780511546877Вагизов М.Р., Хабаров С.П. Построение программных траекторий движения на базе решения задачи «Машина Дубинса» // Информация и космос. 2021. № 3. С. 116–125.Vagizov M.R., Khabarov S.P. Construction of software trajectories of motion on the basis of the solution of the problem “Dubins machine”. Information and Space, 2021, no. 3, pp. 116–125. (in Russian)

The authors declare that there are no conflicts of interest present.