Computing the Minimum-Time Interception of a Moving Target
Pages 975 - 995
Abstract
In this study, we propose an algorithmic framework for solving a class of optimal control problems. This class is associated with the minimum-time interception of moving target problems, where a plant with a given state equation must approach a moving target whose trajectory is known a priori. Our framework employs an analytical description of the distance from an arbitrary point to the reachable set of the plant. The proposed algorithm is always convergent and cannot be improved without losing the guarantee of its convergence to the correct solution for arbitrary Lipschitz continuous trajectories of the moving target. In practice, it is difficult to obtain an analytical description of the distance to the reachable set for the sophisticated state equation of the plant. Nevertheless, it was shown that the distance can be obtained for some widely used models, such as the Dubins car, in an explicit form. Finally, we illustrate the generality and effectiveness of the proposed framework for simple motions and the Dubins model.
References
[1]
Abaffy J and Galantai A An always convergent algorithm for global minimization of univariate Lipschitz functions Acta Polytech. 2013 10 7 21-39
[2]
Akulenko LD and Shmatkov AM Synthesis of a control in the problem of the time-optimal transfer of a point mass to a specified position with zero velocity J. Appl. Math. Mech. 1998 62 1 123-131
[3]
Akulenko LD and Shmatkov AM Time-optimal transfer to a sphere at zero terminal velocity Dokl. Math. 2001 64 1 137-140
[4]
Akulenko LD and Shmatkov AM Transfer of a dynamic object onto the surface of an ellipsoid J. Comput. Syst. Sci. Int. 2018 57 1 63-71
[5]
Bakolas E Optimal guidance of the isotropic rocket in the presence of wind J. Optim. Theory Appl. 2014 162 3 954-974
[6]
Bakolas E and Tsiotras P Optimal synthesis of the asymmetric sinistral/dextral Markov–Dubins problem J. Optim. Theory Appl. 2011 150 2 233-250
[7]
Bakolas E and Tsiotras P Optimal synthesis of the Zermelo–Markov–Dubins problem in a constant drift field J. Optim. Theory Appl. 2013 156 2 469-492
[8]
Boissonnat, J.D., Bui, X.N.: Accessibility region for a car that only moves forwards along optimal paths. Tech. Rep. RR-2181, INRIA (1994)
[9]
Boissonnat JD, Cerezo A, and Leblond J Shortest paths of bounded curvature in the plane J. Intell. Robot. Syst. 1994 11 1 5-20
[10]
Bui, X.N., Soueres, P., Boissonnat, J.D., Laumond, J.P.: The shortest path synthesis for non-holonomic robots moving forwards. Tech. Rep. RR-2153, INRIA (1993)
[11]
Buzikov ME and Galyaev AA Time-optimal interception of a moving target by a Dubins car Autom. Remote. Control. 2021 82 5 745-758
[12]
Buzikov ME and Galyaev AA Minimum-time lateral interception of a moving target by a Dubins car Automatica 2022 135
[13]
Cacace S, Lai AC, and Loreti P Modeling and optimal control of an octopus tentacle SIAM J. Control. Optim. 2020 58 1 59-84
[14]
Chernousko FL An optimal algorithm for finding the roots of an approximately computed function USSR Comput. Math. Math. Phys. 1968 8 4 1-23
[15]
Chitsaz, H., LaValle, S.M.: Time-optimal paths for a Dubins airplane. In: Proc IEEE Conf Decis, pp. 2379–2384. IEEE (2007)
[16]
Clements JC Minimum-time turn trajectories to fly-to points Optim. Control Appl. Methods 1990 11 1 39-50
[17]
Coates S, Pachter M, and Murphey R Optimal control of a Dubins car with a capture set and the homicidal chauffeur differential game IFAC-Pap 2017 50 1 5091-5096
[18]
Cockayne EJ and Hall GWC Plane motion of a particle subject to curvature constraints SIAM J. Optim. 1975 13 1 197-220
[19]
Ding Y, Xin B, and Chen J Curvature-constrained path elongation with expected length for Dubins vehicle Automatica 2019 108
[20]
Dubins LE On curves of minimal length with a constraint on average curvature, and with prescribed initial and terminal positions and tangents Am. J. Math. 1957 79 3 497-516
[21]
Fedotov A, Patsko V, and Turova V Topalov AV Reachable sets for simple models of car motion Recent Advances in Mobile Robotics 2011 Houston IntechOpen 147-172
[22]
Galantai A and Abaffy J Always convergent iteration methods for nonlinear equations of Lipschitz functions Numer. Algorithms 2015 69 2 443-453
[23]
Gopalan A, Ratnoo A, and Ghose D Generalized time-optimal impact-angle-constrained interception of moving targets J. Guid. Control. Dyn. 2017 40 8 2115-2120
[24]
Isaacs R Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization 1965 New York Wiley
[25]
Kaya CY Markov–Dubins path via optimal control theory Comput. Optim. Appl. 2017 68 3 719-747
[26]
Lee EB and Markus L Foundations of Optimal Control Theory 1986 Melbourne Kreiger Publishing Co., Inc.
[27]
Lewin J and Olsder GJ The isotropic rocket—a surveillance evasion game Comput. Math. Appl. 1989 18 1 15-34
[28]
Looker, J.R.: Minimum paths to interception of a moving target when constrained by turning radius. Tech. Rep. DSTO-TR-2227. Australian Goverment Department of Defence (2008)
[29]
Manyam GS, Casbeer DW, Von Moll A, and Fuchs Z Shortest Dubins paths to intercept a target moving on a circle J. Guid. Control. Dyn. 2022 45 11 2107-2120
[30]
Manyam, S.G., Casbeer, D.W.: Intercepting a target moving on a racetrack path. In: Int Conf Unmanned Aircr Syst, pp. 799–806. IEEE (2020)
[31]
Markov AA Some examples of the solution of a special kind of problem on greatest and least quantities Soobshch Karkovsk Mat. Obshch. 1889 2–1 5,6 250-276
[32]
McLain T, Beard RW, and Owen M Valavanis KP and Vachtsevanos GJ Implementing Dubins airplane paths on fixed-wing UAVs Handbook of Unmanned Aerial Vehicles 2014 Berlin Springer 1677-1701
[33]
McNeely RL, Iyer RV, and Chandler PR Tour planning for an unmanned air vehicle under wind conditions J. Guid. Control. Dyn. 2007 30 5 1299-1306
[34]
Meyer Y, Isaiah P, and Shima T On Dubins paths to intercept a moving target Automatica 2015 53 256-263
[35]
Mittal K, Song J, Gupta S, and Wettergren TA Rapid path planning for Dubins vehicles under environmental currents Robot Auton. Syst. 2020 134
[36]
Palumbo NF, Blauwkamp RA, and Lloyd JM Modern homing missile guidance theory and techniques Johns Hopkins APL Tech. Dig. 2010 29 1 42-59
[37]
Patsko VS and Fedotov AA Attainability set at instant for one-side turning Dubins car IFAC-Pap. 2018 51 32 201-206
[38]
Patsko, V.S., Fedotov, A.A.: Analytical description of three-dimensional reachable set for Dubins car. In: Proc Israel Annu Conf Aerosp Sci, pp. 1–30 (2022)
[39]
Patsko VS, Pyatko SG, and Fedotov AA Three-dimensional reachability set for a nonlinear control system J. Comput. Syst. Sci. Int. 2003 42 3 320-328
[40]
Pecsvaradi T Optimal horizontal guidance law for aircraft in the terminal area IEEE Trans. Automat. 1972 17 6 763-772
[41]
Reeds J and Shepp L Optimal paths for a car that goes both forwards and backwards Pac. J. Math. 1990 145 2 367-393
[42]
Rubi B, Perez R, and Morcego B A survey of path following control strategies for UAVs focused on quadrotors J. Intell. Robot. Syst. 2020 98 2 241-265
[43]
Shkel AM and Lumelsky V Classification of the Dubins set Robot. Auton. Syst. 2001 34 4 179-202
[44]
Soueres P and Laumond JP Shortest paths synthesis for a car-like robot IEEE Trans. Automat. 1996 41 5 672-688
[45]
Sukharev AG Optimal search for the roots of a function satisfying a Lipschitz condition USSR Comput. Math. Phys. 1976 16 1 17-26
[46]
Sussmann, H.J., Tang, G.: Shortest paths for the Reeds–Shepp car: a worked out example of the use of geometric techniques in nonlinear optimal control. Tech. Rep. SYCON-91-10, Department of Mathematics Rutgers University (1991)
[47]
Techy L and Woolsey CA Minimum-time path planning for unmanned aerial vehicles in steady uniform winds J. Guid. Control. Dyn. 2009 32 6 1736-1746
[48]
Vana, P., Alves Neto, A., Faigl, J., Macharet, D.G.: Minimal 3D Dubins path with bounded curvature and pitch angle. In: IEEE Int Conf Robot Autom, pp. 8497–8503. IEEE (2020)
[49]
Venkatraman, A., Bhat, S.P.: Optimal planar turns under acceleration constraints. In: Proc IEEE Conf Decis Control, pp. 235–240. IEEE (2006)
[50]
Zhang X, Chen J, and Xin B Path planning for unmanned aerial vehicles in surveillance tasks under wind fields J Cent South Univ 2014 21 8 3079-3091
[51]
Zheng Y, Chen Z, Shao X, and Zhao W Time-optimal guidance for intercepting moving targets by Dubins vehicles Automatica 2021 128
[52]
Zheng Y, Chen Z, Shao X, and Zhao W Time-optimal guidance for intercepting moving targets with impact-angle constraints Chin. J. Aeronaut. 2022 35 7 157-167
Index Terms
- Computing the Minimum-Time Interception of a Moving Target
Index terms have been assigned to the content through auto-classification.
Recommendations
Always convergent iteration methods for nonlinear equations of Lipschitz functions
We define a class of always convergent methods for solving nonlinear equations of real Lipschitz functions. These methods generate monotone iterations that either converge to the nearest zero, if exists or leave the interval in a finite number of steps. ...
Adaptive Dynamic Path Planning Algorithm for Interception of a Moving Target
Most of the 3D curve path planning is used to build static path planning. For intercepting of a moving target, the path planning has to be set in a dynamic condition. L+Dumo algorithm which is based on curve is used to intercept a moving target. In the ...
Minimum-time lateral interception of a moving target by a Dubins car
AbstractThis paper presents the problem of lateral interception by a Dubins car of a target that moves along an a priori known trajectory. This trajectory is given by two coordinates of a planar location and one angle of a heading orientation, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
Publisher
Plenum Press
United States
Publication History
Published: 06 July 2024
Accepted: 30 June 2024
Received: 18 October 2022
Author Tags
Author Tags
Qualifiers
- Research-article
Funding Sources
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 07 Jan 2025