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

Обложка

Цитировать

Полный текст

Аннотация

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

Об авторах

А. А. Галяев

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

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

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».