Kontraktační síť

Kontraktační síť je multiagentní systém pro distribuované řešení problémů. Každý agent v síti může vystupovat v jedné ze dvou rolí – jako manažer úkolu či jako jeho řešitel. Vyjednávání mezi agenty se řídí zákonem nabídky a poptávky.

Distribuované řešení problémů

Pro umožnění řešení daného problému multiagentním systémem je nutné, aby tento systém byl schopen následujících činností:

1. Dekompozice problému na menší samostatné části – podproblémy
2. Vhodné rozdělení podproblémů mezi řešitelské agenty
3. Vyřešení jednotlivých podproblémů
4. Syntéza řešení původního problému

Přitom žádný agent nemá k dispozici kompletní data ani kontrolu nad celým procesem řešení problému. Úkolem kontraktační sítě je vyřešení druhého bodu, tedy rozdělení dílčích podproblémů mezi jednotlivé agenty.

Princip kontraktační sítě

Každému agentu v síti může být přidělen libovolný problém k řešení. Na základě analýzy přiděleného problému se agent může rozhodnout problém sám vyřešit nebo jeho řešení předat jinému agentu. K předání problému dál dochází typicky ve dvou situacích:

• Když agent vyhodnotí, že jemu zadaný problém je z hlediska kvality či ceny řešení výhodnější rozložit na podproblémy a ty pak zadat ostatním agentům.
• Když agent nemá k řešení problému dostatečné informace.

Dojde-li k jedné z těchto situací, agent se stane manažerem úkolu a rozešle všem nečinným agentům zprávu o zadání nového úkolu. Každý z nich vyhodnotí, zda oznámený úkol odpovídá jeho schopnostem, a případně odešle manažerovi nabídku na vyřešení problému, může se však i rozhodnout na nabídku nereagovat. Zadavatel z vrácených nabídek poté vybere tu nejvýhodnější a danému agentu přidělí úkol, čímž z něj udělá řešitele úkolu. Komunikaci mezi agenty má na starosti Contract net protocol – jazyk a soubor pravidel vyvinutý speciálně pro řešení rozdělování a sledování úkolů a vyjednávání.

Contract Net Protocol

Tento prostředek vzájemné komunikace mezi agenty v kontraktační síti byl představen Reidem G. Smithem roku 1980. Na něm staví v dnešní době používaná verze navržená roku FIPA pocházející z roku 2002 . Jedná se o vysokoúrovňový protokol, který se zabývá sémantickou stránkou zpráv předávaných mezi agenty. Nestará se o samotné doručování zpráv, což je úlohou nízkoúrovňových protokolů. Protokol předem nespecifikuje, které agenty budou plnit manažerskou a které řešitelskou roli. Přiřazení rolí vyplývá z činnosti agentů. Jednotlivé agenty mohou v jeden okamžik vystupovat v jedné nebo obou z těchto rolí ve vazbě ke konkrétním úkolům. Například pokud jeden agent dostane přidělen určitý úkol, který se rozhodne dále rozdělit mezi jiné agenty, vystupuje zároveň v roli řešitele i manažera.

Vyhledávání a vyjednávání

Schéma procesu vyjednávání v kontraktační síti

Každý manažerský agent má k dispozici seznam nečinných agentů. Všechny potenciální řešitele informuje zprávou o novém úkolu. Každý neaktivní agent má oproti tomu přístup k seznamu aktuálně nepřidělených úkolů. Proces vyjednávání má pak následující průběh:

1. Nevyužitý agent prohlédne seznam nepřidělených úkolů a vybere, které z nich jsou pro něj vhodné. Ostatní úkoly odmítne.
2. Na každý z úkolů, které vyhodnotil jako vhodné pro přijetí k řešení, odešle odpovídajícímu manažerskému agentu zprávu obsahující nabídku ceny řešení úkolu.
3. Každý manažerský agent vybere z obdržených nabídek tu, kterou vyhodnotí jako nejvýhodnější, a zadá úkol k řešení vítěznému nevyužitému agentu. Ostatní nabídky odmítne.
4. Řešitelský agent získává zodpovědnost za vykonání zadaného úkolu. Na základě analýzy úkolu jej buď vyřeší sám nebo dále rozdělí na podúkoly vhodné pro zadání dalším agentům. Tím se z něj stává další manažerský agent a celý proces se opakuje.

Díky těmto pravidlům a posloupnosti vyjednávání může vzniknout hierarchická struktura zadaných úkolů a odpovědností za jejich vyřešení.

