До постановки задачі переслідування на площині

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Проблеми програмування
Datum:	2013
1. Verfasser:	Яловець, А.Л.
Sprache:	Ukrainisch
Veröffentlicht:	Інститут програмних систем НАН України 2013
Schlagworte:	Прикладні засоби програмування та програмне забезпечення
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/86670
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	До постановки задачі переслідування на площині / А.Л. Яловець // Проблеми програмування. — 2013. — № 2. — С. 95-100. — Бібліогр.: 4 назв. — укр.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

_version_	1860109546039541760
author	Яловець, А.Л.
author_facet	Яловець, А.Л.
citation_txt	До постановки задачі переслідування на площині / А.Л. Яловець // Проблеми програмування. — 2013. — № 2. — С. 95-100. — Бібліогр.: 4 назв. — укр.
collection	DSpace DC
container_title	Проблеми програмування
description	Пропонується постановка задачі переслідування на площині з точки зору мультиагентного підходу. Показуються розбіжності, які відрізняють пропоновану постановку задачі від постановки такої задачі з точки зору теорії диференційних ігор. Наводиться перелік методів, які необхідно розробити.
first_indexed	2025-12-07T17:32:54Z
fulltext	Прикладні засоби програмування та програмне забезпечення © А.Л. Яловець, 2013 ISSN 1727-4907. Проблеми програмування. 2013. № 2 95 УДК 004.942+623.465 А.Л. Яловець ДО ПОСТАНОВКИ ЗАДАЧІ ПЕРЕСЛІДУВАННЯ НА ПЛОЩИНІ Пропонується постановка задачі переслідування на площині з точки зору мультиагентного підходу. Показуються розбіжності, які відрізняють пропоновану постановку задачі від постановки такої задачі з точки зору теорії диференційних ігор. Наводиться перелік методів, які необхідно розробити. Вступ Задача переслідування на площині – відома задача, досить глибоко вивчена та досліджена (див., наприклад, [1, 2]). Здебі- льшого її дослідження виконується в рамках теорії диференційних ігор [3, 4]. Разом з тим, за своєю сутністю ця задача може успішно вирішуватись за допомогою методів та моделей мультиагентних сис- тем. При цьому, оточуюче середовище ро- зглядається як динамічна система, а утікачі та переслідувачі – як агенти, які діють у такій системі. Мета даної роботи – постановка задачі переслідування на пло- щині з точки зору мультиагентного підхо- ду. Для того, щоб відокремити таку поста- новку від загальновідомої, ми наводимо короткий огляд традиційної постановки задачі. 1. Традиційна постановка задачі переслідування на площині Коротко опишемо традиційне тлу- мачення сутності задачі переслідування на площині у відповідності до [2]. Нехай точ- ка Р починає рух на площині з деякого по- чаткового стану 0x . Якщо фіксувати всі її поточні положення, то ми отримаємо на площині деяку неперервну криву, яка на- зивається траєкторією руху. Шлях, який буде пройдено вздовж траєкторії, будемо обраховувати, починаючи з точки 0x . В продовж будь-якого руху довжина шляху s , пройденого точкою Р, залежить від ча- су. Як наслідок, шлях s можна розглядати як функцію часу: )(tss  . Якщо відомий спосіб переміщення точки Р по траєкторії руху, то можна задати формулу, яка визна- чає положення точки на траєкторії у будь-який момент часу, тобто закон руху точки. Траєкторія руху точки Р на площині може представляти собою як пряму, так і криву лінію. Відповідно до цього рухи ро- зподіляються на криволінійні та прямолі- нійні. Простим рухом називається рух, при якому відстань, пройдена точкою Р з поча- ткового стану 0x задається виразом: tts )( , де t – час, на протязі якого від- бувався рух, )(ts – шлях, пройдений точ- кою Р з початкового стану 0x за час t ,  – шлях, пройдений точкою Р за одиницю часу, який називається лінійною швидкіс- тю точки. Простий рух характеризується тим, що величина  є постійною та не за- лежить від часу. Таким чином, простий рух точки Р з початкового стану 0x на площині є рух по будь-якій криволінійній траєкторії, що ви- ходить з цієї точки, з постійною лінійною швидкістю  . Простий рух точки Р може розгля- датися у випуклій множині S на площині, якщо в процесі руху точка Р не покидає множину S . Нагадаємо, що множина на- зивається випуклою, якщо відрізок, який з’єднує будь-які дві його точки, повністю належить до цієї множини. Як правило, в дослідженнях перес- лідування на площині розглядається підк- лас простих рухів, а саме рухи по ломаним з кінцевим числом вершин. Тобто передба- чається, що точка Р, рухаючись з постій- ною лінійною швидкістю  з початкового стану 0x , може змінювати напрям свого руху лише кінцеве число разів. Зазначимо, Прикладні засоби програмування та програмне забезпечення 96 що будь-який простий рух може бути з до- статнім ступенем точності апроксимова- ним простим рухом по ломаним з кінцевим числом вершин. Виходячи з викладених положень коротко розглянемо сутність гри переслі- дування з простим рухом з точки зору тео- рії диференційних ігор [2]. Нехай на площині задано випуклу множину S . Точки mPPP ,,, 21  та E пе- реміщуються в S , перебуваючи у стані простого руху з постійними лінійними швидкостями m ,,, 21  та  відпові- дно (розглядаються тільки прості рухи по ломаних з кінцевим числом вершин). В те- орії ігор сукупність точок mPPP ,,, 21  на- зивають гравцями-переслідувачами або на- рядом, а E – гравцем-утікачем. Рух наря- ду P та утікача E починається в момент часу 0t з початкових положень )0(),0(,),0(),0( 21 EPPP m . Положення гра- вців EPPP m ,,,, 21  у момент часу 0t позначаються відповідно ),(),( 21 tPtP )(),(, tEtPm . Вважається, що наряд здійснив зустріч з E , якщо хоча б один з переслі- дувачів iP наряду P здійснив зустріч з E , тобто коли вперше положення E збіжить- ся з положенням хоча б одного пересліду- вача iP наряду P . Переслідування наря- дом P утікача E починається в момент часу 0t і завершується, коли наряд P здійснює зустріч з E . При цьому вимага- ється, щоб у процесі руху всі переслідувачі з наряду P та утікач E не покидали мно- жини S . Мета наряду P – зустріч з утіка- чем E за мінімальний час, а мета утікача E – відтягнути момент зустрічі або уник- нути її, якщо це можливо. В теорії диференційних ігор вважа- ється, що в кожний момент часу 0t гра- вцю E відомо своє положення та поло- ження всіх переслідувачів в цей же момент часу. Кожний переслідувач iP з наряду P в момент часу 0t знає положення всіх членів наряду, включаючи себе, положен- ня гравця E та напрям його руху в цей же момент часу t , однак йому невідомі май- бутні маневри E , тобто iP не знає, коли і як гравець E буде змінювати напрям свого руху в майбутньому. Така гра переслідування назива- ється грою переслідування з простим рухом і позначається як  Sm ;1, , де m підкреслює залежність від числа пе- реслідувачів, а S – залежність від виду множини S . У випадку, коли S співпадає з площиною, таку гру також позначають як )1,(m . Кінцеве число  називається оп- тимальним часом переслідування у грі );1,( Sm відносно початкових положень )0(,),0(),0( 21 mPPP  і )0(E , якщо вико- нані наступні умови: а) для будь-яких рухів гравця E іс- нує спосіб поведінки наряду P такий, що гарантує йому зустріч з E не пізніше, ніж за час  ; б) існує такий спосіб поведінки гра- вця E , що наряд P не може здійснити зу- стріч з E до моменту часу  . Якщо для кінцевого числа  вико- нано тільки умову а), то число  назива- ють гарантованим часом переслідування щодо початкових положень ),0(),0( 21 PP )0(, mP і )0(E , а якщо для кінцевого чис- ла  виконано тільки умову б), то число  називають гарантованим часом уник- нення зустрічі відносно початкових поло- жень )0(,),0(),0( 21 mPPP  і )0(E . Нехай  – оптимальний час пере- слідування щодо початкових положень )0(,),0(),0( 21 mPPP  і )0(E . Тоді будь- який спосіб поведінки гравця E , при якому наряд P не може здійснити з ним зустріч до моменту  (умова б)), нази- вають оптимальною стратегією гравця E . Спосіб поведінки наряду P , при якому гарантується зустріч з E за час не більше, ніж за час  (умова а)), називають оптимальною стратегією наряду P . Під рішенням гри );1,( Sm розумі- ється знаходження оптимальної стратегії наряду P , оптимальної стратегії гравця E та оптимального часу переслідування. Прикладні засоби програмування та програмне забезпечення 97 2. Пропонована постановка задачі переслідування на площині Наведемо окремі уточнення до ви- щевикладеної загальновідомої постановки задачі, які дозволять з одного боку, сфор- мулювати її у термінах мультиагентного підходу, з іншого – визначити перелік но- вих математичних методів, які необхідно розробити. Перш за все треба відзначити, що виходячи з положень теорії диференційних ігор необхідно знати закон руху точки. На практиці не представляється можливим напевно знати закон руху точки Е (і, як наслідок, точок iP ), оскільки (як буде по- казано далі) на зміни характеру руху то- чки впливає дуже багато чинників, дію яких заздалегідь точно описати та форма- лізувати не вдається. Нехай на площині задано випуклу множину S , яка відповідає динамічно- му середовищу, в межах якого діють аген- ти. Змістовно множину S можна інтерп- ретувати як морську ділянку кордону України, в межах якої діють кораблі різ- ного призначення (що інтерпретуються як агенти). В загальному випадку можна виді- лити три категорії агентів: 1) агенти- утікачі, що формують множину },,,{ 21 nEEEE  ; 2) агенти-переслідувачі, що формують множину },,,{ 21 mPPPP  ; 3) інші агенти, що формують множину A , які не є ані утікачами, ані переслі- дувачами, але також знаходяться (руха- ються або ні) в S . Надалі нас будуть цікавити тільки агенти перших двох категорій, хоча в де- яких компонентах задачі переслідування вплив агентів множини A буде врахову- ватись (наприклад, в задачах маневруван- ня). Зазначимо, що вплив агентів множини A змістовно означає врахування приро- ди, геометрії та поведінки об’єктів, яким такі агенти відповідають. Зокрема, такі об’єкти можуть бути як рухомими, так і нерухомими, як точковими (напри- клад, кораблі), так і просторовими (напри- клад, острови). На відміну від постановки задачі, викладеної в п. 1 даної роботи, в нашо- му випадку розглядається не один утікач, а множина утікачів E , де 1)( Ecard . Це зумовлює необхідність розгляду різ- них угрупувань kGr переслідувачів )( PPP ii  , кожне з яких є прототипом наряду з вищевикладеної постановки та переслідує цілком визначеного утікача )( EEE jj  . Введемо множину угрупу- вань },,,{ 21 wGrGrGrGr  , де кожна kGr містить деяку кількість )( PPP ii  та одно- го )( EEE jj  , тобто для будь-якої гру- пи kGr виконується умова, що 2)( kGrcard . Для будь-яких двох груп справедливо, що }{1  kk GrGr . Оче- видно, що EPGrGrGr w  21 , де )(Grcardw  . Кожний агент ji EP , починає рух у момент часу 0t , має поточні координати в ортогональній системі координат і пере- міщується в S , перебуваючи у стані прос- того руху з постійною швидкістю у будь- який момент часу 0t , який передує його можливій зупинці (внаслідок захоплення або інших причин). Параметри, що харак- теризують стан будь-якого агента множин EP, у момент часу 0t однозначно опи- суються кортежем  iiii vyx ,),,( , де ),( ii yx – поточні координати і-того аген- та; iv – швидкість руху і-го агента; i - кут руху і-го агента в ортогональній си- стемі координат. Таким чином, у якості параметрів руху і-того агента розглядаєть- ся не лінійна швидкість, а швидкість iv та кут руху i , оскільки в будь-який момент часу 0t будь-яка траєкторія руху може бути апроксимована ломаною з кінцевим числом вершин, де будь-який фрагмент цієї ломаної, що є прямою, може бути од- нозначно описаний за допомогою саме цих двох параметрів, значення яких у даний момент часу є постійними. Будемо говорити, що переслідувачі, що належать окремій групі kGr , наздогна- ли утікача jE ( kj GrE  ), якщо хоча б один з переслідувачів ki GrP  опинився в Прикладні засоби програмування та програмне забезпечення 98 зоні захоплення утікача jE , а сам утікач при цьому вважається захопленим. Підкре- слимо, що ми не вживаємо словосполу- чення «здійснив зустріч», використане в п. 1 даної роботи, оскільки під ним розу- міється збіг положень iP та jE , а вживає- мо поняття «наздогнав». Розглядаючи аге- нтів iP та jE , ми враховуємо фізичні вла- стивості об’єктів, що відповідають таким агентам. Очевидно, що ситуація збігу по- ложень фактично відповідає зіткненню об’єктів, у якості яких виступають агенти. Як наслідок, розглядаємо зону захоплення, під якою розуміємо квадрат, сторона яко- го залежить від геометричних розмірів об’єкта, що відповідає jE , а центр квадра- та задається поточними координатами ),( jj yx агента jE , що в цілому забезпечує запобігання зіткненню об’єктів, що відпо- відають агентам iP та jE . Виходячи з цього, стає очевидним, що для моделювання поведінки агентів множин P та E необхідно враховувати додаткові (крім введених раніше) власти- вості об’єктів, що таким агентам відпові- дають. Додатково введемо наступні пара- метри опису агентів: геометричний розмір Gm об’єкта (домен допустимих значень: «великий», «середній», «малий»), клас Cl об’єкта («військовий», «цивільний»), нале- жність Bn об’єкту («свій», «чужий», «не- розпізнаний», «берегова охорона»). Напри- клад, агент iP у загальному випадку має наступні додаткові властивості: iPprop = ={«середній», «військовий», «берегова охо- рона»}. В свою чергу, множина можливих додаткових властивостей агента jE визначається з декартового добутку:  .}»«{\ охоронабереговаBnClGmprop jE  Будемо говорити, що в кожний мо- мент часу 0t утікачу kj GrE  відомо своє положення, але він знає положення тільки тих переслідувачів PPi  та інших утікачів, що належать множині E , які зна- ходяться в його зоні спостереження. Під зоною спостереження утікача jE розумі- ється квадрат, сторона якого дорівнює деякому додатному числу, що змістовно інтерпретується як подвійне значення простору видимості в один бік, а центр квадрата задається поточними координа- тами ),( jj yx утікача jE . За допомогою зони спостереження моделюються погодні умови, загальна видимість тощо. У свою чергу, в утікача kj GrE  можуть бути два можливих стани щодо обізнаності про його переслідувачів: 1) коли він знає, хто саме його переслідує; 2) коли він не знає своїх переслідувачів. В першому випадку утікач kj GrE  реа- гує (тобто запобігає захопленню) тільки на переслідувачів ki GrP  , а з іншими агентами тільки уникає зіткнення. В дру- гому випадку утікач kj GrE  аналізує всіх можливих переслідувачів PPi  , які зна- ходяться в його зоні спостереження, але реагує тільки на тих, хто гіпотетично мо- же виступати як його переслідувачі, тоб- то може входити до складу групи kGr , а з іншими агентами, як і в першому випад- ку, тільки уникає зіткнення. Для виявлен- ня, хто саме є його переслідувачами, агент- утікач динамічно формує припущення, які в кожний момент часу 0t уточнюються в залежності від поведінки можливих пе- реслідувачів. Кожний агент PPi  та EE j  уникає зіткнення з іншими агентами, які потрапили в його зону зіткнення, за ви- нятком ситуації, коли iP та jE належать одній і тій же групі kGr . Зона зіткнення геометрично збігається з зоною захоплення (див. вище). Для уникнення зіткнення агенти використовують спеціальні методи маневрування. У випадку, коли iP та jE належать одній і тій же групі kGr , зона зіткнення розглядається як зона захоп- лення, що відповідає ситуації, коли iP на- здогнав jE . Також, як і в постановці, наведеній в п. 1 даної роботи, кожний агент-пере- слідувач ki GrP  у момент часу 0t знає положення всіх переслідувачів, що нале- жать множині P , включаючи себе, поло- Прикладні засоби програмування та програмне забезпечення 99 ження kj GrE  , швидкість та напрям його руху, а також положення, швидкість та напрям руху інших утікачів, що належать множині E , у цей же момент часу t , однак йому невідомі майбутні маневри таких агентів-утікачів. Кожний агент-переслідувач iP kGr у момент часу 0t аналізує стан утікачів }){\( kn GrGRE  . Будемо позна- чати розрахунковий час захоплення пе- реслідувачем iP утікача jE як j i E P t . Тоді будемо говорити, що відбувся взаємний перехід агентів-переслідувачів в інші гру- пи, якщо для двох агентів ki GrP  та sm GrP  , які відповідно переслідують агентів-утікачів kj GrE  та sr GrE  , одночасно виконуються співвідношення r i j i E P E P tt  та j m r m E P E P tt  . При цьому агент iP переходить з групи kGr до групи sGr , а агент mP – з групи sGr до групи kGr . Очевидно, що обмеженням можливих пе- реходів є те, що constGrcard k )( та constGrcard s )( . Для виконання таких взаємних переходів агенти-переслідувачі вступають у перемовини, в ході яких з боку агентів-ініціаторів надаються відпо- відні пропозиції, які можуть бути прий- няті, або відхилені агентами-реципієнтами. Під агентом-ініціатором розуміється агент-переслідувач, який першим розпі- знав можливість більш скорішого захоп- лення агента-утікача, що належить іншій групі, ніж агента-утікача, що належить поточній групі агента-переслідувача, та опублікував відповідну пропозицію. Під агентом-реципієнтом розуміється агент- переслідувач, що належить групі, якій адресовано пропозицію агента-ініціатора, який проаналізував стан агента-утікача, що належить групі агенту-ініціатору, та за результатами аналізу прийняв або відхи- лив цю пропозицію. За аналогією з п. 1 даної роботи, пе- реслідувачі ki GrP  мають за мету наздог- нати утікача kj GrE  за мінімальний час, а утікач jE – відтягнути момент захоп- лення або уникнути його, якщо це можли- во. Узагальнюючи вищевикладене, мо- жна зробити декілька висновків. По-перше, можна стверджувати, що в пропонованій постановці напевно знати закон руху будь-якої точки kj GrE  (і, як наслідок, точок ki GrP  ) практично немо- жливо, оскільки на зміни її руху впливає досить багато чинників. Зокрема, на харак- тер руху агента-утікача впливають: − статичні та рухомі об’єкти, що на- лежать множині A та знаходяться в межах множини S , для уникнення від зіткнення з якими агенту-утікачу необхідно маневру- вати; − рухомі об’єкти, що належать мно- жи-нам P і E та знаходяться в межах множини S , для уникнення від зіткнення з якими агенту-утікачу необхідно маневру- вати; − обмеження на дії агента-утікача, що накладаються зоною спостереження; − невизначеність складу групи його агентів-переслідувачів; − можливість динамічної зміни скла- ду групи, до якої належать його агенти- переслідувачі. З цього випливає, що заздалегідь визначити час переслідування (як оптима- льний час переслідування) практично не- можливо. Будемо говорити, що кожний агент-переслідувач ki GrP  у процесі пе- реслідування агента-утікача kj GrE  на- магається мінімізувати свій шлях, тобто метою агента-переслідувача ki GrP  є ви- бір найкоротшого шляху для захоплення агента-утікача. В свою чергу, метою аген- та-утікача kj GrE  є як найбільше зрос- тання шляху, пройденого агентами- переслідувачами ki GrP  до моменту його захоплення (або взагалі, уникнення такого моменту). Як наслідок, виникає задача вибору стратегій поведінки як для агентів- переслідувачів, так і для агентів-утікачів, які б забезпечували досягнення поставле- ної мети. По-друге, можна уточнити сутність агентів, що розглядаються. Очевидно, що Прикладні засоби програмування та програмне забезпечення 100 агенти-утікачі належать до класу когнітив- них агентів. У свою чергу, агенти- переслідувачі належать до класу реактив- них агентів з дещо розширеними функція- ми (зокрема, вони можуть вступати у пе- ремовини). По-третє, можна визначити перелік методів, які необхідно розробити. До таких методів належать: − методи формування стратегії пове- дінки агента-переслідувача та агента- утікача; − метод генерації оптимальних угру- пувань агентів-переслідувачів; − метод формування оптимального розташування агентів-переслідувачів; − методи перегрупування агентів- переслідувачів; − методи розпізнавання сукупності агентів, що переслідують окремого агента- утікача; − методи маневрування агентів з метою уникнення зіткнень з іншими агентами. Висновки Пропонована постановка задачі пе- реслідування на площині (на відміну від постановки цієї задачі з точки зору теорії диференційних ігор) ґрунтується на конс- татації факту, що в реальній дійсності за- здалегідь знати закон руху довільного уті- кача (переслідувача) неможливо. Такий погляд на проблему унеможливлює вико- ристання методів диференційних ігор для вирішення досліджуваної задачі і вимагає пошуку нових підходів. Одним з можли- вих підходів до вирішення задачі є мульти- агентний підхід, який і покладено в основу запропонованої постановки задачі. Пропонована постановка задачі від- зеркалює поточний погляд на проблему моделювання поведінки агентів у рамках задачі переслідування на площині. В пода- льшому плануємо уточнювати та удоско- налювати цю постановку. 1. Петросян Л.А., Томский Г.В. Геометрия простого преследования. – Новосибирск: Наука, 1983. – 140 с. 2. Петросян Л.А., Рисхиев Б.Б. Преследова- ние на плоскости. – М.: Наука, 1991. – 91 с. 3. Айзекс Р. Дифференциальные игры. – М.: Мир, 1967. – 479 с. 4. Красовский Н.Н., Субботин А.И. Позиции- онные дифференциальные игры. – М.: Наука, 1974. – 456 с. Одержано 10.08.2012 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 1538, E-mail: yal@isofts.kiev.ua mailto:yal@isofts.kiev.ua
id	nasplib_isofts_kiev_ua-123456789-86670
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
issn	1727-4907
language	Ukrainian
last_indexed	2025-12-07T17:32:54Z
publishDate	2013
publisher	Інститут програмних систем НАН України
record_format	dspace
spelling	Яловець, А.Л. 2015-09-25T19:39:10Z 2015-09-25T19:39:10Z 2013 До постановки задачі переслідування на площині / А.Л. Яловець // Проблеми програмування. — 2013. — № 2. — С. 95-100. — Бібліогр.: 4 назв. — укр. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/86670 004.942+623.465 Пропонується постановка задачі переслідування на площині з точки зору мультиагентного підходу. Показуються розбіжності, які відрізняють пропоновану постановку задачі від постановки такої задачі з точки зору теорії диференційних ігор. Наводиться перелік методів, які необхідно розробити. uk Інститут програмних систем НАН України Проблеми програмування Прикладні засоби програмування та програмне забезпечення До постановки задачі переслідування на площині published earlier
spellingShingle	До постановки задачі переслідування на площині Яловець, А.Л. Прикладні засоби програмування та програмне забезпечення
title	До постановки задачі переслідування на площині
title_full	До постановки задачі переслідування на площині
title_fullStr	До постановки задачі переслідування на площині
title_full_unstemmed	До постановки задачі переслідування на площині
title_short	До постановки задачі переслідування на площині
title_sort	до постановки задачі переслідування на площині
topic	Прикладні засоби програмування та програмне забезпечення
topic_facet	Прикладні засоби програмування та програмне забезпечення
url	https://nasplib.isofts.kiev.ua/handle/123456789/86670
work_keys_str_mv	AT âlovecʹal dopostanovkizadačípereslíduvannânaploŝiní

До постановки задачі переслідування на площині

Institution

Ähnliche Einträge