Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space

Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space

The article provides an analytical review of the main trends dominant in the world in solving the problems of modeling the processes of pursuit/escape in three-dimensional space. In order to obtain a more structured consideration of the current state, the main aspects of the research performed are i...

Ausführliche Beschreibung

Gespeichert in:
Bibliographische Detailangaben
Datum:2025
Hauptverfasser: Romanenko, I.O., Yalovets, A.L.
Format: Artikel
Sprache:Ukrainian
Veröffentlicht: PROBLEMS IN PROGRAMMING 2025
Schlagworte:
agent
player
three-dimensional space
drones
path-planning techniques
pursuit/escape strategies
UDC 004.942:[623.465+656.052.4]
Online Zugang:https://pp.isofts.kiev.ua/index.php/ojs1/article/view/760
Tags: Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:Problems in programming
Завантажити файл: Pdf

Institution

Problems in programming
id pp_isofts_kiev_ua-article-760
record_format ojs
resource_txt_mv ppisoftskievua/1b/72646fffed89da10b68cbf2336cb6d1b.pdf
spelling pp_isofts_kiev_ua-article-7602025-09-02T15:46:41Z Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space Аналітичний огляд стану досліджень з моделювання процесів переслідування/утікання у тривимірному просторі Romanenko, I.O. Yalovets, A.L. agent; player; three-dimensional space; drones; path-planning techniques; pursuit/escape strategies UDC 004.942:[623.465+656.052.4] агент; гравець; тривимірний простір; безпілотні літальні апарати; методи планування шляхів; стратегії переслідування/утікання УДК 004.942:[623.465+656.052.4] The article provides an analytical review of the main trends dominant in the world in solving the problems of modeling the processes of pursuit/escape in three-dimensional space. In order to obtain a more structured consideration of the current state, the main aspects of the research performed are identified and further analysis of such aspects is carried out. The main approaches to modeling the process of pursuit/escape in three dimensional space and the objects that are considered are analyzed. The methods of planning the paths of participants in the process of pursuit/escape in three-dimensional space are studied. The approaches used to form pursue/escape strategies in three-dimensional space are considered. Based on the results of the analysis, it is substantiated that the review allows to get a general idea of the main global trends that have developed today in the study of the processes of pursuit/escape in three-dimensional space. Prombles in programming 2025; 1: 3-12 В статті наведено аналітичний огляд основних тенденцій, домінуючих у світі в рамках вирішення про блем моделювання процесів переслідування/утікання у тривимірному просторі. З метою отримання більш структурованого розгляду існуючого стану виявлено основні аспекти виконуваних досліджень та здійснено подальший аналіз таких аспектів. Проаналізовано основні підходи до моделювання процесу переслідування/утікання у тривимірному просторі та об’єкти, які при цьому розглядаються. Досліджено методи планування шляхів учасників процесу переслідування/утікання у тривимірному просторі. Розг лянуто підходи, використані для формування стратегій переслідування/утікання у тривимірному прос торі. За результатами аналізу обґрунтовано, що виконаний огляд дозволяє отримати загальне уявлення про основні світові тенденції, що склалися на сьогодні в дослідженнях процесів переслідування/утікання у тривимірному просторі.Prombles in programming 2025; 1: 3-12 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2025-08-27 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/760 10.15407/pp2025.01.003 PROBLEMS IN PROGRAMMING; No 1 (2025); 3-12 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2025); 3-12 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2025); 3-12 1727-4907 10.15407/pp2025.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/760/812 Copyright (c) 2025 PROBLEMS IN PROGRAMMING
institution Problems in programming
baseUrl_str https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date 2025-09-02T15:46:41Z
collection OJS
language Ukrainian
topic agent
player
three-dimensional space
drones
path-planning techniques
pursuit/escape strategies
UDC 004.942:[623.465+656.052.4]
spellingShingle agent
player
three-dimensional space
drones
path-planning techniques
pursuit/escape strategies
UDC 004.942:[623.465+656.052.4]
Romanenko, I.O.
Yalovets, A.L.
Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
topic_facet agent
player
three-dimensional space
drones
path-planning techniques
pursuit/escape strategies
UDC 004.942:[623.465+656.052.4]
агент
гравець
тривимірний простір
безпілотні літальні апарати
методи планування шляхів
стратегії переслідування/утікання
УДК 004.942:[623.465+656.052.4]
format Article
author Romanenko, I.O.
Yalovets, A.L.
author_facet Romanenko, I.O.
Yalovets, A.L.
author_sort Romanenko, I.O.
title Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
title_short Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
title_full Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
title_fullStr Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
title_full_unstemmed Analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
title_sort analytical review of the state of research on modeling the processes of pursuit/escape in three-dimensional space
title_alt Аналітичний огляд стану досліджень з моделювання процесів переслідування/утікання у тривимірному просторі
description The article provides an analytical review of the main trends dominant in the world in solving the problems of modeling the processes of pursuit/escape in three-dimensional space. In order to obtain a more structured consideration of the current state, the main aspects of the research performed are identified and further analysis of such aspects is carried out. The main approaches to modeling the process of pursuit/escape in three dimensional space and the objects that are considered are analyzed. The methods of planning the paths of participants in the process of pursuit/escape in three-dimensional space are studied. The approaches used to form pursue/escape strategies in three-dimensional space are considered. Based on the results of the analysis, it is substantiated that the review allows to get a general idea of the main global trends that have developed today in the study of the processes of pursuit/escape in three-dimensional space. Prombles in programming 2025; 1: 3-12
publisher PROBLEMS IN PROGRAMMING
publishDate 2025
url https://pp.isofts.kiev.ua/index.php/ojs1/article/view/760
work_keys_str_mv AT romanenkoio analyticalreviewofthestateofresearchonmodelingtheprocessesofpursuitescapeinthreedimensionalspace
AT yalovetsal analyticalreviewofthestateofresearchonmodelingtheprocessesofpursuitescapeinthreedimensionalspace
AT romanenkoio analítičnijoglâdstanudoslídženʹzmodelûvannâprocesívpereslíduvannâutíkannâutrivimírnomuprostorí
AT yalovetsal analítičnijoglâdstanudoslídženʹzmodelûvannâprocesívpereslíduvannâutíkannâutrivimírnomuprostorí
first_indexed 2025-07-17T10:03:34Z
last_indexed 2025-09-17T09:20:42Z
_version_ 1850410841577357312
fulltext Комп’ютерне моделювання 3 © І.О. Романенко, А.Л. Яловець, 2025 ISSN 1727-4907. Проблеми програмування. 2025. №1 УДК 004.942:[623.465+656.052.4] https://doi.org/10.15407/pp2025.01.003 І.О. Романенко, А.Л. Яловець АНАЛІТИЧНИЙ ОГЛЯД СТАНУ ДОСЛІДЖЕНЬ З МОДЕЛЮВАННЯ ПРОЦЕСІВ ПЕРЕСЛІДУВАННЯ/УТІКАННЯ У ТРИВИМІРНОМУ ПРОСТОРІ В статті наведено аналітичний огляд основних тенденцій, домінуючих у світі в рамках вирішення про- блем моделювання процесів переслідування/утікання у тривимірному просторі. З метою отримання більш структурованого розгляду існуючого стану виявлено основні аспекти виконуваних досліджень та здійснено подальший аналіз таких аспектів. Проаналізовано основні підходи до моделювання процесу переслідування/утікання у тривимірному просторі та об’єкти, які при цьому розглядаються. Досліджено методи планування шляхів учасників процесу переслідування/утікання у тривимірному просторі. Розг- лянуто підходи, використані для формування стратегій переслідування/утікання у тривимірному прос- торі. За результатами аналізу обґрунтовано, що виконаний огляд дозволяє отримати загальне уявлення про основні світові тенденції, що склалися на сьогодні в дослідженнях процесів переслідування/утікання у тривимірному просторі. Ключові слова: агент, гравець, тривимірний простір, безпілотні літальні апарати, методи планування шля- хів, стратегії переслідування/утікання. I.O. Romanenko, A.L. Yalovets ANALITICAL REVIEW OF THE STATE OF RESEARCH ON MODELING THE PROCESSES OF PURSUIT/ESCAPE IN THREE-DIMENSIONAL SPACE The article provides an analytical review of the main trends dominant in the world in solving the problems of modeling the processes of pursuit/escape in three-dimensional space. In order to obtain a more structured consideration of the current state, the main aspects of the research performed are identified and further analysis of such aspects is carried out. The main approaches to modeling the process of pursuit/escape in three- dimensional space and the objects that are considered are analyzed. The methods of planning the paths of participants in the process of pursuit/escape in three-dimensional space are studied. The approaches used to form pursue/escape strategies in three-dimensional space are considered. Based on the results of the analysis, it is substantiated that the review allows to get a general idea of the main global trends that have developed today in the study of the processes of pursuit/escape in three-dimensional space. Keywords: agent, player, three-dimensional space, drones, path-planning techniques, pursuit/escape strategies. Вступ Задачі переслідування/утікання є ві- домими задачами, які мають велике теоре- тичне та прикладне значення, є достатньо вивченими та дослідженими, причому тра- диційно їх дослідження виконуються в рам- ках теорії диференціальних ігор (див., на- приклад, [1-6]). Огляд сучасного стану та- ких досліджень для випадку пересліду- вання/утікання на площині викладено, на- приклад, в [7]. Водночас в останні десяти- річчя задачі переслідування/утікання також активно досліджуються і за допомогою му- льтиагентного підходу (див., наприклад, [8- 13]). Однак, як зауважується в [14-16], на сьогоднішній день відомі дослідження в ос- новному стосуються задач пересліду- вання/утікання на площині, і є лише незна- чна кількість відкритих публікацій, присвя- чених дослідженням задач пересліду- вання/утікання у тривимірному просторі. Метою даної статті є огляд стану до- сліджень з моделювання процесів переслі- дування/утікання у тривимірному просторі на основі аналізу відкритих джерел. З ме- тою отримання більш структурованого ро- згляду існуючого стану, в статті здійсню- Комп’ютерне моделювання 4 ється виявлення основних аспектів вико- нуваних досліджень процесів пересліду- вання/утікання у тривимірному просторі та провадиться подальший аналіз таких ас- пектів. 1. Основні аспекти досліджень процесів переслідування/утікання у тривимірному просторі За результатами узагальнення ана- лізу відкритих джерел [14-24] виявлено ни- зку аспектів досліджень процесів переслі- дування/утікання у тривимірному просторі, яким відповідають: Підходи, використані для моделювання процесу переслідування/утікання: - підхід, заснований на теорії диферен- ціальних ігор [15, 18, 19, 21, 22, 24]; - мультиагентний підхід [14, 16, 17, 20, 23]. Об’єкти досліджень: - безпілотні літальні апарати [15, 17 – 22]; - автономні підводні апарати [16, 22]; - безпілотні наземні апарати [14, 15, 20]; - персонажі комп’ютерних ігор [23]; - гіперзвукові транспортні засоби [24]. Склад учасників досліджуваного про- цесу переслідування/утікання: - один переслідувач та один утікач [15, 18, 21]; - два переслідувача та один утікач [20, 24]; - декілька переслідувачів та один утікач [14, 19, 23]; - декілька переслідувачів та декілька утікачів [16, 22]; - до 100 переслідувачів та 100 утікачів [17]. Структура складу учасників досліджу- ваного процесу переслідування/уті- кання: - гомогенна [14, 16 – 19, 21, 22, 24]; - гетерогенна [15, 20, 23]. Задачі, розв’язувані в рамках моделю- вання процесу переслідування/уті- кання: - планування дій утікача [19] або пере- слідувачів [19, 23]; - планування траєкторій руху переслі- дувачів [14, 22, 23]; - прогнозування траєкторій руху уті- кача [19]. Особливості врахування впливу навко- лишнього середовища на об’єкт дослі- джень: - врахування вітрових навантажень [19, 22]; - врахування підводних потоків [22]; - врахування рельєфу місцевості [14, 16, 20]. Використані методи планування шля- хів: - метод потенціальних полів [19, 20]; - метод, заснований на побудові діаг- рами Вороного [14, 22]; - метод, заснований на побудові графа видимості [14, 23]. Підходи, використані для формування стратегій переслідування/утікання: - геометричний підхід, заснований на побудові кіл (сфер) Аполлонія [15, 19]; - підхід, заснований на Марківських процесах прийняття рішень [17, 24]; - підхід, заснований на використанні методів пошуку на графах [14, 23]. 2. Змістовний аналіз виявлених аспектів досліджень Аналіз виявлених аспектів дозволяє зробити два очевидних висновка. По-пе- рше, розглянуті дослідження практично в однаковій мірі засновані на використанні обох підходів до моделювання процесів пе- реслідування/утікання: як підходу, що ґрун- тується на теорії диференціальних ігор, так і мультиагентного підходу. По-друге, у яко- сті об’єктів досліджень в переважній біль- шості випадків виступають безпілотні літа- льні апарати (БПЛА) та автономні підводні апарати (АПА). Проаналізуємо ці висновки й те, що з них випливає. 2.1. Щодо підходів до моделю- вання процесу переслідування/уті- кання. Паритет у використанні обох підхо- дів до моделювання свідчить про наявність однакової зацікавленості в отриманні як теоретичних, так і прикладних результатів досліджень проблеми переслідування/уті- Комп’ютерне моделювання 5 кання у тривимірному просторі. Однак, як можна побачити вище, вибір конкретного підходу впливає на аналізований склад учасників досліджуваного процесу перес- лідування/утікання: теоретико-ігровий підхід до моделювання дозволяє досліджу- вати лише обмежений склад учасників (ма- ксимально це декілька переслідувачів та утікачів), тоді як мультиагентний підхід – досить великий склад (до 100 переслідува- чів та 100 утікачів). Така різниця поясню- ється тим [8], що, якщо теоретико-ігровий підхід ґрунтується на наявності закону ево- люції досліджуваної динамічної системи, заданої відповідними диференціальними рівняннями, які передбачають спрощений розгляд процесу переслідування/утікання та дозволяють описати лише досить прості ситуації, то мультиагентний підхід не пот- ребує завдання закону еволюції динамічної системи (за неї в обох випадках виступає процес переслідування/утікання), а еволю- ція системи відбувається внаслідок дій та взаємодій агентів, які задаються певними правилами або алгоритмами. На їх основі формуються (з урахуванням явища емер- джентності) достатньо складні ситуації пе- реслідування/утікання. Слід зауважити, що іноді в публіка- ціях спостерігаються випадки (див., напри- клад, [22]), коли в дослідженнях використо- вується теоретико-ігровий підхід, але грав- ців називають агентами. Наголосимо, що це концептуальна помилка, яка вводить в оману читача й спотворює зміст публікації через підміну понять та свідчить, принай- мні, про нездатність авторів розрізнити за- значені підходи. Далі, не порушуючи загальності ви- кладення, з метою запобігання таких непо- розумінь, розглядаючи умовного учасника процесу переслідування/утікання будемо іменувати його як «агент (гравець)», розу- міючи під цим щоразу лише одну з цих назв, яка відповідатиме сутності використо- вуваного підходу для моделювання. Тобто, якщо в дослідженнях використано підхід, заснований на теорії диференціальних ігор, то змістовно під терміном «агент (гравець)» будемо розуміти гравця; якщо ж мультиаге- нтний підхід – то агента. 2.2. Щодо об’єктів досліджень. Ро- згляд таких об’єктів досліджень як БПЛА та АПА потребують врахування впливу на- вколишнього середовища на них. Так, в [22] зазначається, що «причина, через яку ми ро- зглядаємо динамічні умови навколишнього середовища, полягає в тому, що наявність змінних в часі або просторово мінливих по- токів може істотно вплинути на рух транс- портних засобів і відповідну стратегію. Це стосується, зокрема, випадків, коли перес- лідувачами або утікачами (або обома) є не- великі автономні підводні апарати (АПА) або невеликі безпілотні літальні апарати (БПЛА)». В [19] підкреслюється, що для БПЛА проблема моделювання процесів пе- реслідування/утікання ускладнюється наяв- ністю значних вітрових навантажень, які впливають на траєкторію та стратегії руху агентів (гравців). Крім того, як зауважу- ється в [20], одночасно необхідно врахову- вати рельєф місцевості. В аналізованих публікаціях враху- вання навантажень на об’єкт досліджень з боку навколишнього середовища, зокрема, забезпечується як за допомогою диференці- альних рівнянь [22], так і з використанням інтелектуальних методів управління [19]. Наприклад, в [19] інтелектуальні методи управління базуються на стратегіях, що ре- алізуються за допомогою бази знань, в якій подано множину правил управління, що враховують задані обмеження управління та існуючі збурення навколишнього середо- вища. Крім того, вид об’єкта досліджень впливає на вибір методів планування шля- хів агентів (гравців), в межах яких також вирішуються проблеми обходу перешкод навколишнього середовища. Наприклад, якщо розглядати як об’єкт досліджень БПЛА або АПА, то в аналізованих дослі- дженнях [19, 20, 22] такими методами ви- ступають метод потенціальних полів та ме- тод, заснований на побудові діаграми Воро- ного. В інших випадках [14, 23] викорис- тано метод, заснований на побудові графа видимості. Ці методи розглянуто в п. 2.4. Окремо слід згадати про безпілотні наземні апарати (БНА), які зазвичай не ро- зглядаються як об’єкти досліджень проце- сів переслідування/утікання у тривимір- Комп’ютерне моделювання 6 ному просторі. Однак в аналізованих дос- лідженнях [14, 15, 20] БНА виступають та- кими об’єктами досліджень або в складі гетерогенної команди агентів (гравців) [15, 20], в якій БНА діє на площині та виступає як утікач [15, 20], так і переслідувач [20], а БПЛА діють у тривимірному просторі та виступають переслідувачами, або в складі гомогенної команди агентів (гравців) [14], що діють у навколишньому середовищі 2.5D (тобто в 2D-середовищі, доповненому картою висот). 2.3. Щодо складу учасників дослі- джуваного процесу переслідування/уті- кання. Спостережувані тенденції в аналізо- ваних дослідженнях такі, що понад дві тре- тини розглянутих складів учасників містять лише одного утікача. Водночас, переважна більшість таких випадків досліджувалася з точки зору теорії диференціальних ігор. Це свідчить про те, що сучасні дослідження пе- реслідування/утікання у тривимірному про- сторі здебільшого орієнтовані на розгляд найпростіших ситуацій. З іншого боку, у цих дослідженнях розглядались як гомогенні, так і гетерогенні структури складу учасників процесу перес- лідування/утікання. Наприклад, в [18, 19, 21] гомогенні структури включали тільки БПЛА. В свою чергу, в [15] гетерогенна структура учасників переслідування/уті- кання включала БПЛА як переслідувача та БНА як утікача, в [20] – БПЛА та БНА як переслідувачів та БНА як утікача, а в [23] – персонажів комп’ютерної гри як пересліду- вачів та персонажа, керованого людиною- гравцем, як утікача. 2.4. Щодо методів планування шляхів агентів (гравців). Зауважимо, що для вирішення проблем планування шляхів навколишнє середовище необхідно перет- ворити на певне дискретне подання, прида- тне для виконання планування шляхів за до- помогою відомих методів. Для цього вико- ристовуються такі підходи [25]: ― Планування на основі методу по- тенціальних полів. Цей підхід заснований на створенні градієнту в навколишньому се- редовищі агента (гравця), що направляє його у вільному просторі навколишнього середовища до цільової позиції з множини його попередніх позицій. ― Побудова графу пошуку. Цей під- хід передбачає побудову графу зв’язності у вільному просторі навколишнього середо- вища агента (гравця), на якому і здійсню- ється пошук шляхів. Планування на основі методу по- тенціальних полів засновано на ідеї ство- рення штучного потенціального поля в на- вколишньому середовищі агента (гравця), де він розглядається як точка, на яку це поле впливає. Ціль (глобальний мінімум у цьому полі) діє на агента (гравця) як сила тяжіння, а перешкоди – як сили відштовхування. Су- перпозиція всіх сил плавно направляє аге- нта (гравця) до цілі, одночасно уникаючи його зіткнень з відомими перешкодами. Треба зауважити, що використання підходу потенціальних полів дозволяє забезпечити більше, ніж планування шляху. Таке поле утворює закон керування рухом агента (гра- вця): якщо агент (гравець) може локалізу- вати своє місцезнаходження відносно на- вколишнього середовища та потенціаль- ного поля, то він завжди може визначити свій наступний потрібний крок, заснований на полі. Основним недоліком підходу на ос- нові потенціальних полів є те, що у полі мо- жуть існувати локальні мінімуми, які мо- жуть дезорієнтувати агента (гравця) у по- шуку цілі. Зауважимо, що в аналізованих дослідженнях метод потенціальних полів використовувався з урахуванням певних об- межень навколишнього середовища або по- єднувався з іншими методами. Наприклад, в [20] цей метод використовувався для пла- нування дій переслідувачів лише у разі, коли утікачі знаходяться в полі зору (тобто в межах прямої видимості) переслідувачів. У свою чергу, в [19] метод потенціальних полів, використаний для вирішення про- блеми уникнення перешкод, поєднано з ге- ометричним підходом, заснованим на побу- дові сфер Аполлонія, що загалом забезпе- чило формування раціональних стратегій руху агентів (гравців). Будуючи граф пошуку, агент (гра- вець) з’єднує початкову та цільову позиції у вільному просторі навколишнього середо- вища множиною ліній, які утворюють граф зв’язності як множину шляхів, що існують між початковою та цільовою позиціями. Для створення графу пошуку найбільше поши- Комп’ютерне моделювання 7 рення набули методи, засновані на побудові діаграми Вороного та графу видимості. Метод, заснований на побудові діа- грами Вороного. Під час побудови діаг- рами Вороного знаходиться множина то- чок, кожна з яких є центром кругу, вписа- ного у вільний простір навколишнього се- редовища, який торкається як мінімум двох точок контурів перешкод. У процесі з’єд- нання послідовностей таких точок утворю- ються ребра, які складаються з прямих та параболічних сегментів, а вершини графа відповідають точкам зустрічі різних ребер та початковій і цільовій вершинам. Водно- час забезпечується максимізація відстані між агентом (гравцем) та перешкодами в навколишньому середовищі. Створюючи діаграму Вороного, агент (гравець) з’єднує початкову та цільову позиції у вільному просторі навколишнього середовища мно- жиною ліній, що утворюють граф зв’язно- сті як множину шляхів, які існують між по- чатковою та цільовою позиціями. Однак найкоротший шлях, знайдений на діаграмі Вороного, не є оптимальним за критерієм довжини. В аналізованих дослідженнях діа- грама Вороного використовується для розв’язання різних задач. Наприклад, в [14] вона використовується для виявлення вузь- ких ділянок навколишнього середовища агента (гравця) з метою виключення таких ділянок з процесу пошуку шляху на графах. А в [22] за допомогою діаграми Вороного здійснюється динамічне призначення доці- льних переслідувачів для захоплення відпо- відних утікачів. Метод, заснований на побудові графа видимості, де граф видимості скла- дається з множини ребер, що зв’язують усі пари вершин, які є видимими (тобто ребра проходять через вільний простір навколиш- нього середовища) між собою (включаючи початкову та цільові позиції як вершини). Прямі лінії (шляхи), що з’єднують ці вер- шини, є найкоротшими відстанями між ними, і задача пошуку на утворюваному графі видимості полягає в знаходженні за допомогою методів пошуку на графах най- коротшого шляху з множини шляхів, існу- ючих між початковою та цільовою верши- нами цього графа. Завдяки досить простій процедурі його побудови, граф видимості отримав досить широке використання на практиці. Водночас, таке подання має свої недоліки. По-перше, розмір графа видимо- сті зростає зі збільшенням полігонів переш- код, що негативно впливає на ефективність використовуваних процедур пошуку на цьому графі. По-друге, ребра, що утворю- ються під час побудови графа видимості, проходять на мінімальній відстані від пере- шкод, що негативно впливає на безпечність навігації агента (гравця) обраним найкоро- тшим шляхом. В аналізованих досліджен- нях [14, 23] цей метод використовується для створення графа, на якому агенти (гравці) виконують пошук шляхів за допомогою ме- тодів пошуку на графах. Зауважимо, що за допомогою зазна- чених методів в рамках виконання пошуку шляхів також забезпечується вирішення проблем обходу перешкод навколишнього середовища. 2.5. Щодо підходів, використаних для формування стратегій пересліду- вання/утікання. Як зазначено в п.1 статті, в аналізованих дослідженнях для форму- вання стратегій переслідування/утікання використано такі підходи: - геометричний підхід, заснований на по- будові кіл (сфер) Аполлонія [15, 19]; - підхід, заснований на Марківських про- цесах ухвалення рішень [17, 24]; - підхід, заснований на використанні ме- тодів пошуку на графах [14, 23]. Коротко проаналізуємо названі під- ходи. Геометричний підхід, заснований на побудові кіл (сфер) Аполлонія викори- стано в [15, 19]. Зокрема, в [15] побудова кола (сфери) Аполлонія ґрунтується на ви- користанні ізохронів. Ізохрон – це множина точок, які агент (гравець) може досягти од- ночасно, а перетин ізохронів переслідувачів та утікачів – це множина точок, до яких вони можуть прибути одночасно. В загаль- ному випадку перетин ізохронів таких аге- нтів (гравців), що рухаються з різною шви- дкістю, утворює коло (сферу) Аполлонія. Формування стратегії переслідування/уті- кання в [15] ґрунтується на побудові пере- тину ізохронів переслідувача, який руха- ється у тривимірному просторі, та ізохронів утікача, що рухається на площині, що від- Комп’ютерне моделювання 8 повідає перетину сфери Аполлонія, побудо- ваної в 3D-просторі, та кола Аполлонія, по- будованого на 2D-площині. В свою чергу, в [19] процес побудови сфер Аполлонія поєд- нано з модифікованим методом потенціаль- них полів, що в результаті дозволило сфор- мувати раціональну стратегію руху агентів (гравців), в межах якої також вирішується проблема уникнення перешкод навколиш- нього середовища. Підхід, заснований на Марківсь- ких процесах ухвалення рішень викорис- тано в [17, 24]. В загальному випадку Мар- ківські процеси ухвалення рішень (МППР) – це основа для моделювання послідовного ухвалення рішень в ситуаціях, коли резуль- тати частково випадкові та частково зале- жать від дій агента (гравця). В МППР агент (гравець) діє в навколишньому середовищі та взаємодіє з ним. Агент (гравець) вибирає дії, а навколишнє середовище реагує на ці дії та формує нові ситуації для агента (гра- вця). Водночас, навколишнє середовище ге- нерує винагороди – числові значення, які агент (гравець) прагне максимізувати з ча- сом шляхом вибору дій. Формально МППР описується кор- тежем 1 1( , , ( , ), ( , ))t t a t t a t tt ts a p s s r s s+ + , де ts – стан навколишнього середовища в момент часу t; ta – дія, вчинена агентом (гравцем) в результаті процесу ухвалення рішень в момент часу t; 1( , )a t ttp s s + – ймовірність пе- реходу навколишнього середовища у стан 1ts + за умови виконання дії ta в стані ts ; 1( , )a t ttr s s + – винагорода, отримувана аген- том (гравцем) в результаті виконання дії ta , внаслідок якої відбувся перехід зі стану ts у стан 1ts + (зазначимо, що 1,t ts s S+  , де S – скінченна множина станів навколиш- нього середовища; ta A , де А – скінченна множина дій, які агент (гравець) може вико- нати). Основним механізмом управління поведінкою агента (гравця) в МППР є фун- кція винагороди. Надаючи позитивні та не- гативні винагороди агенту (гравцю), такий механізм здатний визначити, які дії приво- дять до позитивної винагороди, а рішення МППР дозволяють максимізувати очіку- вання майбутньої винагороди. Так, для вирішення проблем переслі- дування/утікання в [17] використовуються позитивні та негативні винагороди, які по- єднуються разом, утворюючи напругу між потенційними діями. Наприклад, розмі- щення позитивної винагороди біля місця розташування утікача привертає увагу пе- реслідувачів, але розміщення негативної винагороди на утікачі дозволяє запобігти зі- ткненню з ним. Між цими позитивними і негативними винагородами створюється природна рівновага, а це породжує бажану поведінку наближення переслідувача до утікача без зіткнення з ним. У свою чергу, в [24] процес переслі- дування/утікання також моделюється як МППР, однак функція винагороди викорис- товується дещо інакше. Зауважимо, що в [24] досліджується інтелектуальна страте- гія маневру для гіперзвукових транспорт- них засобів. Ефективність цієї стратегії оці- нюється двома показниками: величиною ві- дхилення агента (гравця) від цілі та спожи- ванням енергії під час маневру. При цьому, значення цих показників суперечать один одному протягом всього процесу пересліду- вання/утікання: очікування збільшення ве- личини відхилення від цілі вимагає біль- шого перевантаження під час маневру- вання, що потребує більше енергії, а еконо- мія енергії неминуче призведе до змен- шення величини можливого відхилення. Тому ці показники мають бути кількісно ко- реговані, що здійснюється за рахунок кое- фіцієнта енергозбереження (який виступає як функція винагороди), а зміна величини коефіцієнта енергозбереження дозволяє кі- лькісно регулювати два вищезгаданих пока- зники. Підхід, заснований на викорис- танні методів пошуку на графах, розгля- нуто в [14, 23]. У цих дослідженнях пошук виконується на графі видимості (див. п.2.4). Зазначимо, що для пошуку шляхів на графі видимості можуть використовуватись різні методи (алгоритми), в тому числі: пошуку Комп’ютерне моделювання 9 вшир, пошуку вглиб, Дейкстри, А*, D*. В аналізованих дослідженнях [14, 23] для фо- рмування стратегій переслідування/уті- кання агентів (гравців) використано алго- ритм А*. Алгоритм А* є удосконаленням ал- горитму Дейкстри, яке здійснено шляхом введення евристичної функції, що враховує властивості графу пошуку і дозволяє змен- шити кількість досліджуваних вершин графу. В алгоритмі А* порядок обходу вер- шин графу визначається евристичною фун- кцією )(nf як сумою функції )(ng вартості шляху від початкової до даної вершини n та функції )(nh як евристичної оцінки вар- тості шляху від цієї вершини n до цільової: )()()( nhngnf += . Алгоритм А* досліджує граф ітеративно, розглядаючи шляхи, що виходять з початкової вершини. На кож- ному кроці ітерації алгоритм розглядає вер- шини, суміжні поточній вершині, та обирає ту з них, для якої )(nf є мінімальною, після чого ця вершина «розкривається». В загаль- ному випадку на кожному кроці ітерації ал- горитм оперує з множиною шляхів від по- чаткової вершини до ще не «розкритих» ве- ршин графу. Такі шляхи зберігаються в че- рзі з пріоритетом, де пріоритет визнача- ється за значенням )(nf . Алгоритм продо- вжує свою роботу доти, поки не досягне ці- льової вершини і не визначить шлях до неї з найменшим значенням )(nf . Недоліком алгоритму А* є те, що евристичні оцінки вартості шляхів задані остаточно і не мо- жуть бути змінені в процесі роботи алгори- тму (без його перезапуску), що не дозволяє коректно планувати шляхи в динамічно змі- нюваному середовищі. Зазначимо, що в [14] граф видимості створюється агентом (гравцем) з викорис- танням карти висот. Алгоритм А* виконує пошук мінімального шляху на такому графі, де для кожного ребра графа призначається функція вартості, яка визначається з ураху- ванням обчислення мінімальної відстані до інцидентної вершини графа. В свою чергу, в [23] графом видимості виступає навіга- ційна сітка, яка визначає можливі місця, яким може рухатись агент (гравець). Ребрам такого графа поставлені у відповідність ва- ртісні оцінки, які враховують відстані між вершинами графа та використовуються ал- горитмом А* в процесі пошуку мінімаль- ного шляху. Висновки Виконаний аналітичний огляд відк- ритих джерел дозволяє, на нашу думку, отримати загальне уявлення про основні світові тенденції, що склалися на сьогодні в дослідженнях процесів переслідування/уті- кання у тривимірному просторі. Зокрема, з виконаного огляду стає очевидною однакова зацікавленість в отри- манні як теоретичних, так і прикладних ре- зультатів досліджень процесів пересліду- вання/утікання у тривимірному просторі, що пояснюється великою актуальністю цієї сфери досліджень для різних галузей засто- сування (насамперед військової галузі). Во- дночас, у переважній більшості випадків об’єктом досліджень стають безпілотні лі- тальні й автономні підводні апарати, що на- разі відповідає широкому попиту на вико- ристання цих апаратів для виконання спеці- альних операцій (в тому числі військових). У цьому контексті підвищується актуаль- ність задачі врахування впливу фактору на- вколишнього середовища на досліджувані об’єкти (вітрових навантажень, підводних потоків, особливостей рельєфу місцевості). Необхідність розв’язання таких задач пот- ребувала вирішення низки проблем, в тому числі проблем планування шляхів в навко- лишньому середовищі з урахуванням уник- нення перешкод. А вирішення проблем пла- нування шляхів, у свою чергу, актуалізу- вало необхідність вирішення проблем фор- мування стратегій переслідування/утікання у тривимірному просторі. Наголосимо, що окреслені вище ас- пекти характеризують лише основні на- прями досліджень проблем пересліду- вання/утікання у тривимірному просторі, але не обмежують їх. ЛІТЕРАТУРА 1. Айзекс Р. Дифференциальные игры. М.: Мир, 1967. 479 с. 2. Красовский Н.Н., Субботин А.И. Позицион- ные дифференциальные игры. М.: Наука, 1974. 456 с. Комп’ютерне моделювання 10 3. Петросян Л.А., Рисхиев Б.Б. Преследование на плоскости. М.: Наука, 1991. 91 с. 4. Петросян Л.А., Томский Г.В. Геометрия простого преследования. Новосибирск: Наука, 1983. 140 с. 5. Пшеничный Б.Н., Остапенко В.В. Диффе- ренциальные игры. К.: Наукова думка, 1992. 259 с. 6. Чикрий А.А. Конфликтно управляемые процессы. К.: Наукова думка, 1992. 364 с. 7. Weintraub I.E., Pachter M., García E. An Intro- duction to Pursuit-evasion Differential Games. 2020 American Control Conference (ACC), pp. 1049-1066, DOI: 10.23919/ACC45564.2020.9147205 8. Яловець А.Л. Мультиагентне моделювання переслідування на площині: від теорії до програмної реалізації. К.: Наукова думка, 2019. 165 с. 9. Lopez V.G., Lewis F.L., Wan Y., Sanchez E.N., Fan L. Solutions for Multiagent Pursuit-Eva- sion Games on Communication Graphs: Fi- nite-Time Capture and Asymptotic Behaviors. IEEE Transactions on Automatic Control, 2020. Vol. 65, No. 5, pp. 1911-1923, DOI: 10.1109/TAC.2019.2926554 10. Deng Z., Kong Z. Multi-Agent Cooperative Pursuit-Defense Strategy Against One Single Attacker. IEEE Robotics and Automation Let- ters, 2020. Vol. 5, No. 4, pp. 5772-5778, DOI: 10.1109/LRA.2020.3010740 11. Liang X., Zhou B., Jiang L., Meng G., Xiu Y. Collaborative pursuit-evasion game of multi- UAVs based on Apollonius circle in the envi- ronment with obstacle. Connection Science, 2023. Vol. 35, Iss.1, pp. 1-24, DOI: 10.1080/09540091.2023.2168253 12. Paczolay G., Harmati I. A Simplified Pursuit- evasion Game with Reinforcement Learning. Periodica Polytechnica Electrical Engineering and Computer Science, 2021. Vol. 65, No. 2, pp. 160-166, DOI: 10.3311/PPee.16540 13. de Souza C., Newbury R., Cosgun A., Castillo P., Vidolov B., Kulić D. Decentralized Multi- Agent Pursuit Using Deep Reinforcement Learning. IEEE Robotics and Automation Let- ters, 2021. Vol. 6, No. 3, pp. 4552-4559, DOI: 10.1109/LRA.2021.3068952 14. Kolling A., Kleiner A., Lewis M., Sycara K. Pursuit-evasion in 2.5d based on team-visibil- ity. 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems, Taipei, Tai- wan, 2010, pp. 4610-4616, DOI: 10.1109/IROS.2010.5649270 15. Li S., Wang C., Xie G. Pursuit-evasion differ- ential games of players with different speeds in spaces of different dimensions, 2022 American Control Conference, Atlanta, GA, USA, 2022, pp. 1299-1304, DOI: 10.23919/ACC53348.2022.9867329 16. Özkahraman Ö., Ögren P. Underwater Caging and Capture for Autonomous Underwater Ve- hicles. Global Oceans 2020: Singapore – U.S. Gulf Coast, Biloxi, MS, USA, 2020, pp. 1-8, DOI: 10.1109/IEEECONF38699.2020.9389311 17. Bertram J.R., Wei P. An Efficient Algorithm for Multiple-Pursuer-Multiple-Evader Pur- suit/Evasion Game. ArXiv, 2019, abs/1909.04171, DOI: 10.48550/arXiv.1909.04171 18. Chen N., Li L., Mao W. Equilibrium Strategy of the Pursuit-Evasion Game in Three-Dimen- sional Space. IEEE/CAA Journal of Automat- ica Sinica, 2024. Vol. 11, No. 2, pp. 446-458, DOI: 10.1109/JAS.2023.123996Ya 19. Khachumov M., Khachumov V. Modeling the Solution of the Pursuit–Evasion Problem Based on the Intelligent–Geometric Control Theory. Mathematics, 2023. Vol. 11, Is. 23, 4869. DOI: 10.3390/math11234869 20. Liang X., Wang H., Luo H. Collaborative Pur- suit-Evasion Strategy of UAV/UGV Heteroge- neous System in Complex Three-Dimensional Polygonal Environment, Complexity, 2020. Vol. 2020, pages 1-13, DOI: 10.1155/2020/7498740 21. Segal A., Miloh T. Barrier strategies and cap- ture criteria in a 3D pursuit-evasion differential game. Optimal Control Applications & Meth- ods, 1995. Vol. 16, Is. 5, pp. 321-340, DOI: 10.1002/j.1099-1514.1995.tb00024.x 22. Sun W., Tsiotras P., Yezzi A.J. Multiplayer Pur- suit-Evasion Games in Three-Dimensional Flow Fields. Dynamic Games and Applica- tions, 2019. Vol. 9, Is. 4, pp. 1188-1207, DOI: 10.1007/s13235-019-00304-4 23. Şahin İ., Kumbasar T. Catch me if you can: A pursuit-evasion game with intelligent agents in the Unity 3D game environment, 2020 Interna- tional Conference on Electrical Engineering (ICEE), Istanbul, Turkey, 2020, pp. 1-6, DOI: 10.1109/ICEE49691.2020.9249828 24. Yan T., Jiang Z., Li T., Gao M., Liu C. Intelli- gent maneuver strategy for hypersonic vehicles in three-player pursuit-evasion games via deep reinforcement learning. Frontiers in Neurosci- ence, 2024. 18:1362303, DOI: 10.3389/fnins.2024.1362303 25. Яловець А.Л. До постановки задачі розпі- знавання невідомого оточуючого середо- вища, навігації та планування шляхів аген- Комп’ютерне моделювання 11 том в ньому. Проблеми програмування. 2018. № 1. С. 113-127, DOI: 10.15407/pp2018.01.113 REFERENCES 1. Isaaks R. (1967) Differential games. Мir. 479 p. (in Russian) 2. Krasovsky N.N., Subbotin A.I. (1974) Posi- tional differential games. Nauka. 456 p. (in Russian) 3. Petrosyan L.A., Riskhiev B.B. (1991) Pursuit on the plane. Nauka. 91 p. (in Russian) 4. Petrosyan L.A., Tomsky G.V. (1983) Geometry of simple pursuit. Nauka. 140 p. (in Russian) 5. Pshenichny B.N., Ostapenko V.V. (1992) Dif- ferential games. Naukova dumka. 259 p. (in Russian) 6. Chikriy A.A. (1992) Conflict-controlled pro- cesses. Naukova dumka. 364 p. (in Russian) 7. Weintraub I.E., Pachter M., García E. (2020) An introduction to pursuit-evasion differential games. 2020 American Control Conference (ACC), pp. 1049-1066, DOI: 10.23919/ACC45564.2020.9147205 8. Yalovets A.L. (2019) Multi-agent modeling of pursuit on the plane: from theory to software implementation. Naukova dumka. 165 p. (in Ukrainian) 9. Lopez V.G., Lewis F.L., Wan Y., Sanchez E.N., Fan L. (2020) Solutions for multiagent pursuit- evasion games on communication graphs: fi- nite-time capture and asymptotic behaviors. IEEE Transactions on Automatic Control. Vol. 65, No. 5, pp. 1911-1923, DOI: 10.1109/TAC.2019.2926554 10. Deng Z., Kong Z. (2020) Multi-agent coopera- tive pursuit-defense strategy against one single attacker. IEEE Robotics and Automation Let- ters. Vol. 5, No. 4, pp. 5772-5778, DOI: 10.1109/LRA.2020.3010740 11. Liang X., Zhou B., Jiang L., Meng G., Xiu Y. (2023) Collaborative pursuit-evasion game of multi-UAVs based on Apollonius circle in the environment with obstacle. Connection Sci- ence. Vol. 35, Iss.1, pp. 1-24, DOI: 10.1080/09540091.2023.2168253 12. Paczolay G., Harmati I. (2021) A simplified pursuit-evasion game with reinforcement learning. Periodica Polytechnica Electrical Engineering and Computer Science. Vol. 65, No. 2, pp. 160-166, DOI: 10.3311/PPee.16540 13. de Souza C., Newbury R., Cosgun A., Castillo P., Vidolov B., Kulić D. (2021) Decentralized multi-agent pursuit using deep reinforcement learning. IEEE Robotics and Automation Let- ters. Vol. 6, No. 3, pp. 4552-4559, DOI: 10.1109/LRA.2021.3068952 14. Kolling A., Kleiner A., Lewis M., Sycara K. (2010) Pursuit-evasion in 2.5d based on team- visibility. 2010 IEEE/RSJ International Con- ference on Intelligent Robots and Systems, Tai- pei, Taiwan. pp. 4610-4616, DOI: 10.1109/IROS.2010.5649270 15. Li S., Wang C., Xie G. (2022) Pursuit-evasion differential games of players with different speeds in spaces of different dimensions, 2022 American Control Conference, Atlanta, GA, USA. pp. 1299-1304, DOI: 10.23919/ACC53348.2022.9867329 16. Özkahraman Ö., Ögren P. (2020) Underwater caging and capture for autonomous underwater vehicles. Global Oceans 2020: Singapore – U.S. Gulf Coast, Biloxi, MS, USA, pp. 1-8, DOI: 10.1109/IEEECONF38699.2020.9389311 17. Bertram J.R., Wei P. (2019) An Efficient algo- rithm for multiple-pursuer-multiple-evader pursuit/evasion game. ArXiv, abs/1909.04171, DOI: 10.48550/arXiv.1909.04171 18. Chen N., Li L., Mao W. (2024) Equilibrium strategy of the pursuit-evasion game in three- dimensional space. IEEE/CAA Journal of Au- tomatica Sinica. Vol. 11, No. 2, pp. 446-458, DOI: 10.1109/JAS.2023.123996Ya 19. Khachumov M., Khachumov V. (2023) Model- ing the solution of the pursuit–evasion problem based on the intelligent–geometric control the- ory. Mathematics. Vol. 11, Is. 23, 4869. DOI: 10.3390/math11234869 20. Liang X., Wang H., Luo H. (2020) Collabora- tive pursuit-evasion strategy of uav/ugv heter- ogeneous system in complex three-dimen- sional polygonal environment. Complexity. Vol. 2020, pages 1-13, DOI: 10.1155/2020/7498740 21. Segal A., Miloh T. (1995) Barrier strategies and capture criteria in a 3D pursuit-evasion dif- ferential game. Optimal Control Applications & Methods. Vol. 16, Is. 5, pp. 321-340, DOI: 10.1002/j.1099-1514.1995.tb00024.x 22. Sun W., Tsiotras P., Yezzi A.J. (2019) Multi- player pursuit-evasion games in three-dimen- sional flow fields. Dynamic Games and Appli- cations. Vol. 9, Is. 4, pp. 1188-1207, DOI: 10.1007/s13235-019-00304-4 23. Şahin İ., Kumbasar T. (2020) Catch me if you can: A pursuit-evasion game with intelligent agents in the Unity 3D game environment, 2020 International Conference on Electrical Engineering (ICEE), Istanbul, Turkey. pp. 1-6, DOI: 10.1109/ICEE49691.2020.9249828 Комп’ютерне моделювання 12 24. Yan T., Jiang Z., Li T., Gao M., Liu C. (2024) Intelligent maneuver strategy for hypersonic vehicles in three-player pursuit-evasion games via deep reinforcement learning. Frontiers in Neuroscience. 18:1362303, DOI: 10.3389/fnins.2024.1362303 25. Yalovets A.L. (2018) On the problem of recog- nizing the unknown environment, navigating and planning paths by an agent in it. Problems in Programming. № 1. pp. 113-127. (in Ukrain- ian) DOI: 10.15407/pp2018.01.113 Одержано: 25.02.2025 Внутрішня рецензія отримана: 04.03.2025 Зовнішня рецензія отримана: 07.03.2025 Про авторів: Романенко Ігор Олександрович, доктор технічних наук, професор, провідний науковий співробітник https://orcid.org/0000-0001-5339-7900 Яловець Андрій Леонідович, доктор технічних наук, старший науковий співробітник, головний науковий співробітник http://orcid.org/0000-0001-6542-3483 Місце роботи авторів: Інститут проблем математичних машин і систем НАН України, Тел.: (+38) 044 526 13 69. E-mail: andriy.yalovets@gmail.com

Ähnliche Einträge