Оптимизация плана перехвата прямолинейно движущихся целей

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Доступ платный или только для подписчиков

Аннотация

Рассматривается задача комбинаторной оптимизации поиска плана перехвата в простых движениях прямолинейно движущихся целей как модификация динамической задачи коммивояжера. Вводятся новые для такой задачи макрохарактеристики и определения, которые используются для классификации полученных решений. Описаны векторные критерии, составленные из нескольких функционалов, имеющих прикладное значение. Для двух типов критериев доказаны принципы неоптимальности простоя и максимальной скорости. Предложен и реализован интеллектуальный полнопереборный алгоритм с элементами динамического программирования для поиска оптимальных планов по введенным критериям перехвата. Для набора различных начальных обстановок собрана статистика решений разработанного алгоритма, на которой исследованы предложенные макрохарактеристики и сделаны выводы об их применимости в качестве локальных правил для жадного алгоритма поиска субоптимального плана перехвата.

Об авторах

А. А. Галяев

Институт проблем управления им. В.А. Трапезникова РАН

Email: galaev@ipu.ru
Москва)

В. П. Яхно

Институт проблем управления им. В.А. Трапезникова РАН

Email: vic_iakhno@mail.ru
Москва)

П. В. Лысенко

Институт проблем управления им. В.А. Трапезникова РАН

Email: pavellysen@ipu.ru
Москва)

Л. М Берлин

Институт проблем управления им. В.А. Трапезникова РАН

Email: berlin.lm@phystech.edu
Москва)

М. Э Бузиков

Институт проблем управления им. В.А. Трапезникова РАН

Автор, ответственный за переписку.
Email: me.buzikov@physics.msu.ru
Москва)

Список литературы

  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

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

© Российская академия наук, 2023