Příklad - Distributed Sensing System

Pro lepší pochopení celého procesu uveďme názornou ukázku fungování kontraktační sítě DSS, jejímž úkolem je tvorba mapy hustoty provozu v určité lokalitě. V této síti vystupují agenti s různými schopnostmi. První skupinou agentů jsou senzory. Ty dokáží shromažďovat data ze svého okolí, ale nemají dostatečný výpočetní výkon pro jejich další zpracování. Druhou skupinou jsou agenty, které nejsou vybaveny prostředky pro snímání dat z reálného světa, ale oplývají vysokým výpočetním výkonem. Z toho vyplývá, že všichni druzí jmenovaní se přirozeně stávají zadavateli úkolů pro senzory.

Vyhlášení úkolu signal

Vyhlášení úkolu probíhá formou zprávy zvané Task Announcement message. Její struktura je následující:

TO: * (zpráva je zaslána všem volným agentům)
FROM: 25 (identifikace odesílatele)
TYPE: Task Announcement (typ zprávy je oznámení o novém úkolu)
CONTRACT: 22-3-1 (kódové označení kontraktu)

TASK ABSTRACTION (stručný popis úkolu)

TASK TYPE SIGNAL (název typu úkolu)

POSITION LAT 47N LONG 17E (specifikuje lokalitu, o jejíž data má manažerský agent zájem)

ELIGIBILITY SPECIFICATION (podmínky, které musí řešitelské agenty splňovat)

MUST-HAVE SENSOR (jsou vyžadovány agenty vybavené senzory vnějšího prostředí)

MUST-HAVE POSITION AREA A (přihlásit o úkol se mohou pouze agenty nacházející se v určité lokalitě)

BID SPECIFICATION (informace, které musí být součástí vrácené nabídky)

POSITION LAT LONG (pozice agentu)

EVERY SENSOR NAME TYPE (názvy a typy senzorů, kterými agent oplývá)

EXPIRATION TIME (dokdy je možné zasílat nabídky)

28 1730Z FEB 1979

Zpracování oznámení o úkolu signal potenciálními řešiteli

Každý agent, který přijal oznámení o novém úkolu, mu na základě obdržené specifikace přiřadí hodnocení vyjadřující vhodnost tohoto úkolu pro plnění. Nejdříve si ověří, zda splňuje zadané podmínky. Pokud ne, rovnou tento úkol odmítne. Pokud podmínky splňuje, zařadí jej na seznam seznam vhodných úkolů a určí jeho pořadí na základě daných kriterií. V tomto konkrétním případě je takovým kriteriem vzdálenost od zadavatele. Čím menší vzdálenost, tím vhodnější se úkol bude jevit v konkurenci ostatních obdržených specifikací, jelikož menší vzdálenost znamená nižší pravděpodobnost výskytu komunikačních problémů.

Zpracování a odeslání nabídky

Na nejvhodnější specifikaci agent odpoví konkrétní nabídkou. Tato nabídka může vypadat například následovně:

TO: 25
FROM: 42
TYPE: BID
CONTRACT: 22-3-1

NODE ABSTRACTION

POSITION LAT 62N LONG 9W

SENSOR NAME S1 TYPE S

SENSOR NAME S2 TYPE S

SENSOR NAME T1 TYPE T

Povšimněme si položky NODE ABSTRACTION. Ta obsahuje data o agentu vyžadovaná specifikací. Může ale obsahovat i žádost o další specifikace v případě, oznámení o úkolu není pro řešitele dostatečně specifické.

Vyhodnocení nabídek

Jak zadavatel postupně dostává nabídky na vyhlášený úkol, řadí je dle stanovených kritérií od nejatraktivnějších po ty nejméně zajímavé. V této fázi má zadavatel dvě možnosti. Může čekat až do ukončení doby specifikované pro řešitele k zasílání nabídek, a pak vybrat tu nejvhodnější. Druhou možností je definovat parametry, při jejichž splnění je nabídka označena jako uspokojivá a okamžitě přijata. Druhá možnost urychlí proces vyjednávání, ale může způsobit, že nedojde k výběru optimální nabídky.

Agentu, jehož nabídka byla vybrána jako vítězná, je následovně odeslána zpráva o přidělení úkolu. Její podoba je následující:

TO: 42
FROM: 24
TYPE: AWARD
CONTRACT: 22-3-1

TASK SPECIFICATION

SENSOR NAME S1

SENSOR NAME S2

Plnění úkolu, hlášení výsledků a ukončení kontraktu

