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

Обложка

Цитировать

Полный текст

Аннотация

Рассматривается динамическая задача коммивояжёра (ДЗК) с прямолинейно и равномерно движущимися целями. Параметры закона движения целей, такие как начальное положение, скорость и направление, считаются заранее известными. В иностранной литературе для подобной задачи употребительно название "moving-target traveling salesman problem" (MTTSP). В рамках общей постановки рассмотрена частная подзадача -- задача о перераспределении целей между двумя коммивояжёрами (перехватчиками). В качестве критерия оптимальности исследуется временной критерий, т.е. наибольшее из времён работ двух перехватчиков. Полагая известным оптимальный план обхода целей для одного перехватчика, ставится задача о поиске оптимального плана для каждого из двух при заданной исходной конфигурации целей. Тем самым исследуемая в работе в рамках MTTSP подзадача отличается от общей постановки наличием дополнительной информации. Для этой постановки предложены два алгоритма перераспределения целей, проведен их статистический анализ и представлены результаты их работы. Первый из алгоритмов более точен, т.е. характеризуется меньшей средней ошибкой, но более длителен в исполнении. Второй алгоритм демонстрирует более быструю работу за счёт уменьшения точности.

Об авторах

Андрей Алексеевич Галяев

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

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

Павел Дмитриевич Долгушин

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

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

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

  1. ГАЛЯЕВ А.А., ЯХНО В.П., ЛЫСЕНКО П.В. и др. Оптими-зация плана перехвата прямолинейно движущихся целей //Автоматика и телемеханика. – 2023. – Т. 10. – С. 18–36.
  2. СИХАРУЛИДЗЕ Г.Г. Об одном обобщении задачи коммиво-яжёра. I // Автоматика и телемеханика. – 1971. – Т. 8. –С. 116–123.
  3. BUZIKOV M.E., GALYAEV A.A. Minimum-time lateralinterception of a moving target by a Dubins car // Automatica. –2022. – Vol. 135.
  4. MENGER K. Das botenproblem // Ergebnisse einesMathematischen Kolloquiums 2. – 1932. – Vol. 39. – P. 11–12.
  5. LAWLER E.L., LENSTRA J.K., RINNOOY KAN A.H.G.et al. The Traveling Salesman Problem: A Guided Tour ofCombinatorial Optimization // 1985. – P. 1–476.
  6. HELVIG С., ROBINS G., ZELIKOVSKY A. The moving-target traveling salesman problem // Journal of Algorithms. –2003. – Vol. 49. – P. 153–174.
  7. STIEBER A., FUGENSCHUH A. Dealing with time in themultiple traveling salespersons problem with moving targets //Central European Journal of Operations Research. – 2020. –Vol. 30. – P. 991–1017.
  8. CHOUBEY N.S. Moving target travelling salesman problemusing genetic algorithm // Int. J. Comput. Appl. – 2013. –Vol. 70. – P. 30–34.
  9. ISAIAH P., SHIMA T. Motion planning algorithms for theDubins travelling salesperson problem // Automatica. – 2015. –Vol. 53. – P. 247–255.
  10. STIEBER A. The multiple traveling salesperson problem withmoving targets // Cottbus Mathematical Preprints. – 2022.
  11. AHRENS B. The tour construction framework for the dynamicTravelling Salesman Problem // IEEE SoutheastCon. – 2015. –P. 1–8.
  12. SMITH C.D. Assessment of genetic algorithm based assignmentstrategies for unmanned systems using the multiple travelingsalesman problem with moving targets // Thesis (M.S.),Department of Civil and Mechanical Engineering, Universityof Missouri. – 2021.
  13. VANA P., ALVES NETO A., FAIGL J. et al. Minimal 3Ddubins path with bounded curvature and pitch angle // IEEEInt. Conf. Robot. Autom., IEEE. – 2020 – P. 8497–8503.
  14. AKULENKO L.D., SHMATKOV A.M. Transfer of a dynamicobject onto the surface of an ellipsoid // J. Comput. Syst. Sci.Int. – 2018. – Vol. 57(1). – P. 63–71.
  15. PATSKO V.S., FEDOTOV A.A. Attainability set at instantfor one-side turning dubins car // IFAC-Papers. – 2018. –Vol. 51(32). – P. 201–206.
  16. RUBI B., PEREZ R., MORCEGO B. A survey of path followingcontrol strategies for UAVs focused on quadrotors // J. Intell.Robot. Syst. – 2020. – Vol. 98(2). – P. 241–265.
  17. BUZIKOV M.E., GALYAEV A.A. Time-optimal interceptionof a moving target by a dubins car // Automation and RemoteControl. – 2021. – Vol. 82(5). – P. 745–758.
  18. CACASE S., LAI A.C., LORETI P. Modeling and optimalcontrol of an octopus tentacle // SIAM J. Control. Optim. –2020. – Vol. 58(1). – P. 59–84.
  19. MANYAM G.S., CASBEER D.W., VON MOLL A., FUCHS Z.Shortest dubins paths to inter- cept a target moving on a circle //J. Guid. Control. Dyn. – 2022. – Vol. 45(11). – P. 2107–2120.
  20. PECSVARADI T. Optimal horizontal guidance law for aircraftin the terminal area // IEEE Trans. Automat. – 1972. –Vol. 17(6) – P. 763–772.
  21. SHKEL A.M., LUMELSKY V. Classification of the Dubinsset // Robot. Auton. Syst. – 2001. – Vol. 34(4) – P. 179–202.

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

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


Creative Commons License
Эта статья доступна по лицензии Creative Commons Attribution-NonCommercial 4.0 International License.

Согласие на обработку персональных данных

 

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