Distribution of defenders among targets using greedy algorithm based on model of scanning system on plane

The article examines the pressing problem of rapidly distributing a limited contingent of defenders (mobile agents) among a dynamically changing set of targets on a plane. In conditions where the number of objects requiring maintenance or protection is constantly changing (new targets appear or existing ones disappear), and resources are strictly limited, choosing an optimal assignment strategy becomes critical. To address this problem, the author develops a simulation model of a scanning system that monitors the spatial position of targets in real time. The proposed approach is based on the use of a greedy algorithm, which makes a locally optimal decision at each simulation step regarding the assignment of a defender to the highest-priority target. The scientific novelty of this work lies in the seamless integration of this algorithm with a dynamic cost matrix. This matrix is not static, but is recalculated for each iteration, taking into account the current coordinates of targets, their importance, and availability, allowing the system to adapt to changing circumstances. A significant contribution to the development of this topic is the creation of a comprehensive visualization system. Unlike existing analogs, it allows for the simultaneous display of not only the spatial distribution of participants (defenders and targets), but also the current state of the cost matrix, as well as visualization of the decision-making logic for assignment. The practical significance of this research extends far beyond purely defensive tasks. The developed computational method can be effectively applied in civilian sectors, such as logistics (for distributing a limited number of couriers to incoming orders), managing groups of mobile robots (organizing patrols or interactions), and in monitoring and alerting systems where rapid response to incidents is required. Thus, the work represents a ready-made prototype of an intelligent decision support system for a wide range of resource allocation problems in a non-stationary environment.

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).