Po přidělení úkolu je mezi zadavatelem a řešitelem ustaven komunikační kanál sloužící k předávání zpráv týkajících se aktuálního stavu plnění úkolu. Existuje několik typů zpráv, jejichž pomocí spolu agenty komunikují.

Prvním z nich je informační zpráva, která slouží pro obecnou komunikaci ohledně řešené úlohy. Informační zprávy jsou nepovinné a jejich použití záleží na konkrétní implementaci modelu kontraktační sítě.

Druhým typem zprávy je hlášení týkající se pokroku ve vykonání úkolu. Hlášení mohou být dvou typů:

• Průběžné hlášení informuje zadavatele o stádiu dokončení úkolu v průběhu jeho plnění. Umožňuje řídit posloupnost plnění úkolu nebo jej pozastavit, pokud zadavatel čeká na výsledky plnění jiného řešitele, které jsou nutné pro pokračování v dané úloze.
• Závěrečné hlášení obsahuje informace o výsledcích plnění úkolu v momentě jeho dokončení.

Řešení konfliktů, nestandardních situací a efektivity

Vítězství ve více vyhlášených úkolech najednou

Za určitých okolnosti může dojít k tomu, že řešitel obdrží několik úkolů najednou, protože zvítězil ve více než jedné zadané poptávce. Tato situace může nastat ve chvíli, kdy potenciální řešitel vyhodnotí několik zadání jako stejně vhodná, na všechna odpoví a zároveň více než jedna z jím podaných nabídek zvítězí. V takovém případě řeší zadané úkoly v pořadí, ve kterém dorazily. Jiným řešením je předejití této situaci tak, že agent po přidělení prvního úkolu zasílá ostatním zadavatelům na jimi přidělované úkoly zamítavou reakci. Některých případech může být výhodnější první způsob řešení situace, v jiných druhý. To záleží na poměru časové náročnosti komunikace mezi agenty na jedné straně a náročnosti spočítání zadaných úkolů na straně druhé. V případě rozsáhlé sítě agentů může vyšší počet zpráv spojených s mechanismem odmítání úkolů způsobit zahlcení komunikační infrastruktury a ve výsledku vést ke zpomalení systému. Parametry komunikace je nutné zvážit při návrhu systému.

Zadavatel nedostane odpověď

K takové situaci může dojit v případě, kdy v systému nejsou žádné volné agenty, které by mohly podávat nabídky na řešení úkolů, vyhodnotí vyhlášený úkol jako nezajímavý nebo když neexistuje žádný potenciální řešitel, který by vyhovoval kriteriím stanoveným v zadání úkolu.

V prvních dvou případech lze situaci řešit opakováním vyhlášením úkolu, dokud se nenajde volný agent, který se k řešení přihlásí. Ve třetím případě by však opakované zveřejnění úkolu k ničemu nevedlo. Proto existuje mechanismus zvaný Immediate response, který zabezpečuje, že zadavatel dostane odpověď i v případě, že není nikdo, kdo by úkol řešil. Díky tomuto mechanismu se zadavatel dozví důvod, proč se nepodařilo nalézt vhodného řešitele. Podobně jako v předchozím případě znamená tato dodatečná komunikace zvýšení režie a potenciální zpomalení systému při velkém počtu agentů.

Přímé kontrakty

V případě, kdy zadavatel například z minulého plnění stejného typu úkolu ví, který řešitel je pro něj nejvhodnější, může díky této funkci oslovit pouze jeho nebo mu úkol přidělit rovnou bez vyjednávání o podmínkách. To přináší výhodu v podobě nižšího zatížení komunikačního kanálu a zrychlení procesu díky absenci termínu ukončení posílání nabídek.

Zpráva o dostupnosti agentu

V případě, kdy jsou všechny agenty zaneprázdněny řešením přidělených úkolů, pozbývá zveřejňování nových úkolů smyslu, protože představuje pouze další zbytečnou zátěž komunikační infrastruktury. Proto existuje typ zprávy zvaný node available. Tuto zprávu zašle řešitelský agent v momentě, kdy nemá zadán žádný úkol a je nevyužitý. Tato zpráva obsahuje detaily o jeho schopnostech a může být rozeslána všem zadavatelským agentům. Zadavatelské agenty porovnají možnosti volného řešitele s požadavky v seznamu nezadaných úkolů a v případě, že se tyto se schopnostmi řešitelského agentu potkávají, mohou jej zadavatelé přímo oslovit.