Отправить статью по E-mail Оптимизация плана перехвата прямолинейно движущихся целей
- Авторы: Галяев А.А.1, Яхно В.П.1, Лысенко П.В.1, Берлин Л.М1, Бузиков М.Э1
-
Учреждения:
- Институт проблем управления им. В.А. Трапезникова РАН
- Выпуск: № 10 (2023)
- Страницы: 18-36
- Раздел: Статьи
- URL: https://journals.rcsi.science/0005-2310/article/view/233414
- DOI: https://doi.org/10.31857/S0005231023100033
- EDN: https://elibrary.ru/YEYLZE
- ID: 233414
Цитировать
Открытый доступ
Доступ предоставлен
Только для подписчиков
Аннотация
Рассматривается задача комбинаторной оптимизации поиска плана перехвата в простых движениях прямолинейно движущихся целей как модификация динамической задачи коммивояжера. Вводятся новые для такой задачи макрохарактеристики и определения, которые используются для классификации полученных решений. Описаны векторные критерии, составленные из нескольких функционалов, имеющих прикладное значение. Для двух типов критериев доказаны принципы неоптимальности простоя и максимальной скорости. Предложен и реализован интеллектуальный полнопереборный алгоритм с элементами динамического программирования для поиска оптимальных планов по введенным критериям перехвата. Для набора различных начальных обстановок собрана статистика решений разработанного алгоритма, на которой исследованы предложенные макрохарактеристики и сделаны выводы об их применимости в качестве локальных правил для жадного алгоритма поиска субоптимального плана перехвата.
Об авторах
А. А. Галяев
Институт проблем управления им. В.А. Трапезникова РАН
Email: galaev@ipu.ru
Москва)
В. П. Яхно
Институт проблем управления им. В.А. Трапезникова РАН
Email: vic_iakhno@mail.ru
Москва)
П. В. Лысенко
Институт проблем управления им. В.А. Трапезникова РАН
Email: pavellysen@ipu.ru
Москва)
Л. М Берлин
Институт проблем управления им. В.А. Трапезникова РАН
Email: berlin.lm@phystech.edu
Москва)
М. Э Бузиков
Институт проблем управления им. В.А. Трапезникова РАН
Автор, ответственный за переписку.
Email: me.buzikov@physics.msu.ru
Москва)
Список литературы
- Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. 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
