Email this article Optimization of Interception Plan for Rectilinearly Moving Targets
- Authors: Galyaev A.A.1, Yakhno V.P.1, Lysenko P.V.1, Berlin L.M.1, Buzikov M.E.1
-
Affiliations:
- Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
- Issue: No 10 (2023)
- Pages: 18-36
- Section: Articles
- URL: https://journals.rcsi.science/0005-2310/article/view/233414
- DOI: https://doi.org/10.31857/S0005231023100033
- EDN: https://elibrary.ru/YEYLZE
- ID: 233414
Cite item
Open Access
Access granted
Subscription Access
Abstract
The article considers the problem of combinatorial optimization of interception of rectilinearly moving targets as a modification of the traveling salesman problem. New macro characteristics and definitions for this problem are introduced and used to classify the obtained solutions. Vector criteria composed of several important for applications functionals are described. The principles of nowaiting
and maximum velocity are proved for two types of criteria. An intelligent brute-force algorithm with dynamic programming elements for finding optimal plans according to the introduced intercept criteria is proposed and implemented. Statistics of solutions of the developed algorithm is collected for a set of different initial parameters and the proposed macro characteristics are investigated. The conclusions about their applicability as local rules for the greedy algorithm for finding a suboptimal intercept plan are drawn.
About the authors
A. A. Galyaev
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
Email: galaev@ipu.ru
Moscow, Russia
V. P. Yakhno
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
Email: vic_iakhno@mail.ru
Moscow, Russia
P. V. Lysenko
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
Email: pavellysen@ipu.ru
Moscow, Russia
L. M. Berlin
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
Email: berlin.lm@phystech.edu
Moscow, Russia
M. E. Buzikov
Trapeznikov Institute of Control Sciences, Russian Academy of Sciences
Author for correspondence.
Email: me.buzikov@physics.msu.ru
Moscow, Russia
References
- Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. I // А и Т. 1971. No. 8. P. 116-123.
- Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. II // А и Т. 1971. No. 10. P. 142-147.
- Picard J.C., Queyranne M. The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling // Oper. Res. 1978. V. 26. No. 1. P. 86-110. https://doi.org/10.1287/opre.26.1.86
- Helvig C.S., Robins G., Zelikovsky A. The moving-target traveling salesman problem // J. Algorithm.Comput. Technol. 2003. V. 49. No. 1. P. 153-174. https://doi.org/10.1016/S0196-6774(03)00075-0
- Garey M.R., Johnson D.S. Computers and intractability: A guide to the theory of NP-completeness. San Francisco, Calif.: W.H. Freeman & Co., 1979.
- Ny J., Feron E., Frazzoli E. On the Dubins traveling salesman problem // IEEE Trans. Automat. Contr. 2012. V. 57. No. 1. P. 265-270. https://doi.org/10.1109/TAC.2011.2166311
- Isaiah P., Shima T. Motion planning algorithms for the Dubins travelling salesperson problem // Automatica. 2015. V. 53. P. 247-255. https://doi.org/10.1016/j.automatica.2014.12.041
- Stieber A. The multiple traveling salesperson problem with moving targets. Brandenburg University of Technology Cottbus-Senftenberg, 2022.
- Ahrens B. The tour construction framework for the dynamic Travelling Salesman Problem // SoutheastCon, IEEE. 2015. P. 1-8. https://doi.org/10.1109/SECON.2015.7132999
- Choubey N.S. Moving target travelling salesman problem using genetic algorithm // Int. J. Comput. Appl. 2013. V. 70. No. 1. P. 30-34. https://doi.org/10.5120/11937-7726
- Smith C.D. Assessment of genetic algorithm based assignment strategies for unmanned systems using the multiple traveling salesman problem with moving targets // Thesis (M.S.), Department of Civil and Mechanical Engineering. University of Missouri, Kansas City, 2021.
- Buzikov M.E., Galyaev A.A. Minimum-time lateral interception of a moving target by a Dubins car // Automatica. 2022. V. 135. https://doi.org/10.1016/j.automatica.2021.109968
- Galyaev A.A., Lysenko P.V., Rubinovich E.Y. Optimal Stochastic Control in the Interception Problem of a Randomly Tacking Vehicle // Mathematics. 2021. V. 9. No. 19. https://doi.org/10.3390/math9192386
- Galyaev A.A., Dobrovidov A.V., Lysenko P.V., Shaikin M.E. et.al. Path Planning in Threat Environment for UUV with Non-Uniform Radiation Pattern // Sensors. 2020. V. 20. No. 7. https://doi.org/10.3390/s20072076
