1 Вступ

1.1 Мотивація

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

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

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

1.2 Мети проекту

Загальна мета цього проекту - фундаментальне дослідження в області координації для самоорганізації децентралізованих агентно-орієнтованих систем.

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

Друга мета проекту, на основі вищезгаданого аналізу, розвинути концепцію механізмів координації й співробітництва для гнучкої системи автоматизації виробничого середовища на прикладі моделі "Lego-роботи". Для цього повинен бути розроблений механізм вибору діяльності.

1.3 Стислий огляд проекту

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

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

Далі фактично починається процес розробки. На основі вищезгаданого розвинений механізм координації для гнучкого виробничого середовища "Lego-роботи". Спочатку у п’ятій главі проаналізовано застосування різних підходів до координації. Потім розвинений механізм координації. Цей механізм описаний шостій главі.

2 Опис й аналіз виробничого середовища

Середовища, як сказано в [RuNo03], є проблемами, до яких агенти та мультиагентні системи є рішенням. Так, особливості середовища безпосередньо впливають на спосіб, яким програма агента повинна бути розвинена.

Взагалі, виробниче середовище складається з:

· безпосередньо середовища: середовище, у якій працює агент.

· критерію якості роботи: це дозволяє знати, як добре агент досягає його цілей.

· способів дій: можливі шляхи, як агент може діяти в системі.

· датчиків: сприйняття агентом середовища.

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

2.1 Класифікація Навколишніх середовищ Завдань

Згідно з [RuNo03], середовища можуть бути класифіковані в таких вимірах:

· Такі, що повністю обдивляються або такі, що частково обдивляються. Якщо датчики агента дають йому доступ до повного стану середовища в кожному пункті вчасно, то виробниче середовище повністю обдивляється. Інакше воно частково обдивляється.

· Детерміновані або стохастичні. Якщо наступний стан середовища повністю визначено поточним станом і дією, виконаною агентом, то ми говоримо, що середовище детерміноване.

· Статичні або динамічні. Якщо середовище може змінитися, у той час як агент міркує, то ми говоримо, що середовище є динамічним.

· Дискретні або безперервні. Дискретне/безперервне розходження може бути застосоване до стану середовища, до способу, яким обробляється час, до сприйняття агентом середовища и до впливу агентом на середовище.

· Одноагентні або мультиагентні. У мультиагентних середовищах виникають такі проблеми проектування агентів як комунікація та стохастичне поводження. Агентні середовища можуть буду конкурентними або кооперативними.

2.2 Аналіз виробничого середовища, що розробляється

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

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

· Воно є стохастичним. Майбутній стан системи не може бути передбачений у сучасний момент, насамперед тому що користувач може динамічно ввести нові завдання.

· Воно є динамічним. Середовище може динамічно змінитися протягом роботи.

· Воно безперервне. Час є безперервним, і неможливо визначити кінцеве число станів системи.

· Воно мультиагентне. Система складається з безлічі різних агентів, які взаємодіють один з одним.

2.3 Опис моделі "Lego-роботи"

Модель була зібрана й використовується як приклад виробничого середовища. Вона складається з таких частин:

· Станції. Вони моделюють станції, що виконують роботу. Спеціальний вид станції - склад, що моделює склад, що тримає деталі.

· Деталі. Вони моделюють деталі, які виробляються в виробничому середовищі. Деталі повинні транспортуватися між станціями відповідно до їхніх власних планів. Транспортування виконується Lego-роботами.

· Lego-роботи. Вони моделюють транспортери, що транспортують деталі між станціями.

Більш повну інформацію щодо моделі, "Lego-роботи" можна знайти в [Resc04].

3 Короткий аналіз агентно-орієнтованої методології

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

3.1 Визначення агента

В літературі немає угоді, що фактично є агентом. Замість цього є кілька визначень. Оскільки написано в [RuNo03], у літературі можуть бути знайдені такі визначення:

· "Агент - комп'ютерна система, що розташована в середовищі і здатна до автономної дії в цьому середовищі, щоб достигнути свою мету". [Weis99]

· Агенти програмного забезпечення - ті, які мають такі особливості:

· Вони розташовані в середовищі

· Вони здатні до гнучкої автономної дії, щоб достигнути свою мету. [JSW96]

· "Агент - що-небудь, що сприймає своє середовище через датчики й впливає на те середовище через виконавчі елементи." [RuNo03]

