Geometric approach to the solution of the Dubins car problem in the formation of program trajectories

Khabarov 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). doi: 10.17586/2226-1494-2021-21-5-653-663

The paper considers an approach to the formation of control program trajectories of moving objects (UAVs, ships) as a solution to the optimal problem in terms of Dubins path search. Instead of directly solving the Pontryagin’s maximum principle, it is proposed to use a simple analysis of possible control strategies in order to determine among them the optimal one in terms of time spent on a trajectory. The problem of finding the shortest trajectory of movement of an object from one point to another is solved, and for both points their coordinates and heading angles at these points are given, as well as three absolute values of the circulation radii corresponding to the given control signals on each of the three sections of the trajectory. The problem of finding the Dubins curves is reduced to determining the parameters of two intermediate points at which the control changes. All possible directions of control change options are considered, taking into account the existing constraints, also the lengths of the corresponding motion trajectories are calculated, and the optimal one is selected. The problem of constructing a trajectory is solved as well, which ensures a smooth conjugation of two linear fragments of trajectories and passes through the point of their intersection. The solution of the optimal trajectory problem using the Dubins car gives a single trajectory. In contrast to this, the proposed method considers several trajectories admissible by the constraints, from which the optimal one is selected by exhaustive search. The presence of several feasible strategies gives advantages for each specific situation of choosing a trajectory depending on the environment. Instead of directly solving the Pontryagin’s maximum principle and constructing a three-dimensional optimal trajectory, the authors used a simple analysis of possible control strategies in order to determine among them the optimal one in terms of elapsed time. The approach was motivated by the limited number of possible control strategies for Dubins paths, as well as the simplicity of analytical calculations for each of them, which allows performing these calculations in real time. The high speed of calculations for the problem of determining the optimal trajectory is due to the fact that the proposed method does not require complex calculations to solve the problem of nonlinear optimization, which follows from the Pontryagin’s principle.

1. Parlangeli G., Indiveri G. Dubins inspired 2D smooth paths with bounded curvature and curvature derivative. IFAC Proceedings Volumes, 2010, vol. 43, no. 16, pp. 252–257. https://doi.org/10.3182/20100906-3-IT-2019.00045

2. Jha B., Chen Z., Shima T. Shortest bounded-curvature paths via circumferential envelope of a circle. IFAC-PapersOnLine, 2020, vol. 53, no. 2, pp. 15674–15679. https://doi.org/10.1016/j.ifacol.2020.12.2554

3. Kumar M., Keil E., Rao A.V. Chance-constrained path planning in narrow spaces for a Dubins vehicle. International Robotics & Automation Journal, 2021, vol. 7, no. 2, pp. 46‒61. https://doi.org/10.15406/iratj.2021.07.00277

4. 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)

5. Khabarov S.P., Shilkina M.L. Formation of programmed trajectories for UAV movement, taking into account their controllability. Digital technologies in forestry. Proceedings of the 2nd All-Russian scientific and technical webinar conference. St. Petersburg, Saint Petersburg State Forest Technical University, 2021, pp. 141–143. (in Russian)

6. 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, vol. 79, no. 3, pp. 497–516. https://doi.org/10.2307/2372560

7. Markov A.A. Some examples of the solution of a special kind of problem on greatest and least quantities. Soobshhenija Har'kovskogo matematicheskogo obshhestva. Vtoraja serija, 1889, vol. 1, no. 2, pp. 250-276. (in Russian)

8. Patsko 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-197

9. Patsko V.S., Fedotov A.A. Reachable set for Dubins car and its application to observation problem with incomplete information. Proc. 27th Mediterranean Conference on Control and Automation (MED), 2019, pp. 489-494. https://doi.org/10.1109/MED.2019.8798511

10. Liu Y., Ma J., Ma N., Zhang G. Path planning for underwater glider under control constraint. Advances in Mechanical Engineering, 2017, vol. 9, no. 8, pp. 1–9. https://doi.org/10.1177/1687814017717187

11. Berdyshev Yu.I. On a time-optimal control for the generalized Dubins car. Trudy instituta matematiki i mekhaniki UrO RAN, 2016, vol. 22, no. 1, pp. 26–35. (in Russian)

12. 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.

13. Silverberg L., Xu D. Dubins waypoint navigation of small-class unmanned aerial vehicles. Open Journal of Optimization, 2019, vol. 8, no. 2, pp. 59–72. https://doi.org/10.4236/ojop.2019.82006

14. Meyer Y., Isaiah P., Shima T. On Dubins paths to intercept a moving target. Automatica, 2015, vol. 53, pp. 256–263. https://doi.org/10.1016/j.automatica.2014.12.039

15. Pecsvaradi T. Optimal horizontal guidance law for aircraft in the terminal area. IEEE Transactions on Automatic Control, 1972, vol. 17, no. 6, pp. 763–772. https://doi.org/10.1109/TAC.1972.1100160

16. Bakolas E., Tsiotras P. Optimal synthesis of the asymmetric sinistral/dextral Markov-Dubins problem. Journal of Optimization Theory and Applications, 2011, vol. 150, no. 2, pp. 233–250. https://doi.org/10.1007/s10957-011-9841-3

17. Bogatyrev V.A., Bogatyrev A.V., Bogatyrev S. 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_9

18. Bogatyrev V.A., Bogatyrev S.V., Derkach A.N. Timeliness of the reserved maintenance by duplicated computers of heterogeneous delay-critical stream. CEUR Workshop Proceedings, 2019, vol. 2522, pp. 26–36.

19. LaValle S.M. Planning Algorithms. Cambridge University Press, 2006, 1023 p. https://doi.org/10.1017/CBO9780511546877

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License