Распределение защитников по целям с использованием «жадного» алгоритма на основе модели сканирующей системы на плоскости

В статье рассматривается актуальная задача оперативного распределения ограниченного контингента защитников (мобильных агентов) между динамически изменяющимся множеством целей на плоскости. В условиях, когда количество объектов, требующих обслуживания или защиты, постоянно меняется (появляются новые или исчезают существующие цели), а ресурсы строго лимитированы, критически важным становится выбор оптимальной стратегии назначения. Для решения этой проблемы автором разработана имитационная модель сканирующей системы, которая осуществляет мониторинг пространственного положения целей в реальном времени. Основой предложенного подхода является использование «жадного» алгоритма (greedy algorithm), который на каждом шаге моделирования принимает локально оптимальное решение о назначении защитника на наиболее приоритетную цель. Научная новизна работы заключается в органичной интеграции этого алгоритма с динамической матрицей стоимостей. Данная матрица не является статичной, а пересчитывается для каждой итерации с учетом текущих координат целей, их важности и доступности, что позволяет системе адаптироваться к изменениям обстановки. Существенным вкладом в развитие темы также является создание комплексной визуализационной системы. В отличие от существующих аналогов, она позволяет одновременно отображать не только пространственное распределение участников (защитников и целей), но и текущее состояние матрицы стоимостей, а также визуализировать логику принятия решений по назначению. Практическая значимость проведенного исследования выходит далеко за рамки сугубо оборонительных задач. Разработанный вычислительный метод может быть эффективно применен в гражданских секторах, таких как логистика (для распределения ограниченного парка курьеров по поступающим заказам), управление группами мобильных роботов (организация патрулирования или взаимодействия), а также в системах мониторинга и оповещения, где необходимо оперативно реагировать на инциденты. Таким образом, работа представляет собой готовый прототип интеллектуальной системы поддержки принятия решений для широкого класса задач распределения ресурсов в нестационарной среде.

1. Cormen T. H., Leiserson C. E., Rivest R. L. et al. Introduction to algorithms. 3rd ed. Cambridge, MA : The MIT Press, 2009. 1292 p.

2. Papadimitriou C. H., Steiglitz K. Combinatorial optimization: Algorithms and complexity. Mineola, NY : Dover Publications, 1998. 528 p.

3. Bertsekas D. P. Network optimization: Continuous and discrete models. Belmont, MA : Athena Scientific, 1998. 593 p.

4. Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2, no. 1–2. P. 83–97.

5. Burkard R., Dell’Amico M., Martello S. Assignment problems. Philadelphia, PA : Society for Industrial and Applied Mathematics, 2009. 382 p.

6. Zavlanos M. M., Spesivtsev L., Pappas G. J. A distributed auction algorithm for the assignment problem // Proceedings of the 47th IEEE Conference on Decision and Control, December 9–11, 2008, Cancun, Mexico. Piscataway, NJ : Institute of Electrical and Electronics Engineers, 2008. P. 1212–1217.

7. Choi H. L., Brunet L., How J. P. Consensus-based decentralized auctions for robust task allocation // IEEE Transactions on Robotics. 2009. Vol. 25, no. 4. P. 912–926.

8. Michael N., Zavlanos M. M., Kumar V. et al. Distributed multi-robot task assignment and formation control // Proceedings of the 2008 IEEE International Conference on Robotics and Automation, May 19–23, 2008, Pasadena. New York, NY : Institute of Electrical and Electronics Engineers, 2008. P. 128–133.

9. Enright J. J., Frazzoli E., Pavone M. et al. UAV routing and coordination in stochastic, dynamic environments // Handbook of Unmanned Aerial Vehicles / K. P. Valavanis, G. J. Vachtsevanos, eds. Dordrecht : Springer, 2015. P. 2079–2109. https://doi.org/10.1007/978-90-481-9707-1_28.

10. Beard R. W., McLain T. W., Nelson D. B. et al. Decentralized cooperative aerial surveillance using fixedwing miniature UAVs // Proceedings of the IEEE. 2006. Vol. 94, no. 7. P. 1306–1324.

11. Savla K., Frazzoli E., Bullo F. Traveling salesperson problems for the Dubins vehicle // IEEE Transactions on Automatic Control. 2008. Vol. 53, no. 6. P. 1378–1391.

12. Otte M., Correll N. Any-com multi-robot path-planning with dynamic teams: Multi-robot coordination under communication constraints // Springer Tracts in Advanced Robotics. 2014. Vol. 79. P. 743–757.

13. Khamis A., Hussein A., Elmogy A. Multi-robot task allocation: A review of the state-of-the-art // Cooperative Robots and Sensor Networks / A. Koubâa, J. R. Martínez-de Dios, eds. Cham : Springer, 2015. P. 31–51.

14. Gerkey B. P., Matarić M. J. A formal analysis and taxonomy of task allocation in multi-robot systems // The International Journal of Robotics Research. 2004. Vol. 23, no. 9. P. 939–954.

15. Liu L., Shell D. A. Large-scale multi-robot task allocation via dynamic partitioning and distribution // Autonomous Robots. 2012. Vol. 33, no. 3. P. 291–307.

16. Программа распределения защитников по целям при моделировании радара на плоскости на основе «жадного» алгоритма. URL: https://github.com/dubanovalex67-eng/Modeling/blob/main/Radar_with_Defenders_Greedy.m (дата обращения: 7.02.2026).

17. Программа-функция «жадного» алгоритма. URL: https://github.com/dubanovalex67-eng/Modeling/blob/main/Greedy_Pursuit.m (дата обращения: 7.02.2026).

18. Видео, результат моделирования работы радара на плоскости. URL: https://vimeo.com/1162478327?share=copy&fl=sv&fe=ci (дата обращения: 7.02.2026).

19. Видео, динамическая матрица стоимостей радара. URL: https://vimeo.com/1162481636?share=copy&fl=sv&fe=ci (дата обращения: 7.02.2026).

20. Видео, динамическая матрица стоимостей «защитник – цель». URL: https://vimeo.com/1162480737?share=copy&fl=sv&fe=ci (дата обращения: 7.02.2026).

21. Видео, результат распределения защитников по целям. URL: https://vimeo.com/1162481876?share=copy&fl=sv&fe=ci (дата обращения: 7.02.2026).