· "Інтелектуальні агенти безупинно виконують три функції: сприйняття динамічних умов у середовищі; дії, що впливають на середовище; і міркування, щоб інтерпретувати сприйняття, вирішити проблеми і визначити дії." [Haye95]

· Агент - обмежена одиниця програмного забезпечення з певною метою. Будучи автономним, агент пробує досягти цієї мети й для цього взаємодіє безупинно з середовищем й іншими агентами [WGU03].

Останнє визначення агента [WGU03] покриває найзагальніші аспекти концепції агента, тому його було відібрано для цього проекту.

3.2 Фундаментальні поняття агентно-орієнтованої методології

Відповідно до [WUG03] фундаментальні поняття агентно-орієнтованої методології такі (Рисунок 3.1):

Рисунок 3.1: Фундаментальні поняття агентно-орієнтованої методології

· Інкапсуляція: стан та поведінка скомбіновані в агенті.

· Орієнтація на мету: агент поводиться таким чином, щоб досягти певну мету. Мети можуть бути визначені або розроблювачем, або користувачем під час виконання.

· Реактивність: це здатність агента отримувати інформацію про середовище та діяти відповідним чином.

· Автономія: автономія означає контроль над внутрішнім станом й поведінкою. Поведінка агента визначається винятково агентом, а не зовнішніми агентами. Автономія - також попередня умова для проактивності.

· Проактивність: проактивність означає здатність діяти без прямого впливу від зовнішньої сторони. Попередня умова для проактивності - існування цілей.

· Взаємодія: агенти взаємодіють один з одним, щоб досягти індивідуальних цілей і скоординувати використання загальних ресурсів.

· Сталість: агенти мають їхній власний потік контролю. Тому вони спроможні тримати свій внутрішній стан протягом циклу життя.

3.3 Процес ухвалення рішення

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

Питання: як агент приймає рішення, що зробити, відповідно до його моделі середовища? Як написано в [Fern03], залежно від способу, як агенти приймають рішення, що робити, агенти можуть бути класифіковані у двох найважливіших групах:

· Агенти на основі мети:

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

Рисунок 3.2: Агент на основі мети

· Агенти на основі корисності:

Функція корисності трансформує стан у число, що описує пов'язаний ступінь успіху. Агент буде пробувати максимізувати цей ступінь успіху. (Рисунок 3.3)

Рисунок 3.3: Агент на основі корисності

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

Саме такою системою є система автоматизації виробничого середовища, тому в системі, що розробляється, будуть використовуватися агенти на основі корисності.

4 Аналіз Методів Координації

Проблема координації – центральний пункт в мультиагентних системах. Без цього група агентів перетвориться у збори індивідуалів, які не в змозі виконати глобальну мету.

Отже, що є фактично координацією? Відповідно до [GHN+97], координація - процес, в якому агенти беруть участь, щоб гарантувати, що їх дії будуть послідовним і гармонічними. Іншими словами координація дає можливість мультиагентної системі діяти як одна одиниця.

Відповідно до [NLJ96] є кілька причин, чому багаторазові агенти мають потребу в координації:

· Запобігати хаос

Координація необхідна, тому що, з децентралізацією в системах на основі агента, може легко початися хаос. Агенти мають лише локальні мети й знання, що може суперечити іншим. Саме тому група агентів повинна бути скоординована.

· Задовольняти глобальні обмеження

Зазвичай є глобальні обмеження, які група агентів повинна задовольнити, щоб діяти успішно. Агенти повинні координувати їхнє поводження, щоб задовольнити такі глобальні обмеження.

· Розподіляти досвід, ресурси або інформацію

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

· Вирішувати залежності між діями агента

Мети агентів є часто взаємозалежними. Агенти повинні бути скоординованими, щоб вирішувати індивідуальні мети.

· Ефективність

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

Координація, у свою чергу, може вимагати співробітництва. Однак співробітництво серед ряду агентів не обов'язково приводить до координації. Дійсно, це може навіть привести до незв'язного поводження. Це виникає, тому що агенти, щоб співробітничати успішно, повинні підтримати моделі один одного так само як розвити й підтримувати моделі їхніх майбутніх взаємодій. Якщо вірування агента друг про друга неправильні, співробітництво може привести до незв'язного поводження.

