Proceedings of Petersburg Transport University Proceedings of Petersburg Transport University Известия Петербургского университета путей сообщения 1815-588X 2658-6851 89096 10.20295/1815-588X-2024-03-744-760 Современные технологии - транспорту HIGH TECHNOLOGIES FOR TRANSPORT Современные технологии - транспорту Problems of search and pursuit of unmanned aerial vehicles using the game-theoretic approach Проблемы поиска и преследования беспилотных летательных аппаратов с использованием теоретико-игрового подхода Малафеев Олег Алексеевич Malafeev Oleg Alekseevich o.malafeev@spbu.ru

доктор физико-математических наук;

doctor of physical and mathematical sciences;

 Чжан Кунь Chzhan Kun' z282250684@mail.ru Зайцева Ирина Владимировна Zayceva Irina Vladimirovna i.zaitseva@rshu.ru

кандидат физико-математических наук;

candidate of physical and mathematical sciences;

 Гаранин Антон Владимирович Garanin Anton Vladimirovich garanin@nt-smt.ru Санкт-Петербургский государственный университет Санкт-Петербург Россия St. Petersburg State University Saint-Petersburg Russian Federation Санкт-Петербургский государственный университет Санкт-Петербург Россия St. Petersburg State University Saint-Petersburg Russian Federation Российский государственный гидрометеорологический университет Санкт-Петербург Россия Russian State Hydrometeorological University Saint-Petersburg Russian Federation ООО «Новые технологии» Санкт-Петербург Россия New Technologies LLC Saint-Petersburg Russian Federation 30 09 2024 30 09 2024 21 3 744 760 30 09 2024 https://atjournal.ru/en/nauka/article/89096/view

Цель: оптимизация эффективности стратегий обнаружения и захвата четырехроторных беспилотных летательных аппаратов (квадрокоптеров). Методы: математическое моделирование, аппарат теории игр, венгерский метод решения задачи о назначениях, теория принятия решений, принцип динамического программирования, пакет Maple для решения примеров. Результаты: для выполнения условий решения задачи об оптимальных назначениях необходимо и достаточно, чтобы она была сбалансирована. Данную задачу о назначениях можно сбалансировать, введя необходимое количество фиктивных катеров или убегающих. После этого можно сформулировать и решить двойственную задачу об оптимальных назначениях. Полученную игру можно решить любым методом решения матричных игр. Таким образом можно определить политику преследования и поиска между беспилотными летательными аппаратами. Практическая значимость: все ускользнувшие квадрокоптерные БПЛА могут быть преследованы и успешно перехвачены с использованием разработанных моделей. Приведены примеры исследования математических моделей с помощью программного пакета Maple.

Currently, the application of mathematical modeling theory is widely used in various fields and, among other things, can be used to prevent illegal actions. This study examines scenarios involving a single pursuer tracking a single evader, as well as situations involving multiple pursuers pursuing multiple evaders. The authors formulate this problem as a search and pursuit problem for four-rotor unmanned aerial vehicles (UAVs) or quadcopters. The solution to the problem is based on game theory, as it provides a mathematical framework for modeling and studying strategic interactions involving multiple decision makers. The authors consider a game where the set of strategies of the runner is the set of possible combinations of speeds and directions of his movement, and the set of strategies of the pursuer is the set of all possible permutations of the elements of his speeds. The matrix of the resulting game consists of elements that are the time of capture. A mathematical problem on the optimal assignments of searching and pursuing unmanned aerial vehicles is formulated and solved. Purpose: optimizing the effectiveness of strategies for detecting and capturing four-rotor unmanned aerial vehicles (quadcopters). Methods: methods of mathematical modeling, game theory apparatus, Hungarian method of solving the problem of assignments, decision theory, the principle of dynamic programming, the Maple package for solving examples were used. Results: In order to fulfill the conditions for solving the problem of optimal assignments, it is necessary and sufficient that it is balanced. This assignment problem can be balanced by entering the required number of fictitious boats or escaping boats. After that, it is possible to formulate and solve the dual problem of optimal appointments. The resulting game can be solved by any method of solving matrix games. In this way, it is possible to determine the policy of harassment and search between drones. Practical importance: All escaped quadcopter UAVs can be chased and successfully intercepted using the developed models. Examples of the study of mathematical models using the Maple software package are given.

 теория игр квадрокоптер модель кооперативная теория игр Simulink MPC- моделирование game theory quadcopter model cooperative game theory Simulink MPC modeling

