Citation:
Xing Zhou,Kelin Zhu,Shuang Liu,et al.Quality-guaranteed Dubins Path Planning for USV Based on Mixed-integer Piecewise-linear Programming for Addressing the Extended Minimum-time Intercept Problem[J].Journal of Marine Science and Application,2026,(4):216-227.[doi:10.1007/s11804-025-00759-5]
Click and Copy
Quality-guaranteed Dubins Path Planning for USV Based on Mixed-integer Piecewise-linear Programming for Addressing the Extended Minimum-time Intercept Problem
Xing Zhou,Kelin Zhu,Shuang Liu,et al.Quality-guaranteed Dubins Path Planning for USV Based on Mixed-integer Piecewise-linear Programming for Addressing the Extended Minimum-time Intercept Problem[J].Journal of Marine Science and Application,2026,(4):216-227.[doi:10.1007/s11804-025-00759-5]
Info
- Title:
- Quality-guaranteed Dubins Path Planning for USV Based on Mixed-integer Piecewise-linear Programming for Addressing the Extended Minimum-time Intercept Problem
- Author(s):
- Xing Zhou1; Kelin Zhu2; Shuang Liu3; Zhaoqing Li1; Wenxin Zhang1; Kang Du1
- Affilations:
- Keywords:
- Minimum-time intercept problem; Dubins vehicle; Mixed-integer piecewise-linear program; Linearization; Approximate error; trigonometric function; USV
- DOI:
- 10.1007/s11804-025-00759-5
- 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}), where h is the piecewise length.
References:
[1] Bui XN, Boissonnat JD, Soueres P, Laumond JP (1994) Shortest Path Synthesis for Dubins Non-Holonomic Robot. Proceedings of the 1994 Ieee International Conference on Robotics and Automation San Diego CA USA: 2-7. https://doi.org/10.1109/ROBOT.1994.351019
[2] Buzikov ME, Galyaev AA (2022) Minimum-Time Lateral Interception of a Moving Target by a Dubins Car. Automatica 135: 109968. https://doi.org/10.1016/j.automatica.2021.109968
[3] Chen Z, Shi MT (2019) Shortest Dubins Paths Through Three Points. Automatica 105: 368-375. https://doi.org/10.1016/j.automatica.2019.04.007
[4] Chen Z, Wang K, Shi H (2023) Elongation of Curvature-Bounded Path. Automatica 151: 110936. https://doi.org/10.1016/j.automatica.2023.110936
[5] De Palma D, Parlangeli G (2022) Shortest Path Type Classification for Real-Time Three-Points Dubins Problems. 2022 30th Mediterranean Conference on Control and Automation (Med), Athens, Greece, 520-525. https://doi.org/10.1109/MED54222.2022.9837205
[6] Ding Y, Xin B, Chen J (2019) Curvature-Constrained Path Elongation with Expected Length for Dubins Vehicle. Automatica 108: 108495. https://doi.org/10.1016/j.automatica.2019.108495
[7] Dubins LE (1957) On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents. American Journal of Mathematics 79(3): 497-516. https://doi.org/10.2307/2372560
[8] Fan J, Zhang X, Zou Y (2023) Hierarchical Path Planner for Unknown Space Exploration Using Reinforcement Learning-Based Intelligent Frontier Selection. Expert Systems with Applications 230: 120630. https://doi.org/10.1016/j.eswa.2023.120630
[9] Fu J, Sun G, Liu J, Yao W, Wu L (2023) On Hierarchical Multi-Uav Dubins Traveling Salesman Problem Paths in a Complex Obstacle Environment. IEEE Transactions on Cybernetics 54: 1-13. https://doi.org/10.1109/TCYB.2023.3265926
[10] Gerdts M, Rogovs S, Valenti G (2021) A Piecewise Linearization Algorithm for Solving Minlp in Intersection Management. VEHITS, Virtual, Online, 438-445. https://doi.org/10.5220/0010437104380445
[11] Ghassemzadeh A, Xu H, Guedes Soares C (2024) 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 23 (2): 927-946. https://doi.org/10.1007/s11804-024-00540-0
[12] Gopalan A, Ratnoo A, Ghose D (2016) Time-Optimal Guidance for Lateral Interception of Moving Targets. Journal of Guidance, Control, and Dynamics 39(3): 510-525. https://doi.org/10.2514/1.G001527
[13] Jha B, Chen Z, Shima T (2022) Time-Optimal Dubins Trajectory for Moving Obstacle Avoidance. Automatica 146: 110637. https://doi.org/10.1016/j.automatica.2022.110637
[14] LaValle SM (2006) Planning Algorithms. New York, NY, USA: Cambridge university press. https://doi.org/10.1017/CBO9780511546877
[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 (2011) A Method for Guidance and Control of an Autonomous Vehicle in Problems of Border Patrolling and Obstacle Avoidance. Automatica 47(3): 515-524. https://doi.org/10.1016/j.automatica.2011.01.024
[17] Meyer Y, Isaiah P, Shima T (2015) On Dubins Paths to Intercept a Moving Target. Automatica 53: 256-563. https://doi.org/10.1016/j.automatica.2014.12.039
[18] Moon B, Sachdev S, Yuan J, Scherer S (2023) Time-Optimal Path Planning in a Constant Wind for Uncrewed Aerial Vehicles Using Dubins Set Classification. IEEE Robotics and Automation Letters 9(3): 1-8. https://doi.org/10.1109/LRA.2023.3333167
[19] Niu Y, Yan X, Wang Y, Niu Y (2023) Three-Dimensional Ucav Path Planning Using a Novel Modified Artificial Ecosystem Optimizer. Expert Systems with Applications 217: 119499. https://doi.org/10.1016/j.eswa.2022.119499
[20] Ntakolia C, Moustakidis S, Siouras A (2023) Autonomous Path Planning with Obstacle Avoidance for Smart Assistive Systems. Expert Systems with Applications 213: 119049. https://doi.org/10.1016/j.eswa.2022.119049
[21] Rathinam S, Manyam SG, Zhang Y (2019) Near-Optimal Path Planning for a Car-Like Robot Visiting a Set of Waypoints with Field of View Constraints. IEEE Robotics and Automation Letters 4(2): 391-398. https://doi.org/10.1109/LRA.2018.2890433
[22] Sadeghi A, Smith SL (2016) On Efficient Computation of Shortest Dubins Paths Through Three Consecutive Points. 2016 Ieee 55th Conference on Decision and Control (Cdc), Las Vegas, NV, USA, 6010-5. https://doi.org/10.1109/CDC.2016.7799192
[23] Shima T (2011) Intercept-Angle Guidance. Journal of Guidance, Control, and Dynamics 34(2): 484-492. https://doi.org/10.2514/1.51026
[24] Shkel AM, Lumelsky V (2001) Classification of the Dubins Set. Robotics and Autonomous Systems 34(4): 179-202. https://doi.org/10.1016/S0921-8890(00)00127-5
[25] Sussmann HJ, Tang G (1991) 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 10: 1-71
[26] Xu H, Guedes Soares C (2023) Review of Path-Following Control Systems for Maritime Autonomous Surface Ships. Journal of Marine Science and Application 22(2): 153-171. https://doi.org/10.1007/s11804-023-00338-6
[27] Zheng Y, Chen Z, Shao X, Zhao W (2021) Time-Optimal Guidance for Intercepting Moving Targets by Dubins Vehicles. Automatica 128: 109557. https://doi.org/10.1016/j.automatica.2021.109557
Memo
- Memo:
- Received date:2024-9-8;Accepted date:2025-9-4。<br>Foundation item:This work is partly supported by the National Natural Science Foundation of China (Grant No. 62306325)<br>Corresponding author:Xing Zhou,Email:E-mail:zhouxing@nudt.edu.cn