Координація може також відбутися без співробітництва. Аналогічно, відсутність співробітництва серед агентів не обов'язково приводить до незв'язного поводження.

Щоб досягати координації, агентам, імовірно, треба спілкуватися один з одним. Однак, агенти можуть досягти координації без комунікації, використовуючи моделі поведінки один одного. У такій ситуації, координація може бути досягнута через організацію.

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

5 Підходи до координації у виробничому середовищі

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

Ціль координації в межах системи полягає в тому, щоб знайти таку відповідність між завданнями транспортування деталей й роботами, що їх виконують, яка приносять найвищу корисність (Рисунок 5.1).

Рисунок 5.1: Відповідність між завданнями транспортування й роботами

Далі наведені 4 методі координації, які можуть бути використані у мультиагентному виробничому середовищі (Рисунок 5.2).

Рисунок 5.2: Підходи до координації у виробничому середовищі

5.1 Ієрархічний (Централізований) Підхід

5.1.1 Опис

Ієрархічні або централізовані підходи засновані на припущенні, що є центральний координуючий агент (Рисунок 5.3)

Рисунок 5.3: Ієрархічний (централізований) підхід

Мета цього центрального координатора полягає в тому, щоб зробити й потім удосконалити список всіх дій транспортування. Щоб зробити це, він має:

· спочатку одержати інформацію від деталей про завдання, які повинні бути виконані;

· після одержання нової інформації виробити відповідність між завданнями транспортування деталей та роботів.

Вищезгаданий описаний підхід координації був здійснений в [Resc04].

5.1.2 Переваги

Такий підхід до координації, здається, є найпростішим. Так, відносно легко здійснити ієрархічний підхід у реальному прототипі.

Він також приводить до помірного комунікаційного навантаження. Дійсно, деталі зв'язуються з агентом координатором лише один раз, щоб оголосити завдання транспортування. З роботами також зв'язуються лише один раз, коли глобальний план готовий.

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

5.1.3 Недоліки

Перший пункт - низька надійність. З відмовою агента-координатора ціла система стає недіючою. Це типовий недолік всіх централізованих систем.

По-друге, хоча глобальне навантаження на систему зв’язку порівняно низьке, всі комунікації проходять через об'єкт координатора. Таким чином, зі збільшенням кількості агентів у системі, координатор може стати вузьким місцем цілої системи. Це, у свою чергу приводить до зменшення швидкості й надійності.

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

5.2 Контрактний Підхід

5.2.1 Опис

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

Рисунок 5.4: Контрактний підхід

Цей підхід використовувався, наприклад, в [MuBo96] у мультиагентній системі для розподіленого планування розподіленої обробки.

5.2.2 Переваги

Контрактний підхід децентралізований за своєю природою, тому система, здійснена на його основі буде більше надійною та швидкою.

Контрактний підхід також дозволяє робити повністю динамічний розподіл завдань. Це уможливлює додавати й видаляти агентів у процесі виконання.

Контрактний протокол також пропонує природні здібності до балансування навантаження.

5.2.3 Недоліки

Однак повна децентралізація – це також недолік, тому що при ній дуже важко вирішувати конфлікти між роботами, наприклад, у випадку розподілу ресурсу.

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

5.3 Командне планування

5.3.1 Опис

Згідно з цим підходом робота відбувається

1. Таке чи інше розподілення завдань транспортування деталей між роботами. Чим ближче початковий розподіл до оптимального розподілу, тим краще.

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

Графічне уявлення командного планування наведено нижче (Рисунок 5.5).

Рисунок 5.5: Командне планування

Є 2 дуже важливих питання для командного планування:

· Як зробити початковий розподіл, перше наближення, так, щоб воно було як можливо ближче до оптимального?

· Як виконувати згадану вище оптимізацію?

Немає загальних відповідей на ці питання, таких, що підходять для всіх типів середовищ. Деякі ідеї щодо того, як зробити перше наближення й зробити оптимізацію представлені в [EPR95] й [Modi03].

Дуже цікавий приклад практичної реалізації командного планування може бути знайдений в [EPR95], де представлений евристичний алгоритм максимізації глобальної корисності через комбінацію локальних планів.

5.3.2 Переваги

Фактично, результат командного планування такий же самий, як і при ієрархічному плануванні – це спільний для всіх агентів план роботи. Але завдяки командному плануванню план отримується у повністю розподіленій манері, що веде до більшої надійності, швидкості, мінімальній кількості вузьких місць. І це все ще оптимально!

