Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів

Розглядається проблема управління стратегіями переслідування/утікання агентів на площині. Аналізується існуючий підхід з управління стратегіями переслідування/утікання, запропонований Р. Айзексом, та обґрунтовується недоцільність його використання для випадку управління агентами. Пропонується метод...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Яловець, А.Л.
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2013
Назва видання:	Проблеми програмування
Теми:	Прикладні засоби програмування та програмне забезпечення
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/86697
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів / А.Л. Яловець // Проблеми програмування. — 2013. — № 4. — С. 94-99. — Бібліогр.: 4 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-86697
record_format	dspace
spelling	irk-123456789-866972015-09-27T03:02:11Z Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів Яловець, А.Л. Прикладні засоби програмування та програмне забезпечення Розглядається проблема управління стратегіями переслідування/утікання агентів на площині. Аналізується існуючий підхід з управління стратегіями переслідування/утікання, запропонований Р. Айзексом, та обґрунтовується недоцільність його використання для випадку управління агентами. Пропонується метод найближчої точки та обґрунтовуються переваги його використання для управління стратегіями переслідування/утікання для довільної кількості агентів. 2013 Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів / А.Л. Яловець // Проблеми програмування. — 2013. — № 4. — С. 94-99. — Бібліогр.: 4 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/86697 004.942+623.465 uk Проблеми програмування Інститут програмних систем НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Ukrainian
topic	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення
spellingShingle	Прикладні засоби програмування та програмне забезпечення Прикладні засоби програмування та програмне забезпечення Яловець, А.Л. Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів Проблеми програмування
description	Розглядається проблема управління стратегіями переслідування/утікання агентів на площині. Аналізується існуючий підхід з управління стратегіями переслідування/утікання, запропонований Р. Айзексом, та обґрунтовується недоцільність його використання для випадку управління агентами. Пропонується метод найближчої точки та обґрунтовуються переваги його використання для управління стратегіями переслідування/утікання для довільної кількості агентів.
author	Яловець, А.Л.
author_facet	Яловець, А.Л.
author_sort	Яловець, А.Л.
title	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів
title_short	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів
title_full	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів
title_fullStr	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів
title_full_unstemmed	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів
title_sort	про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів
publisher	Інститут програмних систем НАН України
publishDate	2013
topic_facet	Прикладні засоби програмування та програмне забезпечення
url	http://dspace.nbuv.gov.ua/handle/123456789/86697
citation_txt	Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів / А.Л. Яловець // Проблеми програмування. — 2013. — № 4. — С. 94-99. — Бібліогр.: 4 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT âlovecʹal prometodnajbližčoítočkiâkmetodupravlínnâstrategíâmipereslíduvannâutíkannâagentív
first_indexed	2025-07-06T14:14:16Z
last_indexed	2025-07-06T14:14:16Z
_version_	1836907240051703808
fulltext	Прикладні засоби програмування та програмне забезпечення © А.Л. Яловець, 2013 94 ISSN 1727-4907. Проблеми програмування. 2013. № 4 УДК 004.942+623.465 А.Л. Яловець ПРО МЕТОД НАЙБЛИЖЧОЇ ТОЧКИ ЯК МЕТОД УПРАВЛІННЯ СТРАТЕГІЯМИ ПЕРЕСЛІДУВАННЯ/УТІКАННЯ АГЕНТІВ Розглядається проблема управління стратегіями переслідування/утікання агентів на площині. Аналізу- ється існуючий підхід з управління стратегіями переслідування/утікання, запропонований Р. Айзексом, та обґрунтовується недоцільність його використання для випадку управління агентами. Пропонується метод найближчої точки та обґрунтовуються переваги його використання для управління стратегіями переслідування/утікання для довільної кількості агентів. Вступ В роботі [1] ми запропонували ме- тод формування стратегії поведінки аген- та-переслідувача та, моделюючи процес переслідування/утікання агентів засобами системи «Навігація» (версія 1.0), розгляну- ли випадок «один утікач – один пересліду- вач», у рамках якого керування агентом- утікачем здійснював користувач, а агент- переслідувач автоматично реагував на дії агента-утікача, приймаючи оптимальні рі- шення на основі використання розробле- ного нами метода переслідування на пло- щині. Тобто якщо агент-переслідувач в хо- ді процесу моделювання діяв оптимально, то агент-утікач – ні. Водночас у [1] ми обґрунтували до- цільні стратегії поведінки агента-утікача та його агентів-переслідувачів, засновані на розробленому нами методі переслідування. Але при цьому залишився неформалізова- ним процес управління використанням цих стратегій в рамках рішення загальної зада- чі переслідування/утікання. Мета даної ро- боти – викладення метода найближчої точки, який узагальнює процеси викорис- тання таких стратегій поведінки агентів для випадку n переслідувачів та m утікачів, де n ≥ m. 1. Аналіз стратегії переслідування/утікання для випадку «один утікач – два переслідувачі» Дослідимо відому стратегію пере- слідування/утікання для випадку «один утікач – два переслідувачі», розглянуту Р. Айзексом в [2, с. 189] (для зручності ви- кладення далі цю стратегію будемо нази- вати стратегією Р. Айзекса). Як буде пока- зано далі, розгляд даної стратегії важливий тому, що в загальному випадку максимум два переслідувачі (з довільної їх кількості) впливають на характер поведінки дослі- джуваного утікача. Мета дослідження – оцінка доцільності використання стратегії Р. Айзекса для управління стратегіями по- ведінки агентів. Сутність стратегії Р. Айзекса поля- гає в знаходженні найбільш віддаленої то- чки від утікача в області, утвореної в ре- зультаті перетину двох кіл Аполлонія, по- будованих для кожної з пар утікач-пере- слідувач, та виконанню простого руху (за умови, що швидкості переслідувачів біль- ше швидкості утікача) до цієї точки як уті- качем, так і його переслідувачами (або, як буде показано далі, одним з його переслі- дувачів). При цьому, стратегії поведінки утікача та його переслідувачів будуть оп- тимальними. Моделювання стратегії Р. Айзекса засобами системи «Навігація», версія 1.5. З метою дослідження стратегії Р. Айзекса нами розроблений прототип системи «На- вігація». В ході досліджень виявлено, що можуть виникати 3 різні випадки: 1) коли два кола Аполлонія пере- тинаються і переслідувачі розташовані по різні боки щодо лінії, що проходить через точку розміщення утікача та найбільш від- далену точку перетину кіл Аполлонія; 2) коли два кола Аполлонія пере- тинаються і переслідувачі розташовані по Прикладні засоби програмування та програмне забезпечення 95 один бік щодо лінії, що проходить через точку розміщення утікача та найбільш від- далену точку перетину кіл Аполлонія; 3) коли два кола Аполлонія не пе- ретинаються (одне коло знаходиться в ме- жах іншого). Перший випадок відповідає ситуа- ції, розглянутій Р. Айзексом в [2] (рис. 1). У даному випадку утікач Е та переслідува- чі Р1 і Р2, у відповідності до стратегії Р. Айзекса, мають рухатись до точки 1 (точки перетину кіл Аполлонія як найбільш від- даленої точки області перетину). За умови, що Е, Р1 та Р2 перебуватимуть при цьому у стані простого руху, вони одночасно дося- гнуть точки 1. Другий випадок відповідає ситуації (рис. 2), коли утікача Е буде захоплено тільки одним переслідувачем (Р1) в точці 1, а інший переслідувач (Р2) буде рухатись у напрямку точки 2. Цей випадок має місце тоді, коли точки дислокації переслідувачів Р1 та Р2 (рис. 2) розташовані з одного боку щодо січної MN, яку проведено через точ- ку дислокації Е та найбільш віддалену (щодо Е) точку перетину кіл Аполлонія. Третій випадок також відповідає ситуації (рис. 3), коли утікача Е буде захо- плено тільки одним переслідувачем (Р1) в точці 1, а інший переслідувач (Р2) буде ру- хатись у напрямку точки 2. Окремо відзначимо, що у другому і третьому випадках точка 1 відповідає най- більш віддаленій від Е точці області пере- тину кіл Аполлонія. Виходячи з цього (див. рис. 2 та рис. 3), в даних випадках оптима- льна стратегія утікача Е полягає у тому, що він має рухатись за напрямом, що задається променем, направленим від переслідувача Р1 до утікача Е, що повністю збігається з нашими висновками в [1] щодо доцільної стратегії поведінки агента-утікача. В свою чергу, переслідувачі Р1 та Р2 у всіх випад- ках рухаються у відповідності до стратегії паралельного зближення (або, інакше ка- жучи, стратегії, що відповідає методу пере- слідування, викладеному в [1]). Недоліки стратегії Р. Айзекса. Виходячи з проведених досліджень можна назвати такі основні недоліки: 1) напрям руху утікача обчислю- ється в результаті виконання розрахунків у відповідності до метода, запропоновано- го Р. Айзексом, і не змінюється в процесі P1 P2 E 1 Рис. 1. Приклад стратегій переслідування/утікання для випадку 1 Прикладні засоби програмування та програмне забезпечення 96 E P1 P2 1 2 M N Рис. 2. Приклад стратегій переслідування/утікання для випадку 2 E P1 P2 1 2 Рис. 3. Приклад стратегій переслідування/утікання для випадку 3 Прикладні засоби програмування та програмне забезпечення 97 переслідування. В дійсності ж, напрям ру- ху утікача задається явно на початку про- цесу переслідування, як вхідний параметр задачі переслідування, і в будь-який на- ступний момент часу формується ситуа- ційно в залежності від дій його пересліду- вачів (ясно, що при цьому утікач має нама- гатися сформувати оптимальну стратегію утікання). 2) стратегія Р. Айзекса передбачає тільки простий рух утікача/переслідувачів. У дійсності на характер руху як утікача, так і переслідувачів можуть впливати різні перешкоди (як рухомі, так і нерухомі), які вимагають необхідності виконання відпо- відних маневрів. До того ж, швидкість ру- ху як утікача, так і переслідувачів може змінюватись у процесі переслідування. Як наслідок, очевидно, що в загальному випа- дку характер руху утікача/переслідувачів не є простим. Очевидно, що метод, який доцільно покласти в основу управління стратегіями переслідування/утікання, не повинен мати таких недоліків. 2. Метод найближчої точки Метод найближчої точки призначе- ний для формування оптимального напря- му руху утікача в залежності від поточних напрямів руху його переслідувачів. Як ми показали в п. 1 статті, можливі два стани (які ми будемо називати рівноважними станами) щодо оптимального напряму руху утікача: Стан 1. Коли утікач і два його най- ближчі переслідувачі рухаються до точки перетину двох кіл Аполлонія як найбільш віддаленої точки області перетину цих кіл (див. випадок 1 в п. 1 статті). Стан 2. Коли утікач рухається за напрямом, що задається променем, напра- вленим від найближчого переслідувача до цього утікача (див. випадки 2, 3 в п. 1 статті). Тут під найближчим переслідувачем розуміється переслідувач, який на даний момент часу може скоріше за всіх інших переслідувачів наздогнати утікача (тобто точка Аполлонія, яка побудована від цього переслідувача, буде найближчою до утіка- ча). Далі ми будемо посилатися на названі стани. Сутність методу найближчої точ- ки полягає у тому, що утікач у процесі пе- реслідування в кожний момент часу ви- значає найближчу до нього точку Аполло- нія (з точок, побудованих від переслідува- чів, що потрапили в його зону спостере- ження [3]) та, якщо він не перебуває у рів- новажному стані, то поступово змінює кут свого руху з метою досягнення рівноваж- ного стану, або якщо він перебуває у рів- новажному стані, а положення цієї точки Аполлонія виводить його з цього стану, то поступово змінює кут свого руху з метою досягнення нового рівноважного стану. Зазначимо також, що точка Аполлонія та доцільний напрям руху переслідувачів, ви- користовувані у методі найближчої точки, визначаються за допомогою розробленого нами метода переслідування [1]. Відмін- ною ознакою пропонованого метода най- ближчої точки є те, що він, на відміну від стратегії Р. Айзекса, взагалі не передбачає необхідності побудови кіл Аполлонія. Особливості застосування методу найближчої точки розглянемо на прикладі (рис. 4). Нехай задано зону спостереження утікача як квадрат 10001000 точок, а зна- чення зміни кута руху для утікача (коли він перебуває в нерівноважному стані) складає 2 за кожні 0.2 сек. його руху. За- значимо, що в прототипі системи «Навіга- ція», версія 2.0 [4], де цей метод реалізова- но, ці параметри є настроюваними. Нехай на початок процесу переслідування/ уті- кання агенти розташовані на місцях, пока- заних на рис. 4, і утікач Е рухається під кутом 147 з постійною швидкістю 5 вуз- лів, а переслідувачі Р1 та Р2 рухаються з постійними швидкостями відповідно 7 та 8 вузлів. На початку процесу переслідування в межах зони спостереження агента-утіка- ча Е знаходиться тільки агент-пересліду- вач Р1, точка Аполлонія, побудована від якого, є точкою 1 (точку 2 як точку Апол- лонія, побудовану від переслідувача Р2, на рис. 4 показано довідково). У відповіднос- ті до метода найближчої точки, з метою переходу до рівноважного стану (стану 2 – див. вище) агент-утікач Е поступово змі- нює напрям свого руху, ухиляючись від Прикладні засоби програмування та програмне забезпечення 98 P1 P2 E 1 2 3 4 6 E’ P1' P2' 5 Рис. 4. Приклад застосування метода найближчої точки агента-переслідувача Р1 як свого найближ- чого переслідувача. Агенти-переслідувачі, реагуючи на зміни напряму руху агента- утікача, в кожний момент часу перевизна- чають доцільний кут свого руху і також розвертаються. При цьому точка 1 посту- пово зміщується до положення точки 4, а точка 2 – до положення точки 3. В резуль- таті агент-утікач переходить до рівноваж- ного стану (стану 2), агент-переслідувач Р1 рухається безпосередньо за агентом-утіка- чем Е у напрямку точки 4, а агент-пере- слідувач Р2 рухається у напрямку точки 3, але він залишається за межами зони спо- стереження агента-утікача Е. Такий рух триває, поки агент-утікач не опиниться в точці 5, що відповідає ситуації, коли агент- переслідувач Р2 потрапив в межі зони спо- стереження агента-утікача Е. При цьому найближчою точкою Аполлонія для аген- та-утікача Е стає точка 3, і він починає змінювати напрям руху з метою переходу до нового рівноважного стану, ухиляючись від агента-переслідувача Р2 як свого най- ближчого переслідувача. В свою чергу, агенти-переслідувачі реагують на зміну напряму руху агента-утікача, в кожний момент часу перевизначають доцільний кут свого руху і також розвертаються. При цьому точки 3 та 4 поступово зміщуються до положення точки 6, і процес зміни на- пряму руху триватиме до тих пір, поки агент-утікач Е не досягне рівноважного стану (стану 1), при якому і агент-утікач (що опиниться в точці Е), і його агенти- переслідувачі (що опиняться відповідно у точках Р1 та Р2 – див. рис. 4) будуть руха- тися у напрямку точки 6 як найбільш від- даленої точки області перетину двох кіл Аполлонія. Зазначимо, що кола Аполлонія на рис. 4 показані умовно, з метою підтер- дження збігання результатів роботи мето- ду найближчої точки з результатами відп- рацювання стратегії Р. Айзекса. Прикладні засоби програмування та програмне забезпечення 99 Легко помітити, що даний метод справедливий для довільної кількості пе- реслідувачів. Дійсно, в будь-який момент часу переслідування кожний агент-утікач може опинитися в одному з двох станів (або у рівноважному, або у нерівноважно- му). Якщо утікач перебуває у нерівноваж- ному стані, то на його поведінку в кожний момент часу впливає один і тільки один найближчий агент-переслідувач, що зна- ходиться в межах зони спостереження уті- кача. Якщо ж агент-утікач перебуває в рів- новажному стані, то в кожний момент часу на його поведінку можуть впливати мак- симум два агенти-переслідувачі, відносно яких рівноважний стан сформовано. Останнє положення потребує додаткового обґрунтування. Як ми показали вище, іс- нує два види рівноважного стану. В стані 2, незалежно від загальної кількості перес- лідувачів, на поведінку агента-утікача впливає один і тільки один найближчий переслідувач, що знаходиться в межах йо- го зони спостереження. В стані 1 в загаль- ному випадку на поведінку утікача можуть впливати стільки агентів-переслідувачів, скільки з них утворили ту ж саму загальну точку Аполлонія, яка утворена двома його найближчими агентами-переслідувачами відповідно до умов виникнення стану 1. Тобто агент-утікач в даному випадку обов’язково буде рухатись у напрямку цієї точки Аполлонія, що відповідає сутності стану 1, незалежно від того, скільки аген- тів-переслідувачів утворили таку точку. Інакше кажучи, випадок, коли довільна кількість агентів-переслідувачів утворила загальну точку Аполлонія, зводиться до випадку, який відповідає стану 1. Висновки З вищевикладеного випливають пе- реваги запропонованого метода: 1) метод дозволяє адаптивно до по- точних змін формувати оптимальну стра- тегію поведінки агента-утікача; 2) метод дозволяє адаптивно до по- точних змін підтримувати оптимальні стратегії поведінки агентів-переслідувачів; 3) метод дозволяє моделювати про- цес переслідування/утікання в реальному масштабі часу, враховуючи при цьому особливості поведінки різних за властиво- стями агентів. Очевидно, що метод найближчої точки не має недоліків, наведених в п. 1 статті (в тому числі він справедливий у випадку, коли рух агентів не є простим). В цілому можна стверджувати, що метод найближчої точки дозволяє моде- лювати поведінку агентів в мультиагент- ному стилі і є прийнятним методом управ- ління стратегіями переслідування/утікання довільної кількості агентів. 1. Яловець А.Л. Про один метод переслі- дування на площині // Проблеми програму- вання. – 2013. – № 3. – С. 117–124. 2. Айзекс Р. Дифференциальные игры. – М.: Мир, 1967. – 479 с. 3. Яловець А.Л. До постановки задачі переслі- дування на площині // Проблеми програму- вання. – 2013. – № 2 – С. 95–100. 4. Яловець А.Л., Кондращенко В.Я., Арістов В.В. Свідоцтво № 46897 про реєстрацію авторського права на твір «Комп’ютерна програма – “Мультиагентна система “Наві- гація”, версія 2.0”». – Державна служба інтелектуальної власності України, 2012. Одержано 20.03.2013 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 15 38. E-mail: yal@isofts.kiev.ua mailto:yal@isofts.kiev.ua

Про метод найближчої точки як метод управління стратегіями переслідування/утікання агентів

Репозитарії

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