Koopman B. O. Search and screening // Operation evolution group office of the chief of naval operations. Report № 56. Washington, 1946. Koopman B. O. Search and screening // Operation evolution group office of the chief of naval operations. Report № 56. Washington, 1946. Хеллман О. Введение в теорию оптимального поиска / пер. с англ. Е. М. Столяровой. М.: Наука, 1985. 246 с. Hellman O. Vvedenie v teoriyu optimal'nogo poiska / per. s angl. E. M. Stolyarovoy. M.: Nauka, 1985. 246 s. Абчук В. А., Суздаль В. Г. Поиск объектов. М.: Советское радио, 1977. 336 с. Abchuk V. A., Suzdal' V. G. Poisk ob'ektov. M.: Sovetskoe radio, 1977. 336 s. Староверов О. В. Об одной задаче поиска // Теория вероятностей и ее применение. 1963. Т. 8, № 2. С. 196–201. Staroverov O. V. Ob odnoy zadache poiska // Teoriya veroyatnostey i ee primenenie. 1963. T. 8, № 2. S. 196–201. Kelin M. Note a sequential search // Naval research Logistic Quarterly. 1968. Vol. 15, № 3. Kelin M. Note a sequential search // Naval research Logistic Quarterly. 1968. Vol. 15, № 3. Koopman B. O. Theory of search: I. Kinematic bases // Operations Reseach. 1956. Vol. 4, № 3. Koopman B. O. Theory of search: I. Kinematic bases // Operations Reseach. 1956. Vol. 4, № 3. Koopman B. O. Theory of search: III. The optimum distribution of searching efforts // Operations Research. 1957. Vol. 5, № 5. Koopman B. O. Theory of search: III. The optimum distribution of searching efforts // Operations Research. 1957. Vol. 5, № 5. Алферов Г. В., Малафеев О. А., Мальцева А. С. Теоретико-игровые модели поиска подвижного объекта при инспектировании // Проблемы механики и управления: нелинейные динамические системы, 2014. С. 11–19. Alferov G. V., Malafeev O. A., Mal'ceva A. S. Teoretiko-igrovye modeli poiska podvizhnogo ob'ekta pri inspektirovanii // Problemy mehaniki i upravleniya: nelineynye dinamicheskie sistemy, 2014. S. 11–19. Алферов Г. В., Малафеев О. А., Мальцева А. С. Модель проведения антикоррупционных инспекций // Управление социально-экономическим развитием регионов: проблемы и пути их решения: сборник научных статей 4‑й Международной научно-практической конференции / Юго-Зап. гос. ун-т. Курск, 2014. С. 20–24. Alferov G. V., Malafeev O. A., Mal'ceva A. S. Model' provedeniya antikorrupcionnyh inspekciy // Upravlenie social'no-ekonomicheskim razvitiem regionov: problemy i puti ih resheniya: sbornik nauchnyh statey 4‑y Mezhdunarodnoy nauchno-prakticheskoy konferencii / Yugo-Zap. gos. un-t. Kursk, 2014. S. 20–24. Malafeyev O., Kun Zhang. Problems of search and pursuit of unmanned aerial vehicles using the game-theoretic approach. Arxiv: 2305.19832. Malafeyev O., Kun Zhang. Problems of search and pursuit of unmanned aerial vehicles using the game-theoretic approach. Arxiv: 2305.19832. Лапшин В. П. Кинематические основы тео- рии поиска // Морской сборник. 1962. № 8. Lapshin V. P. Kinematicheskie osnovy teo- rii poiska // Morskoy sbornik. 1962. № 8. Charnes A., Cooper W. Theory of search: optimal distribution of search effort // Managemen Science. 1958. Vol. 5, № 1. Charnes A., Cooper W. Theory of search: optimal distribution of search effort // Managemen Science. 1958. Vol. 5, № 1. MacQueen J., Miller R. G. Optimal persistence polices // Operations Research. 1960. Vol. 8, № 3. MacQueen J., Miller R. G. Optimal persistence polices // Operations Research. 1960. Vol. 8, № 3. Posner E. C. Optimal search procedures // IEEE Transactions of Information Theory. 1963. Vol. 9, № 3. Posner E. C. Optimal search procedures // IEEE Transactions of Information Theory. 1963. Vol. 9, № 3. Дубровин К. О., Сиротин П. А. Время пребывания цели в районе поиска // Морской сборник, 1965. № 6. Dubrovin K. O., Sirotin P. A. Vremya prebyvaniya celi v rayone poiska // Morskoy sbornik, 1965. № 6. Морз Ф. М., Кимбелл Д. Е. Методы исследования операций / пер. с англ. И. А. Полетаева и К. Н. Трофимова, под ред. А. Ф. Горохова. М.: Советское радио, 1956. 308 с. Morz F. M., Kimbell D. E. Metody issledovaniya operaciy / per. s angl. I. A. Poletaeva i K. N. Trofimova, pod red. A. F. Gorohova. M.: Sovetskoe radio, 1956. 308 s. Брэм Дж. А. Игра с поиском N-области для 2 игроков // Отчет OIRM 31, 1963. Brem Dzh. A. Igra s poiskom N-oblasti dlya 2 igrokov // Otchet OIRM 31, 1963. Нейтс М. Ф. Многоэтапная поисковая игра // Журнал СИАМ. 1963. Т. 11, № 2. Neyts M. F. Mnogoetapnaya poiskovaya igra // Zhurnal SIAM. 1963. T. 11, № 2. Джонсон С. М. Поисковая игра // Достижения в теории игр. Издательство Принстонского университета, 1964. Dzhonson S. M. Poiskovaya igra // Dostizheniya v teorii igr. Izdatel'stvo Prinstonskogo universiteta, 1964. Danskin J. M. A theory of reconnaissance // Operations Research. 1963. Vol. 10, № 3. Danskin J. M. A theory of reconnaissance // Operations Research. 1963. Vol. 10, № 3. Айзекс Р. Дифференциальные игры / пер. с англ. В. И. Аркина, Э. Н. Симаковой; под ред. М. И. Зеликина. М.: Мир. 1967. 479 с. Ayzeks R. Differencial'nye igry / per. s angl. V. I. Arkina, E. N. Simakovoy; pod red. M. I. Zelikina. M.: Mir. 1967. 479 s. Зеликин М. И. Об одной дифференциальной игре с неполной информацией // ДАН СССР. Серия «Математика, физика». 1972. Т. 202, № 5. Zelikin M. I. Ob odnoy differencial'noy igre s nepolnoy informaciey // DAN SSSR. Seriya «Matematika, fizika». 1972. T. 202, № 5. Альперн С. Поисковая игра с подвижным укрытием на круге // Дифференциальные игры и теория управления. Нью-Йорк: Марсель Деккер, 1974. Al'pern S. Poiskovaya igra s podvizhnym ukrytiem na kruge // Differencial'nye igry i teoriya upravleniya. N'yu-York: Marsel' Dekker, 1974. Форман Дж. К. Принцесса и чудовище на круге // Дифференциальные игры и теория управления. Нью-Йорк: Марсель Деккер, 1974. Forman Dzh. K. Princessa i chudovische na kruge // Differencial'nye igry i teoriya upravleniya. N'yu-York: Marsel' Dekker, 1974. Форман Ю. Г. Дифференциальные поисковые игры с мобильным хидером // Журнал СИАМ по управлению и оптимизации. 1977. Т. 15, № 5. Forman Yu. G. Differencial'nye poiskovye igry s mobil'nym hiderom // Zhurnal SIAM po upravleniyu i optimizacii. 1977. T. 15, № 5. Хальперн Б. Робот и задача преследования кролика // The American Math. 1969. Т. 76, № 2. Hal'pern B. Robot i zadacha presledovaniya krolika // The American Math. 1969. T. 76, № 2. Гал С. Поисковые игры с подвижным и неподвижным хадером // Журнал СИАМ по управлению и оптимизации. 1979. Т. 17, № 1. Gal S. Poiskovye igry s podvizhnym i nepodvizhnym haderom // Zhurnal SIAM po upravleniyu i optimizacii. 1979. T. 17, № 1. Фицджеральд Ч. Дифференциальная игра «Принцесса и чудовище» // Журнал СИАМ по управлению и оптимизации. 1979. Т. 17, № 6. Ficdzheral'd Ch. Differencial'naya igra «Princessa i chudovische» // Zhurnal SIAM po upravleniyu i optimizacii. 1979. T. 17, № 6. Уилсон Д. Д. Дифференциальные игры без информации // Журнал СИАМ по управлению и оптимизации. 1977. Т. 15, № 2. Uilson D. D. Differencial'nye igry bez informacii // Zhurnal SIAM po upravleniyu i optimizacii. 1977. T. 15, № 2. Mathematical model of network flow control / I. V. Zaitseva [et al.] // IOP Conference Series: Materials Science and Engineering. “1st International Conference on Innovative Informational and Engineering Technologies, IIET 2020”, 2020. P. 012036. Mathematical model of network flow control / I. V. Zaitseva [et al.] // IOP Conference Series: Materials Science and Engineering. “1st International Conference on Innovative Informational and Engineering Technologies, IIET 2020”, 2020. P. 012036. Алферов Г. В. Генерация стратегии робота в условиях неполной информации о среде // Проблемы механики и управления: нелинейные динамические системы. 2003. № 35. С. 4–24. Alferov G. V. Generaciya strategii robota v usloviyah nepolnoy informacii o srede // Problemy mehaniki i upravleniya: nelineynye dinamicheskie sistemy. 2003. № 35. S. 4–24. Григорьева К. В., Иванов А. С., Малафеев О. А. Статическая коалиционная модель инвестирования инновационных проектов // Экономическое возрождение России. 2011. № 4. С. 90–98. Grigor'eva K. V., Ivanov A. S., Malafeev O. A. Staticheskaya koalicionnaya model' investirovaniya innovacionnyh proektov // Ekonomicheskoe vozrozhdenie Rossii. 2011. № 4. S. 90–98.