О перераспределении целей между перехватчиками в динамической задаче коммивояжёра
- Авторы: Галяев А.А.1, Долгушин П.Д.1
-
Учреждения:
- ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
- Выпуск: № 110 (2024)
- Страницы: 87-112
- Раздел: Математическая теория управления
- URL: https://bakhtiniada.ru/1819-2440/article/view/285149
- DOI: https://doi.org/10.25728/ubs.2024.110.4
- ID: 285149
Цитировать
Полный текст
Аннотация
Рассматривается динамическая задача коммивояжёра (ДЗК) с прямолинейно и равномерно движущимися целями. Параметры закона движения целей, такие как начальное положение, скорость и направление, считаются заранее известными. В иностранной литературе для подобной задачи употребительно название "moving-target traveling salesman problem" (MTTSP). В рамках общей постановки рассмотрена частная подзадача -- задача о перераспределении целей между двумя коммивояжёрами (перехватчиками). В качестве критерия оптимальности исследуется временной критерий, т.е. наибольшее из времён работ двух перехватчиков. Полагая известным оптимальный план обхода целей для одного перехватчика, ставится задача о поиске оптимального плана для каждого из двух при заданной исходной конфигурации целей. Тем самым исследуемая в работе в рамках MTTSP подзадача отличается от общей постановки наличием дополнительной информации. Для этой постановки предложены два алгоритма перераспределения целей, проведен их статистический анализ и представлены результаты их работы. Первый из алгоритмов более точен, т.е. характеризуется меньшей средней ошибкой, но более длителен в исполнении. Второй алгоритм демонстрирует более быструю работу за счёт уменьшения точности.
Об авторах
Андрей Алексеевич Галяев
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: galaev@ipu.ru
Москва
Павел Дмитриевич Долгушин
ФГБУН Институт проблем управления им. В.А. Трапезникова РАН
Email: dolpad@ipu.ru
Москва
Список литературы
- ГАЛЯЕВ А.А., ЯХНО В.П., ЛЫСЕНКО П.В. и др. Оптими-зация плана перехвата прямолинейно движущихся целей //Автоматика и телемеханика. – 2023. – Т. 10. – С. 18–36.
- СИХАРУЛИДЗЕ Г.Г. Об одном обобщении задачи коммиво-яжёра. I // Автоматика и телемеханика. – 1971. – Т. 8. –С. 116–123.
- BUZIKOV M.E., GALYAEV A.A. Minimum-time lateralinterception of a moving target by a Dubins car // Automatica. –2022. – Vol. 135.
- MENGER K. Das botenproblem // Ergebnisse einesMathematischen Kolloquiums 2. – 1932. – Vol. 39. – P. 11–12.
- 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.
- HELVIG С., ROBINS G., ZELIKOVSKY A. The moving-target traveling salesman problem // Journal of Algorithms. –2003. – Vol. 49. – P. 153–174.
- 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.
- CHOUBEY N.S. Moving target travelling salesman problemusing genetic algorithm // Int. J. Comput. Appl. – 2013. –Vol. 70. – P. 30–34.
- ISAIAH P., SHIMA T. Motion planning algorithms for theDubins travelling salesperson problem // Automatica. – 2015. –Vol. 53. – P. 247–255.
- STIEBER A. The multiple traveling salesperson problem withmoving targets // Cottbus Mathematical Preprints. – 2022.
- AHRENS B. The tour construction framework for the dynamicTravelling Salesman Problem // IEEE SoutheastCon. – 2015. –P. 1–8.
- 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.
- 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.
- 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.
- PATSKO V.S., FEDOTOV A.A. Attainability set at instantfor one-side turning dubins car // IFAC-Papers. – 2018. –Vol. 51(32). – P. 201–206.
- 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.
- 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.
- 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.
- 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.
- PECSVARADI T. Optimal horizontal guidance law for aircraftin the terminal area // IEEE Trans. Automat. – 1972. –Vol. 17(6) – P. 763–772.
- SHKEL A.M., LUMELSKY V. Classification of the Dubinsset // Robot. Auton. Syst. – 2001. – Vol. 34(4) – P. 179–202.
Дополнительные файлы