Крім того довгострокове планування дозволяє робити точну оцінку, коли кожне завдання буде виконано, і коли глобальну мету буде досягнуто. Так, у межах мультиагентних систем з передбачуваним часом виконання завдання, командне планування робить роботу ще більш передбачуваною.

5.3.3 Недоліки

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

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

Третій та останній недолік стає очевидним при порівнянні командного планування та ієрархічних підходів. Дійсно, спільний план - результат в обох випадках, але при першому підході це отримано в розподіленій манері. В основному, це перевага. Але, з іншого боку, це також приводить до збільшення навантаження на систему комунікації, зо можна розглядати як недолік.

5.4 Стохастичне розподілене планування

5.4.1 Опис

Стохастичне розподілене планування описано у [HoRa97]. При цьому підході, на відміну від командного планування, рішення, щодо вибору завдання транспортування деталей, виноситься в час прибуття цього завдання.

Стохастичне розподілене планування працює таким чином:

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

2. Якщо обраний робот за деякими власними причинами відмовляється від виконання завдання, то перший пункт повторюється.

Концептуальна різниця між командним плануванням і стохастичним розподіленим плануванням – це час, для якого планується діяльність. Під час командного планування план виробляється для певного, відносно тривалого періоду часу, тоді як при стохастичному розподіленому плануванні план робиться лише для найближчого часу.

Графічно стохастичне розподілене планування може бути описано так (Рисунок 5.6):

Рисунок 5.6: Стохастичне розподілене планування

Опис підходу для координації мультиагентних систем, який використовує стохастичне динамічне планування може бути знайдений у [LRP02].

5.4.2 Переваги

По перше, стохастичне розподілене планування може бути дуже корисним у системах, куди завдання прибувають динамічно й повинні бути виконані також динамічно.

По друге, відсутність довгострокового плану захищає систему від несподіваних затримок, а саме такі затримки не впливають суттєво на всю систему взагалі.

5.4.3 Незручності

Насамперед, стохастичне розподілене планування не бере до уваги діяльність агентів, яка буде здійснена навіть у найближчому майбутньому. Тому, не варто очікувати, що отриманий план буде оптимальним. Однак, у багатьох системах реального часу немає іншого шляху.

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

6 Розробка механізму координації

У цій главі буде виконана розробка механізму координації для гнучкого виробничого середовища. Спочатку будуть проаналізовані переваги та недоліки вибору різних підходів. Після цього буде розроблений механізм координації для виробничого середовища "Lego-роботи".

6.1 Аналіз Можливих Підходів

6.1.1 Короткий огляд Підходів

Як вже було написано раніше, існує 4 підходи до координації в мультиагентних системах автоматизації гнучкого виробничого середовища:

· Ієрархічний (централізований) підхід;

· Контрактний підхід ;

· Командне планування;

· Стохастичне розподілене планування.

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

Навпроти контрактний підхід децентралізований за своєю природою, що збільшує надійність і швидкість. Однак цей підхід вимагає занадто велику відповідальність від роботів, фактично при цьому підході ролі транспортері і деталі граються агентом робота. Це приносить високий ступінь нерівномірності до навантаження системи - роботи повинні робити занадто багато дій: управляти переміщенням, одержувати завдання, обмінюватися завданнями один з одним. Крім того це торкає і надійність: якщо агент робота із уже призначеним завданням виходить із ладу, то відразу завдання транспортування декількох деталей будуть загублені. Третій недолік - масштабованість системи, яка працює згідно з моделлю контрактного підхожу. З ростом кількості роботів навантаження на систему комунікації драматично збільшується. Таким чином, контрактний підхід неприпустимий до координації у гнучких виробничих середовищах, таких як модель “Роботи Lego”.

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

Різниця між цими двома підходами - часовий інтервал, для якого планується діяльність. Під час командного планування, діяльність планується для всіх відомих завдань транспортування, а при стохастичному розподіленому плануванні план робиться лише для тих завдань транспортування, які повинні бути виконані в безпосередньому майбутньому (Рисунок 6.1).

Рисунок 6.1: Командне планування й стохастичне розподілене планування

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

