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

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

REFERENCES

1.   Chentsov A.G., Chentsov A.A. A discrete-continuous routing problem with precedence constraints. Proc. Steklov Inst. Math., 2018, vol. 300, suppl. 1, pp. 56–71. doi: 10.1134/S0081543818020074

2.   Tormagov T.A., Generalov A.A., Shavin M.Y., Rapoport L.B. Motion control of autonomous wheeled robots in precision agriculture. Gyroscopy and Navigation, 2022, vol. 13, no. 1, pp. 23–35. doi: 10.1134/S2075108722010072

3.   Rogachev G.N., Rogachev N.G. Fuzzy optimization in the problems of forklift path planning. Vestnik Samarskogo Gos. Tekh. Univ., Ser. Tekh. Nauki, 2018, vol. 1 (57), pp. 18–30 (in Russian).

4.   Vagizov M.R., Khabarov S.P. Calculation of the trajectory of motion of the uav, taking into account the requirement of reducing its speed at the end point. Inform. i Kosmos, 2022, no. 1, pp. 122–128 (in Russian).

5.   Markov A.A. A few examples of solving a special kind of problems about the largest and smallest quantities. Soobshcheniya Khar’kov. Mat. Obshchestva, Ser. 2, 1889, vol. 1, no. 2, pp. 250–276 (in Russian).

6.   Isaacs R. Differential games. NY, John Wiley and Sons, 1965, 384 p. ISBN: 978-0471428602. Translated to Russian under the title Differentsial’nye igry, Moscow, Mir publ., 1967.

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, no. 3, p. 497–516. doi: 10.2307/2372560

8.   Berdyshev Yu. I. On the problem of touring of two points by a nonlinear control system of third order. Izvestiya Ural’skogo Gos. Univ. Ser. Mat. i Mekh., 2003, vol. 5 (26), pp. 24-33 (in Russian).

9.   Berdyshev Yu. I. Nelineinye zadachi posledovatel’nogo upravleniya i ikh prilozhenie [Nonlinear sequential control problems and their application]. Yekaterinburg, UrO RAN Publ., 2015, 193 p. ISBN 978-5-8295-0381-9.

10.   Berdyshev Yu. I. On the problem of sequential traversal of a set of smooth manifolds by a nonlinear controlled object. Diff. Equ., 2002, vol. 38, no. 11, pp. 1541–1552. doi: 10.1023/A:1023676619449

11.   Chen Z., Shima T. Shortest Dubins paths through three points. Automatica, 2019, vol. 105, pp. 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, pp. 247–255. doi: 10.1016/j.automatica.2014.12.041

13.   Patsko V.S., Fedotov A.A. Analytic description of a reachable set for the Dubins car. Trudy Inst. Math. Mekh. UrO RAN, 2020, vol. 26, no. 1, pp. 182–197 (in Russian). doi: 10.21538/0134-4889-2020-26-1-182-197

14.   Buzikov M. E., Galyaev A. A. Algorithms for calculating the optimal trajectory of interception of a moving target by a Dubins car. In: Proc. XIV All-Russian Multiconference on Control Problems, Rostov-on-the-Don, South Federal Univ. Publ., 2021, vol. 1, pp. 73–76 (in Russian). ISBN 978-5-9275-3849-2.

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

16.   Buzikov M. E., Galyaev A. A. Time-optimal interception of a moving target by a Dubins car. Autom. Remote Control, 2021, vol. 82, no. 5, pp. 745–758. doi: 10.1134/S0005117921050015

17.   Cockayne E.J., Hal G.W.C. Plane motion of a particle subject to curvature constraints. SIAM J. Control Optim., 1975, vol. 13, no. 1, pp. 197–220. doi: 10.1137/0313012

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.