The architecture and functionality of the multi-agent system Navigation

The features of the design, development and functioning of the multi-agent system Navigation are investigated. System architecture and substantiate the choice of language implementation of the system are provided. The functionality of the subsystems of multi-agent systems Navigation is analyzed in d...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2018
Автор:	Yalovets, A.L.
Формат:	Стаття
Мова:	Ukrainian
Опубліковано:	Інститут програмних систем НАН України 2018
Теми:	architecture multi-agent system functions of subsystems multi-agent model-ling UDC 004.942+004.415.2
Онлайн доступ:	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/224
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Problems in programming
Завантажити файл:

Репозитарії

Problems in programming

id	pp_isofts_kiev_ua-article-224
record_format	ojs
resource_txt_mv	ppisoftskievua/1f/9616412d37a628bde154e8716180421f.pdf
spelling	pp_isofts_kiev_ua-article-2242024-04-28T11:56:41Z The architecture and functionality of the multi-agent system Navigation Архитектура и функциональные возможности мультиагентной системы Навигация Архітектура та функціональні можливості мультиагентної системи Навігація Yalovets, A.L. architecture; multi-agent system; functions of subsystems; multi-agent model-ling UDC 004.942+004.415.2 архитектура; мультиагентная система; функции подсистем; мультиагентное моделирование УДК 004.942+004.415.2 архітектура; мультиагентна система; функції підсистем; мультиагентне моделювання УДК 004.942+004.415.2 The features of the design, development and functioning of the multi-agent system Navigation are investigated. System architecture and substantiate the choice of language implementation of the system are provided. The functionality of the subsystems of multi-agent systems Navigation is analyzed in detail. The results of multi-agent modelling of pursuit/escape processes by means of the multi-agent system in different modes of its functioning are compared on meaningful example.Problems in programming 2017; 1: 83-96 Рассматриваются особенности проектирования, разработки и функционирования мультиагентной системы Навигация. Приводится архитектура системы и обосновывается выбор языка реализации системы. Детально анализируются функциональные возможности подсистем мультиагентной системы Навигация. На содержательном примере сравниваются результаты мультиагентного моделирования процессов преследования/убегания агентов средствами мультиагентной системы при разных режимах ее функционирования.Problems in programming 2017; 1: 83-96 Розглядаються особливості проектування, розробки та функціонування мультиагентної системи Навігація. Наводиться архітектура системи та обґрунтовується вибір мови реалізації системи. Детально аналізуються функціональні можливості підсистем мультиагентної системи Навігація. На змістовному прикладі порівнюються результати мультиагентного моделювання процесів переслідування/утікання агентів засобами мультиагентної системи за різними режимами її функціонування.Problems in programming 2017; 1: 83-96 Інститут програмних систем НАН України 2018-11-20 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/224 10.15407/pp2017.01.083 PROBLEMS IN PROGRAMMING; No 1 (2017); 83-96 ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2017); 83-96 ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2017); 83-96 1727-4907 10.15407/pp2017.01 uk https://pp.isofts.kiev.ua/index.php/ojs1/article/view/224/217 Copyright (c) 2018 ПРОБЛЕМИ ПРОГРАМУВАННЯ
institution	Problems in programming
baseUrl_str	https://pp.isofts.kiev.ua/index.php/ojs1/oai
datestamp_date	2024-04-28T11:56:41Z
collection	OJS
language	Ukrainian
topic	architecture multi-agent system functions of subsystems multi-agent model-ling UDC 004.942+004.415.2
spellingShingle	architecture multi-agent system functions of subsystems multi-agent model-ling UDC 004.942+004.415.2 Yalovets, A.L. The architecture and functionality of the multi-agent system Navigation
topic_facet	architecture multi-agent system functions of subsystems multi-agent model-ling UDC 004.942+004.415.2 архитектура мультиагентная система функции подсистем мультиагентное моделирование УДК 004.942+004.415.2 архітектура мультиагентна система функції підсистем мультиагентне моделювання УДК 004.942+004.415.2
format	Article
author	Yalovets, A.L.
author_facet	Yalovets, A.L.
author_sort	Yalovets, A.L.
title	The architecture and functionality of the multi-agent system Navigation
title_short	The architecture and functionality of the multi-agent system Navigation
title_full	The architecture and functionality of the multi-agent system Navigation
title_fullStr	The architecture and functionality of the multi-agent system Navigation
title_full_unstemmed	The architecture and functionality of the multi-agent system Navigation
title_sort	architecture and functionality of the multi-agent system navigation
title_alt	Архитектура и функциональные возможности мультиагентной системы Навигация Архітектура та функціональні можливості мультиагентної системи Навігація
description	The features of the design, development and functioning of the multi-agent system Navigation are investigated. System architecture and substantiate the choice of language implementation of the system are provided. The functionality of the subsystems of multi-agent systems Navigation is analyzed in detail. The results of multi-agent modelling of pursuit/escape processes by means of the multi-agent system in different modes of its functioning are compared on meaningful example.Problems in programming 2017; 1: 83-96
publisher	Інститут програмних систем НАН України
publishDate	2018
url	https://pp.isofts.kiev.ua/index.php/ojs1/article/view/224
work_keys_str_mv	AT yalovetsal thearchitectureandfunctionalityofthemultiagentsystemnavigation AT yalovetsal arhitekturaifunkcionalʹnyevozmožnostimulʹtiagentnojsistemynavigaciâ AT yalovetsal arhítekturatafunkcíonalʹnímožlivostímulʹtiagentnoísisteminavígacíâ AT yalovetsal architectureandfunctionalityofthemultiagentsystemnavigation
first_indexed	2024-09-16T04:07:36Z
last_indexed	2024-09-16T04:07:36Z
_version_	1818568185731874816
fulltext	Архітектура програмного забезпечення © А.Л. Яловець, 2017 ISSN 1727-4907. Проблеми програмування. 2017. № 1 83 УДК 004.942+004.415.2 А.Л. Яловець АРХІТЕКТУРА ТА ФУНКЦІОНАЛЬНІ МОЖЛИВОСТІ МУЛЬТИАГЕНТНОЇ СИСТЕМИ НАВІГАЦІЯ Розглядаються особливості проектування, розробки та функціонування мультиагентної системи Наві- гація. Наводиться архітектура системи та обґрунтовується вибір мови реалізації системи. Детально ана- лізуються функціональні можливості підсистем мультиагентної системи Навігація. На змістовному прикладі порівнюються результати мультиагентного моделювання процесів переслідування/утікання агентів засобами мультиагентної системи за різними режимами її функціонування. Ключові слова: архітектура, мультиагентна система, функції підсистем, мультиагентне моделювання. Вступ Мультиагентна система (МАС) На- вігація [1, 2] створена на основі методів, викладених в [3–8]. МАС Навігація приз- начена для моделювання поведінки мно- жини інтелектуальних агентів у складному динамічному середовищі. Змістовно під динамічним середовищем розуміється ді- лянка морського кордону, в межах якої протидіють два класи кораблів: кораблі- порушники (утікачі) та кораблі берегової охорони (переслідувачі). Відповідно до цього, розглядаються два класи антагоніс- тичних агентів (агенти-утікачі та агенти- переслідувачі), які протидіють у динаміч- ному середовищі. Перед початком процесу моделювання переслідування агенти- переслідувачі засобами системи оптималь- но розподіляються по групах, кожна з яких націлена на захоплення цілком визначено- го агента-утікача. Кожний з агентів- переслідувачів, що належить окремій гру- пі, реагує на дії відповідного агента- утікача, а агенти-утікачі, в свою чергу, ре- агують на дії агентів-переслідувачів, які призначені для їх захоплення. Вважається, що кожний агент-утікач може перебувати в одному з двох станів: або він знає своїх переслідувачів, або він не знає своїх пере- слідувачів. У другому випадку кожний агент-утікач у кожний момент часу свого руху формує припущення щодо своїх віро- гідних переслідувачів, на дії яких він і реа- гує. Будь-який агент намагається діяти найоптимальнішим чином: агенти-пере- слідувачі використовують оптимальні стратегії для найшвидшого захоплення ві- дповідних агентів-утікачів, а агенти- утікачі використовують відповідні страте- гії для збільшення часу їх захоплення (або уникнення цього) агентами-переслідува- чами. З метою як найшвидшого захоплен- ня агентів-утікачів агенти-переслідувачі в процесі переслідування можуть вступати між собою у перемовини, за результатами яких можуть переходити в інші групи. Агенти для запобігання зіткнень з іншими агентами використовують методи манев- рування, які відповідають вимогам Міжна- родних правил попередження зіткнення суден у морі [9]. 1. Архітектура та мова реалізації МАС Навігація Узагальнену архітектуру МАС На- вігація показано на рис. 1. В архітектурі МАС можна умовно виділити дві укрупне- ні функціонально орієнтовані складові (се- редовище формування даних для мульти- агентного моделювання та середовище мультиагентного моделювання процесів переслідування/утікання), пов’язані між собою через підсистему керування проце- сом моделювання (див. рис. 1). До складу середовища формування даних для мультиагентного моделювання входять три підсистеми, засобами яких ви- конується завантаження, підготовка, реда- гування та збереження початкових даних, потрібних для функціонування середовища мультиагентного моделювання процесів переслідування/утікання, яке, в свою чер- гу, включає до свого складу дві головні підсистеми МАС Навігація. Функціональні можливості підсистем, показаних на рис. 1, Архітектура програмного забезпечення 84 Рис. 1. Узагальнена архітектура МАС Навігація розглянуто в п. 2 даної роботи. Для реалізації МАС Навігація вико- ристано мову PDC Visual Prolog 5.2 (VIP) з наступних міркувань: по-перше, VIP – це реляційна мова, завдяки чому суттєво спрощується створення, обробка та збере- ження різноманітних баз даних (БД), пот- рібних для опису агентів та їх станів; по-друге, VIP – це мова логічного програ- мування, за допомогою якої забезпечуєть- ся адекватний опис логіки поведінки аген- тів у різноманітних ситуаціях та подання знань агентів про їх дії у різних обставинах. 2. Функціональні можливості підсистем МАС Навігація 2.1. Підсистема завантажен- ня/формування/редагування/зберігання опису агентів дозволяє побудувати нову БД описів агентів або завантажити раніше збережену БД. Під побудовою БД описів агентів розуміється процес послідовного формування множини агентів у графічно- му полі. Під формуванням агента розумі- ється упорядкована сукупність операцій, що включає (див. рис. 2): вибір вида агента (з панелі інструментів), параметризацію агента та його відображення у вибраній точці графічного поля. Як видно з рис. 2, як інтерфейс ця підсистема разом з діало- говим інтерфейсом використовує інтер- фейс графічної підсистеми відображення станів агентів (див. п. 2.6). Сформовані описи агентів можуть бути відредаговані за допомогою pull-down меню, що відкривається при виділенні агента у графічному полі і натисканні на праву кнопку миші. Вибір опції меню „Ви- лучити” призводить до вилучення агента з графічного поля (та його опису з БД). Ви- бір опції „Редагувати” призводить до зава- нтаження діалогу параметризації (див. рис. 2), в якому користувач має можли- вість внести зміни до опису агента. Архітектура програмного забезпечення 85 Рис. 2. Приклад виконання параметризації агента Описи агентів утворюють БД описів агентів, яка може бути збережена та по- вторно завантажена. Сформована (заван- тажена) БД описів агентів утворює почат- ковий стан агентів (див. рис. 1), викорис- товуваний для подальшого моделювання процесів переслідування/утікання. 2.2. Підсистема налаштування параметрів моделювання дозволяє сфо- рмувати значення додаткових параметрів, які впливають на результати модельова- ного процесу переслідування/утікання агентів. Як інтерфейс ця підсистема вико- ристовує діалог «Установки параметрів» (див. рис. 3). Рис. 3. Діалог налаштування параметрів Засобами цього діалогу задаються додаткові параметри властивостей як агентів-утікачів, так і агентів-пересліду- вачів. Для агентів-утікачів задаються зна- чення двох параметрів: зони спостере- ження та обізнаності щодо складу їх пере- слідувачів. За допомогою зони спостереження моделюється простір видимості для агентів- утікачів і вони спостерігають тільки тих інших агентів, які в ній перебувають. За- значимо, що агенти-утікачі можуть перебу- вати в одному з двох станів: або вони зна- ють своїх агентів-переслідувачів, або ні. В другому випадку кожний агент-утікач для визначення складу своїх вірогідних агентів- переслідувачів (які потрапили в його зону спостереження) в кожний момент модельо- ваного часу формує припущення. В свою чергу, агенти-переслідувачі для зменшення часу переслідування мо- жуть або переходити в інші групи, або ні, що і задається за допомогою діалогу. Як наслідок, в результаті відповід- них призначень параметрів можливі чоти- ри альтернативи з моделювання поведінки агентів: «агенти-утікачі знають своїх аген- тів-переслідувачів та агенти-переслідувачі не перегруповуються»; «агенти-утікачі не знають своїх агентів-переслідувачів та Архітектура програмного забезпечення 86 агенти-переслідувачі не перегруповують- ся»; «агенти-утікачі знають своїх агентів- переслідувачів та агенти-переслідувачі пе- регруповуються»; «агенти-утікачі не зна- ють своїх агентів-переслідувачів та агенти- переслідувачі перегруповуються». Зазна- чені альтернативи суттєво розширяють функціональні можливості МАС Навігація щодо моделювання процесів пересліду- вання/утікання на площині (приклади мо- делювання див. п. 3 даної роботи). 2.3. Підсистема автоматично- го/ручного формування угрупувань аге- нтів дозволяє сформувати групи агентів двома шляхами: автоматично (для цього використовується метод, викладений в [8]) або вручну. Автоматичне формування груп аге- нтів відбувається шляхом отримання опти- мального рішення щодо стану груп, при якому мінімізується загальний час захоп- лення всіх утікачів переслідувачами з ура- хуванням обмеження, що швидкість кожно- го переслідувача у групі перебільшує шви- дкість відповідного утікача. При цьому, якщо швидкість окремого переслідувача у групі менша за швидкість відповідного уті- кача, підсистема діагностує помилку, для усунення якої необхідно засобами підсис- теми завантаження/формування/редагу- вання/зберігання опису агентів (див. п. 2.1) відредагувати швидкості агентів. Тобто ця підсистема може також використовувати інтерфейс підсистеми, описаної в п. 2.1. Результати автоматичного форму- вання груп агентів користувач може перег- лянути за допомогою діалогу „Формування груп” (див. рис. 4), який є інтерфейсом да- ної підсистеми. В процесі формування груп вручну користувач може створювати групи за сво- їми уподобаннями, редагувати склад груп та переглядати розташування агентів у гра- фічному полі (на рис. 4 показано приклад виділення агента для перегляду). Тобто да- на підсистема може також використовувати інтерфейс графічної підсистеми відобра- ження станів агентів (див. п. 2.6 та рис. 1). Рис. 4. Діалог формування/редагування стану груп агентів Архітектура програмного забезпечення 87 2.4. Підсистема керування проце- сом моделювання стає доступною після успішного завершення роботи підсистеми автоматичного/ручного формування угру- пувань агентів (див. п. 2.3), – при цьому стає активною кнопка „Запуск пересліду- вання” панелі інструментів головного вік- на МАС. При натисканні на цю кнопку керування передається підсистемі дискре- тної обробки паралельних процесів (див. рис. 1 та п. 2.5 даної роботи). При цьому стає активною (enabled) кнопка „Зупинити переслідування” панелі інструментів го- ловного вікна МАС, а кнопка „Запуск пе- реслідування” стає неактивною (disabled). Користувач МАС Навігація в будь- який момент модельованого часу має мо- жливість призупинити процес моделю- вання шляхом натискання на кнопку „Зу- пинити переслідування”. При цьому стає неактивною кнопка „Зупинити пересліду- вання”, а кнопка „Продовжити пересліду- вання” панелі інструментів головного вік- на МАС стає активною. При натисканні на кнопку „Зупи- нити переслідування” відбувається зни- щення таймера, запущеного на початку процесу моделювання, поточний стан агентів запам’ятовується як початковий стан агентів (див. рис. 1) та за- пам’ятовуються траєкторії здійснених ру- хів всіх агентів, що разом утворюють фа- зову траєкторію динамічної системи на момент зупинки модельованого часу. Зу- пинка процесу моделювання надає корис- тувачу можливість змінити поточні пара- метри моделювання та проаналізувати стан агентів на даний момент модельова- ного часу. Поновлення процесу моделювання відбувається шляхом натискання на кноп- ку „Продовжити переслідування”, при цьому ця кнопка стає неактивною, а кноп- ка „Зупинити переслідування” – актив- ною. При натисканні на кнопку „Продов- жити переслідування” відбувається запуск таймера і процес моделювання засобами підсистеми дискретної обробки паралель- них процесів поновлюється зі збережено- го початкового стану агентів з урахуван- ням поточних параметрів моделювання (див. рис. 1). 2.5. Підсистема дискретної оброб- ки паралельних процесів є головною пі- дсистемою МАС Навігація, в рамках якої реалізовано методи, викладені в [3–7]. За- собами цієї підсистеми підтримуються всі аспекти прийняття рішень агентами в ме- жах модельованих процесів. При активації даної підсистеми ві- дбувається запуск таймера і в кожний мо- мент модельованого часу кожний рухо- мий агент аналізує свій поточний стан та стани інших агентів з метою вирішення поставлених перед ним задач. На рис. 5 показано діаграму діяль- ності і-го агента в довільний момент мо- дельованого часу (в нотації UML). Ця діа- грама узагальнено характеризує всі осно- вні аспекти прийняття рішень довільним агентом (додатково зазначимо, що діагра- му діяльності щодо виконання маневру- вання агентами наведено в [5]). Для зага- льності подання, в діаграмі розглянуто будь-якого агента (як рухомого, так і не- рухомого), хоча в реалізації поточні стани нерухомих агентів підсистемою не розгля- даються та не поновлюються. Засобами даної підсистеми в кож- ний момент модельованого часу послідов- но розглядаються всі рухомі агенти відпо- відно до наведеної діаграми їх діяльності. З точки зору програмної реалізації, це відбувається в процесі виконання ок- ремого періоду таймера події e_Timer. Пі- сля завершення виконання періоду тайме- ра події e_Timer, виконується виклик по- дії e_Update, в рамках якої відбувається перемальовування поновленого стану всіх агентів засобами підсистеми відображен- ня станів агентів (див. п. 2.6 та рис. 1), після чого керування знов передається події e_Timer і так далі, до моменту захо- плення всіх утікачів або призупинення процесу моделювання засобами підсисте- ми керування процесом моделювання (див. п. 2.4). Зазначимо, що множина знань аген- тів, яка включає (див. рис. 5) правила прийняття рішень агентами та алгоритми, використовувані ними для оптимізації вла- сних дій, узагальнено утворюють БЗ аген- тів щодо прийняття рішень (див. рис. 1). Архітектура програмного забезпечення 88 Рис. 5. Діаграма діяльності і-го агента в довільний момент модельованого часу Архітектура програмного забезпечення 89 Слід підкреслити, що дана підсис- тема не має власного інтерфейсу, але ви- користовує чотири зовнішні інтерфейси (див. рис. 1): графічної підсистеми відо- браження станів агентів (графічне вікно для малювання поточних станів агентів у кожний момент модельованого часу) та протоколів (три графічних вікна для відо- браження текстових протоколів дій, пере- мовин та припущень агентів). 2.6. Графічна підсистема відо- браження станів агентів, як вище пока- зано, використовується декількома підси- стемами як інтерфейс (див. рис. 1) та при- значена для відображення поточних ста- нів агентів як на етапі формування описів агентів (див. п. 2.1), так і в процесі муль- тиагентного моделювання (див. п. 2.5). Водночас основним призначенням цієї підсистеми є надання користувачу МАС Навігація головного інтерфейсу мульти- агентного моделювання, оскільки саме завдяки їй користувач може в реальному масштабі часу спостерігати всі візуальні аспекти модельованих процесів. У даній підсистемі реалізовано основні функціо- нальні можливості, притаманні графічним системам (у тому числі масштабування, здвиг, знаходження та виділення об’єктів моделювання тощо). 3. Функціональні можливості МАС Навігація Функціональні можливості МАС Навігації щодо мультиагентного моделю- вання процесів переслідування/утікання розглянемо на прикладі, в якому засобами підсистеми налаштування параметрів мо- делювання (див. п. 2.2 даної роботи) зада- но чотири різні режими моделювання: 1) утікачам відомі їх переслідувачі, які не можуть перегруповуватись (рис. 7); 2) утікачам невідомі їх пересліду- вачі, які не можуть перегруповуватись (рис. 8); 3) утікачам відомі їх переслідува- чі, які можуть перегруповуватись (рис. 9); 4) утікачам невідомі їх пересліду- вачі, які можуть перегруповуватись (рис. 10). На рис. 6 показано приклад почат- кової дислокації агентів, який ми будемо далі використовувати для демонстрації розбіжностей при різних режимах моде- лювання процесів переслідуван- ня/утікання агентів на площині. На рису- нку в центрі дислокації розташовані уті- качі (обведені колом), які оточені перес- лідувачами. Результати мультиагентного моде- лювання процесів переслідуван- ня/утікання, виконаного засобами МАС Навігація, для чотирьох вищезазначених режимів моделювання наведено в табли- цях 1–4. Зазначимо, що час, витрачений аге- нтами-переслідувачами на захоплення аге- нтів-утікачів, обчислюється в секундах модельованого часу (див. табл. 1–4), який визначається внаслідок здійснення муль- тиагентного моделювання засобами МАС Навігація при встановленому періоді тай- мера зі значенням 0.2 сек. Абревіатури, що позначають агентів, є їх унікальними іден- тифікаторами, які автоматично генерують- ся при первинному формуванні описів аге- нтів (наприклад, 28ЧРВ сформовано шля- хом конкатенації порядкового номера аге- нта (28) та ознак «чужий» (Ч), «рухомий» (Р) та «військовий» (В)). Порівняння результатів моделю- вання при режимах, в яких переслідувачі не вступали у перемовини (не перегрупо- вувались), а утікачі знали (див. рис. 7 та табл. 1) або не знали (див. рис. 8 та табл. 2) своїх переслідувачів, дозволяє зробити ви- сновок, що у даному випадку наявність знань в утікачів щодо їх переслідувачів, по-перше, значно збільшує як мінімальний час їх захоплення (до 90 % – див., напри- клад, мінімальний час захоплення утікача 28ЧРВ в табл. 1 та 2), так і загальний мак- симальний час переслідування (до 25 %), по-друге, призводить до різних траєкторій руху утікачів, внаслідок чого їх первинне захоплення здійснюється різними переслі- дувачами (за винятком утікача 31ЧРВ, у якого траєкторія руху та переслідувач з мінімальним часом захоплення в обох ре- жимах збігаються, що пояснюється тим, що даний утікач, на відміну від інших уті- качів, у процесі свого руху не відчував впливу переслідувачів з інших груп). Архітектура програмного забезпечення 90 Рис. 6. Приклад початкової дислокації агентів Рис. 7. Утікачі знають своїх переслідувачів; переслідувачі не можуть перегруповуватись Архітектура програмного забезпечення 91 Рис. 8. Утікачі не знають своїх переслідувачів; переслідувачі не можуть перегруповуватись Рис. 9. Утікачі знають своїх переслідувачів; переслідувачі можуть перегруповуватись Архітектура програмного забезпечення 92 Рис. 10. Утікачі не знають своїх переслідувачів; переслідувачі можуть перегруповуватись Таблиця 1 Результати мультиагентного моделювання процесів переслідування/утікання для випадку, коли утікачам відомі їх переслідувачі, переслідувачі не можуть перегруповуватись Номер групи Утікач Склад опти- мальної групи переслідувачів Переслідувач/ min час захоплення (с) Переслідувач/ max час захоплення (с) Загальний max час пересліду- вання (с) 1 28ЧРВ 23СРВ 25СРВ 26СРВ 23СРВ/40 26СРВ/40 40 2 29ЧРВ 20СРВ 21СРВ 22СРВ 21СРВ/28 20СРВ/36 3 30ЧРВ 17СРВ 19СРВ 24СРВ 24СРВ/18 19СРВ/26 4 31ЧРВ 16СРВ 18СРВ 27СРВ 27СРВ/23 18СРВ/32 Архітектура програмного забезпечення 93 Таблиця 2 Результати мультиагентного моделювання процесів переслідування/утікання для випадку, коли утікачам невідомі їх переслідувачі, переслідувачі не можуть перегруповуватись Номер групи Утікач Склад опти- мальної групи переслідувачів Переслідувач/ min час захоплення (с) Переслідувач/ max час захоплення (с) Загальний max час пересліду- вання (с) 1 28ЧРВ 23СРВ 25СРВ 26СРВ 26СРВ/21 23СРВ/32 32 2 29ЧРВ 20СРВ 21СРВ 22СРВ 22СРВ/23 20СРВ/31 3 30ЧРВ 17СРВ 19СРВ 24СРВ 17СРВ/11 24СРВ/31 4 31ЧРВ 16СРВ 18СРВ 27СРВ 27СРВ/23 18СРВ/28 Таблиця 3 Результати мультиагентного моделювання процесів переслідування/утікання для випадку, коли утікачам відомі їх переслідувачі, переслідувачі можуть перегруповуватись Номер групи Утікач Склад опти- мальної групи переслідувачів Склад групи після пере- групування Переслідувач/ min час захоплення (с) Переслідувач/ max час захоплення (с) Загальний max час пересліду- вання (с) 1 28ЧРВ 23СРВ 25СРВ 26СРВ + 16СРВ 20СРВ 25СРВ 16СРВ/11 20СРВ/23 30 2 29ЧРВ 20СРВ 21СРВ 22СРВ + 21СРВ 26СРВ 27СРВ 26СРВ/16 27СРВ/20 3 30ЧРВ 17СРВ 19СРВ 24СРВ – 17СРВ 19СРВ 24СРВ 19СРВ/21 17СРВ/26 4 31ЧРВ 16СРВ 18СРВ 27СРВ + 18СРВ 22СРВ 23СРВ 23СРВ/14 18СРВ/30 Архітектура програмного забезпечення 94 Таблиця 4 Результати мультиагентного моделювання процесів переслідування/утікання для випадку, коли утікачам невідомі їх переслідувачі, переслідувачі можуть перегруповуватись Номер групи Утікач Склад опти- мальної групи переслідувачів Склад групи після пере- групування Переслідувач/ min час захоп- лення (с) Переслідувач/ max час захоплення (с) Загальний max час пересліду- вання (с) 1 28ЧРВ 23СРВ 25СРВ 26СРВ + 19СРВ 20СРВ 23СРВ 19СРВ/16 23СРВ/29 31 2 29ЧРВ 20СРВ 21СРВ 22СРВ + 21СРВ 22СРВ 25СРВ 25СРВ/19 22СРВ/28 3 30ЧРВ 17СРВ 19СРВ 24СРВ + 17СРВ 24СРВ 26СРВ 17СРВ/11 24СРВ/31 4 31ЧРВ 16СРВ 18СРВ 27СРВ – 16СРВ 18СРВ 27СРВ 27СРВ/13 18СРВ/27 Якщо ж порівнювати результати моделювання при режимах, в яких перес- лідувачі вступали у перемовини (могли перегруповуватись), а утікачі знали (див. рис. 9 та табл. 3) або не знали (див. рис. 10 та табл. 4) своїх переслідувачів, то у дано- му випадку наявність знань в утікачів що- до їх переслідувачів не мала такого зна- чення, як у попередньому порівнянні. По- перше, на дії утікачів (і, як наслідок, на час їх захоплення), які знали своїх пересліду- вачів, впливала необхідність маневрування між собою (на відміну від утікачів, які не знали своїх переслідувачів). По-друге, ви- конане перегрупування переслідувачів (в табл. 3, 4 групи, в яких відбулось перегру- пування, позначено символом «+»; на рис. 9 та 10 переслідувачі, які перегрупувалися, обведені колами) ще більше зменшило час захоплення відповідних утікачів. Водно- час, невиконання перегрупування та наяв- ність знань щодо своїх переслідувачів (див., наприклад, мінімальний час захоп- лення утікача 30ЧРВ в табл. 3 та 1) приз- водить до збільшення часу первинного за- хоплення цього утікача на 17 %. Ефекти від перегрупування віддзер- калює і попарне порівняння режимів, коли утікачам відомі їх переслідувачі, що або перегруповуються, або ні (див. табл. 3 і рис. 9 та табл. 1 і рис. 7), та коли утікачам невідомі їх переслідувачі, що або перегру- повуються, або ні (див. табл. 4 і рис. 10 та табл. 2 і рис. 8). В першому випадку вна- слідок перегрупування мінімальний час захоплення зменшується від 40 % до 73 %, а максимальний час захоплення – від 6 % до 44 % (порівн. табл. 1 та табл. 3); у дру- гому випадку – мінімальний час захоплен- ня зменшується від 17 % до 43 %, а макси- мальний час захоплення – від 4 % до 10 % (порівн. табл. 2 та 4). Слід окремо підкреслити суттєвий вплив процесів маневрування на процеси переслідування/утікання агентів (і, як на- слідок, на час захоплення утікачів): в процесі маневрування агенти не тільки змінюють напрям руху з метою уникнен- ня зіткнень, а й за необхідністю зменшу- ють швидкість свого руху (аж до повної Архітектура програмного забезпечення 95 зупинки), що значно впливає на часові характеристики процесів переслідуван- ня/утікання. Крім того зауважимо, в МАС Навігація реалізовано автоматичні зміни швидкостей агентів у випадках, коли агент-утікач вперше розпізнав, що в зону його спостереження потрапив агент- переслідувач, який гіпотетично може бути його переслідувачем. В такій ситуації да- ний агент-утікач збільшує свою швидкість до максимально можливої, при цьому йо- го фактичні агенти-переслідувачі також збільшують свої швидкості до максима- льно можливих. З вищевикладеного стає очевидним, що формування груп за допомогою мето- дів оптимізації (див. [8]) в розглянутих ди- намічних системах не дозволяє гарантува- ти отримання дійсно оптимальних рішень (за критерієм часу захоплення), оскільки, як показано вище, на поведінку об’єктів оптимізації впливають різні чинники, що ускладнюють визначення чітких критеріїв оптимізації. Як наслідок, стає очевидним, що на основі методів оптимізації можна викона- ти лише первинний розподіл агентів по групах, який у подальшому може бути сут- тєво покращений завдяки перегрупуванню агентів за результатами перемовин. Висновки В статті описано особливості прое- ктування, реалізації та функціонування МАС Навігації, як системи, засобами якої здійснюється моделювання процесів пере- слідування/утікання агентів на площині для загального випадку (n переслідувачів, m утікачів, де n ≥ m). Для МАС Навігації наведено її архітектуру з детальною харак- теристикою основних функціональних компонентів; подано діаграму діяльності довільного агента, яка дозволяє отримати уявлення про «приховані» процеси прий- няття рішень агентами; продемонстровано функціональні можливості МАС Навігація за різними режимами її функціонування. МАС Навігацію можна розглядати як ін- струментарій для практичної перевірки теоретичних результатів, отримуваних у рамках досліджень з теорії диференційних ігор. 1. Яловець А.Л., Кондращенко В.Я., Арістов В.В. Свідоцтво № 46897 про реєстрацію авторського права на твір «Комп’ютерна програма – “Мультиагентна система “Навігація”, версія 2.0”». Державна служба інтелектуальної власності України, 2012. 2. Яловець А.Л., Кондращенко В.Я., Арістов В.В. Свідоцтво № 57880 про реєстрацію авторського права на твір «Комп’ютерна програма – “Мультиагентна система “Наві- гація”, версія 2.5” (“МАС Навігація 2.5”)». – Державна служба інтелектуальної влас- ності України, 2014 р. 3. Яловець А.Л. До постановки задачі перес- лідування на площині. Проблеми програ- мування. 2013. № 2. С. 95–100. 4. Яловец А.Л. Методы моделирования пове- дения агентов в мультиагентной системе «Навигация». Проблеми програмування. 2014. № 2–3. С. 212–220. 5. Яловець А.Л. Проблема моделювання ма- неврування агентів в задачах пересліду- вання/утікання на площині. Проблеми про- грамування. 2015. № 2. С. 86–100. 6. Яловець А.Л. Про метод найближчої точки як метод управління стратегіями переслі- дування/утікання агентів. Проблеми про- грамування. 2013. № 4. С. 94–99. 7. Яловець А.Л. Про один метод пересліду- вання на площині. Проблеми програму- вання. 2013. № 3. С. 117–124. 8. Яловець А.Л. Проблема формування угру- пувань агентів у задачах переслідуван- ня/утікання на площині. Проблеми про- грамування. 2014. № 1. С. 108–118. 9. Коккрофт А.Н., Ламеер Дж.Н.Ф. Руковод- ство по Правилам предупреждения столк- новения. СПб: ООО «МОРСАР». 2005. 320 с. References 1. Yalovets A.L., Kondraschenko V.Ya., Aris- tov V.V. 46897 Certificate of registration of copyright in a product "Computer program – "Multi-agent systems "Navigation" version 2.0" ". The State Service of Intellectual Prop- erty of Ukraine, 2012. (in Ukrainian). 2. Yalovets A.L., Kondraschenko V.Ya., Aris- tov V.V. 57880 Certificate of registration of copyright in a product "Computer program - "Multi-agent systems "Navigation" version Архітектура програмного забезпечення 96 2.5" ("MAS Navigation 2.5")". The State Service of Intellectual Property of Ukraine, 2014. (in Ukrainian). 3. Yalovets A.L. To problem definition of prosecuting in the plane. Problems in pro- gramming. 2013. N 2. P. 95–100. (in Ukrainian). 4. Yalovets A.L. Methods of modelling the be- haviour of agents in multi-agent system "Nav- igation". Problems in programming. 2014. N 2–3. P. 212–220. (in Russian). 5. Yalovets A.L. The problem of modelling of maneuvering of agents in the tasks of pursuit/escape on a plane. Problems in programming. 2015. N 2. P. 86–100. (in Ukrainian). 6. Yalovets A.L. About the method of the near- est point as a method of strategies manage- ment of pursuit/escape of agents. Problems in programming. 2013. N 4. P. 94–99. (in Ukrainian). 7. Yalovets A.L. About one method of the per- secution on a plane. Problems in program- ming. 2013. N 3. P. 117–124. (in Ukrainian). 8. Yalovets A.L. The problem of the formation of groups of agents in the tasks of pur- suit/escape on a plane. Problems in pro- gramming. 2014. N 1. P. 108–118. (in Ukrainian). 9. Cockroft A.N., Lameijer J.N.F. A Guide to the Collision Avoidance Rules. Sankt- Petersburg: “MORSAR” Ltd. 2005. 320 p. (in Russian). Одержано 29.12.2016 Про автора: Яловець Андрій Леонідович, доктор технічних наук, заступник директора інституту. Кількість наукових публікацій в українських виданнях – понад 100. Кількість наукових публікацій в зарубіжних виданнях – 5. http://orcid.org/0000-0001-6542-3483 Місце роботи автора: Інститут програмних систем НАН України. 03187, Київ-187, проспект Академіка Глушкова, 40. Тел.: (044) 526 15 38. E-mail: yal@isofts.kiev.ua mailto:yal@isofts.kiev.ua

The architecture and functionality of the multi-agent system Navigation

Репозитарії

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