Оптимальное распределение дронов в групповом преследовании целей при реализации венгерского алгоритма в системе компьютерной математики

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

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