Моделювання оптимальних стратегій переслідування з простим рухом

Розглядаються стратегії переслідування цілі одним переслідувачем із простим рухом. Критерієм є час захоплення цілі. Наводиться доведення оптимальності стратегії паралельного зближення і погонної стратегії. Стратегія паралельного зближення полягає в тому, що переслідувач, знаючи вектор швидкості цілі...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2022
Автор:	Пашко, С.В.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2022
Назва видання:	Проблеми програмування
Теми:	Прикладне програмне забезпечення
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/188671
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Моделювання оптимальних стратегій переслідування з простим рухом / С.В. Пашко // Проблеми програмування. — 2022. — № 3-4. — С. 478-484. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-188671
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-1886712025-02-09T09:38:55Z Моделювання оптимальних стратегій переслідування з простим рухом Simulation of optimal pursuit strategies with simple motion Пашко, С.В. Прикладне програмне забезпечення Розглядаються стратегії переслідування цілі одним переслідувачем із простим рухом. Критерієм є час захоплення цілі. Наводиться доведення оптимальності стратегії паралельного зближення і погонної стратегії. Стратегія паралельного зближення полягає в тому, що переслідувач, знаючи вектор швидкості цілі в даний момент часу, вважає цей вектор постійним та обчислює на лінії руху цілі точку, в якій може відбутися захоплення, якщо переслідувач рухатиметься з постійною максимальною швидкістю. В кожний момент часу вектор швидкості переслідувача направлений на точку захоплення, а величина швидкості максимальна. Якщо переслідувач рухається з максимальною швидкістю у напрямку цілі, стратегія переслідування називається погонною стратегією. Наведено ряд прикладів переслідування з використанням стратегій паралельного зближення та погонної стратегії, розрахованих числовим методом. Визначено основні параметри руху агентів, що впливають на час захоплення: швидкості цілі та переслідувача, координати цілі та переслідувача в момент початку переслідування, тип і параметри лінії руху цілі; задача переслідування визначається цими параметрами. На основі числового моделювання окреслено множини задач, для яких стратегія паралельного зближення перевершує погонну стратегію або навпаки. Вибрані параметри руху приблизно відповідають параметрам руху сучасних бойових літаків та засобів протиповітряної оборони; в числових експериментах абсолютна величина прискорення цілі не перевищує 10g, де g – прискорення вільного падіння. Оскільки рух переслідувача вважається простим, дозволяється будь-яка абсолютна величина його прискорення. У разі застосування стратегії паралельного зближення ця величина незначно відрізняється від абсолютної величини прискорення цілі; якщо застосовується погонна стратегія, абсолютна величина прискорення переслідувача може бути значно більшою. Strategies for pursuit of a target by one pursuer with simple movement are considered. The criterion is the time to capture the target. The proof of the optimality of the parallel approach strategy and the chasing strategy is presented. The strategy of parallel approach consists in the fact that the pursuer, knowing the velocity vector of the target at current moment, considers this vector to be constant and calculates a point on the target’s line of motion at which capture can occur if the pursuer moves at a constant maximum speed. At each instant of time, the pursuer’s velocity vector is directed to the capture point, and the magnitude of the velocity is maximal. If the pursuer moves at maximum speed in the direction of the target, the pursuit strategy is called a chasing strategy. A number of examples of pursuit using the strategies of parallel approach and chasing strategy, calculated by the numerical method, are given. The main parameters of the movement of the agents affecting the time of capture are determined: the speed of the target and the pursuer, the coordinates of the target and the pursuer at the time of the beginning of the pursuit, the type and parameters of the target’s movement line; the pursuit task is determined by these para-meters. On the basis of numerical modeling, a sets of problems is outlined for which the parallel approach strategy is better then the chasing strategy or vice versa. The selected movement parameters roughly correspond to the movement parameters of modern combat aircraft and air defense equipment; in numerical experiments, the absolute value of the acceleration of the target does not exceed 10g, where g is the accele-ration of free fall. Since the pursuer’s motion is considered simple, any absolute value of its acceleration is allowed. In the case of applying the parallel approach strategy, this value slightly differs from the absolute value of the target’s acceleration; if a chasing strategy is used, the absolute magnitude of the pursuer’s acceleration can be much larger 2022 Article Моделювання оптимальних стратегій переслідування з простим рухом / С.В. Пашко // Проблеми програмування. — 2022. — № 3-4. — С. 478-484. — Бібліогр.: 11 назв. — укр. 1727-4907 DOI: https://doi.org/10.15407/pp2022.03-04.478 https://nasplib.isofts.kiev.ua/handle/123456789/188671 519.8 uk Проблеми програмування application/pdf Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Прикладне програмне забезпечення Прикладне програмне забезпечення
spellingShingle	Прикладне програмне забезпечення Прикладне програмне забезпечення Пашко, С.В. Моделювання оптимальних стратегій переслідування з простим рухом Проблеми програмування
description	Розглядаються стратегії переслідування цілі одним переслідувачем із простим рухом. Критерієм є час захоплення цілі. Наводиться доведення оптимальності стратегії паралельного зближення і погонної стратегії. Стратегія паралельного зближення полягає в тому, що переслідувач, знаючи вектор швидкості цілі в даний момент часу, вважає цей вектор постійним та обчислює на лінії руху цілі точку, в якій може відбутися захоплення, якщо переслідувач рухатиметься з постійною максимальною швидкістю. В кожний момент часу вектор швидкості переслідувача направлений на точку захоплення, а величина швидкості максимальна. Якщо переслідувач рухається з максимальною швидкістю у напрямку цілі, стратегія переслідування називається погонною стратегією. Наведено ряд прикладів переслідування з використанням стратегій паралельного зближення та погонної стратегії, розрахованих числовим методом. Визначено основні параметри руху агентів, що впливають на час захоплення: швидкості цілі та переслідувача, координати цілі та переслідувача в момент початку переслідування, тип і параметри лінії руху цілі; задача переслідування визначається цими параметрами. На основі числового моделювання окреслено множини задач, для яких стратегія паралельного зближення перевершує погонну стратегію або навпаки. Вибрані параметри руху приблизно відповідають параметрам руху сучасних бойових літаків та засобів протиповітряної оборони; в числових експериментах абсолютна величина прискорення цілі не перевищує 10g, де g – прискорення вільного падіння. Оскільки рух переслідувача вважається простим, дозволяється будь-яка абсолютна величина його прискорення. У разі застосування стратегії паралельного зближення ця величина незначно відрізняється від абсолютної величини прискорення цілі; якщо застосовується погонна стратегія, абсолютна величина прискорення переслідувача може бути значно більшою.
format	Article
author	Пашко, С.В.
author_facet	Пашко, С.В.
author_sort	Пашко, С.В.
title	Моделювання оптимальних стратегій переслідування з простим рухом
title_short	Моделювання оптимальних стратегій переслідування з простим рухом
title_full	Моделювання оптимальних стратегій переслідування з простим рухом
title_fullStr	Моделювання оптимальних стратегій переслідування з простим рухом
title_full_unstemmed	Моделювання оптимальних стратегій переслідування з простим рухом
title_sort	моделювання оптимальних стратегій переслідування з простим рухом
publisher	Інститут програмних систем НАН України
publishDate	2022
topic_facet	Прикладне програмне забезпечення
url	https://nasplib.isofts.kiev.ua/handle/123456789/188671
citation_txt	Моделювання оптимальних стратегій переслідування з простим рухом / С.В. Пашко // Проблеми програмування. — 2022. — № 3-4. — С. 478-484. — Бібліогр.: 11 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT paškosv modelûvannâoptimalʹnihstrategíjpereslíduvannâzprostimruhom AT paškosv simulationofoptimalpursuitstrategieswithsimplemotion
first_indexed	2025-11-25T10:55:13Z
last_indexed	2025-11-25T10:55:13Z
_version_	1849759488815398912
fulltext	478 Прикладне програмне забезпечення УДК 519.8 https://doi.org/10.15407/pp2022.03-04.478 МОДЕЛЮВАННЯ ОПТИМАЛЬНИХ СТРАТЕГІЙ ПЕРЕСЛІДУВАННЯ З ПРОСТИМ РУХОМ Сергій Пашко Розглядаються стратегії переслідування цілі одним переслідувачем із простим рухом. Критерієм є час захоплення цілі. Наводиться доведення оптимальності стратегії паралельного зближення і погонної стратегії. Стратегія паралельного зближення полягає в тому, що переслідувач, знаючи вектор швидкості цілі в даний момент часу, вважає цей вектор постійним та обчислює на лінії руху цілі точку, в якій може відбутися захоплення, якщо переслідувач рухатиметься з постійною максимальною швидкістю. В кожний момент часу вектор швидкості переслідувача направлений на точку захоплення, а величина швидкості максимальна. Якщо переслідувач рухається з макси- мальною швидкістю у напрямку цілі, стратегія переслідування називається погонною стратегією. Наведено ряд прикладів переслідування з використанням стратегій паралельного зближення та по- гонної стратегії, розрахованих числовим методом. Визначено основні параметри руху агентів, що впливають на час захоплення: швидкості цілі та переслідувача, координати цілі та переслідувача в момент початку переслідування, тип і параметри лінії руху цілі; задача переслідування визна- чається цими параметрами. На основі числового моделювання окреслено множини задач, для яких стратегія паралельного зближення перевершує погонну стратегію або навпаки. Вибрані параметри руху приблизно відповідають параметрам руху сучасних бойових літаків та засобів протиповітря- ної оборони; в числових експериментах абсолютна величина прискорення цілі не перевищує 10g, де g – прискорення вільного падіння. Оскільки рух переслідувача вважається простим, дозволя- ється будь-яка абсолютна величина його прискорення. У разі застосування стратегії паралельного зближення ця величина незначно відрізняється від абсолютної величини прискорення цілі; якщо застосовується погонна стратегія, абсолютна величина прискорення переслідувача може бути зна- чно більшою. Ключові слова: переслідування, моделювання, оптимальна стратегія, ціль. Strategies for pursuit of a target by one pursuer with simple movement are considered. The criterion is the time to capture the target. The proof of the optimality of the parallel approach strategy and the chas- ing strategy is presented. The strategy of parallel approach consists in the fact that the pursuer, knowing the velocity vector of the target at current moment, considers this vector to be constant and calculates a point on the target’s line of motion at which capture can occur if the pursuer moves at a constant maxi- mum speed. At each instant of time, the pursuer’s velocity vector is directed to the capture point, and the magnitude of the velocity is maximal. If the pursuer moves at maximum speed in the direction of the target, the pursuit strategy is called a chasing strategy. A number of examples of pursuit using the strate- gies of parallel approach and chasing strategy, calculated by the numerical method, are given. The main parameters of the movement of the agents affecting the time of capture are determined: the speed of the target and the pursuer, the coordinates of the target and the pursuer at the time of the beginning of the pursuit, the type and parameters of the target’s movement line; the pursuit task is determined by these para-meters. On the basis of numerical modeling, a sets of problems is outlined for which the parallel approach strategy is better then the chasing strategy or vice versa. The selected movement parameters roughly correspond to the movement parameters of modern combat aircraft and air defense equipment; in numerical experiments, the absolute value of the acceleration of the target does not exceed 10g, where g is the accele-ration of free fall. Since the pursuer’s motion is considered simple, any absolute value of its acceleration is allowed. In the case of applying the parallel approach strategy, this value slightly differs from the absolute value of the target’s acceleration; if a chasing strategy is used, the absolute magnitude of the pursuer’s acceleration can be much larger. Keywords: pursuit, simulation, optimal strategy, target. Вступ Одне з центральних місць в теорії конфліктно керованих процесів займають задачі втечі та пересліду- вання. Вони є актуальними як з точки зору практичних застосувань, так і в теоретичному аспекті. Задачі втечі та переслідування розділяються на задачі степені та якості. В задачах степені вимагається знайти найкращі стратегії поведінки агентів (переслідувача та цілі), траєкторії руху, ціну процесу. В задачах якості необхідно встановити, з яким результатом закінчиться процес, причому вважається, що можливий один із кількох резуль- © С.В. Пашко, 2022 ISSN 1727-4907. Проблеми програмування. 2022. № 3-4. Спеціальний випуск 479 Прикладне програмне забезпечення татів. Наприклад, вимагається дати відповідь на запитання, чи може переслідувач захопити ціль до певного моменту часу, або чи може він захопити ціль взагалі. Крім того, ці задачі можна розділити на два класи. В за- дачах першого класу агенти переміщуються в деякому многовиді, наприклад, в евклідовій площині. Такі задачі називаються неперервними задачами переслідування та втечі; багато з них вивчалися в роботах [1 – 9]. В за- дачах другого класу агенти рухаються вздовж ребер заданого графа. Такі задачі, що називаються дискретними задачами переслідування, вивчалися в працях[10, 11]. У даній роботі задачі переслідування розглядаються як неперервні задачі степені. Розглядаються стра- тегії переслідування цілі одним переслідувачем із простим рухом. Визначено поняття оптимальної стратегії переслідування. Наводиться доведення оптимальності стратегії паралельного зближення та погонної стратегії. На основі числового моделювання окреслено множини задач, для яких стратегія паралельного зближення пере- вершує погонну стратегію або навпаки. 1. Оптимальні стратегії переслідування Розглянемо задачу переслідування однієї цілі одним переслідувачем, що вивчається в теорії диференці- альних ігор. Вважаємо, що переслідувач прагне мінімізувати час захоплення цілі, а ціль прагне максимізувати його. Нехай вектор 0X n-вимірного дійсного евклідового простору nE визначає місцезнаходження цілі E, а век- тор 1X визначає місцезнаходження переслідувача P. Вектори 10,VV розмірності n означають швидкості агентів E та P відповідно. Вектори ii VX , залежать від часу, тобто ).(),( tVVtXX iiii Простір nE складається з n-вимірних векторів ),...,,( 21 nxxxX з дійсними компонентами; вважаємо, що .2 n Норма вектора X визначається формулою ,, 2/1XXX де n i ii yxYX 1 , – скалярний добу- ток векторів ),...,,( 21 nxxxX та ).,...,,( 21 nyyyY Процес починається в момент часу .0t Рух агентів вважається простим, тобто в будь-який момент часу агент може вибрати довільний вектор швидкості руху, норма якого не більша заданої величини. Крім того, швидкості Vi вважаються кусково-неперервними функціями від часу. Це означає, що функції )(tVi у кожному обмеженому часовому проміжку мають не більше скінченого числа точок розриву першого роду. Рівняння руху агентів мають вигляд )()( tVtX ii , .1,0i (1) Кожне із співвідношень (1) виконується в кожний момент, в який відповідна швидкість є неперервною функці- єю часу. Вважаємо, що в будь-який момент часу виконуються нерівності ,1,0, iwV ii а також, що переслідувач може рухатися швидше за ціль, тобто .10 ww Тут 0w , 1w – максимальні величини швидкостей, .00w Позначимо ),( 10 XXX фазовий вектор, що містить координати агентів. Вважаємо, що швидкість цілі залежить тільки від часу та фазового вектора, тобто має вигляд ),(0 XtV а швидкість переслідувача залежить ще й від швидкості цілі та має вигляд ).,,( 01 VXtV Функцію ),(0 XtV назвемо стратегією цілі, а функцію ),,( 01 VXtV – стратегією переслідувача. Нехай 0t такий момент часу, що протягом часового проміжка ],0[ t задіяні деякі стратегії втечі та переслідування, 0X – задане початкове значення фазового вектора. Розв’язком системи (1) на проміжку ],0[ t вважається функція ],,0[),( tX яка задовольняє наступні умови. 1) Функція ],,0[),( tX неперервна на ],,0[ t )0( 0XX . 2) У всі моменти часу τ з проміжку ],,0[ t в які функція )))(,(),(,()( 011 XVXVV неперервна, існує похідна за часом )(1X та виконується рівність ).()( 11 VX Аналогічно в усі моменти ],,0[ t в які функція ))(,()( 00 XVV неперервна, існує похідна за часом )(0X та виконується рівність ).()( 00 VX У точках 0 та t маються на увазі похідні справа і зліва відповідно. Вважаємо, що агенти застосовують сумісні стратегії, тобто такі, що існує єдиний розв’язок )(tX сис- теми (1), що задовольняє заданим початковим умовам, а вектори швидкостей )),(,(0 tXtV )))(,(),(,( 11 tXtVtXtV є кусково-неперервними функціями часу. Прикладами сумісних стратегій є кусково-постійні стратегії Карліна [1]. Стратегію переслідувача ),,( 01 VXtV позначимо Ф, стратегію цілі ),(0 XtV позначимо . Нехай величина ),),0((XT означає час захоплення цілі, тобто перший момент часу, в який координати цілі співпадають з координатами переслідувача. Оптимальним часом втечі назвемо число ).,),0((infsup0 XTt Тут )0(X – початковий фазовий вектор, inf обчислюється за всіма стратегіями Ф такими, що пара ),( су- місна, а sup обчислюється за всіма стратегіями такими, що існує хоча б одна сумісна пара ),( . Назвемо стратегію оптимальною стратегією втечі, якщо для кожної стратегії Ф виконується нерівність .),),0(( 0tXT 480 Прикладне програмне забезпечення Оптимальним часом переслідування назвемо число ).,),0((supinf1 XTt Тут sup обчислюється за всіма стратегіями такими, що пара ),( сумісна, а inf обчислюється за всіма стра- тегіями Ф такими, що існує хоча б одна сумісна пара ),( . Назвемо стратегію оптимальною стратегією переслідування, якщо для кожної стратегії виконується нерівність .),),0(( 1tXT Якщо пара оптимальних стратегій , сумісна і ,10 tt то маємо співвідношення ),,),0((),),0((),),0(( XTXTXT (2) тобто пара стратегій , утворює точку рівноваги. Дійсно, позначимо .0tU З визначення , ви- пливає ,),),0(( UXT ,),),0(( UXT тому .),),0(( UXT Маємо ),,),0((),),0(( XTUXT звідки випливає (2). Число U називається ціною гри. 2. Стратегія паралельного зближення та погонна стратегія Нехай агенти P та E рухаються з максимальними швидкостями у напрямку ,01XX де вектор 0X містить координати цілі, а вектор 1X – координати переслідувача. Ця пара оптимальних стратегій утворює точку рівно- ваги. Точка захоплення X лежить на прямій 01XX на відстані Uw0 від точки ,0X де U – ціна гри. Якщо агент P рухається з максимальною швидкістю у напрямку ,01XX стратегія переслідування називається погонною стратегією. Нехай )(tdd – відстань між агентами. Ціна гри )(tU в момент t обчислюється за формулою .)()( 01 ww tdtU Припустимо, в деякий момент 0t швидкості 0V , 1V є неперервними вектор-функціями від часу. Похідна )(tU обчислюється за формулою ; , )( 01 01 ww NVV tU (3) тут ./ 1010 XXXXN Якщо ,0,1)( ttU то ціль буде захоплено за час, що не перевищує ціну гри. Дійсно, нехай T – момент захоплення цілі. Маємо ,)1()()0( 00 TdtdttUU TT тобто ).0(UT Для будь-якого вектора 0V величина )(tU приймає мінімальне значення за умови, що переслідувач ви- бирає вектор швидкості за формулою ,11 NwV тобто використовує погонну стратегію. Погонна стратегія опти- мальна, оскільки для неї справедливі співвідношення .1 , )( 01 01 ww NVw tU Із співвідношення (3) випливає, що умова 1)(tU рівносильна нерівності ., 0101 wwNVV (4) Обираючи в кожний момент величину швидкості 1V з умови (4), агент P використовує оптимальну стратегію переслідування. Час переслідування в такому випадку не більший за ціну гри. Розглянемо іншу стратегію переслідування – стратегію паралельного зближення. Переслідувач, знаючи швидкість цілі в даний момент часу, вважає цю швидкість постійною та обчислює на лінії руху цілі точку захоплення, в якій він може догнати його, рухаючись із постійною максимальною швидкістю. В поточний момент часу вектор швидкості переслідувача направлений на точку захоплення, а величина швидкості максимальна. Припустимо, переслідувач застосовує стратегію паралельного зближення (рис. 1). Прямі AB і AE пара- лельні прямим EP та BQ відповідно, вектор PQ дорівнює різниці швидкостей 01 VV . Маємо 481 Прикладне програмне забезпечення ;,, 0101 wwPQNPQNVV остання нерівність випливає з нерівності трикутника. Співвідношення (4) (а разом з ним і нерівність 1)(tU ) виконується. Тому стратегія паралельного зближення є оптимальною, тобто забезпечує захоплення цілі за час, що не перевищує ціну гри. E A V0 N P B V1 Q I Рис. 1. Застосування стратегії паралельного зближення Отже, погонна стратегія та стратегія паралельного зближення є оптимальними. Зауважимо, що іс- нує множина оптимальних стратегій, які займають проміжне положення. Швидкість 1V погонної стратегії об- числюється за формулою ,/11 PEPEwV а швидкість 1V стратегії паралельного зближення – за формулою PIPIwV /11 (рис. 1). Легко довести, що будь-яка стратегія переслідування, швидкість якої обчислюється за формулою , /)1(/ /)1(/ 11 PIPIPEPE PIPIPEPE wV де ,10 є оптимальною. Зауважимо, що цілі не завжди застосовують оптимальні стратегії втечі, оскільки окрім задачі уникнути захоплення вони мають інші завдання. Однак описані стратегії переслідування, що обгрунтовані за допомогою теорії диференціальних ігор, виявляються дієвими для широкого класу траєкторій втечі та застосовуються на практиці. Значна частина матеріалу даного та попереднього розділів міститься в роботі [9]. 3. Результати числових розрахунків Розглянемо процес переслідування на площині. Вважаємо, що в момент часу t = 0 переслідувач знахо- диться у початку координат, а ціль знаходиться у точці A. У прикладах, зображених на рис. 2 – 5, вважається, що 5000w м/с, 6001w м/с, величини 21, xx вимірюються в кілометрах. У даному розділі ціль вважається захопленою, якщо відстань від неї до переслідувача не перевищує трьох метрів. Траєкторії погонної стратегії та стратегії паралельного зближення позначаються відповідно 1T та ,2T а точки захоплення цілі позначаються відповідно трикутником та колом. Розглянемо приклади переслідування. Приклад 1. Нехай ціль рухається паралельно осі абсцис із постійною швидкістю, величина якої дорівнює .0w На рис. 2 зображена траєкторія руху цілі та дві траєкторії переслідування, одна з яких належить погонній стратегії, інша – стратегії паралельного зближення. Час захоплення для погонної стратегії становить 64.7 секунди, для стратегії паралельного зближення – 41.1 секунди. Очевидно, у ви- падку прямолінійного та рівномірного руху цілі стратегія паралельного зближення перевершує погонну стратегію. Приклад 2. Траєкторія цілі складається з дуг кола радіусом 4.6 км з центральним кутом 3/2 (рис. 3). Час захоплення для погонної стратегії становить 41.5 секунди, для стратегії паралельного зближення – 21.3 секунди. Приклад 3. Траєкторія цілі являє собою синусоїду з амплітудою 3 км та періодом 10 км (рис. 4). Час захоплення для погонної стратегії становить 65.6 секунди, для стратегії паралельного зближення – 40.8 секунди. 482 Прикладне програмне забезпечення Рис. 2. Траєкторії руху цілі та переслідувача, приклад 1 Рис. 3. Траєкторії руху цілі та переслідувача, приклад 2 Рис. 4. Траєкторії руху цілі та переслідувача, приклад 3 483 Прикладне програмне забезпечення Приклад 4. Траєкторія цілі складається з дуг кола радіусом 4.6 км з центральним кутом 3/2 (рис. 5). Час захоплення для для погонної стратегії становить 56.0 секунди, для стратегії паралельного зближення – 67.3 секунди. Рис. 5. Траєкторії руху цілі та переслідувача, приклад 4 Опишемо числові експерименти, які дають змогу приблизно окреслити множини параметрів, для яких стратегія паралельного зближення перевершує погонну стратегію або навпаки. Вважаємо, що параметри задач переслідування відповідають наступним умовам: • }500,400,300{0w (м/с); • ,01 www де }300,200,100{w (м/с); • ),,( 21 aaA де }10,0,10{1a (км), }20,10,0{2a (км); • лінія руху цілі може бути або синусоїдою, або складатися з дуг кола. У випадку синусоїди її амп- літуда приймає значення з множини }3,2,1{ (км), а період може бути одним з чисел }20,10,7.6{ (км). У випадку дуг радіус кола приймає значення з множини }6.4,6.3,6.2{ (км), а центральний кут може бути одним з чисел };,3/2,3/{ • початкова фаза лінії руху цілі обирається одним із двох способів. Комбінуючи параметри всіма можливими способами, отримуємо 291623 26 задач переслідування. Серед них є 32423 24 таких задач, що в момент часу t = 0 ціль знаходиться на початку координат. Час за- хоплення в таких задачах дорівнює нулю, тому вони не розглядаються. Залишається 25923242916 задач, множину яких позначимо M. У кожній задачі з множини M застосовувалися стратегія паралельного зближення та погонна стратегія. Множина M розбивається на дві множини 21, MM так, що в 1,M входять усі такі задачі, що точка A, в якій знаходиться ціль у початковий момент t = 0, лежить на осі абсцис справа від початку координат, а в М2 входять усі інші задачі множини M. Множини М1 та М2 містять відповідно 324 та 2268 задач. У кожній задачі ціль рухається вздовж відповідної кривої зліва направо (рис. 2 – 5). На множині задач М1 в середньому краще працює погонна стратегія, на множині М2 – стратегія па- ралельного зближення. На множині М1 погонна стратегія має середнє значення часу захоплення цілі 52,7 секунди, а стратегія паралельного зближення – 55,4 секунди; погонна стратегія захоплює ціль раніше, ніж стратегія паралельного зближення у 216 випадках з 324. На множині М2 стратегія паралельного зближення має середнє значення часу захоплення цілі 38,6 секунди, а погонна стратегія – 47,6 секунди; стратегія па- ралельного зближення захоплює ціль раніше, ніж погонна стратегія у 2161 випадку з 2268. Процес переслі- дування в задачі з множини М1 зображений на рис. 5, на рис. 2 – 4 зображені процеси в задачах з множини М2. Отже, в задачах типу М1 доцільно використовувати погонну стратегію, в задачах типу М2 – стратегію паралельного зближення. Обрані параметри руху агентів приблизно відповідають параметрам руху сучасних бойових літаків та засобів протиповітряної оборони; абсолютна величина прискорення цілі не перевищує 10g, де g=9,81 м/с2. Оскільки рух переслідувача вважається простим, дозволяється будь-яка абсолютна величина його прискорен- ня. У разі застосування стратегії паралельного зближення ця величина незначно відрізняється від абсолютної величини прискорення цілі; якщо застосовується погонна стратегія, абсолютна величина прискорення переслі- дувача може бути значно більшою. Висновки У роботі розглядаються стратегії переслідування цілі з простим рухом. Визначено поняття оптимальної стратегії переслідування. Доведено оптимальність стратегії паралельного зближення та погонної стратегії. На основі числового моделювання окреслено множини задач, для яких стратегія паралельного зближення пере- вершує погонну стратегію або навпаки. Література 1. Айзекс Р. Дифференциальные игры. Москва: Мир, 1967. 480 с. 2. Чикрий А.А. Конфликтно управляемые процессы. К.: Наук. думка, 1992. 384 с. 3. Петросян Л.А., Зенкевич Н.А., Шевкопляс Е.В. Теория игр. Санкт-Петербург: БХВ-Петербург, 2012. 424 с. 4. Рихсиев Б.Б. Дифференциальные игры с простыми движениями. Ташкент: ФАН, 1989. 232 с. 484 Прикладне програмне забезпечення 5. Петросян Л.А., Рихсиев Б.Б. Преследование на плоскости. Москва: Наука, 1991. 91 с. 6. Пашко С.В. Максимальное время преследования для стратегии параллельного сближения в случае равенства скоростей игроков. Компьютерная математика: сб. науч. тр. К.: Институт кибернетики имени В.М. Глушкова НАН Украины. 2014. № 1. С. 140 –149. 7. Пашко С.В., Яловец А.Л. Максимальное время преследования для стратегии параллельного сближения. Проблемы программирова- ния. 2014. № 4. С. 78–93. 8. Пашко С.В. Побудова стратегій переслідування з використанням функцій Ляпунова. Проблеми програмування. 2017. № 3. С. 194 –211. 9. Пашко С.В. Математичні методи вибору оптимальних рішень в системах, що складаються з раціональних агентів: дисертація на здо- буття наукового ступеня д-ра фіз.-мат. наук: 01.05.01. Київ, 2018. 322 с. 10. Parsons T.D. Pursuit-evasion in a graph. Theory and applications of graphs. 1978. P. 426–441. 11. Borie R.B., Craig A.T., Koenig S. Algorithms and Complexity Results for Pursuit-Evasion Problems. IJCAI-09. 2009. P. 59–66. References 1. Isaacs R. (1999). Diff erential Games. New York: Dover Publications. 2. Chikrii A.A. (1992). Confl ict-Controlled Processes. Kyiv: Nauk. Dumka. (In Russian). 3. Petrosyan L.A., Zenkevich N.A., Shevkoplyas E.V. (2012). Game theory. St. Petersburg: BHV-Petersburg. (In Russian). 4. Rikhsiev B.B. (1989). Simple Motion Diff erential Games. Tashkent: FAN. (In Russian). 5. Petrosyan L.A., Rykhsiev B.B. (1991) Pursuit on the plane. Moscow: Nauka. (In Russian). 6. Pashko S.V. Maximal time of pursuit for the strategy of parallel approach in case of equal speeds. Computer Mathematics. Kyiv: Institute of Cybernetics of the NAS of Ukraine. 2014. № 1. P. 140 – 149. (in Russian). 7. Pashko S.V., Yalovets A.L. Maximal Time of Pursuit for the Strategy of Parallel Approach. Problems in Programming. 2014. № 4. P. 78 – 93. (In Russian). 8. Pashko S.V. Construction of pursuit strategies using Lyapunov functions. Problems in Programming. 2017. № 4. P. 194 – 211. (In Ukrainian). 9. Pashko S.V. (2018). Mathematical methods of choosing optimal solutions in systems consisting of rational agents: dissertation for obtaining the scientifi c degree of Doctor of Sciences in Physics and Mathematics: 01.05.01. Kyiv. (In Ukrainian). 10. Parsons T.D. Pursuit-evasion in a graph. Theory and applications of graphs. 1978. P. 426–441. 11. Borie R.B., Craig A.T., Koenig S. Algorithms and Complexity Results for Pursuit-Evasion Problems. IJCAI-09. 2009. P. 59 – 66. Одержано 25.08.2022. Про автора: Пашко Сергій Володимирович, доктор фізико-математичних наук, провідний науковий співробітник. Кількість наукових публікацій в українських виданнях – 38. Кількість наукових публікацій в зарубіжних виданнях – 2. Індекс Гірша в SCOPUS – 3. http://orcid.org/0000-0002-0453-4128. Місце роботи автора: Інститут програмних систем НАН України, 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (38)(044) 526 60 25, 068-385-34-66 (моб.) E-mail: pashko55@yahoo.com Прізвища та ініціали автора і назва доповіді українською мовою: Пашко С.В. Моделювання оптимальних стратегій переслідування з простим рухом Прізвища та ініціали автора і назва доповіді англійською мовою: Pashko S.V. Simulation of optimal pursuit strategies with simple motion

Моделювання оптимальних стратегій переслідування з простим рухом

Репозитарії

Схожі ресурси