Optimal allocation of drones in group target pursuit implementing the Hungarian algorithm in a computer algebra system
https://doi.org/10.35266/1999-7604-2025-4-4
Abstract
The paper considers the problem of optimal drone assignment for group pursuit of multiple targets. A MATLAB implementation of the Hungarian algorithm, also known as the Munkres assignment algorithm, is presented for addressing the conventional distribution problem in multi-agent systems. The algorithm provides a globally most suitable solution for minimizing the total cost of assignments between pursuers and targets. The developed program supports loading cost matrices from MAT and CSV files, automatic variable detection in MAT files, and interactive file selection via a graphical interface. Input data validation checking the correctness of matrix dimensions and the absence of invalid values, is implemented. An evaluation of the Hungarian algorithm’s efficacy compared to the greedy algorithm is performed using 10×10 cost matrices. The results demonstrate a significant improvement in quality of solution finding when using the Hungarian algorithm, which confirms its advantages for group pursuit problems. The proposed method can be used in control systems for unmanned aerial vehicles, robotic platforms, and other multi-agent systems requiring optimal resource allocation
About the Author
P. A. Boloev
Buryat State University named after D. Banzarov, Ulan-Ude
Russian Federation
Russian Federation
Doctor of Sciences (Engineering), Professor
References
1. Айзекс Р. Дифференциальные игры. М. : Мир, 1967. 480 с.
2. Понтрягин Л. С. Линейная дифференциальная игра убегания // Тр. МИАН СССР. 1971. Т. 112. С. 30–63.
3. Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М. : Наука, 1974. 456 с.
4. Burkard R. M., Dell’Amico M., Martello S. Assignment problems. Philadelphia, USA : SIAM – Society of Industrial and Applied Mathematics. 2009. Vol. 8. 402 p.
5. Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2, no. 1–2. P. 83–97.
6. Kuhn H. W. Variants of the Hungarian method for assignment problems // Naval Research Logistics Quarterly. 1956. Vol. 3, no. 4. P. 253–258.
7. Munkres J. Algorithms for the assignment and transportation problems // Journal of the Society for Industrial and Applied Mathematics. 1957. Vol. 5, no. 1. P. 32–38.
8. Fischetti M. Operation research lessons. N. p. 1995. 236 p.
9. Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows. Theory, algorithms, and applications. Prentice Hall, 1993. 863 p.
10. Cai X. Canonical coin systems for change-making problems // Proceedings of 2009 Ninth International Conference on Hybrid Intelligent Systems, Shenyang, China. 2009. Vol. 1. p. 499–504. https://doi.org/10.1109/HIS.2009.103.
11. Кормен Т., Лейзерсон Ч., Ривест Р. и др. Жадные алгоритмы // Алгоритмы. Построение и анализ / пер. с англ. под ред. И. В. Красикова. 2-е изд. М. : Вильямс, 2005. С. 442–481.
12. Вагин Д. А., Петров Н. Н. Задача преследования жестко скоординированных убегающих // Известия Российской академии наук. Теория и системы управления. 2001. № 5. С. 75–79.
13. Банников А. C. Некоторые нестационарные задачи группового преследования // Известия Института математики и информатики УдГУ. 2013. № 1. С. 3–46.
14. Банников А. С. Нестационарная задача группового преследования // Вестник Удмуртского Университета. 2008. Вып. 2. С. 14–16.
15. Изместьев И. В., Ухоботов В. И. Задача преследования маломаневренных объектов с терминальным множеством в форме кольца // Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры. 2018. Т. 148. С. 25–31.
16. Панкратова Я. Б. Решение кооперативной дифференциальной игры группового преследования // Дискретный анализ и исследование операций. 2010. Т. 17, № 2. С. 57–78.
17. Программа венгерского алгоритма в MATLAB. URL: https://github.com/dubanovalex67-eng/Hungarian_Algorithm_MATLAB/blob/main/run_hungarian_from_file.m (дата обращения: 09.09.2025).
18. Матрица стоимостей. URL: https://github.com/dubanovalex67-eng/Hungarian_Algorithm_MATLAB/blob/main/cost_matrix.mat (дата обращения: 09.09.2025).
Review
For citations:
Boloev P.A. Optimal allocation of drones in group target pursuit implementing the Hungarian algorithm in a computer algebra system. Proceedings in Cybernetics. 2025;24(4):35-40. (In Russ.) https://doi.org/10.35266/1999-7604-2025-4-4
Views:
20
Email this article 