Навпроти при стохастичному розподіленому плануванні ніяка діяльності заздалегідь не планується, а ніякого плану майбутніх дій немає взагалі. Запити надходять під час роботи, і рішення, який транспорт буде відібраний, виноситься негайно. Ніякому транспортеру не дозволено скасувати завдання у випадку прибуття нового завдання, тому що завдання починається одразу після запиту.

6.2 Розробка механізму координації

У цьому підрозділі розроблюється механізм координації для гнучкого виробничого середовища на прикладі процесу "Lego-роботи".

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

Типово робота під деталями складається із циклів, які складаються із двох дій:

· Обробка деталі на станції

· Транспортування

Спочатку деталь транспортується від складу до станції. Далі деталь обробляється на станції. Тоді треба наступне транспортування і так далі

З погляду параметрів часу обробка деталей детермінована. Інакше кажучи, завжди відомо в момент початку обробки, як довго завдання буде виконуватися, і отже коли обробку буде закінчено та коли наступне транспортування може бути почато. Так, це дає можливість використовувати командне планування, що дає кращі результати.

З іншого боку транспортування - повністю недетермінована дія, оскільки механічні особливості роботів позбавляють можливості точно пророкувати час виконання, бо роботи мають знати час завершення попереднього завдання, щоб планувати наступне завдання.

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

Тому було вирішено розвити комбінацію двох підходів. Цю комбінація була названо стохастичним командним плануванням. При цьому підході виконується командне планування, але тільки для тих завдань, точні часові параметри яких відомі. Типово це будуть завдання, які обробляються на станції або чекають робота, який буде їх транспортувати. Всі інші завдання повинні чекати, поки їхні параметри часу не будуть визначені, тільки після цього починається планування.

Так, головна умова для того, щоб починати процес планування для завдання - точне знання, це - час початку транспортування. Коли ця інформація відома, тоді запит прибуває без очікування. Після того, якщо є вільні роботи, починається процес командного планування, інакше завдання чекає доти один з роботів не стане вільним.

Таким чином, цей новий підхід спадковє властивості двох попередніх підходів:

· Від командного планування: виконання завдання із точною інформацією про час початку виконується заздалегідь, що збільшує ефективність;

· Від стохастичного розподіленого планування: завдання закінчуються стохастично, отже запити й перепланування також відбуваються стохастично.

Таким чином, стохастичне командне планування успадковує переваги від командного планування й стохастичного розподіленого планування й використовує механізми координації залежно від параметрів завдання.

7 Висновки й перспективи

Висновки

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

Спочатку були надані та проаналізовані визначення й особливості виробничого середовища, для якого розроблюється механізм координації. Також модель процесу "Lego-роботи", яка буде використатися у якості прикладу гнучкого виробничого середовища, була стисло описана. Другим пунктом роботи було пояснення агентно-орієнтованої методології. Для цього були визначені поняття "агент" й “мультиагентна система”, та були переглянуті фундаментальні поняття агентно-орієнтованої методології.

Подальша важлива частина роботи була пов’язана з проблемою координації й співробітництва у мультиагентних систем. У цій частині був виконаний аналіз методів координації. Були проаналізовані відомі підходи до координації в гнучкому виробничому середовищі. Зокрема чотири підходи були перераховані: ієрархічний (централізований) підхід, контрактний підхід, командне планування та стохастичне розподілене планування.

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

Таким чином, були досліджені особливості гнучкого виробничого середовища, описані поняття агентно-орієнтованої методології, проаналізовані методи координації. Це послужило базою для розробки механізму координації для гнучкого виробничого середовища на прикладі процесу "Lego-роботи".

Перспективи

Є кілька пунктів, які мають потребу в перегляді з метою поліпшення.

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

Другий пункт – це реалізація запропонованої техніки координації для моделі виробничого середовища "Lego-роботи". Для цього повинні бути зроблені аналіз, проектування та реалізація системи.

Література

