УДК 519.8
MSC: 49N75, 49L20, 90C29
DOI: 10.21538/0134-4889-2026-32-3-30-43
Рассматривается задача защиты подвижной цели от атаки скоростного перехватчика с помощью ложных целей-защитников. Строится минимальная самосогласованная модель задачи в простых движениях с жадной логикой движения хищника-перехватчика. В рамках данной модели производится точная формулировка задачи планирования защиты с целью максимизации кортежного критерия качества. Предложенная постановка задачи оказывается смежной с широким классом задач, известных как обратная динамическая задача коммивояжера. Для поставленной задачи строится алгоритм субоптимального планирования для построения приемлемых решений за быстрое полиномиальное время. Применяются методы динамического программирования, математической оптимизации (последовательное квадратичное программирование методом наименьших квадратов) и локальные эвристические правила. Построенный алгоритм затем исследуется на конкретных примерах начальных данных и проводится статистический анализ его результативности.
Ключевые слова: динамическое программирование, математическая оптимизация, обратная динамическая задача коммивояжера, исследование операций, математическое моделирование
СПИСОК ЛИТЕРАТУРЫ
1. Бузиков М.Э., Галяев А.А. Перехват подвижной цели машиной Дубинса за кратчайшее время // Автоматика и телемеханика. 2021. № 5. С. 3–19.
2. Галяев А.А., Яхно В.П., Лысенко П.В., Берлин Л.М., Бузиков М.Э. Оптимизация плана перехвата прямолинейно движущихся целей // Автоматика и телемеханика. 2023. № 10. С. 18–36.
3. Галяев А.А., Рябушев Е.А. Поиск субоптимального решения динамической задачи коммивояжера методом Монте-Карло // Автоматика и телемеханика. 2024. № 2. С. 103–119.
4. Buzikov M.E., Galyaev A.A. Minimum-time lateral interception of a moving target by a Dubins car // Automatica. 2022. Vol. 135. Art. no. 109968. https://doi.org/10.1016/j.automatica.2021.109968
5. Buzikov M.E., Mayer A.M. Minimum-time interception of a moving target by a material point in a viscous medium // Automatica. 2024. Vol. 167. Art. no. 111795. https://doi.org/10.1016/j.automatica.2021.109968
6. Buzikov M., Galyaev A. The game of two identical cars: An analytical description of the barrier // J. Optim. Theory Appl. 2023. Vol. 198. P. 998–1018. https://doi.org/10.1007/s10957-023-02278-1
7. Samokhin A., Samokhina M., Grigoriev I., Zapletin M. Base on Phobos–Much safer exploration of Mars without the need for humans on the surface of the planet // Acta Astronautica. 2023. Vol. 204. P. 920-925. https://doi.org/10.1016/j.actaastro.2022.12.028
8. Samokhina M., Samokhin A. About the 10th edition of the global trajectory optimization competition GTOC — Settlers of the Galaxy // AIP Conf. Proc. 2021. Vol. 2318, no. 1. 6 p. https://doi.org/10.1063/5.0035910
9. Samokhin A.S., Samokhina M.A., Galyaev A.A. About the GTOC XII problem // 14th Moscow Solar System Symposium (14M-S3). Moscow: IKI RAS, 2023. P. 284.
10. Chung Y., Demange M. On inverse traveling salesman problems // 4OR-Q J. Oper. Res. 2012. Vol. 10. P. 193–209. https://doi.org/10.1007/s10288-011-0194-4
11. Ivanová M., Surynek P., Hirayama K. Area protection in adversarial path-finding scenarios with multiple mobile agents on graphs a theoretical and experimental study of strategies for defense coordination // Proc. 10th Inter. Conf. Agents and Artificial Intelligence (ICAART 2018). Funchal, Madeira, Portugal, 2018; vol. 2. P. 184–191. https://doi.org/10.5220/0006583601840191
12. Li X., Zhang Sh. Learning-based TSP-solvers tend to be overly greedy. 2025. 19 p. https://doi.org/10.48550/arXiv.2502.00767
13. Biediger D. Pursuit and evasion of drone swarms and turrets: PhD Thesis. 2022. 110 p.
14. Blom M., Krumke S.O., de Paepe W.E., Stougie L. The online-TSP against fair adversaries // Algorithms and Complexity (CIAC 2000). Ser. Lecture Notes in Comput. Sci., vol. 1767. Berlin; Heidelberg: Springer, 2000. P. 137–149. https://doi.org/10.1007/3-540-46521-9_12
15. Субботин А.И., Ченцов А.Г. Оптимизация гарантии в задачах управления. М.: Наука, 1981. 288 с.
16. Krasovskii N.N., Subbotin A.I. Game-theoretical control problems. NY: Springer-Verlag, 1988. 517 p.
17. Joshy A.J., Hwang J. PySLSQP: A transparent Python package for the SLSQP optimization algorithm modernized with utilities for visualization and post-processing. 2024. 9 p. https://doi.org/10.48550/arXiv.2408.13420
Поступила 20.02.2026
После доработки 01.04.2026
Принята к публикации 25.05.2026
Галяев Андрей Алексеевич
д-р тех. наук, чл.-корр. РАН
главный науч. сотрудник
Институт проблем управления им. В.А. Трапезникова РАН
г. Москва
e-mail: galaev@ipu.ru
Рябушев Ефим Алексеевич
младший науч. сотрудник
Институт проблем управления им. В.А. Трапезникова РАН
г. Москва
e-mail: lispandhaskell@gmail.com
Ссылка на статью: А.A. Галяев, Е.А. Рябушев. Локальное динамическое планирование для защиты подвижной цели от атаки скоростного перехватчика с ограниченным обзором // Тр. Ин-та математики и механики УрО РАН. 2026. Т. 32, № 3. С. 30-43
English
A.A. Galyaev, E.A. Ryabushev. Local Dynamic Planning for the defense of a mobile target against an attack of the high-speed hunter with limited vision
The problem of protecting a moving target from an attack by a high-speed interceptor using decoy protectors is considered. A minimal self-consistent model of the problem is constructed, based on simple motions and greedy logic governing the interceptor-predator’s movement. Within this model, an exact formulation of the defense planning problem is given, aiming to maximize a tuple quality criterion. The proposed problem statement is shown to be adjacent to a wide class of problems known as the Inverse Dynamic Traveling Salesman Problem. For the formulated problem, a suboptimal planning algorithm is developed to construct acceptable solutions in fast polynomial time. The constructed algorithm is then examined on specific examples of initial data, and a statistical analysis of its performance is conducted.
Keywords: dynamic programming, mathematical optimization, inverse dynamic traveling salesman problem, operations research, mathematical modeling
Received February 20, 2026
Revised April 01, 2026
Accepted May 25, 2026
Andrey Alexeevich Galyaev, Dr. Eng. Sci., Corresponding Member of RAS, Institute of Control Sciences of the Russian Academy of Sciences, Moscow, 117997 Russia, e-mail: galaev@ipu.ru
Efim Alekseevich Ryabushev, Institute of Control Sciences of the Russian Academy of Sciences, Moscow, 117997 Russia, e-mail: lispandhaskell@gmail.com
Cite this article as: A.A. Galyaev, E.A. Ryabushev. Local Dynamic Planning for the defense of a mobile target against an attack of the high-speed hunter with limited vision. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2026, vol. 32, no. 3, pp. 30–43.
