On redistribution of targets between interceptors in moving targets traveling salesman problem
- Авторлар: Galyaev A.A.1, Dolgushin P.D.1
-
Мекемелер:
- V.A. Trapeznikov Institute of Control Sciences of RAS
- Шығарылым: № 110 (2024)
- Беттер: 87-112
- Бөлім: Mathematical control theory
- URL: https://bakhtiniada.ru/1819-2440/article/view/285149
- DOI: https://doi.org/10.25728/ubs.2024.110.4
- ID: 285149
Дәйексөз келтіру
Толық мәтін
Аннотация
The paper considers a moving target traveling salesman problem (MTTSP) with rectilinearly and uniformly moving targets. Parameters of the targets’ law of motion such as initial positions, velocities and motion directions considered to be known. Within the framework of the general formulation, a private subtask is considered -- task on the redistribution of targets between two traveling salesmen (interceptors). Time criterion is used as an optimization criterion. Time criterion here is maximum operating time of two interceptors. Assuming that the optimal plan for bypassing targets for one interceptor is known, the task is to find the optimal plan for each of the two with a given initial target configuration. Thus, the under study problem differs from the general MTTSP in having some additional information. For considered problem two algorithms for redistributing targets are proposed, statistical analysis of both of them is carried out and the results of their work are presented. The first one is more precise but is slower. The second one is faster because of less precision.
Негізгі сөздер
Авторлар туралы
Andrey Galyaev
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: galaev@ipu.ru
Moscow
Pavel Dolgushin
V.A. Trapeznikov Institute of Control Sciences of RAS
Email: dolpad@ipu.ru
Moscow
Әдебиет тізімі
- ГАЛЯЕВ А.А., ЯХНО В.П., ЛЫСЕНКО П.В. и др. Оптими-зация плана перехвата прямолинейно движущихся целей //Автоматика и телемеханика. – 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.
Қосымша файлдар
