Проблема формування угрупувань агентів у задачах переслідування/утікання на площині

Досліджуються особливості задачі формування угрупувань агентів. Виконується постановка задачі формування угрупувань, на основі якої пропонуються та досліджуються два методи (метод перебору та евристичний метод) рішення цієї задачі. Обґрунтовується можливість використання розроблених методів для ріше...

Повний опис

Збережено в:

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

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-86745
record_format	dspace
spelling	irk-123456789-867452015-10-01T03:02:08Z Проблема формування угрупувань агентів у задачах переслідування/утікання на площині Яловець, А.Л. Прикладні засоби програмування та програмне забезпечення Досліджуються особливості задачі формування угрупувань агентів. Виконується постановка задачі формування угрупувань, на основі якої пропонуються та досліджуються два методи (метод перебору та евристичний метод) рішення цієї задачі. Обґрунтовується можливість використання розроблених методів для рішення задач про призначення. 2014 Article Проблема формування угрупувань агентів у задачах переслідування/утікання на площині / А.Л. Яловець // Проблеми програмування. — 2014. — № 1. — С. 108-118. — Бібліогр.: 7 назв. — укр. 1727-4907 http://dspace.nbuv.gov.ua/handle/123456789/86745 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	Досліджуються особливості задачі формування угрупувань агентів. Виконується постановка задачі формування угрупувань, на основі якої пропонуються та досліджуються два методи (метод перебору та евристичний метод) рішення цієї задачі. Обґрунтовується можливість використання розроблених методів для рішення задач про призначення.
format	Article
author	Яловець, А.Л.
author_facet	Яловець, А.Л.
author_sort	Яловець, А.Л.
title	Проблема формування угрупувань агентів у задачах переслідування/утікання на площині
title_short	Проблема формування угрупувань агентів у задачах переслідування/утікання на площині
title_full	Проблема формування угрупувань агентів у задачах переслідування/утікання на площині
title_fullStr	Проблема формування угрупувань агентів у задачах переслідування/утікання на площині
title_full_unstemmed	Проблема формування угрупувань агентів у задачах переслідування/утікання на площині
title_sort	проблема формування угрупувань агентів у задачах переслідування/утікання на площині
publisher	Інститут програмних систем НАН України
publishDate	2014
topic_facet	Прикладні засоби програмування та програмне забезпечення
url	http://dspace.nbuv.gov.ua/handle/123456789/86745
citation_txt	Проблема формування угрупувань агентів у задачах переслідування/утікання на площині / А.Л. Яловець // Проблеми програмування. — 2014. — № 1. — С. 108-118. — Бібліогр.: 7 назв. — укр.
series	Проблеми програмування
work_keys_str_mv	AT âlovecʹal problemaformuvannâugrupuvanʹagentívuzadačahpereslíduvannâutíkannânaploŝiní
first_indexed	2025-07-06T14:17:07Z
last_indexed	2025-07-06T14:17:07Z
_version_	1836907419911847936
fulltext	Прикладні засоби програмування та програмне забезпечення © А.Л. Яловець, 2014 108 ISSN 1727-4907. Проблеми програмування. 2014. № 1 УДК 004.942+623.465 А.Л. Яловець ПРОБЛЕМА ФОРМУВАННЯ УГРУПУВАНЬ АГЕНТІВ У ЗАДАЧАХ ПЕРЕСЛІДУВАННЯ/УТІКАННЯ НА ПЛОЩИНІ Досліджуються особливості задачі формування угрупувань агентів. Виконується постановка задачі фо- рмування угрупувань, на основі якої пропонуються та досліджуються два методи (метод перебору та евристичний метод) рішення цієї задачі. Обґрунтовується можливість використання розроблених мето- дів для рішення задач про призначення. Вступ Проблема формування угрупувань (коаліцій) агентів – це невід’ємна складова загальновідомої проблеми, що отримала назву coalition structure generation problem (CSGP). Можна стверджувати, що в цілому теоретичні підвалини CSGP сформовані та досліджувались в рамках вирішення роз- подільчих задач (у тому числі транспорт- них задач та задач про призначення). За останні роки дослідження CSGP отримали потужного розвитку завдяки задачам, ви- рішуваним у рамках теорії ігор та мульти- агентного підходу. В даній статті CSGP розглядається з точки зору проблематики мультиагентного підходу. Відомо [1], що в загальному ви- падку формування коаліцій агентів відбу- вається в результаті проведення перегово- рів між ними з метою підвищення ефекти- вності рішення деякої складної задачі за рахунок кооперації дій агентів (при цьому ефективність визначається в термінах ви- рішуваної задачі). Як правило, такі коаліції агентів можуть бути сформовані в довіль- ний момент часу, функціонують на протязі короткого проміжку часу і далеко не зав- жди вимоги до їх формування відповіда- ють вимогам оптимальності. На відміну від цього, в нашому ви- падку [2] угрупування агентів формуються до початку процесу переслідування/уті- кання, функціонують на протязі всього ча- су цього процесу (тобто довгостроково) і мають відповідати вимогам оптимальності щодо їх формування. Як показано в [2], за результатами переговорів агенти можуть переходити з групи в групу, але такі пере- ходи можуть відбутися вже в процесі пе- реслідування. Для підкреслення таких роз- біжностей ми використовуємо термін «угрупування» (або «група»), а не «коалі- ція» агентів, хоча у всіх інших аспектах розгляду ці терміни ідентичні за змістом. Сутність задачі формування угру- пувань агентів полягає у наступному. Існує n переслідувачів та m утікачів (де mn  ). Треба сформувати m оптимальних угрупу- вань (що не перетинаються) агентів-пере- слідувачів, необхідних і достатніх для за- хоплення всіх агентів-утікачів. Як показа- но в [3], дана задача є NP-важкою у силь- ному смислі. Слід відзначити, що загальна про- блема переслідування/утікання на площині – це об’єкт досліджень теорії диференцій- них ігор [4]. При цьому, хоча в рамках да- ної теорії вживається термін «наряд», що є аналогом використовуваного нами терміну «угрупування», в ній явно не ставиться пи- тання формування множин оптимальних нарядів щодо захоплення всіх утікачів. З цього випливає, що досліджувана нами задача це нова задача в проблематиці CSGP і для її вирішення необхідно розроб- ляти відповідні математичні методи. Оче- видно, що задача формування оптималь- них угрупувань агентів належить до класу задач цілочисельного лінійного програму- вання і її можна розглядати як окремий різновид розподільчої задачі [5]. 1. Постановка задачі формування оптимальних угрупувань агентів Постановка задачі ґрунтується на двох передумовах: 1) розподіл переслідувачів по гру- пах має бути рівномірним; Прикладні засоби програмування та програмне забезпечення 109 2) цільова функція – це мінімізація по всіх групах максимального часу захоп- лення переслідувачами, що належать окремій групі, відповідного утікача, за умови, що швидкість кожного пересліду- вача у групі більше швидкості утікача. Детальніше розглянемо названі пе- редумови. Рівномірний розподіл по групах орієнтований на гарантування умов захоп- лення кожного з утікачів. У тому випадку, якщо рівномірний розподіл неможливий (якщо кількість переслідувачів по групах не є однаковою), то більша кількість нада- ється групі (групам), націлених на утікача, час захоплення якого більший у порівнянні з іншими утікачами. Для визначення максимального ча- су захоплення переслідувачами утікача ро- зглянемо приклад (див. рис. 1). Нехай на початку процесу переслідування утікач E та переслідувач P розташовані у місцях, показаних на рис. 1. Утікач E рухається зі швидкістю Ev , а переслідувач P – зі шви- дкістю Pv , причому Pv Ev . Як ми пока- зали в [6], оптимальним напрямом руху утікача в даному випадку буде напрям, що задається променем, направленим від перес- лідувача P до цього утікача (будь-який ін- ший напрям руху утіка- ча E призведе до його більш скорішого захоп- лення). Переслідувач P для захоплення утікача E буде рухатись безпо- середньо за ним. При- пустимо, що захоплен- ня утікача відбудеться у точці 1 за час t з моме- нту одночасного почат- ку руху утікача та пере- слідувача. З рисунку легко помітити, що максимально можливий час t захоплення переслідувачем P утікача E визначається за допомогою виразу: . EP vv L t   (1) Виходячи з наведених передумов виконаємо постановку задачі формування оптимальних угрупувань агентів. Нехай задано n ( 0n ) пересліду- вачів та m ( 0m ) утікачів, де mn  . Ма- ксимальний час, необхідний для захоплен- ня j -тим переслідувачем (де nj ,...,2,1 ) i -того утікача (де mi ,...,2,1 ), визначе- ний для випадків, коли швидкості ij vv  , відомий (див. (1)) і дорівнює ijt ( 0ijt ). Введемо булівську змінну ijx , що дорівнює 1, якщо j-тий агент переслідує i-того утікача, і 0 – в протилежному випад- ку. З метою мінімізації загального макси- мального часу захоплення всіх m утікачів необхідно вирішити задачу оптимізації: }.1,0{ ;,,2,1, min; 1 1 1         ij i n j ij m i n j ijij x mikx tx  (2) Як ми показали вище, ik є наперед задані числа, що характеризують розподіл пере- слідувачів по групах, причому nk m i i  1 . 2. Метод перебору з формування оптимальних угрупувань агентів Метод перебору з формування оп- тимальних угрупувань агентів заснований на генерації всіх можливих комбінацій рі- зних сполучень m груп таких, що за скла- дом кожна i -та група ( mi ,,2,1  ) місти- тиме ik переслідувачів (де кількість пере- слідувачів у групах визначається у відпо- відності до передумови 1 (див. розділ 1 статті)) і кожний переслідувач у i -тій гру- пі матиме швидкість, більшу ніж швид- кість i -того утікача, та вибору такого спо- лучення груп, при якому загальний час за- хоплення всіх утікачів буде мінімальним. Зазначимо, що в найгіршому випад- ку кількість комбінацій сполучень (КС), яка буде сформована за допомогою цього метода, складає    m i ik n KC 1 ! ! , де n – загальна кількість переслідувачів, Рис. 1. Приклад P Ev P ·t v E ·t L 1 Прикладні засоби програмування та програмне забезпечення 110 m – загальна кількість утворюваних груп (збігається з загальною кількістю утікачів), ik – кількість переслідувачів в i -тій групі (де mi ,,2,1  ). Ця оцінка в точності ви- конується у тому випадку, якщо всі перес- лідувачі у кожній групі мають швидкості вище, ніж швидкість утікача, віднесеного до тієї ж групи. Очевидно, що даний метод є неефе- ктивним оскільки має високу обчислюва- льну складність. Наприклад, якщо задано лише 12 переслідувачів та 6 утікачів, то загальна кількість комбінацій, що буде сформовано за даним методом, складатиме майже 40 млн. варіантів. З цього випливає необхідність роз- робки евристичного методу рішення задачі формування угрупувань агентів, який би мав низьку обчислювальну складність та давав рішення, близькі до оптимальних. Зазначимо, що доцільність розробки та реалізації методу перебору продиктова- на необхідністю отримання еталонних оп- тимальних рішень щодо формування угру- пувань агентів задля їх порівняння з ре- зультатами роботи запропонованого нами евристичного методу (див. розділ 3 статті). 3. Евристичний метод формуван- ня угрупувань агентів Метод передбачає, що на початку процесу формування угрупувань відомо: кількість n ( 0n ) переслідувачів; кіль- кість m ( 0m ) утікачів (як наслідок, ві- дома кількість утворюваних груп); коор- динати точок розташування та поточна швидкість кожного переслідувача jP ( nj ,,2,1  ) та утікача iE ( mi ,,2,1  ); кількість переслідувачів у кожній групі. Сутність метода полягає у виконан- ні наступних чотирьох кроків. Крок 1. Побудова матриці максима- льного часу захоплення. Для кожної пари jP iE у відповідності із виразом (1) ви- значається максимальний час захоплення утікача iE . На основі отриманих даних (ча- сових одиниць (ч.од.)) будується матриця mn , рядки якої містять відповідні дані по переслідувачам, а стовбці – по утікачам. Крок 2. Ранжирування рядків мат- риці. В кожному рядку матриці знаходить- ся максимальний за значенням ч.од. еле- мент та виконується нумерація рядків у порядку зменшення таких значень. Крок 3. Побудова опорного плану задачі формування угрупувань агентів від- бувається шляхом послідовного аналізу рядків за порядком, визначеним на кроці 2. При цьому в кожному аналізованому ряд- ку вибирається мінімальний елемент та перевіряється стан групи, що відповідає утікачу, ідентифікатор якого розташова- ний у заголовку стовпця, в котрому міс- титься вибраний елемент. Якщо кількість раніше вибраних елементів менше кілько- сті запланованих переслідувачів у аналізо- ваній групі, то ідентифікатор переслідува- ча додається до складу групи. В супротив- ному випадку в аналізованому рядку виби- рається наступний мінімальний елемент і виконується перевірка стану відповідної групи. Крок 3 повторюється до тих пір, доки не будуть сформовані всі групи. Крок 4. Формування угрупувань агентів. На цьому кроці виконується коре- ктування опорного плану, сформованого на кроці 3. Для цього послідовно попарно аналізуються (зліва направо) всі можливі сполучення стовпців. У процесі аналізу в таких стовпцях послідовно вибираються по одному елементу з елементів, доданих до складу груп на кроці 3 (або замінених на кроці 4 – див. далі), до яких знаходяться їх асоційовані елементи. Сутність асоційо- ваного елементу полягає у наступному. Припустимо, що в стовпцях i та j (де ;,,2,1, mji  ji  ) вибрано елементи, що належать відповідно рядкам k та r (де ;,,2,1, nrk  rk  ); перший елемент бу- де позначатися як ikP , а другий – як jrP . Тоді елемент, асоційований першому еле- менту, буде позначатися як jkP , а другому – як irP . Якщо сума значень асоційованих елементів буде менше суми значень виб- раних елементів (тобто, якщо jrikirjk PPPP  ), то у i-тій групі еле- мент ikP буде замінено на елемент irP , а у j-тій групі елемент jrP – на елемент jkP ; в іншому випадку стан цих груп залишиться незмінним. Процес аналізу стовпців про- довжуватиметься до тих пір, поки не бу- Прикладні засоби програмування та програмне забезпечення 111 дуть таким же чином розглянуті всі комбі- нації елементів, вибраних на кроці 3 (або доданих на кроці 4). У випадку, якщо у складі груп відбулися зміни, то описаний процес аналізу повторюється для всіх сто- впців. Виконання кроку 4 триватиме до тих пір, поки у склад груп вже буде немо- жливо внести якісь зміни. Даний евристичний метод отримав назву метода мінімальних перестановок (МП-метод) завдяки своїм відмітним влас- тивостям: на кроці 4 виконуються пе- рестановки елементів і при цьому розгляд- дається мінімальна їх кількість, а саме тільки ті з них, що були додані до складу груп у процесі формування опорного пла- ну (на кроці 3) або замінені на кроці 4. Для демонстрації роботи МП-мето- да розглянемо приклад (див. рис. 2). Нехай задано 5 утікачів та 11 переслідувачів. Роз- поділ по групах здійснено наступним чи- ном (ідентифікатор утікача – кількість пе- реслідувачів): 10ЧРВ – 3; 11ЧРВ – 2; 12ЧРВ – 2; 19ЧРВ – 2; 20ЧРВ – 2. Резуль- тати виконання кроків 1–3 методу наведе- ні в табл.1, де в рядках значення макси- мальних елементів (в ч.од.) викреслені, а мінімальних – показані в прямокутниках. Утікачі 10ЧРВ 11ЧРВ 12ЧРВ 19ЧРВ 20ЧРВ 3ВРС 2ВРС 4ВРС 1ВРС 5ВРС 7ВРС 8ВРС 6ВРС 9ВРС 15ВРС 16ВРС Рис. 2. Приклад розташування агентів на площині Таблиця 1 E P 20ЧРВ 19ЧРВ 12ЧРВ 11ЧРВ 10ЧРВ № п/п 3ВРС 501.0327 345.4408 576.5754 213.3359 99.3058 6 2ВРС 429.6858 287.5740 467.0366 181.8730 95.4958 7 6ВРС 426.5303 268.0972 1064.2049 393.3504 288.4397 3 8ВРС 451.1424 272.3915 1016.2834 360.6651 261.1377 4 1ВРС 455.5799 288.0795 592.1700 234.0547 151.2320 5 4ВРС 335.5805 229.2313 325.9452 158.4404 97.1609 9 16ВРС 349.0485 284.3850 1364.8813 525.1277 397.0915 1 15ВРС 356.6386 264.5223 1223.7569 477.8088 360.4659 2 5ВРС 281.3778 191.3536 283.7464 181.6607 137.7018 10 9ВРС 230.9404 172.9960 373.8740 289.0887 243.0238 8 7ВРС 212.0029 144.0604 197.3407 157.4625 132.4870 11 Прикладні засоби програмування та програмне забезпечення 112 В табл. 2 наведені результати вико- нання кроку 4. Для опису результатів ро- боти методу прийнято наступні умовні по- значення. Символами N позначено на- прям () та номер по порядку (N) викона- ної перестановки. Комірці таблиці, які міс- тять елементи, відкинуті в ході виконання кроку 4, перекреслені хрест-навхрест. Як випливає з табл. 2, в процесі ви- конання кроку 4 відбулося п’ять переста- новок. Розглянемо їх детально. Аналіз стовпців (див. табл. 1, 2), що відповідають утікачам 20ЧРВ та 19ЧРВ, призвів до виконання першої перестанов- ки, в результаті якої переслідувача 5ВРС було виключено зі складу групи, що пере- слідує утікача 20ЧРВ, та додано до групи, що переслідує утікача 19ЧРВ, а пересліду- вача 16ВРС – виключено зі складу групи, що переслідує утікача 19ЧРВ, та додано до групи, що переслідує утікача 20ЧРВ. Легко помітити, що це відбулося внаслідок того, що загальний час переслідування в попе- редніх групах цих переслідувачів переви- щив їх загальний час переслідування у но- вообраних групах. Аналіз інших стовпців щодо стовпця, що відповідає утікачу 20ЧРВ, більше не призвів до перестановок. Аналіз стовпців, що відповідають утікачам 19ЧРВ та 12ЧРВ призвів до дру- гої перестановки, в результаті якої перес- лідувача 5ВРС (переставленого на попере- дньому етапі) виключено зі складу відпо- відної групи та додано до групи, що перес- лідує утікача 12ЧРВ, а переслідувача 4ВРС – виключено зі складу групи, що переслі- дує утікача 12ЧРВ, та додано до групи, що переслідує утікача 19ЧРВ. Подальший аналіз стовпців щодо стовпця (оновленого стану групи), що від- повідає утікачу 19ЧРВ, призвів до третьої перестановки. Це відбулось в процесі ана- лізу стовпця, що відповідає утікачу 10ЧРВ. При цьому переслідувача 4ВРС (перестав- леного на попередньому етапі) виключено зі складу відповідної групи та додано до групи, що переслідує утікача 10ЧРВ, а пе- реслідувача 6ВРС – виключено зі складу групи, що переслідує утікача 10ЧРВ, та додано до групи, що переслідує утікача 19ЧРВ. В свою чергу, аналіз стовпців, що відповідають утікачам 11ЧРВ та 10ЧРВ, призвів до двох перестановок: пересліду- вачів 2ВРС та 3ВРС було виключено з гру- пи, що переслідує утікача 11ЧРВ та додано до групи, що переслідує утікача 10ЧРВ, а переслідувачів 1ВРС та 4ВРС – виключено з групи, що переслідує утікача 10ЧРВ, та додано до групи, що переслідує утікача 11ЧРВ. Легко перевірити, що інших перес- тановок, які б дозволили покращити зага- льний час переслідування, не існує. Таким чином, за допомогою МП- метода сформовано наступні 5 груп (утікач – {його переслідувачі}): 20ЧРВ – {9ВРС, 16ВРС}; 19ЧРВ – {6ВРС, 15ВРС}; 12ЧРВ – {5ВРС, 7ВРС}; 11ЧРВ – {1ВРС, 4ВРС}; 10ЧРВ – {2ВРС, 3ВРС} (в табл. 2 комірки, Таблиця 2 E P 20ЧРВ 19ЧРВ 12ЧРВ 11ЧРВ 10ЧРВ № п/п 3ВРС 501.0327 345.4408 576.5754 213.3359 4 99.3058 6 2ВРС 429.6858 287.5740 467.0366 181.8730 5 95.4958 7 6ВРС 426.5303 268.0972 3 1064.2049 393.3504 288.4397 3 8ВРС 451.1424 272.3915 1016.2834 360.6651 261.1377 4 1ВРС 455.5799 288.0795 592.1700 234.0547 4 151.2320 5 4ВРС 335.5805 229.2313 2 325.9452 158.4404 5 3 97.1609 9 16ВРС 349.0485 1 284.3850 1364.8813 525.1277 397.0915 1 15ВРС 356.6386 264.5223 1223.7569 477.8088 360.4659 2 5ВРС 281.3778 1 191.3536 2 283.7464 181.6607 137.7018 10 9ВРС 230.9404 172.9960 373.8740 289.0887 243.0238 8 7ВРС 212.0029 144.0604 197.3407 157.4625 132.4870 11 Прикладні засоби програмування та програмне забезпечення 113 в яких розташовані вибрані елементи, ви- ділені сірим кольором). Відзначимо, що отриманий результат повністю збігається з оптимальним результатом, сформованим за допомогою метода перебору (див. роз- діл 2 статті). Обчислювальні експерименти, ви- конані на різних ситуаціях щодо складу та станів агентів, показали, що в переважній більшості випадків результати, отримані за допомогою МП-метода, в точності збіга- ються з оптимальними результатами, отри- муваними за допомогою метода перебору. Разом з тим, в окремих випадках можуть виникати колізії, коли МП-метод дає результати, близькі до оптимальних. Для демонстрації цього розглянемо прик- лад (див. рис. 3). Нехай задано 3 утікача та 10 переслідувачів. Розподіл по групах здій- снено наступним чином: 11ЧРВ – 4; 12ЧРВ – 3; 13ЧРВ – 3. Результати виконання кро- ків 1–3 МП-метода наведені в табл. 3. Утікачі 1ВРС 3ВРС 2ВРС 4ВРС 5ВРС 10ВРС 9ВРС 8ВРС 7ВРС 6ВРС 13ЧРВ 11ЧРВ 12ЧРВ Рис. 3. Приклад розташування агентів на площині Таблиця 3 E P 13ЧРВ 12ЧРВ 11ЧРВ № п/п 4ВРС 188.6599 425.2894 342.2410 6 3ВРС 786.3593 858.2734 1081.2086 1 2ВРС 313.6001 563.5073 511.6359 5 1ВРС 717.8997 762.5077 917.3206 3 8ВРС 954.8969 421.0848 816.3402 2 5ВРС 129.0136 297.2840 228.6421 8 10ВРС 112.1387 181.8862 149.4858 10 9ВРС 299.4278 211.5444 273.1016 7 7ВРС 673.0767 255.9162 536.7338 4 6ВРС 247.4528 93.6229 188.6946 9 Прикладні засоби програмування та програмне забезпечення 114 В табл. 4 приведено результати ви- конання кроку 4. Як випливає з таблиці, в даному випадку відбулась тільки одна пе- рестановка (переслідувач 9ВРС був ви- ключений з групи, що переслідує утікача 12ЧРВ, та доданий до групи, що переслі- дує утікача 11ЧРВ, а переслідувач 6ВРС – виключений з групи, що переслідує утіка- ча 11ЧРВ, та доданий до групи, що перес- лідує утікача 12ЧРВ). Таким чином, як випливає з табл. 4, за допомогою МП-метода сформовано три групи (утікач – {його переслідувачі}): 11ЧРВ – {4ВРС, 5ВРС, 9ВРС, 10ВРС}; 12ЧРВ – {6ВРС, 7ВРС, 8ВРС}; 13ЧРВ – {1ВРС, 2ВРС, 3ВРС} з загальним часом переслідування evrt = 3581.9535 ч.од. За- уважимо, що за допомогою метода пере- бору сформовано наступні групи: 11ЧРВ – {5ВРС, 6ВРС, 9ВРС, 10ВРС}; 12ЧРВ – {1ВРС, 7ВРС, 8ВРС}; 13ЧРВ – {2ВРС, 3ВРС, 4ВРС} з загальним часом переслі- дування optt = 3568.0521 ч.од. Порівняння отриманих результатів показує, що похиб- ка МП-метода складає лише 0039.0  opt optevr t tt . Причиною виникнення подібних колізій є похибка методу, що виникає у вироджених випадках і пов’язана з не- можливістю виконання окремої переста- новки (яка характеризується близькістю значень порівнюваних сум), в результаті здійснення якої гарантовано було б отри- мано оптимальний результат. В розгляну- тому прикладі такою перестановкою ма- ла бути перестановка 4ВРС – 1ВРС, яка не відбулась внаслідок того, що 717.8997. + 342.2410 > 917.3206 + 188.6599 Якщо б таку перестановку було здійсне- но, то вона призвела б до перестановки 1ВРС – 6ВРС, яка б і дала оптимальне рі- шення. Для більш детальної перевірки ефек- тивності МП-метода ми розробили спеці- алізовану систему тестування «Генератор тестів» (далі – ССТ ГТ), яку використали для виконання сукупності обчислюваль- них експериментів, результати яких наве- дені в наступному розділі статті. Таблиця 4 E P 13ЧРВ 12ЧРВ 11ЧРВ № п/п 4ВРС 188.6599 425.2894 342.2410 6 3ВРС 786.3593 858.2734 1081.2086 1 2ВРС 313.6001 563.5073 511.6359 5 1ВРС 717.8997 762.5077 917.3206 3 8ВРС 954.8969 421.0848 816.3402 2 5ВРС 129.0136 297.2840 228.6421 8 10ВРС 112.1387 181.8862 149.4858 10 9ВРС 299.4278 211.5444 1 273.1016 7 7ВРС 673.0767 255.9162 536.7338 4 6ВРС 247.4528 93.6229 1 188.6946 9 Прикладні засоби програмування та програмне забезпечення 115 4. Тестування евристичного метода Засобами ССТ ГТ забезпечується по- рівняння результатів формування груп за допомогою двох методів: метода перебору та МП-метода. Для генерування матриці максимального часу захоплення (див. Крок 1 в розділі 3 статті) використовується ге- нератор випадкових чисел (максимальне значення випадкового числа дорівнювало 100). В рамках обчислювальних експери- ментів розглянуто 15 різних співвідношень «кількість переслідувачів – кількість уті- качів», для кожного з яких було згенерова- но 1000 різних випадків вхідних матриць максимального часу захоплення. Приклад робочого вікна ССТ ГТ з діалогом форму- вання тестів показано на рис. 4. Результати виконаної серії тестувань наведені в табл. 5. Рис. 4. Приклад робочого вікна ССТ ГТ Таблиця 5 № з/п Кількість переслідувачів – кількість утікачів Розподіл переслі- дувачів по групах Відсоток оптимальних рі- шень (на 1000 експерим.) Середня похибка 1 13 – 3 5, 4, 4 83.1% 0.035 2 12 – 3 4, 4, 4 81.3% 0.045 3 11 – 4 3, 3, 3, 2 68.9% 0.063 4 11 – 3 4, 4, 3 85.8% 0.041 5 10 – 5 2, 2, 2, 2, 2 58.1% 0.09 6 10 – 4 3, 3, 2, 2 70.6% 0.074 7 10 – 3 4, 3, 3 86.8% 0.051 8 9 – 5 2, 2, 2, 2, 1 63.2% 0.097 9 9 – 4 3, 2, 2, 2 71.9% 0.084 10 9 – 3 3, 3, 3 85.2% 0.065 11 8 – 4 2, 2, 2, 2 74.4% 0.098 12 8 – 3 3, 3, 2 88.7% 0.073 13 7 – 4 2, 2, 2, 1 78.2% 0.098 14 7 – 3 3, 2, 2 89.5% 0.072 15 6 – 3 2, 2, 2 90.8% 0.089 Прикладні засоби програмування та програмне забезпечення 116 В табл. 5 у стовпці «Відсоток опти- мальних рішень» подано відсоткову кіль- кість рішень, отриманих засобами ССТ ГТ за допомогою МП-метода, що збігаються з оптимальними (з 1000 виконаних експери- ментів), сформованими за допомогою ме- тода перебору. Розподіл похибок рішень, близьких до оптимальних, отриманих за допомогою МП-метода, подано на рис. 5 та 6, де кожна похибка вирахувана у від- повідності з наступним співвідношенням: opt optevr t tt  . Діаграми, подані на рис. 5 та 6, ві- дображують кількість похибок, які потра- пили в межі відповідних значень похибок. Легко помітити, що розподіл похибок у всіх виконаних експериментах підпоряд- кований загальному закону: абсолютна 0 10 20 30 40 50 60 70 80 90 100 Значення похибок К іл ь к іс т ь п о х и б о к н а 1 0 0 0 е к с п е р и м е н т ів 0,025 0,05 0,075 0,1 0,125 0,15 0,175 0,2 7 4 1 2 3 5 6. Рис. 5. Розподіл похибок МП-метода для експериментів 1 – 7 (див. табл. 5) 0 10 20 30 40 50 60 70 80 Значення похибок К іл ь к іс т ь п о х и б о к н а 1 0 0 0 е к с п е р и м е н т ів 0,025 0,05 0,075 0,1 0,125 0,15 0,175 0,2 8 . 9 . 11 . 12 . 13 . 14 . 15 . 10 . Рис. 6. Розподіл похибок МП-метода для експериментів 8 – 15 (див. табл. 5) Прикладні засоби програмування та програмне забезпечення 117 більшість похибок належить областям зна- чень 0.025  0.075; зі збільшенням значень похибок кількість похибок суттєво змен- шується. Узагальнюючи результати викона- них обчислювальних експериментів можна стверджувати, що запропонований еврис- тичний метод має достатньо високі показ- ники щодо близькості рішень, отримува- них за його допомогою, до оптимальних рішень, отримуваних за допомогою метода перебору, і тому є доцільним для викорис- тання на практиці. Зазначимо, що в реалізації мультиа- гентної системи «Навігація» [7] ми об’єд- нали можливості викладених методів. Ме- тод перебору використовується у випад- ках, коли загальна кількість переслідувачів не перевищує 15 одиниць або кількість комбінацій сполучень КС (див. розділ 2 статті), що буде утворена, менше 1 млн. варіантів. В інших випадках використову- ється МП-метод. 5. Використання МП-метода для рішення задач про призначення Як показали дослідження, МП-ме- тод також може успішно використовува- тись для рішення задач про призначення. Для проведення обчислювальних експериментів ми використали ССТ ГТ. Результати досліджень подані в табл. 6. Розподіл похибок рішень, близьких до оп- тимальних, отриманих за допомогою МП- метода, подано на рис. 7 Таблиця 6 № з/п Кількість робітників – кі- лькість завдань Відсоток оптимальних рішень (на 1000 експериментів) Середня похибка 1 3 – 3 95.5% 0.198 2 4 – 4 87.9% 0.195 3 5 – 5 76.8% 0.185 4 6 – 6 68.2% 0.167 5 7 – 7 54.2% 0.182 6 8 – 8 47.6% 0.193 0 10 20 30 40 50 60 70 80 Значення похибок К іл ь к іс т ь п о х и б о к н а 1 0 0 0 е к с п е р и м е н т ів 0,025 0,05 0,075 0,1 0,125 0,15 0,175 0,2 1 2 3 4 5 6 Рис. 7. Розподіл похибок МП-метода для експериментів 1 – 6 (див. табл. 6) Прикладні засоби програмування та програмне забезпечення 118 Як випливає з табл. 6 та рис. 7, се- редня похибка МП-метода не перевищує значення 0.2, а розподіл похибок у всіх виконаних експериментах підпорядкова- ний загальному закону: абсолютна біль- шість похибок належить областям значень 0.05  0.15. Зазначимо, що в рамках задач про призначення існують два класи задач: на мінімізацію (саме цей клас задач ми дослі- джували в обчислювальних експеримен- тах) та максимізацію цільової функції. Встановлено, що МП-метод може успішно використовуватись і для рішення класу за- дач щодо максимізації цільової функції. Для цього необхідно (див. розділ 3 статті) на кроці 2 знаходити мінімальний елемент, на кроці 3 – максимальний елемент, на кроці 4 – вибирати значення суми асоційо- ваних елементів, що буде більшою за суму початкових елементів. Висновки Як випливає з вищевикладеного, запропоновані в статті методи дозволяють ефективно вирішувати задачу формування оптимальних груп агентів у рамках моде- льованого процесу переслідування/утікан- ня агентів на площині для випадку n пере- слідувачів та m утікачів (де mn  ). При цьому, метод перебору дозволяє якісно ви- рішувати цю задачу для випадку, коли значення n та m достатньо малі. Як показа- но в статті, в загальному ж випадку доці- льно використовувати запропонований нами евристичний метод – метод мініма- льних перестановок, що дозволяє отриму- вати рішення, які або збігаються з опти- мальними, або є близькими до оптималь- них. На нашу думку, теоретичне та прик- ладне значення запропонованого метода мінімальних перестановок виходить за ра- мки досліджуваної задачі формування оп- тимальних груп агентів, – як ми показали, він може також використовуватись для рі- шення задач про призначення. 1. Dunin-Keplicz B., Verbrugge R. Teamwork in multi-agent systems: a formal approach. – Wiley, UK, 2010. – 224 p. 2. Яловець А.Л. До постановки задачі переслі- дування на площині // Проблеми програму- вання. – 2013. – № 2. – С. 95–100. 3. Пашко С.В., Яловец А.Л. Численные мето- ды решения задач оптимизации преследо- вания // Проблеми програмування. – 2013. – № 4. – С. 82–88. 4. Петросян Л.А., Рисхиев Б.Б. Преследова- ние на плоскости. – М.: Наука, 1991. – 91 с. 5. Гольштейн Е.Г., Юдин Д.Б. Задачи линей- ного программирования транспортного типа. – М.: Наука, 1969. – 382 с. 6. Яловець А.Л. Про один метод пересліду- вання на площині // Проблеми програму- вання. – 2013. – № 3. – С. 117–124. 7. Яловець А.Л., Кондращенко В.Я., Арістов В.В. Свідоцтво № 46897 про реєстрацію авторського права на твір «Комп’ютерна програма – “Мультиагентна система “Наві- гація”, версія 2.0”». – Державна служба інтелектуальної власності України, 2012. Одержано 13.08.2013 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 1538. E-mail: yal@isofts.kiev.ua mailto:yal@isofts.kiev.ua

Проблема формування угрупувань агентів у задачах переслідування/утікання на площині

Репозитарії

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