[BuMu92]	Bussmann, S.; Muller, J.: A Negotiation Framework for Co-operating Agents. In: Deen, S. M. (ed.), Proc. CKBS-SIG, Dake Centre, University of Keele. 1992, 1-17.
[EPR95]	Ephrati, E.; Pollack M.E., Rosenschein, J.S.: A Tractable Heuristic that Maximiyes Global Utility through Local Plan Combination. 1995.
[GHN+97]	Green, S.; Hurst, L.; Nangle, B; Cunningham, P.; Somers, F.; Evans, R.: Software Agents: A review. 1997.
[Göhn04]	Göhner, P.: Industrial Automation. In: Lecture Notes. Summer term 2004.
[Fern03]	Fernandez, P.F.G.: Development of an Agent Oriented Control Application to a Railway Model. Master Thesis. 2003.
[JSW96]	Jennings, N.R., Sycata, K., Woodridge, M.: A roadmap of agent research and development. In: Int. Journal of Autonomous Agents and Multi-agent Systems. 1996, No. 1 (1), pp7…38.
[Haye95]	Hayes-Roth, B.: An architecture for adaptative intelligent systems. In: Artificial Intelligence: Special Issue on Agents and Interactivity 72. 1995, pp329…365.
[HoRa97]	Holthaus, O.; Rajendran, C.: New Dispatching Rules for Scheduling in a Job Shop – An Experimental Study. In: International Journal of Advanced Manufacturing Technology. 1997, 13, No.2, pp. 148…153
[KrMa91]	Kreifelt, T.; von Martial, F.: A negotiation framework for autonomous agents. In: Y. Demazeau & J. P. Muller (eds), Decentralized A. I. 2, Elsevier Science. 1991.
[LRP02]	Lorenzo, C.; Raffaele, P.; Pierluigi, S.: Real Time Scheduling Using a Dispatching Rule Based Autonomous Agent System. 2002
[Maes95]	Maes, P.: Artificial Life Meets Entertainment: Life like Autonomous Agents. In: Communications of the ACM. 1995, No. 38, 11, pp. 108…114.
[Modi03]	Modi, P.J.: Distributed Constraint Optimization for Multiagent Systems. 2003
[MuBo96]	Musliner, D.J.; Boddy, M.S.: Contract-Based Distributed Scheduling for Distributed Processung. 1996.
[NLJ96]	Nwana, H.; Lee, L.; Jenings, N.: Coordination in Software Agents. In: BT Technology Journal. 1996, 14(4).
[RaGe95]	Rao, A.;Georgeff, M.: BDI Agents: From Theory to Practice. In: Proceedings of the First International - Conference on Multi-Agent Systems (ICMAS-95), San Francisco, USA. 1995.
[Resc04]	Resch, M.: Development of an Agent Oriented Controlled Production Process Model. Diplomarbeit. 2004.
[RoZl94]	Rosenschein, J.S.; Zlotkin, G.: Rules of Encounter: Designing Conventions for Automated Negotiation among Computers. In: MIT Press. 1994.
[RuNo03]	Russell, S.; Norvig, P.: Artificial Intelligence: A Modern Approach. Prentice Hall. 2003.
[SaFo89]	Sathi, A., Fox, M.S.: Constraint-directed negotiation of resource allocations. In: L. Gasser & M. Huhns (eds), Distributed Artificial Intelligence 2, Morgan Kaufmann. 1989.
[Tvei01]	Tveit, A.: A survey of Agent-Oriented Software Engineering. In: First NTNU CSGSC. 2001.
[Vlas03]	Vlassis N.: Multiagent Systems and Distributed AI. 2003.
[Weis99]	Weiss, G.: Multiagent Systems. In: MIT Press. 1999.
[Werk90]	Werkman, K.J.,: Knowledge-based model of negotiation using shareable perspectives. In: Proc. of the 10th Int. Workshop on DAI, Texas. 1990.
[WJK00]	Wooldridge, M.; Jennings, N.; Kinny, D.: The Gaia Methodology for Agent-Oriented Analysis and Design. In: Autonomous Agents and Multi-Agent Systems. 2000, no. 3, pp.285…312.
[WoJe94]	Wooldridge, M., Jennings, N.: Agent theories, architectures and languages: A survey. Intelligent Agents, Agent Theories, Architectures and Languages (ATAL 94), Vol. 890 Springer-Verlag Lecture Notes in Artificial Intelligence. 1994. pp1…32.
[WoJe99]	Wooldridge, M.; Jennings, N.: The Cooperative Problem-Solving Process. In: J. Logic Computat. 1999, Vol. 9, No.4, pp.563-592.
[WUG03]	Wagner, T.; Göhner, P.; Urbano, P.: Softwareagenten – Einführung und Überblick über eine alternative Art der Softwareentwicklung. In: atp - Automatisierungstechnische Praxis. 2003, pp. 3...31.