Construction of pursuit strategies with using Lyapunov functions

This paper is concerned with differential pursuit-evasion games, in which several agents chase one. The time of capture of a target is used as the criterion. The motion of agents is simple one, the velocities are piecewise-continuous. The function that specifies the maximal time of capture of the ta...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Pashko, S.V.
Формат:	Стаття
Мова:	Українська
Опубліковано:	PROBLEMS IN PROGRAMMING 2018
Теми:	pursuit-evasion game agent strategy of parallel approach Lyapunov function maximal time of pursuit UDC 518.9
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/305
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

_version_	1859502764364660736
author	Pashko, S.V.
author_facet	Pashko, S.V.
author_sort	Pashko, S.V.
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
collection	OJS
datestamp_date	2024-04-28T11:48:08Z
description	This paper is concerned with differential pursuit-evasion games, in which several agents chase one. The time of capture of a target is used as the criterion. The motion of agents is simple one, the velocities are piecewise-continuous. The function that specifies the maximal time of capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach in the following sense. Maximal time of pursuit for the new strategy is not more than maximal time of pursuit for the strategy of parallel approach; at the same time there are many games, for which maximal time of pursuit for the new strategy is less than for the strategy of parallel approach. In case of pursuit-evasion game on a plane we find explicit form of Lyapunov function and calculate velocities of pursuers using the gradient of this function. Numerical examples show that such velocities of pursuers reduce the maximal time of pursuit. In case of pursuit-evasion game in a multidimensional Euclidean space, Lyapunov function is equal to an optimal value of an objective function of appropriate linear programming problem. The velocities of pursuers are calculated with using the gradient of this function.Problems in programming 2017; 3: 194-211
first_indexed	2025-07-17T09:34:09Z
format	Article
fulltext	Методи та засоби комп'ютерного моделювання © С.В. Пашко, 2017 194 ISSN 1727-4907. Проблеми програмування. 2017. № 3 УДК 518.9 С.В. Пашко ПОБУДОВА СТРАТЕГІЙ ПЕРЕСЛІДУВАННЯ З ВИКОРИСТАННЯМ ФУНКЦІЙ ЛЯПУНОВА Розглядаються диференційні ігри переслідування, в яких кілька агентів доганяють одного. Критерієм виступає час захоплення цілі. Для відомої стратегії паралельного зближення описана функція, що за- дає максимальний час переслідування. Ця функція використовується як функція Ляпунова для побу- дови нової стратегії переслідування, що перевершує стратегію паралельного зближення в наступно- му сенсі. Максимальний час переслідування для побудованої стратегії не перевищує максимального часу для стратегії паралельного зближення; водночас існує значна кількість ігор, в яких максималь- ний час переслідування для нової стратегії виявляється меншим, ніж для стратегії паралельного зближення. Ключові слова: конфліктно керований процес, агент, стратегія паралельного зближення, функція Ляпу- нова, максимальний час переслідування Вступ В даній роботі розглядається задача переслідування одного втікача кількома переслідувачами в скінченновимірному дійсному евклідовому просторі. Критерієм виступає час захоплення цілі, який перес- лідувачі намагаються мінімізувати, а вті- кач – максимізувати. Рух агентів вважаєть- ся простим, швидкості вважаються куско- во-неперервними за часом. Останнім часом проводяться роботи з створення багатоагентних роботизованих систем захисту, систем безпілотних апара- тів тощо, тому задача, що розглядається, є актуальною. В роботах [1, 2] задача пересліду- вання вирішена за умови, що втікач не на- лежить внутрішній частині опуклої оболо- нки, яка утворена переслідувачами. Знай- дено оптимальні стратегії переслідування та ціна гри. Доведено, що всі агенти з пос- тійними максимальними швидкостями ру- хаються до деякої точки, де відбувається захоплення цілі. В даній роботі розгляда- ються здебільшого ігри (іншими словами – конфліктно керовані процеси), в яких уті- кач належить внутрішній частині опуклої оболонки, що утворена переслідувачами. Оптимальні стратегії відомі не для всіх та- ких процесів. Побудована в даній роботі ефекти- вна стратегія переслідування суттєво спи- рається на класичну стратегію паралельно- го зближення. Нагадаємо, що стратегія па- ралельного зближення полягає у наступ- ному [2]. Кожен переслідувач, знаючи швидкість втікача в даний момент часу, вважає цю швидкість постійною та обчис- лює на лінії руху втікача точку захоплен- ня, в якій він може догнати його, рухаю- чись з постійною максимальною швидкіс- тю. В поточний момент часу вектор швид- кості переслідувача направлений на точку захоплення, а величина швидкості макси- мальна. Якщо максимальні швидкості пе- реслідувача і втікача рівні, а точка захоп- лення не існує, переслідувач рухається па- ралельно втікачеві. В даній роботі максимальний час переслідування W для стратегії паралель- ного зближення, що залежить від коорди- нат агентів, використовується як функція Ляпунова для побудови стратегії переслі- дування, яка перевершує стратегію пара- лельного зближення в наступному розу- мінні. Для будь-якого конфліктно керова- ного процесу (з-поміж тих, що розгляда- ються) виконується нерівність ,WT  во- дночас для багатьох процесів справедливе співвідношення ;WT  тут T – максима- льний час переслідування для побудованої стратегії. В цій статті результати роботи [3] узагальнюються на випадок багатовимір- ного евклідового простору та на процеси з довільною кількістю переслідувачів. В роботі [4] доведено, що за умови рівності швидкостей всіх агентів, у випа- Методи та засоби комп'ютерного моделювання 195 дку, коли втікач оточений переслідувача- ми, ціль буде захоплена, якщо всі перес- лідувачі застосовують стратегію парале- льного зближення. В роботах [5, 6] також розглядається стратегія паралельного зближення, за допомогою якої вирішу- ються конфліктно керовані процеси якості та наводяться оцінки часу захоплення цілі. Детально стратегія паралельного зближення розглядається в [2]; відмічено, що в загальному випадку ця стратегія не є оптимальною. В роботах [1, 2, 7, 8] побу- довано оптимальні стратегії пересліду- вання кількома агентами одного втікача, але тільки за деяких умов щодо розташу- вання агентів у просторі або їх кількості. Застосування функцій Ляпунова для керу- вання динамічними системами розгляда- ється в роботі [9]. Стратегії, максимальний час переслідування та функції Ляпунова Нехай у точці )(00 tXX  n- вимірного дійсного евклідового простору nE в момент часу t знаходиться втікач E, а в точках )(tXX ii  знаходяться переслі- дувачі ,iP .,...,2,1 ki  Вектори )(tVV ii  розмірності n, ,,...,1,0 ki  означають швидкості агентів (нульове значення інде- ксу i відноситься до втікача E). Простір nE складається з n- вимірних векторів ),...,,( 21 nxxxX  з дій- сними компонентами, .2  n Норма вектора X визначається формулою ,, 2/1 XXX  де    n i ii yxYX 1 , – скалярний добуток векторів ),...,,( 21 nxxxX  та Y  1 2( , ,..., ).ny y y Процес переслідування починається в момент часу .0t Рівняння руху агентів мають вигляд ,ii VX  .,...,2,1,0 ki  (1) Кожне із співвідношень (1) виконується в кожен момент, в який відповідна швид- кість є неперервною функцією від часу. Вважаємо, що виконуються обме- ження ,0 ii wV  ,,...,1,0 ki  де  iw0 – максимальна величина швидкості, а також нерівності ,0 iww  .,...,2,1 ki  (2) Нехай ))(),...,(),(()( 10 tXtXtXtX k – фазовий вектор, що містить координати агентів. Вважаємо, що швидкість 0V аген- та E має вигляд ));(,(0 tXtV назвемо цю швидкість стратегією втікача та позначимо . Вважаємо, що швидкість iV агента iP має вигляд )),(,(),(,( 0 tXtVtXtVi };,...,2,1{ ki назвемо цю швидкість стратегією i-го пе- реслідувача та позначимо .i Стратегією переслідування назвемо вектор ).,...,,( 21 k Швидкості ,,...,2,1),( kitVi  вва- жаються кусково-неперервними функція- ми від часу. Це означає, що в кожному об- меженому часовому проміжку існує не бі- льше скінченого числа точок розриву пер- шого роду. Нехай 0il – задані числа, ,)()()( 0 tXtXtd ii  ,0t .,...,2,1 ki  Визначимо функцію )(td наступним чи- ном: ,0)( td якщо для деякого значення },...,2,1{ ki справедлива рівність 0)( tdi або виконується нерівність ;)( ii ltd  1)( td в протилежному випадку. Часом захоплення цілі назвемо величину }.0)(inf{),),0((  tdtXT Втікач E намагається максимізувати вели- чину ),,),0(( XT а переслідувачі нама- гаються її мінімізувати. Максимальним часом пересліду- вання для стратегії  назвемо величину Методи та засоби комп'ютерного моделювання 196 ).,),0((sup)),0((   XTXT З двох стратегій переслідування більш ефективною вважаємо ту, для якої макси- мальний час переслідування менший. Вважаємо, що ,)0()0( 0 ii lXX  .,...,2,1 ki  Для таких значень i, що ,0wwi  додатко- во вимагаємо виконання нерівності .0il Розглянемо питання про існування та властивості розв’язку системи рівнянь (1). Нехай 0T такий момент часу, що на протязі відрізка ],0[ T задіяні деякі страте- гії втечі та переслідування, ].,0[ Tt  Апрі- орі слід вважати, що фазовий вектор )(tX може не існувати або може виявитися не єдиним. Визначимо функцію )(t наступ- ним чином:        .)(векторівмножинаіснує),( ),(векторєдинийіснує),( ,існуєне)(, )( tKtK tXtX tX t Тут множина )(tK складається з векторів )(tX та містить більше одного елемента. Припустимо, швидкість втікача ви- значається функцією ),())(,( 00 tVttV  а швидкості переслідувачів визначаються функціями ),()))(,(),(,( 0 tVttVttV ii  .,...,2,1 ki  Вважаємо, що швидкості виби- раються вказаним способом у кожен мо- мент часу, і ці швидкості є векторами дій- сного n-вимірного евклідового простору .nE Також вважаємо, що функції ,,...,1,0),( kitVi  є кусково-неперервни- ми. Звідси випливає, що для кожного },...,1,0{ ki та для кожного t існує єдине значення  t iii dVXtX 0 ,)()0()(  причому функції )(tX i абсолютно непере- рвні [10]. Тому в кожен момент часу існує єдине значення фазового вектора )).(),...,(),(()( 10 tXtXtXtX k Очевидно, )(tX – єдиний розв’язок системи (1), що задовольняє заданим початковим умовам. Отже, справедлива теорема. Теорема 1. Нехай на проміжку ],0[ T швидкості агентів існують та є кус- ково-неперервними функціями від часу. Тоді система диференційних рівнянь (1) має єдине рішення ],,0[),( TttX  що за- довольняє заданим початковим умовам. Це рішення є абсолютно неперервною функ- цією від часу. Як бачимо, за умови існування та кускової неперервності швидкостей для всіх ],0[ Tt  виконується рівність ),()( tXt  тобто функція )(t не прий- має значень  або ).(tK Тому можна вва- жати, що швидкості визначаються вираза- ми )),(,(0 tXtV ))).(,(),(,( 0 tXtVtXtVi Далі замість виразу ))(,(0 tXtV будемо вживати ),(0 tV замість виразу )))(,(),(,( 0 tXtVtXtVi – ).(tVi Прикладами кусково-неперервних стратегій можна вважати кусково-постійні стратегії Карліна [1]. Стратегії переслідування, побудо- вані далі, засновані на використанні фун- кції Ляпунова ).(XW Нехай функція ),(XW визначена на фазовому просторі або на його підмножині, в якій лежать тра- єкторії фазової точки, приймає скінчені дійсні значення та задовольняє наступним умовам: 1) функція )(XW обмежена знизу; 2) існує така стратегія пересліду- вання, що для будь-якої стратегії втечі в кожен момент часу ,0t що не перевищує часу захоплення цілі, виконується нерів- ність ,)0()( ctWtW  де 0c – констан- та, )),(()( tXWtW  )).0(()0( XWW  Умови 1) – 2) гарантують існування стратегії переслідування, яка забезпечує захоплення цілі за скінчений час. Дійсно, нехай ).(inf ~ XWW X  Із співвідношення ctWW  )0( ~ випливає, що час захоплен- ня цілі не перевищує величини . ~ )0( c WW   Методи та засоби комп'ютерного моделювання 197 Вважаємо, що в кожен момент часу переслідувачі вибирають свою швидкість таким чином, щоб функція )(tW зменшу- валась якомога швидше. Найкращою фун- кцією Ляпунова )(XW слід вважати ціну процесу (гри). Якщо ця функція невідома, слід знайти функцію Ляпунова, що забез- печує якомога менший максимальний час переслідування, та скористатись нею для побудови стратегії переслідування. Максимальний час переслідування для стратегії паралельного зближення Припустимо, всі переслідувачі за- стосовують стратегію паралельного збли- ження. Тоді швидкості переслідувачів )(tVi обчислюються за формулами ,)()()( 0 ii NttVtV  ,,...,2,1 ki  ,0t (3) де , )0()0( )0()0( 0 0 XX XX N i i i     iNtVt ),()( 0 .)(),( 2 0 22 0 tVwNtV ii  Функція )(0 tV вважається кусково- неперервною. Це призводить до того, що функції ),(tVi ,,...,2,1 ki  також є кусково- неперервними. Тому з теореми 1 випливає, що система рівнянь (1) має єдине рішення, яке задовольняє заданим початковим умо- вам. Це рішення є абсолютно неперервною функцією. Позначимо conv },...,,{ 21 kXXX опуклу оболонку точок .,...,, 21 kXXX Не- хай int Z – внутрішня частина множини Z. Розглянемо випадок, коли точка розташу- вання втікача 0X в початковий момент на- лежить внутрішності опуклої оболонки точок ,,...,, 21 kXXX тобто виконується умова 0X int conv }.,...,,{ 21 kXXX (4) Стратегія паралельного зближення має наступну властивість. Кути між векто- рами  iXX 0 та  jXX 0 на протязі конфлікт- ного процесу залишаються постійними, оскільки прямі )()(0 tXtX q і )0()0(0 qXX паралельні для всіх моментів t, що не пе- ревищують часу закінчення процесу, kq ,...,2,1 [2]. Тому з того, що умова (4) виконується в початковий момент, випли- ває, що ця умова виконується на протязі всього процесу. З теореми 1 [11] випливає існуван- ня оптимальної стратегії втечі  ,...,,( * 2 * 1 tt ),,...,,, ** 2 * 1 * kk ZZZt де величини *, ii Zt означають наступне. Представимо проміжок ),,0[ T де     k i itT 1 – час захо- плення цілі, у вигляді об’єднання k промі- жків, що не перетинаються, .),[),0[ 1 )2()1( k i iiT     Довжина проміжка ),[ )2()1( ii  дорівнює ,* it а вектор швидкості стратегії втечі  на проміжку ),[ )2()1( ii  дорівнює ,* 0 iZw де ,1* iZ ,,...,2,1 ki  n-вимірні вектори * iZ не змінюються з часом. Теорема 2 [11] стверджує, що в ко- жен момент часу ),0( Tt такий, що оп- тимальна стратегія )( 0 tV неперервна, ви- конується рівність .)( 0 * 0 wtV  З роботи [11] випливає, що з будь- якою наперед заданою точністю можна отримати оптимальну стратегію втечі, ви- рішивши задачу лінійного програмування наступного вигляду max, }{   RR Rt (5) , }{ ii RR RiR ldtu   ,,...,2,1 ki  (6) ,0Rt }.{RR (7) Тут Rt – змінні величини, R – )1( n - вимірний вектор, }{R – скінчена множина таких векторів, визначена в [11], величини iRu визначені в [11], .)0()0( 0XXd ii  Методи та засоби комп'ютерного моделювання 198 За умови рівності швидкостей всіх агентів у роботі [12] доведена теорема, що дозволяє точно визначити оптимальну стратегію втечі, використовуючи оптима- льне рішення наступної задачі лінійного програмування: max, }{ 2 1    II s Ist (8) , }{ 2 1 ii II s IsiIs ldtu     ,,...,2,1 ki  (9) ,0Ist }{II  , .2,1s (10) Тут Ist – змінні величини, },...,,{ 121  niiiI – підмножина множини },...,2,1{ k така, що система векторів },...,,{ 121   niii NNNH лінійно незалежна, }{I – множина всіх та- ких підмножин, величини iIsu розрахову- ються за формулами       ,0,,,2 ,0,,0 IsiIsi Isi iIs NNNNw NN u ,,...,2,1 ki  },{II  ,2,1s де 21, II NN – вектори одиничної довжини, ортогональні кожному вектору системи H, причому .21 II NN  Розглянемо випадок, коли точка ро- зміщення втікача 0X не належить опуклій оболонці точок .,...,, 21 kXXX Нехай вико- нуються співвідношення 0X conv },,...,,{ 21 kXXX (11) ,0wwi  ,0il .,...,2,1 ki  (12) Позначимо iA сферу Аполлонія, що відноситься до пари агентів E, .iP Во- на являє собою геометричне місце точок, в яких можуть зустрітися агенти E і ,iP якщо вони рухаються рівномірно та пря- молінійно з максимальними швидкостя- ми. Нехай iC – замкнутий шар Аполло- нія, що відповідає сфері .iA Тоді  k i iCC 1  – множина таких точок просто- ру ,nE до яких агент E встигне дійти не пізніше за кожного переслідувача. Внут- рішність множини C являє собою множи- ну точок, до яких втікач E встигне дійти раніше за будь-якого переслідувача. Не- хай CX  – найбільш віддалена точка від точки 0X з множини C, тобто для ко- жного CX  справедлива нерівність .00 XXXX  Припустимо, втікач застосовує стратегію, яка полягає в тому, що він постійно рухається з максимальною швидкістю в напрямку точки X (що вирахувана в момент 0t ). До моменту часу 00 / wXX  захоплення відбутися не може, тому для будь-якої стратегії переслідування максимальний час пере- слідування )),0(( XT задовольняє не- рівності ./)),0(( 00 wXXXT   (13) Справедлива наступна теорема. Теорема 2. За умов (11), (12) засто- сування стратегії паралельного зближення забезпечує захоплення цілі за час, що не перевищує величини ./ 00 wXX  Доведення цієї теореми грунтується на ідеях, які застосовані під час доведення теорем 6.1 та 9.1 роботи [2]. Відмінність полягає у тому, що в теоремі 9.1 побудова- на стратегія переслідування, яка дещо від- різняється від стратегії паралельного зближення, та використані інші класи до- пустимих швидкостей агентів. Якщо виконуються співвідношення (11), (12), то з теореми 2 та з оцінки (13) випливає наступне. Стратегія паралельно- го зближення є оптимальною, стратегія втечі агента E, яка полягає в прямоліній- ному русі з максимальною швидкістю у напрямку до точки ,X також є оптималь- ною, величина 00 / wXX  є ціною кон- фліктно керованого процесу. Методи та засоби комп'ютерного моделювання 199 Замінивши в рівняннях руху iX на ,0XX i  отримуємо систему рівнянь ,0VVX ii  ;,...,2,1 ki  (14) агент E постійно знаходиться в початку вибраної декартової системи координат, ).0,...,0,0()(0 tX Далі вважаємо, що вико- нуються рівняння (14); фазовим вектором вважаємо )).(),...,(()( 1 tXtXtX k Застосування функції Ляпунова в задачах переслідування на площині Розглянемо приклад застосування функції Ляпунова в задачах переслідуван- ня на площині. Нехай кількість пересліду- вачів дорівнює трьом та максимальні швидкості всіх агентів рівні, тобто вико- нуються умови ,3k ,2n .3210 wwwww  (15) Також вважаємо, що в початковий момент часу справедливе співвідношення (4), оскільки інакше у випадку рівних швидкостей неможливо гарантувати захо- плення цілі. Зауважимо, що за умови (4) оптимальні стратегії переслідування в за- гальному випадку в літературі не описані. Символами  ,, позначимо кути ,,, 302 XXX ,,, 103 XXX 201 ,, XXX відповідно. Маємо .2  Вважа- ємо, що   . З умови (4) випливають нерівності 0 ,   . Оптимальне зна- чення цільової функції задачі (8) – (10) по- значимо W. В роботі [12] доведена форму- ла , sinsin2 1 332211            ldldld w W (16) де .3,2,1,  iXd ii Величина W означає максимальний час переслідування для стратегії паралельного зближення. Очеви- дно, величина W є функцією від фазової точки X, ).(XWW  Використаємо цю функцію для побудови стратегії пересліду- вання. Якщо переслідувачі застосовують стратегію паралельного зближення, а вті- кач застосовує оптимальну стратегію вте- чі, розраховану на цей випадок, то викону- ється рівність .1)( tW Але якщо перес- лідувачі вибирають швидкості з умови мі- німуму величини )(tW і на деякому часо- вому проміжку похідна )(tW існує, вико- нується нерівність ,1)( tW поза цим проміжком використовується стратегія па- ралельного зближення, функція )(tW не- перервна, то максимальний час пересліду- вання буде меншим. За умови, що переслі- дувачі діють розумно, нерівність 1)( tW неможлива, оскільки вони можуть викори- стовувати стратегію паралельного збли- ження. На множині точок X, що задоволь- няють умові (4) і нерівностям ,ii lX  ,3,2,1i функція )(XW – кусково-гладка. Якщо фазова точка належить області гладкості, то швидкості переслідування, для яких величина )(tW приймає мініма- льне значення, легко розрахувати, вико- ристовуючи градієнт функції ).(XW В протилежному випадку для визначення швидкостей переслідування досить вирі- шити кілька простих екстремальних за- дач, по одній для кожної прилеглої облас- ті гладкості. Якщо точка ),0,0(0 X в якій зна- ходиться втікач, належить границі множи- ни conv },,,{ 321 XXX і виконуються нерів- ності ,3,2,1,  ilX ii то величина ),,( 321 XXXW приймає значення . За умови (4) справедливо співвідношення .),,( 321 XXXW Якщо стратегія перес- лідування така, що функція )(tW є незрос- таючою, то із справедливості умови (4) в початковий момент випливає її справедли- вість на протязі всього процесу. З цього випливає, що виконуються нерівності .,,0   Нехай .3,2,1),,(  iyxX iii За умов ,0   ,3,2,1,  ilX ii знай- демо градієнт   332211 ,,,,, yxyxyx WWWWWWG  Методи та засоби комп'ютерного моделювання 200 функції ),,,,,,( 332211 yxyxyxW використо- вуючи (16). Тут ii yx WW , − похідні функції W за змінними ii yx , відповідно. Маємо  2 3 2 2 2 322 , 1cos1sin XX XX          32 2 3232 2 3 2 3 2 2 2 2 XX yyxxyxyx . 2 32 23 32 3322 2 2 2 3 2 3 2 2 dd D XX yxyxyxyx    (17) Тут ,233223 yxyxD  Аналогічно отри- муємо ,sin 31 13 dd D  (18) де .133113 yxyxD  З (16) – (18) випливає формула . 2 23 3322 2 13 11 1 3             D ldld d D ld d w d W (19) З нерівностей   ,,0 випливає, що величини 13D і 23D не дорівнюють нулю. Нехай       .0,1 ,0,1 13 13 13 D D s З визначення 13D випливають формули ,/,/ 313113313113 xsyDysxD  за допомогою яких з (19) виводимо ,)(2 2 1113 1 1 1132 13 313 1                lddy d l xD wD ds Wx .)(2 2 1113 1 1 1132 13 313 1                lddx d l yD wD ds Wy Інші компоненти градієнта обчислюються подібним чином. В області гладкості функції )(XW знайдемо швидкості переслідувачів та вті- кача, для яких досягається мінімакс вели- чини ).(tW Нехай )(t – кут, який утво- рює з віссю абсцис вектор швидкості ),(0 tV )(ti – кути, що утворюють з віссю абсцис вектори швидкостей ),(tVi .3,2,1i Маємо )),(sin),()(cos()( 00 tttvtV  )),(sin),()(cos()( tttvtV iiii  .3,2,1i Тут ivv ,0 – величини швидкостей втікача та переслідувачів. Система рівнянь (14) набуває вигляду ,coscos 0  vvx iii  ,sinsin 0  vvy iii  .3,2,1i Позначимо ),,,( 321 vvvv  ).,,( 321   Маємо )(maxmin 0,, tW vv       3 1,, 0 maxmin i iyix vv yWxW ii       3 1 0 ,, coscosmaxmin 0 i iix vv vvW i      sinsin 0vvW iiyi        3 1,, sincosmaxmin 0 i iyixi vv ii WWv                   3 1 3 1 0 sincos i y i x ii WWv     3 1 sincos i iyixi ii WWv  .sincos 3 1 3 1 0            i y i x ii WWv  (20) Тут 0,,, vvii  – значення змінних, для яких досягається мінімакс. Позначимо , 2 3 1 2 3 1 0                    i y i x ii WW     , 22 ii yxi WW  .3,2,1i (21) З (20) випливає, що мінімакс досягяється за умов Методи та засоби комп'ютерного моделювання 201 ,3210 wvvvv  ,/cos 0 3 1     i xi W ,/sin 0 3 1     i yi W ,/cos ixi i W   ,/sin iyi i W   .3,2,1i Отже, для досягнення мінімаксу значення )(tW в момент часу t швидкості можна вибрати за формулами ,, 3 1 3 10 0            i y i x ii WW w V    .3,2,1,,  iWW w V ii yx i i  (22) Величина )(tW в такому випадку обчис- люється наступним чином .)( 3 1 0           i iwtW  (23) Легко довести, що в області гладкості фу- нкції )(XW справедливі нерівності .3,2,1),2/(1  iwi Отже, у формулах (22) знаменники ,3,2,1, ii більші нуля. В області гладкості функції )(XW компоненти її градієнта мають неперервні часткові похідні за фазовими змінними ,,,,,, 332211 yxyxyx а швидкість втікача вважається кусково-неперервною функці- єю від часу. Із співвідношень (14), (22) ви- пливають рівняння руху   .3,2,1,, 0  iVWW w X ii yx i i   (24) З теореми про існування та єдиність рі- шення нормальної системи диференційних рівнянь [13] випливає, що існує єдине не- продовжне рішення )(tX системи (24), що задовольняє заданим початковим умовам. Це рішення є неперервною функцією. Знайдемо швидкості переслідувачів та втікача, для яких досягається мінімакс величини ),(tW у випадку відсутності не- перервних часткових похідних, тобто у випадку, коли виконуються співвідношен- ня ,  або ,  або .  Нехай в деякій точці X фазового простору виконується співвідношення .  Тоді  ,,max 21 WWW  де , sinsin2 1 332211 1            ldldld w W . sinsin2 1 332211 2            ldldld w W Позначимо M множину точок X фазового простору, що задовольняють рівнянню ).()( 21 XWXW  Очевидно, .MX  В де- якій околиці точки X множина M являє собою гладку п’ятивимірну поверхню. Не- хай 1G та 2G – градієнти функцій 1W та 2W відповідно, H – вектор одиничної дов- жини, ортогональний до поверхні M в точ- ці .X Легко довести, що .21 GG  Очевид- но, ),( 21 GGzH  де z – дійсне число. Нехай ./)( 2121 GGGGH  Позначимо ),,,( 321 VVVV  ).,,( 0000 VVVV  Вважаючи вектор 0V постійним, вирішимо дві екстремальні задачі (25) і (26), та з двох оптимальних рішень виберемо краще для переслідувачів, тобто те, для якого значен- ня цільової функції менше. min,, 10 V GVV  ,0,0  HVV ,3,2,1,  iwVi (25) min,, 20 V GVV  ,0,0  HVV .3,2,1,  iwVi (26) Втікач повинен вибрати таку шидкість ,0V щоб після цього вирішення задач (25) та (26) давало якомога гірший результат для переслідування. Випадки   і   роз- глядаються аналогічно. Отже, для мно- жини фазових точок, які задовольняють нерівностям Методи та засоби комп'ютерного моделювання 202 ,ii lX  ,3,2,1i та умові (4), описана стратегія пересліду- вання, що грунтується на функції Ляпуно- ва ).(XW Назвемо цю стратегію .0 За досить загальних умов можна довести, що побудована швидкість переслідування )(tV є вимірною функцією. Однак вище стратегія переслідування ))(,(),(,()( 0 tXtVtXtVtV  визначена як така, що є кусково- неперервною функцією від часу. Опишемо одну з можливих кусково-неперервних стратегій переслідування. Якщо переслідувач в кожен момент часу рухається у напрямку втікача з мак- симальною швидкістю, стратегія переслі- дування називається погонною. Нехай 0 – константа. Скажемо, що в момент часу t  виконується умова H, якщо для кожного числа ),(  tt справедливе наступне твердження. Якщо на проміжку ),[  tt застосовуються стратегія 0 та будь-яка стратегія втечі і для всіх ),[  ttt виконуються нерів- ності ,,...,2,1,)( kiltX ii  то на цьому проміжку  функції )(tV та )(tW є непере- рвними у всіх точках t за винятком, мож- ливо, тих точок, в яких функція )(0 tV має розрив;  функції )(tV і )(tW допускають розриви тільки першого роду;  за умови існування )(tW вико- нується нерівність .1)( tW Тут величина )(tW  означає похідну спра- ва. Визначимо функцію )(t наступ- ним чином:       .випадкуіншомув1 ,істьсправедливавстановлен ачамипереслідувмоментвякщо,0 )( H t t Вважаємо, що рівність 0)( t тягне за собою справедливість H для моменту t. Очевидно, якщо )(tX належить області гладкості функції ),(XW права частина рівності (23) менша за 1 та виконуються нерівності ,)( ii ltX  ,,...,2,1 ki  то існує таке ,0 що в момент t виконується умова H; в такому випадку вважаємо, що переслідувачами встановлена справедли- вість умови H та .0)( t Стратегія переслідування 1 . Не- хай процес починається в момент часу 0t у фазовій точці ).0(X Виберемо .0t Нехай , – додатні числа, що є параметрами стратегії переслідування. У кожен момент часу t такий, що ,0)( tX i ,,...,2,1 ki  виконуються наступні дії: 1) Якщо виконуються нерівності ,)( ii ltX  ,,...,2,1 ki  переходимо до кроку 2). Переслідувачі, для яких ,)( ii ltX  обчислюють свої швидкості ),(tVi використовуючи погонну стратегію, всі інші переслідувачі для обчислення швидкості використовують стратегію па- ралельного зближення. Переходимо до кроку 7); 2) якщо ,tt  переходимо до кро- ку 5); 3) Нехай .tt  Якщо ,1)( t ви- бираємо  tt та переходимо до кроку 5), інакше переходимо до кроку 6); 4) нехай .tt  Якщо , 2 }0)(,\|sup{    ttt то вибираємо  tt та переходимо до кроку 5), інакше переходимо до кроку 6); 5) для обчислення швидкостей всіх переслідувачів використовуємо стра- тегію паралельного зближення. Переходи- мо до кроку 7); 6) для обчислення швидкостей всіх переслідувачів використовуємо стра- тегію 0 ; 7) застосовуємо швидкості перес- лідування ).(tVi Під час використання стратегії 1 на проміжку часу такому, що для всіх i Методи та засоби комп'ютерного моделювання 203 справедливі нерівності ,)( ii ltX  почер- гово застосовуються стратегії 0 та стра- тегія паралельного зближення; момент за- кінчення роботи останньої позначено .t Довжина часового проміжку застосування стратегії 0 не менша ,2/ а стратегії паралельного зближення – не менша  (окрім, можливо, останнього часового проміжку). Швидкість втікача вважається кусково-неперервною. Застосування стра- тегії 1 гарантує, що функції )(tV та )(tW також є кусково-неперервними. Як- що для деякого i виконується умова ,)( ii ltX  то i-й переслідувач використо- вує погонну стратегію; це призводить до того, що момент t є часом захоплення цілі за умови, що вектор швидкості втікача є неперервним та відмінним від )( )( tX tX w i i . Нехай використовується стратегія ,1 а процес починається в момент 0t з фазової точки ),0(X в якій функція )(XW є гладкою. Із співвідношення (23) випли- ває, що для досить малого числа 0 справедливе наступне. Якщо в нульовий момент часу виконується нерівність 1)0( W (беремо похідну справа), то не- рівність 1)( tW залишається справедли- вою на протязі деякого часового проміжку ),,0( 1t де .01 t Оскільки в інші моменти часу виконується нерівність 1)( tW (за винятком скінченого числа моментів, у яких похідна )(tW не існує), максималь- ний час переслідування буде меншим, ніж за умови використання стратегії паралель- ного зближення. Якщо процес починається з фазової точки ),0(X в якій функція )(XW є глад- кою, та виконується нерівність 1)0( W (мається на увазі похідна справа), то нері- вність 1)0( W виконується також для процесів, початкова фазова точка яких на- лежить деякому шару з центром в ).0(X Для всіх таких процесів стратегія 1 за- безпечує менший максимальний час пере- слідування, ніж стратегія паралельного зближення. Як показують приклади, поча- ткові фазові точки, що задовольняють вказаним умовам, існують. Оскільки для будь-якої максимальної швидкості w та для будь-якого набору чисел il кожен процес визначається своєю початковою фазовою точкою, можна сказати, що стра- тегія 1 забезпечує менший максималь- ний час переслідування у порівнянні зі стратегією паралельного зближення для множини процесів, міра Лебега яких дода- тня. Водночас доведена в наступному роз- ділі теорема 4 стверджує, що для всіх про- цесів стратегія 1 не гірша за стратегію паралельного зближення. Розглянемо приклади задач перес- лідування. Нехай ,1w в момент часу 0t переслідувачі 321 ,, PPP розташовані в точках ),200,300( ),300,300( )400,0(  відповідно, а втікач знаходиться на почат- ку координат. У початковій фазовій точці функція Ляпунова (16) є гладкою, її граді- єнт задається наведеними вище формула- ми. Обчислення показують, що в даній то- чці за умов 0321  lll справедливе співвідношення 237.1)0( W (тут )0(W − похідна справа функції )(tW для 0t ), у випадку 30321  lll виконується рів- ність ,229.1)0( W а у випадку 300321  lll справедлива рівність .469.1)0( W Ясно, що існує проміжок часу ),0( 1t такий, для якого 1)( tW та .01 t Тому максимальний час пересліду- вання для побудованої стратегії 1 за умови, що число 0 досить мале, мен- ший, ніж для стратегії паралельного збли- ження. В таблиці наведено приклади зна- чень величини )0(W для декількох почат- кових фазових точок, у кожній з яких фун- кція )(XW гладка. Вважаємо, що .0321  lll Для кожної початкової фазо- вої точки ),,,,,( 332211 yxyxyx з цієї таблиці величина )0(W менша за ,1 тому для кожного процесу, що починається з такої точки, побудована стратегія перевершує стратегію паралельного зближення. Методи та засоби комп'ютерного моделювання 204 Таблиця. Приклади значень величини )0(W Функції Ляпунова для задач переслідування в багатовимірному евклідовому просторі Нехай у n-вимірному евклідовому просторі k переслідувачів доганяють одно- го втікача. Вважаємо, що в початковий момент виконується умова (4) та максима- льні швидкості всіх агентів рівні, ....10 wwww k  Нехай W – оптимальне значення ці- льової функції задачі лінійного програму- вання (8) – (10). Величина W дорівнює максимальному часу переслідування для стратегії паралельного зближення. Ясно, що W є функцією від параметрів задачі лі- нійного програмування (8) – (10), які в свою чергу є функціями від координат фа- зової точки X, тому W є функцією від X, тобто ).(XWW  Виберемо функцію )(XW як функцію Ляпунова для того, щоб побудувати нову стратегію переслідуван- ня, що перевершує стратегію паралельного зближення. Нехай A – матриця розміру ;sr  yb, – вектори розмірності r; xc, – векто- ри розмірності s. Вважаємо, що ранг мат- риці A дорівнює r та виконуються умови ).0,...,0,0(,  brs Якщо вектор приймає участь в операціях з матрицями, він вважа- ється матрицею-стовпцем, вираз TA озна- чає транспоновану матрицю. Опорне рішення задачі лінійного програмування, яка зведена до канонічно- го виду, називається невиродженим, якщо воно має рівно r додатніх компонент [14] (вважаємо, що матриця обмежень A роз- міру sr  задовольняє наведеним вище умовам). Справедлива наступна теорема, що за змістом є близькою до теореми 3.9 роботи [15]. Теорема 3. Нехай для ,0AA  00 , ccbb  опорні оптимальні рішення  yx , відповідно прямої   ),,(0,,max cbAWxbAxxc x  та двоїстої   ),,(,min cbAWcyAyb T y  задач лінійного програмування невиро- джені. Тоді оптимальні рішення  yx , єдині та виконуються співвідношення 1x 1y 2x 2y 3x 3y )0(W 2 3 3 1 3 1 87.1 1 2 3 1 3 1 59.1 1 3 3 2 3 1 25.1 1 3 3 1 3 1 32.1 1 3 2 1 3 1 24.1 0 1 3 1 2 1 18.1 0 1 3 1 3 2 22.1 0 2 3 1 2 1 18.1 0 2 3 1 3 2 21.1 0 3 3 1 2 1 17.1 0 3 3 1 3 2 20.1 Методи та засоби комп'ютерного моделювання 205   ,,, 000    j j xcbA c W ,,...,1 sj    ,,, 000    i i ycbA b W ,,...,1 ri    ,,, 000    ij ij yxcbA a W .,...,1,,...,1 sjri  Розглянемо досить малу околицю точки  .,, 000 cbA З невиродженості рі- шень    000000 ,,,,, cbAyycbAxx   випливає, що в цій околиці множина но- мерів базисних координат оптимальних рішень не змінюється. З теореми 3 робимо висновок, що справедливі формули    ,,,,, cbAxcbA c W j j       ,,,,, cbAycbA b W i i         ,,,,,,, cbAycbAxcbA a W ij ij    .,...,1,,...,1 sjri  Тут вектори    cbAycbAx ,,,,,  є опор- ними оптимальними рішеннями прямої та двоїстої задач для точки  cbA ,, та обчис- люються за формулами   ,,, 1bBcbAx       ,,, 1 cBcbAy T   де B – оптимальна базисна матриця, c – вектор розмірності r, що містить базисні компоненти вектора c. Оскільки матриця B невироджена, то елементи матриці 1B є неперервними функціями від B, а вектори    cbAycbAx ,,,,,  є неперервними фун- кціями від  .,, cbA Тому в достатньо ма- лій околиці точки  000 ,, cbA часткові по- хідні ijij a W b W c W       ,, є неперервними фун- кціями від  .,, cbA Таким чином, використовуючи тео- рему 3, можна обчислити часткові похідні функції W за елементами матриці A та век- торів ., cb Для задачі (8) – (10) згадані елементи простими формулами пов’язані з точками фазового простору. Оскільки час- ткові похідні є неперервними функціями від  ,,, cbA то, використовуючи правило диференціювання складної функції [16], можна обчислити градієнт функції )(XW в області її гладкості. Задачу (8) – (10) запишемо в насту- пному вигляді: max, }{ 2 1    II s Ist (27) , }{ 2 1 ii II s IsiIs bztu     ,,...,2,1 ki  (28) ,0Ist ,0iz },{II  ,2,1s .,...,2,1 ki  (29) Тут ,)0( iii ldb  величини iIsu обчис- люються за формулами       ,0,,,2 ,0,,0 IsiIsi Isi iIs NNNNw NN u ,,...,2,1 ki  },{II  .2,1s (30) Нехай  Ist – оптимальні значення змінних Ist задачі (27) – (29),  iy – оптима- льні значення двоїстих змінних, ),,...,,( 21 iniii xxxX  .,...,2,1 ki  Застосо- вуючи теорему 3 до задачі (27) – (29), отримуємо    x XW )(                         k i i iII s iIs iIs x b b W x u u W 1 }{ 2 1  , 1 }{ 2 1     x b y x u yt k i II s iIs iIs               .,...,2,1,,...,2,1 nk   (31) Маємо      x b .... 22 2 2 1     X x xxx x n     (32) Методи та засоби комп'ютерного моделювання 206 Обчислимо . x uiIs   Нагадаємо, що },...,,{ 121  niiiI – підмножина множини },...,2,1{ k така, що система векторів },...,,{ 121   niii NNNH лінійно незалежна, }{I – множина всіх таких підмножин, 21, II NN – вектори одиничної довжини, ортогональні кожному вектору із системи H, причому .21 II NN  Ясно, що за умов Ii або 0, Isi NN , або   iIIi ,, виконується рівність .0   x uiIs (33) Оскільки ,/ iii XXN  то за умов ,Ii 0,,  Isi NNi  справедливі співвідно- шення       Isi iIs NN x w x u ,2      IsNXX x w ,/2           n j j n j Isjj x nx x w 1 2 1 2    , , 2 3 2   X xNXXn w IsIs   (34) де Isjn – j-та компонента вектора ,IsN ).,...,( 1 IsnIsIs nnN  У випадку ,, IIi   0, Isi NN маємо ,2 1        n j Isj ij iIs x n nw x u  (35) де ijn – j-та компонента вектора ,iN ).,...,( 1 inii nnN  Часткові похідні x nIsj   з формули (35) легко обчислити. Використовуючи формули (31) – (35), можна розрахувати градієнт   knxxx WWWG ,...,, 1211  функції  knxxxW ,...,, 1211 в точках її гладкості. В області гладкості функції )(XW знайдемо швидкості агентів, для яких до- сягається мінімакс величини ).(tW Пред- ставимо швидкості iV у вигляді ),,...,,( 21 iniiii vvvvV  де .,...,1,0,1..., 22 2 2 1 kivvvVv iniiii  Рівняння руху набувають вигляду .,...,2,1,,...,2,1,00 njkivvvvx jijiij  Позначимо ).,...,,( 21 kVVVV  Маємо )(maxmin 0 tW VV     k i n j ijx VV xW ij 1 10 maxmin      k i n j jijix VV vvvvW ij 1 1 00 )(maxmin 0                k i n j jx k i n j ijxi VV vWvvWv ijij 1 1 00 1 10 maxmin . 1 1 00 1 1        n j k i xj k i n j ijxi ijij WvvvWv (36) Тут jiji vvvv 00 ,,, – значення змінних, для яких досягається мінімакс. Позначимо , 2 1 1 0              n j k i xij W , 1 2    n j xi ij W .,...,2,1 ki  З формули (36) випливає, що мінімакс до- сягяється за умов ,...10 wvvv k  ,/ 0 1 0    k i xj ij Wv ,/ ixij ij Wv  ,,...,2,1 ki  .,...,2,1 nj  Методи та засоби комп'ютерного моделювання 207 Отже, для досягнення мінімаксу величини )(tW в момент часу t швидкості можна ви- брати за формулами ,,..., 110 0 1            k i x k i x ini WW w V    .,...,2,1,,..., 1 kiWW w V ini xx i i   (37) Якщо },,...,1,0{,0 kii  швидкість iV можна вибрати будь-якою з множини .ii wV  Значення )(tW обчислюється на- ступним чином .)( 1 0            k i iwtW  (38) Як показують числові приклади, на- ведені в таблиці, величина )(tW у багатьох випадках є меншою, ніж .1 Внаслідок цього максимальний час переслідування виявляється меншим, ніж для стратегії па- ралельного зближення. Нехай sign          .0,1 ,0,0 ,0,1 )( x x x x Позначимо  відкриту область фазового простору, в якій виконуються наступні умови:  0X int conv },,...,,{ 21 kXXX ,ii lX  ;,...,2,1 ki   в задачі (27) – (29) існують невиро- джені опорні оптимальні рішення прямої та двоїстої задач;  величини sign  Isi NN , та sign )( i не змінюються, }{II  , ,2,1s .,...,2,1 ki  В області  функція )(XW – гладка. Побудуємо стратегію переслідуван- ня. Припустимо, фазова точка X в деякий момент часу t знаходиться в області . Позначимо  ,0},,...,2,1{:0  ikiiI   .0},,...,2,1{:1  ikiiI  Нехай i-й переслідувач за умови 0Ii ви- користовує стратегію паралельного збли- ження, а якщо ,1Ii то його швидкість розраховується за відповідною формулою (37). Із співвідношень (14), (37) випли- вають рівняння руху ,0VVX ii  ,0Ii (39)   .,,..., 101 IiVWW w X ini xx i i    (40) Неважко перевірити, що компоненти гра- дієнта   knxxx WWWG ,...,, 1211  в області  мають неперервні часткові похідні за фа- зовими змінними. Швидкість втікача 0V вважається кусково-неперервною функці- єю від часу. Оскільки для 0Ii переслі- дувачі застосовують стратегію паралель- ного зближення, то функції ,, 0IiVi  є кусково-неперервними функціями від ча- су. З теореми про існування та єдиність рішення нормальної системи диференцій- них рівнянь [13] випливає, що існує єдине непродовжне рішення )(tX системи (39) − (40), що задовольняє заданим початко- вим умовам. Це рішення є неперервною функцією. Якщо в деякий момент часу t фазо- ва точка не належить області , необхід- но вирішити екстремальну задачу, в якій швидкість втікача в момент t вважається відомою, а швидкості переслідувачів iV вибираються таким чином, щоб величина W зменшуваласть якомога швидше за умов ,wVi  .,...,2,1 ki  Нехай, напри- клад, всі опорні оптимальні рішення зада- чі (27) − (29) невироджені, },...,,{ 21 qBBB − множина оптимальних базисних мат- риць, кожна з яких відповідає невиродже- ному опорному оптимальному рішенню. Необхідно вирішити наступну екстрема- льну задачу: .,...,2,1,min,,max 0 ,...,1 kiwVVVG i V r qr   Методи та засоби комп'ютерного моделювання 208 Тут ),,...,,( 21 kVVVV  ),,...,,( 0000 VVVV  rG − градієнт функції ,)()( 1 1 j k j rr bBXW    b – вектор обмежень задачі (27) − (29), вектор b та матриці rB – функції від фазо- вої точки X. Якщо існують вироджені опо- рні оптимальні рішення задачі (27) − (29), екстремальна задача має подібний вигляд. Детально розглядати ці задачі не станемо; вважаємо, що переслідувачі можуть вирі- шувати їх з достатньою точністю. Описану стратегію переслідування позначимо .0 У загальному випадку, який тут ро- зглядається, для забезпечення кускової неперервності швидкостей можна засто- сувати стратегію ,1 що описана в попе- редньому розділі та використовується там же для вирішення більш простої задачі; в такому разі необхідно врахувати, що кіль- кість переслідувачів дорівнює k. Стратегія 1 використовує стратегію 0 як допо- міжну. Зауваження, зроблені в поперед- ньому розділі щодо стратегії ,1 залиша- ються справедливими і тут. Зокрема, за- лишається справедливим висновок про те, що стратегія 1 забезпечує менший мак- симальний час переслідування у порів- нянні зі стратегією паралельного збли- ження для множини процесів, міра Лебега яких додатня. Водночас, як стверджує те- орема 4, для всіх процесів стратегія 1 не гірша за стратегію паралельного збли- ження. Доведемо теорему про максималь- ний час переслідування для стратегії .1 Позначимо G множину фазових точок ),,...,,( 21 kXXXX  які задовольняють умовам ,ii lX  ,,...,2,1 ki  0X int conv }.,...,,{ 21 kXXX Лема 1. Функція )(XW неперервна на множині G. Доведення леми наводити не буде- мо. Нехай процес починається у фазовій точці X, ),( 1XT – максимальний час пе- реслідування для стратегії .1 Теорема 4. Справедлива нерівність ).(),( 1 XWXT  Доведення. Припустимо, застосову- ється стратегія .1 Позначимо 1t момент часу такий, що для 1tt  виконуються не- рівності ,)( ii ltX  ,, . . . ,2,1 ki  та існує як мінімум одна точка ),( 1tX i для якої справедлива рівність .)( 1 ii ltX  Нехай в момент 1t існує не менше двох точок ),( 1tX i які не лежать на одному промені, що виходить з початку коорди- нат, та для яких справедливі рівності .)( 1 ii ltX  Оскільки починаючи з момен- ту 1t переслідувачі, для яких справедливі рівності ,)( 1 ii ltX  застосовують погон- ну стратегію, то легко довести, що 1t є ча- сом захоплення цілі. Нехай в момент часу 1t існує тільки одна точка ),( 1tX i для якої справедлива рівність ii ltX )( 1 (якщо існують декіль- ка точок ),( 1tX i для яких ,)( 1 ii ltX  та які лежать на одному промені, що вихо- дить з початку координат, ситуація аналі- зується аналогічно). Оскільки починаючи з моменту 1t переслідувач, для якого ,)( 1 ii ltX  застосовує погонну стратегію, то оптимальною стратегією втікача є рух з максимальною швидкістю у напрямку, протилежному від переслідувача .iP В та- кому випадку, згідно стратегії ,1 всі пе- реслідувачі, за винятком ,iP застосовують стратегію паралельного зближення. Швид- кість переслідувача ,iP який застосовує погонну стратегію, дорівнює швидкості, що відповідає стратегії паралельного зближення. Якщо в момент 1tt  неперер- вності функції )(0 tV швидкість )(0 tV не є максимальною або не направлена у на- прямку, протилежному від переслідувача ,iP то t – час захоплення цілі. Методи та засоби комп'ютерного моделювання 209 Оскільки функції kitVi ,...,1,0),(  – кусково-неперервні, з теореми 1 ви- пливає, що система диференційних рів- нянь (14) має єдине рішення ),(tX яке задовольняє заданим початковим умо- вам. Це рішення є неперервною функці- єю від часу. Нехай t  – момент часу та- кий, що .0 1tt  Згідно з лемою 1 фун- кція ))(()( tXWtW  неперервна на про- міжку ],0[ t  як суперпозиція неперерв- них функцій. З опису стратегії 1 випливає, що існує скінчена множина моментів часу i ,...,, 10 така, що ,...0 10 ti   а на інтервалах ),(),,(),...,,(),,( 12110 tiii   почергово застосовуються стратегії пара- лельного зближення та ,0 причому на кожному з інтервалів використовується тільки одна з них. Якщо на інтервалі ),( ti  застосову- ється стратегія паралельного зближення, то з визначення функції W випливають співвідношення  ))(())(()()( ii XWtXWWtW  .ti   (41) Якщо на інтервалі ),( ti  застосовується стратегія ,0 то співвідношення (41) ви- пливають з того, що функція )(tW непере- рвна на відрізку ],,0[ t на інтервалі ),( ti  похідна )(tW має розриви тільки першого роду не більш як у скінченому числі точок, а в точках неперервності похідної викону- ється нерівність .1)( tW З тих же при- чин справедливі нерівності .,...,2,1,)()( 11 ijWW jjjj    Маємо      i j jj WWWtW 1 10 )()()()(    ,)()( 1 1 ttWtW i i j jji      звідки випливає нерівність ).0()( WtWt  (42) Нехай i – такий номер, що .)( 1 ii ltX  Позначимо T  час захоплення цілі за умови, що, починаючи з момента ,t швидкість 0V – постійна та обчислюється за формулою , )( )( 0 tX tX wV i i    а переслідувачі застосовують стратегію паралельного зближення. Очевидно, спра- ведлива нерівність ),(tWtT  тому з (42) випливає ).0(WT  (43) Починаючи з моменту часу ,1t оп- тимальна швидкість 0V є постійною та об- числюється за формулою , )( )( 1 1 0 tX tX wV i i (44) а швидкості переслідувачів відповідають стратегії паралельного зближення. Тому ),,( 11 tttTtT   де T − час захоп- лення цілі для стратегії 1 за умови (44), а величина ),( 1tt задовольняє умові ,0),(lim 1 0   tt  де .1 tt  Оскільки ),,( 11 ttttTT   то з (43) випливає ),0(),( 11 WttT  (45) де ).,(),( 1111 tttttt   Справедливе співвідношення ,0),(lim 11 0   tt  тому з (45) випливає нерівність ).0(WT  Теорему доведено. Теорема 4 доводить те, що макси- мальний час переслідування для стратегії 1 не більший, ніж для стратегії парале- льного зближення. В даній роботі функція Ляпунова використана у випадку рівності швидкос- тей агентів. Якщо швидкості переслідува- Методи та засоби комп'ютерного моделювання 210 чів перевищують швидкість втікача, функ- цію Ляпунова можна побудувати, викори- стовуючи задачу лінійного програмування (5) − (7). В такому разі слід враховувати, що оптимальне значення її цільової функ- ції лише приблизно дорівнює максималь- ному часу переслідування для стратегії па- ралельного зближення. Для побудови фун- кції Ляпунова можна також використати відповідну задачу нелінійного програму- вання. Висновки В статті розглянуто задачу переслі- дування одного втікача кількома переслі- дувачами. Побудовано стратегії пересліду- вання з використанням функції Ляпунова. Для будь-якого конфліктно керованого процесу виконується нерівність ,WT  во- дночас для багатьох процесів справедливе співвідношення ,WT  де W та T – макси- мальний час переслідування для стратегії паралельного зближення та побудованої стратегії відповідно. 1. Айзекс Р. Дифференциальные игры. М.: Мир, 1967. 480 с. 2. Рихсиев Б.Б. Дифференциальные игры с простыми движениями. Ташкент: ФАН, 1989. 232 с. 3. Пашко С.В. Эффективные стратегии пре- следования, основанные на использовании функции Ляпунова. Доповіді НАН Укра- їни. 2016. № 1. С. 26–33. 4. Пшеничный Б.Н., Остапенко В.В. Диффе- ренциальные игры. Киев: Наук. думка, 1992. 264 c. 5. Чикрий А.А. Конфликтно управляемые процессы. Киев: Наук. думка, 1992. 384 с. 6. Пшеничный Б.Н., Чикрий А.А., Раппопорт И.С. Эффективный метод решения диффе- ренциальных игр со многими пресле- дователями. ДАН СССР. 1981. 256.3. С. 530–535. 7. Ибрагимов Г.И., Рихсиев Б.Б. О некоторых достаточных условиях оптимальности времени преследования в дифференци- альной игре со многими преследующими. Автоматика и телемеханика. 2006. № 4. С. 16–24. 8. Иванов Р.П., Ледяев Ю.С. Оптимальность времени преследования в дифференци- альной игре многих объектов с простыми движениями. Труды МИАН СССР. 1981. 158. C. 87–97. 9. Кунцевич В.М., Лычак М.М. Синтез систем автоматического управления с помощью функций Ляпунова. М.: Наука, 1977. 400 с. 10. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1972. 496 с. 11. Пашко С.В., Яловец А.Л. Максимальное время преследования для стратегии парал- лельного сближения. Проблеми програ- мування. 2014. № 4. С. 78–93. 12. Пашко С.В. Гарантированное время пре- следования для стратегии параллельного сближения в случае равенства скоростей игроков. Компьютерная математика. 2014. № 1. С. 140–149. 13. Понтрягин Л.С. Обыкновенные дифферен- циальные уравнения. М.: Наука, 1965. 331 с. 14. Ляшенко И.Н., Карагодова Е.А., Черникова Н.В., Шор Н.З. Линейное и нелинейное программирование. Киев: Вища школа, 1975. 371 с. 15. Первозванский А.А. Математические моде-ли в управлении производством. М.: Наука, 1975. 615 с. 16. Фихтенгольц Г.М. Курс дифференциаль- ного и интегрального исчисления. М.: Наука, 1969. Т. 1. 607 с. References 1. Isaacs R. (1999). Differential Games. New York: Dover Publications. 2. Rikhsiev B.B. (1989). Simple Motion Differential Games. Tashkent: FAN. (In Russian). 3. Pashko S.V. (2016). Effective Strategies of Pursuit, Based on Lyapunov Function. Dopov. NAN Ukraine. N 1. P. 26 – 33. (In Russian). 4. Pshenichnyi B.N., Ostapenko V.V. (1992). Differential Games. Kyiv: Nauk. Dumka. (In Russian). Методи та засоби комп'ютерного моделювання 211 5. Chikrii A.A. (1992). Conflict-Controlled Processes. Kyiv: Nauk. Dumka. (In Russian). 6. Pshenichnyi B.N., Chikrii A.A., Rappoport I.S. (1981). Dokl. AN SSSR. 256. 3. P. 530–535. (In Russian). 7. Ibragimov G.I., Rikhsiev B.B. (2006). On some Sufficient Conditions for Optimality of the Pursuit Time in the Differential Game with Multiple Pursuers. Automation and Remote Control. Volume 67, Issue 4. P. 529–537. (In Russian). 8. Ivanov R.P., Lediaev Yu.S. (1981). Time Optimality for the Pursuit of Several Objects with Simple Motion in a Differential Game. Trudy Mat. Inst. Steklov.158. P. 87–97. (In Russian). 9. Kuntsevich V.M., Lychak M.M. (1977). Synthesis of Systems of Automatic Control with the Use of Lyapunov Functions. Moscow: Nauka. (In Russian). 10. Kolmogorov A.N., Fomin S.V. (1972). Introductory Real Analysis. Moscow: Nauka. (In Russian). 11. Pashko S.V., Yalovets A.L. (2014). Maximal Time of Pursuit for the Strategy of Parallel Approach. Problems in Programming. N 4. P. 78–93. (In Russian). 12. Pashko S.V. (2014). 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. N 1. P. 140–149. (in Russian). 13. Pontryagin L.S. (1965). Ordinary Differential Equations. Moscow: Nauka. (In Russian). 14. Lyashenko I.N., Karagodova E.A., Cher- nikova N.V., Shor N.Z. (1975). Linear and Nonlinear Programming. Kyiv: Vishcha Shkola. (In Russian). 15. Pervozvansky A.A. (1975). Mathematical Models in Production Management. Moscow: Nauka. (In Russian). 16. Fikhtengolts G.M. (1969). Course of Differential and Integral Calculus. Volume 1. Moscow: Nauka. (In Russian). Одержано 06.06.2017. Про автора: Пашко Сергій Володимирович, кандидат фізико-математичних наук, старший науковий співробітник. Кількість наукових публікацій в українських виданнях – понад 30. Кількість наукових публікацій в зарубіжних виданнях – 2. Індекс Хірша в SCOPUS – 3. http://orcid.org/0000-0002-0453-4128. Місце роботи автора: Інститут програмних систем НАН України, 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 6025. E-mail: pashko55@yahoo.com https://www.google.com/books?hl=en&lr=&id=iNryCAAAQBAJ&oi=fnd&pg=PR9&dq=chikrii&ots=cTBgrIxSjs&sig=Rjf2Fgvf_0IkncBeQaAdFZeZCQQ https://www.google.com/books?hl=en&lr=&id=iNryCAAAQBAJ&oi=fnd&pg=PR9&dq=chikrii&ots=cTBgrIxSjs&sig=Rjf2Fgvf_0IkncBeQaAdFZeZCQQ https://link.springer.com/journal/10513 https://link.springer.com/journal/10513 https://link.springer.com/journal/10513/67/4/page/1 https://scholar.google.com.ua/citations?user=G7Uxx9cAAAAJ&hl=en&oi=sra https://www.google.com/books?hl=en&lr=&id=cbbCAgAAQBAJ&oi=fnd&pg=PP1&dq=Kolmogorov&ots=19Jdm1tX6C&sig=DBb-oxuCPL14iV5mgP44Uc4cnvA mailto:pashko55@yahoo.com
id	pp_isofts_kiev_ua-article-305
institution	Problems in programming
keywords_txt_mv	keywords
language	Ukrainian
last_indexed	2025-07-17T09:34:09Z
publishDate	2018
publisher	PROBLEMS IN PROGRAMMING
record_format	ojs
resource_txt_mv	ppisoftskievua/ff/9f06a3f0851db80ae45347f15ce3e9ff.pdf
spelling	pp_isofts_kiev_ua-article-3052024-04-28T11:48:08Z Construction of pursuit strategies with using Lyapunov functions Построение стратегий преследования с использованием функций Ляпунова Побудова стратегій переслідування з використанням функцій Ляпунова Pashko, S.V. pursuit-evasion game; agent; strategy of parallel approach; Lyapunov function; maximal time of pursuit UDC 518.9 конфликтно управляемый процесс; агент; стратегия параллельного сближения; функция Ляпунова; максимальное время преследования УДК 518.9 конфліктно керований процес; агент; стратегія паралельного зближення; функція Ляпунова; максимальний час переслідування УДК 518.9 This paper is concerned with differential pursuit-evasion games, in which several agents chase one. The time of capture of a target is used as the criterion. The motion of agents is simple one, the velocities are piecewise-continuous. The function that specifies the maximal time of capture of the target for the well-known strategy of parallel approach is described. This function is used as a Lyapunov function for constructing the new chase strategy, which outperforms the strategy of parallel approach in the following sense. Maximal time of pursuit for the new strategy is not more than maximal time of pursuit for the strategy of parallel approach; at the same time there are many games, for which maximal time of pursuit for the new strategy is less than for the strategy of parallel approach. In case of pursuit-evasion game on a plane we find explicit form of Lyapunov function and calculate velocities of pursuers using the gradient of this function. Numerical examples show that such velocities of pursuers reduce the maximal time of pursuit. In case of pursuit-evasion game in a multidimensional Euclidean space, Lyapunov function is equal to an optimal value of an objective function of appropriate linear programming problem. The velocities of pursuers are calculated with using the gradient of this function.Problems in programming 2017; 3: 194-211 Рассматриваются дифференциальные игры преследования, в которых несколько агентов догоняют одного. Критерием является время захвата цели. Для известной стратегии параллельного сближения описана функция, задающая максимальное время преследования. Эта функция используется как функция Ляпунова для построения новой стратегии преследования, которая превосходит стратегию параллельного сближения в следующем смысле. Максимальное время преследования для построенной стратегии не превосходит максимального времени для стратегии параллельного сближения; вместе с тем существует значительное количество игр, в которых максимальное время преследования для новой стратегии оказывается меньшим, чем для стратегии параллельного сближения.Problems in programming 2017; 3: 194-211 Розглядаються диференційні ігри переслідування, в яких кілька агентів доганяють одного. Критерієм виступає час захоплення цілі. Для відомої стратегії паралельного зближення описана функція, що задає максимальний час переслідування. Ця функція використовується як функція Ляпунова для побудови нової стратегії переслідування, що перевершує стратегію паралельного зближення в наступному сенсі. Максимальний час переслідування для побудованої стратегії не перевищує максимального часу для стратегії паралельного зближення; водночас існує значна кількість ігор, в яких максимальний час переслідування для нової стратегії виявляється меншим, ніж для стратегії паралельного зближення. Problems in programming 2017; 3: 194-211 PROBLEMS IN PROGRAMMING ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ ПРОБЛЕМИ ПРОГРАМУВАННЯ 2018-11-12 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/305 10.15407/pp2017.03.194 PROBLEMS IN PROGRAMMING; No 3 (2017); 194-211 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 3 (2017); 194-211 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 3 (2017); 194-211 1727-4907 10.15407/pp2017.03 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/305/299 Copyright (c) 2018 PROBLEMS OF PROGRAMMING
spellingShingle	pursuit-evasion game agent strategy of parallel approach Lyapunov function maximal time of pursuit UDC 518.9 Pashko, S.V. Construction of pursuit strategies with using Lyapunov functions
title	Construction of pursuit strategies with using Lyapunov functions
title_alt	Построение стратегий преследования с использованием функций Ляпунова Побудова стратегій переслідування з використанням функцій Ляпунова
title_full	Construction of pursuit strategies with using Lyapunov functions
title_fullStr	Construction of pursuit strategies with using Lyapunov functions
title_full_unstemmed	Construction of pursuit strategies with using Lyapunov functions
title_short	Construction of pursuit strategies with using Lyapunov functions
title_sort	construction of pursuit strategies with using lyapunov functions
topic	pursuit-evasion game agent strategy of parallel approach Lyapunov function maximal time of pursuit UDC 518.9
topic_facet	pursuit-evasion game agent strategy of parallel approach Lyapunov function maximal time of pursuit UDC 518.9 конфликтно управляемый процесс агент стратегия параллельного сближения функция Ляпунова максимальное время преследования УДК 518.9 конфліктно керований процес агент стратегія паралельного зближення функція Ляпунова максимальний час переслідування УДК 518.9
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/305
work_keys_str_mv	AT pashkosv constructionofpursuitstrategieswithusinglyapunovfunctions AT pashkosv postroeniestrategijpresledovaniâsispolʹzovaniemfunkcijlâpunova AT pashkosv pobudovastrategíjpereslíduvannâzvikoristannâmfunkcíjlâpunova

Construction of pursuit strategies with using Lyapunov functions

Репозитарії

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