Quality-guaranteed Dubins Path Planning for USV Based on Mixed-integer Piecewise-linear Programming for Addressing the Extended Minimum-time Intercept Problem

Abstract

During the use of robotics in applications such as antiterrorism or combat, a motion-constrained pursuer vehicle, such as a Dubins unmanned surface vehicle (USV), must get close enough (within a prescribed zero or positive distance) to a moving target as quickly as possible, resulting in the extended minimum-time intercept problem (EMTIP). Existing research has primarily focused on the zero-distance intercept problem, MTIP, establishing the necessary or sufficient conditions for MTIP optimality, and utilizing analytic algorithms, such as root-finding algorithms, to calculate the optimal solutions. However, these approaches depend heavily on the properties of the analytic algorithm, making them inapplicable when problem settings change, such as in the case of a positive effective range or complicated target motions outside uniform rectilinear motion. In this study, an approach employing a high-accuracy and quality-guaranteed mixed-integer piecewise-linear program (QG-PWL) is proposed for the EMTIP. This program can accommodate different effective interception ranges and complicated target motions (variable velocity or complicated trajectories). The high accuracy and quality guarantees of QG-PWL originate from elegant strategies such as piecewise linearization and other developed operation strategies. The approximate error in the intercept path length is proved to be bounded to

h^2/(4\sqrt{2})

\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$h^{2}/(4\sqrt 2)$$\end{document}

, where h is the piecewise length.

Keywords

Minimum-time intercept problem / Dubins vehicle / Mixed-integer piecewise-linear program / Linearization / Approximate error / trigonometric function / USV

References

[1] Bui XN, Boissonnat JD, Soueres P, Laumond JP. Shortest Path Synthesis for Dubins Non-Holonomic Robot. Proceedings of the 1994 Ieee International Conference on Robotics and Automation San Diego CA USA, 199427

[2] Buzikov ME, Galyaev AA. Minimum-Time Lateral Interception of a Moving Target by a Dubins Car. Automatica, 2022, 135: 109968

[3] Chen Z, Shi MT. Shortest Dubins Paths Through Three Points. Automatica, 2019, 105: 368-375

[4] Chen Z, Wang K, Shi H. Elongation of Curvature-Bounded Path. Automatica, 2023, 151: 110936

[5] De Palma D, Parlangeli G. Shortest Path Type Classification for Real-Time Three-Points Dubins Problems. 2022 30th Mediterranean Conference on Control and Automation (Med), Athens, Greece, 2022520-525

[6] Ding Y, Xin B, Chen J. Curvature-Constrained Path Elongation with Expected Length for Dubins Vehicle. Automatica, 2019, 108: 108495

[7] Dubins LE. 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, 79(3): 497-516

[8] Fan J, Zhang X, Zou Y. Hierarchical Path Planner for Unknown Space Exploration Using Reinforcement Learning-Based Intelligent Frontier Selection. Expert Systems with Applications, 2023, 230: 120630

[9] Fu J, Sun G, Liu J, Yao W, Wu L. On Hierarchical Multi-Uav Dubins Traveling Salesman Problem Paths in a Complex Obstacle Environment. IEEE Transactions on Cybernetics, 2023, 54: 1-13

[10] Gerdts M, Rogovs S, Valenti G. A Piecewise Linearization Algorithm for Solving Minlp in Intersection Management, 2021438-445Virtual, Online

[11] Ghassemzadeh A, Xu H, Guedes Soares C. Optimal Path Following Controller Design Based on Linear Quadratic Regulator for Underactuated Ships in Varying Wave and Wind Conditions. Journal of Marine Science and Application, 2024, 23(2): 927-946

[12] Gopalan A, Ratnoo A, Ghose D. Time-Optimal Guidance for Lateral Interception of Moving Targets. Journal of Guidance, Control, and Dynamics, 2016, 39(3): 510-525

[13] Jha B, Chen Z, Shima T. Time-Optimal Dubins Trajectory for Moving Obstacle Avoidance. Automatica, 2022, 146: 110637

[14] LaValle SM. Planning Algorithms, 2006, New York, NY, USA, Cambridge university press

[15] Liu L, Wang X, Yang X, Liu H, Li J, Wang P (2023) Path Planning Techniques for Mobile Robots: Review and Prospect. Expert Systems with Applications: An International Journal 227 (C). https://doi.org/10.1016/j.eswa.2023.120254

[16] Matveev AS, Teimoori H, Savkin AV. A Method for Guidance and Control of an Autonomous Vehicle in Problems of Border Patrolling and Obstacle Avoidance. Automatica, 2011, 47(3): 515-524

[17] Meyer Y, Isaiah P, Shima T. On Dubins Paths to Intercept a Moving Target. Automatica, 2015, 53: 256-563

[18] Moon B, Sachdev S, Yuan J, Scherer S. Time-Optimal Path Planning in a Constant Wind for Uncrewed Aerial Vehicles Using Dubins Set Classification. IEEE Robotics and Automation Letters, 2023, 9(31-8

[19] Niu Y, Yan X, Wang Y, Niu Y. Three-Dimensional Ucav Path Planning Using a Novel Modified Artificial Ecosystem Optimizer. Expert Systems with Applications, 2023, 217: 119499

[20] Ntakolia C, Moustakidis S, Siouras A. Autonomous Path Planning with Obstacle Avoidance for Smart Assistive Systems. Expert Systems with Applications, 2023, 213: 119049

[21] Rathinam S, Manyam SG, Zhang Y. Near-Optimal Path Planning for a Car-Like Robot Visiting a Set of Waypoints with Field of View Constraints. IEEE Robotics and Automation Letters, 2019, 4(2): 391-398

[22] Sadeghi A, Smith SL. On Efficient Computation of Shortest Dubins Paths Through Three Consecutive Points. 2016 Ieee 55th Conference on Decision and Control (Cdc), Las Vegas, NV, USA, 20166010-5

[23] Shima T. Intercept-Angle Guidance. Journal of Guidance, Control, and Dynamics, 2011, 34(2): 484-492

[24] Shkel AM, Lumelsky V. Classification of the Dubins Set. Robotics and Autonomous Systems, 2001, 34(4): 179-202

[25] Sussmann HJ, Tang G. Shortest Paths for the Reeds-Shepp Car: A Worked Out Example of the Use of Geometric Techniques in Nonlinear Optimal Control. Rutgers Center for Systems and Control Technical Report, 1991, 10: 1-71

[26] Xu H, Guedes Soares C. Review of Path-Following Control Systems for Maritime Autonomous Surface Ships. Journal of Marine Science and Application, 2023, 22(2): 153-171

[27] Zheng Y, Chen Z, Shao X, Zhao W. Time-Optimal Guidance for Intercepting Moving Targets by Dubins Vehicles. Automatica, 2021, 128: 109557

RIGHTS & PERMISSIONS

Harbin Engineering University and Springer-Verlag GmbH Germany, part of Springer Nature