procyberВестник кибернетикиProceedings in Cybernetics1999-7604Бюджетное учреждение высшего образования Ханты-Мансийского автономного округа – Югры «Сургутский государственный университет»10.35266/1999-7604-2025-4-4procyber-718Research ArticleТЕХНИЧЕСКИЕ НАУКИEngeneeringОптимальное распределение дронов в групповом преследовании целей при реализации венгерского алгоритма в системе компьютерной математикиOptimal allocation of drones in group target pursuit implementing the Hungarian algorithm in a computer algebra systemhttps://orcid.org/0000-0002-3940-1296БолоевП. А.BoloevP. A.

доктор технических наук, профессор

Doctor of Sciences (Engineering), Professor

https://orcid.org/0000-0002-1855-2562ДубановА. А.DubanovA. A.

кандидат технических наук, доцент

Candidate of Sciences (Engineering), Docent

alandubanov@mail.ruБурятский государственный университет имени Доржи Банзарова, Улан-УдэРоссияBuryat State University named after D. Banzarov, Ulan-UdeRussian Federation2025181220252443540Copyright © Болоев П.А., Дубанов А.А., 20252025Болоев П.А., Дубанов А.А.Boloev P.A., Dubanov A.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.vestcyber.ru/jour/article/view/718

В работе рассматривается задача оптимального назначения дронов для группового преследования множественных целей. Представлена реализация в системе компьютерной математики венгерского алгоритма (алгоритма Манкреса) для решения классической задачи назначения в контексте многоагентных систем. Алгоритм обеспечивает глобально оптимальное решение задачи минимизации общей стоимости назначений между преследователями и целями. Разработанная программа поддерживает загрузку матриц стоимостей из файлов формата MAT и CSV, автоматическое определение переменных в MAT-файлах и интерактивный выбор файлов через графический интерфейс. Реализована функция валидации входных данных с проверкой корректности размерности матриц и отсутствия недопустимых значений. Проведено сравнительное исследование эффективности венгерского алгоритма относительно жадного подхода на примерах матриц стоимостей размером 10×10. Результаты демонстрируют значительное улучшение качества решения при использовании венгерского алгоритма, что подтверждает его преимущества для задач группового преследования. Предложенное решение может быть использовано в системах управления беспилотными летательными аппаратами, роботизированных платформах и других многоагентных системах, требующих оптимального распределения ресурсов

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

венгерский алгоритмзадача назначениягрупповое преследованиедронымногоагентные системыMATLABоптимизацияHungarian algorithmassignment problemgroup pursuitdronesmulti-agent systemsMATLABoptimizationReferencesАйзекс Р. Дифференциальные игры. М. : Мир, 1967. 480 с.Айзекс Р. Дифференциальные игры. М. : Мир, 1967. 480 с.Понтрягин Л. С. Линейная дифференциальная игра убегания // Тр. МИАН СССР. 1971. Т. 112. С. 30–63.Понтрягин Л. С. Линейная дифференциальная игра убегания // Тр. МИАН СССР. 1971. Т. 112. С. 30–63.Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М. : Наука, 1974. 456 с.Красовский Н. Н., Субботин А. И. Позиционные дифференциальные игры. М. : Наука, 1974. 456 с.Burkard R. M., Dell’Amico M., Martello S. Assignment problems. Philadelphia, USA : SIAM – Society of Industrial and Applied Mathematics. 2009. Vol. 8. 402 p.Burkard R. M., Dell’Amico M., Martello S. Assignment problems. Philadelphia, USA : SIAM – Society of Industrial and Applied Mathematics. 2009. Vol. 8. 402 p.Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2, no. 1–2. P. 83–97.Kuhn H. W. The Hungarian method for the assignment problem // Naval Research Logistics Quarterly. 1955. Vol. 2, no. 1–2. P. 83–97.Kuhn H. W. Variants of the Hungarian method for assignment problems // Naval Research Logistics Quarterly. 1956. Vol. 3, no. 4. P. 253–258.Kuhn H. W. Variants of the Hungarian method for assignment problems // Naval Research Logistics Quarterly. 1956. Vol. 3, no. 4. P. 253–258.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.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.Fischetti M. Operation research lessons. N. p. 1995. 236 p.Fischetti M. Operation research lessons. N. p. 1995. 236 p.Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows. Theory, algorithms, and applications. Prentice Hall, 1993. 863 p.Ahuja R. K., Magnanti T. L., Orlin J. B. Network Flows. Theory, algorithms, and applications. Prentice Hall, 1993. 863 p.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.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.Кормен Т., Лейзерсон Ч., Ривест Р. и др. Жадные алгоритмы // Алгоритмы. Построение и анализ / пер. с англ. под ред. И. В. Красикова. 2-е изд. М. : Вильямс, 2005. С. 442–481.Кормен Т., Лейзерсон Ч., Ривест Р. и др. Жадные алгоритмы // Алгоритмы. Построение и анализ / пер. с англ. под ред. И. В. Красикова. 2-е изд. М. : Вильямс, 2005. С. 442–481.Вагин Д. А., Петров Н. Н. Задача преследования жестко скоординированных убегающих // Известия Российской академии наук. Теория и системы управления. 2001. № 5. С. 75–79.Вагин Д. А., Петров Н. Н. Задача преследования жестко скоординированных убегающих // Известия Российской академии наук. Теория и системы управления. 2001. № 5. С. 75–79.Банников А. C. Некоторые нестационарные задачи группового преследования // Известия Института математики и информатики УдГУ. 2013. № 1. С. 3–46.Банников А. C. Некоторые нестационарные задачи группового преследования // Известия Института математики и информатики УдГУ. 2013. № 1. С. 3–46.Банников А. С. Нестационарная задача группового преследования // Вестник Удмуртского Университета. 2008. Вып. 2. С. 14–16.Банников А. С. Нестационарная задача группового преследования // Вестник Удмуртского Университета. 2008. Вып. 2. С. 14–16.Изместьев И. В., Ухоботов В. И. Задача преследования маломаневренных объектов с терминальным множеством в форме кольца // Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры. 2018. Т. 148. С. 25–31.Изместьев И. В., Ухоботов В. И. Задача преследования маломаневренных объектов с терминальным множеством в форме кольца // Итоги науки и техники. Современная математика и ее приложения. Тематические обзоры. 2018. Т. 148. С. 25–31.Панкратова Я. Б. Решение кооперативной дифференциальной игры группового преследования // Дискретный анализ и исследование операций. 2010. Т. 17, № 2. С. 57–78.Панкратова Я. Б. Решение кооперативной дифференциальной игры группового преследования // Дискретный анализ и исследование операций. 2010. Т. 17, № 2. С. 57–78.Программа венгерского алгоритма в MATLAB. URL: https://github.com/dubanovalex67-eng/Hungarian_Algorithm_MATLAB/blob/main/run_hungarian_from_file.m (дата обращения: 09.09.2025).Программа венгерского алгоритма в MATLAB. URL: https://github.com/dubanovalex67-eng/Hungarian_Algorithm_MATLAB/blob/main/run_hungarian_from_file.m (дата обращения: 09.09.2025).Матрица стоимостей. URL: https://github.com/dubanovalex67-eng/Hungarian_Algorithm_MATLAB/blob/main/cost_matrix.mat (дата обращения: 09.09.2025).Матрица стоимостей. URL: https://github.com/dubanovalex67-eng/Hungarian_Algorithm_MATLAB/blob/main/cost_matrix.mat (дата обращения: 09.09.2025).

The authors declare that there are no conflicts of interest present.