Optimization of Interception Plan for Rectilinearly Moving Targets

封面

如何引用文章

全文:

开放存取 开放存取
受限制的访问 ##reader.subscriptionAccessGranted##
受限制的访问 订阅存取

详细

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.

作者简介

A. Galyaev

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: galaev@ipu.ru
Moscow, Russia

V. Yakhno

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: vic_iakhno@mail.ru
Moscow, Russia

P. Lysenko

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: pavellysen@ipu.ru
Moscow, Russia

L. Berlin

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

Email: berlin.lm@phystech.edu
Moscow, Russia

M. Buzikov

Trapeznikov Institute of Control Sciences, Russian Academy of Sciences

编辑信件的主要联系方式.
Email: me.buzikov@physics.msu.ru
Moscow, Russia

参考

  1. Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. I // А и Т. 1971. No. 8. P. 116-123.
  2. Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. II // А и Т. 1971. No. 10. P. 142-147.
  3. 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
  4. 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
  5. 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.
  6. 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
  7. 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
  8. Stieber A. The multiple traveling salesperson problem with moving targets. Brandenburg University of Technology Cottbus-Senftenberg, 2022.
  9. 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
  10. 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
  11. 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.
  12. 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
  13. 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
  14. 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

版权所有 © The Russian Academy of Sciences, 2023

##common.cookie##