Smluvní síťový protokol - Contract Net Protocol

The Smluvní síťový protokol (CNP) is a task-sharing protocol in multiagentní systémy, představený v roce 1980 Reidem G. Smithem.[1] Používá se k alokaci úkolů mezi autonomními agenty. Je to blízko zapečetěné aukční protokoly. Spoléhá se hlavně na Subdodavatel: manažer navrhuje úkol několika agentům. Posledně jmenovaní navrhnou, mezi něž se vedoucí rozhodne přidělit úkol. Tento úkol lze poté rozdělit a zadat subdodavateli.

Formální popis

Formalizace protokolu může být provedena prostřednictvím řečový akt teorie. V tomto protokolu může být každý agent buď manažer nebo dodavatel

  1. Protokol inicializuje správce, který odešle a výzva k předkládání návrhů dodavatelům
  2. Dodavatelé mohou zaslat buď a návrh pokud mají zájem nebo a odmítnout pokud nejsou. Tento návrh obsahuje všechny prvky požadované správcem při jeho výběru.
  3. Vedoucí vybere z návrhů ten, který mu nejlépe vyhovuje, a zašle příslušnému dodavateli akceptovat. To poslat odmítnout ostatním dodavatelům, aby je informovali o svém rozhodnutí.
  4. Jakmile je smlouva dokončena, dodavatel informuje manažera pomocí informovat zpráva. Pokud existuje výsledek ke komunikaci, je také komunikován prostřednictvím informovat zpráva. Pokud dodavatel nemůže splnit svou zakázku, informuje o tom manažera prostřednictvím a zrušení zpráva.

Síťový protokol smlouvy lze reprezentovat pomocí AUML formalismus:

Diagram AUML protokolu síťového protokolu

Tento protokol lze použít k implementaci hierarchických organizací, kde správce přiřazuje úkoly dodavatelům, kteří se zase rozkládají na úkoly na nižší úrovni a přiřazují je na nižší úroveň. Tento druh organizace lze použít, když agenti spolupracují, tj. když jsou jejich cíle totožné. V této situaci je možné zajistit, aby dodavatelé nelhali manažerovi, když předloží svůj návrh. Když jsou agenti konkurenceschopní, protokol skončí v organizaci tržiště, velmi podobné aukcím.[2]

Implementace

Protokol byl implementován FIPA v ACL (Agent Communication Language).[3]

Protokol Contract Net Protocol byl implementován pro různé problémy a kontexty. Původní článek popisuje případ použití senzorové sítě. Následné práce v této souvislosti ukázaly svou užitečnost.[4] Používá se také pro přidělování úkolů více robotů.[5] Používá se také jako vyjednávací protokol jak pro tržiště elektronického obchodování [6] a pro dodavatelské řetězce.[7]

Problémy a rozšíření

Reid G Smith identifikoval několik problémů souvisejících s jeho protokolem. Zejména navrhuje vytvářet pouze krátké zprávy a komunikovat pouze s agenty, kteří by mohli být relevantní pro navrhovaný úkol, aby se zabránilo přetížení síťové komunikace, pokud jde o vyměňované zprávy. Za účelem omezení počtu interakcí, v případě, že manažer ví, s jakým dodavatelem by chtěl uzavřít smlouvu, může jej kontaktovat přímo a předložit nabídku, kterou může nebo nemůže přijmout.

Druhá otázka souvisí s mírou obsazenosti dodavatele, když existuje mnoho úkolů. V tomto případě může být pro manažera skutečně komplikované najít dostupné dodavatele. Za účelem vyřešení tohoto problému může dodavatel odpovědět na výzvu k podávání návrhů, i když již pracuje na jiné zakázce. Tento trik lze použít k prevenci situace, kdy manažer volá výzvy k podávání návrhů, aniž by dostal jakoukoli odpověď, protože dodavatelé jsou zaneprázdněni. V tomto případě dodavatelé přidají ke svému návrhu okamžik, kdy budou připraveni uzavřít návrh od manažera. Podobně v této situaci je možné vést seznam všech dostupných dodavatelů, aby je manažer mohl nejprve kontaktovat. Tento trik umožňuje vyhnout se přetížení sítě kvůli tomu, že manažeři zasílají výzvy k předkládání návrhů všem agentům znovu a znovu a zároveň zajišťují, že nakonec najdou dodavatele, který by na navrhovaný úkol uzavřel smlouvu. Tyto informace dodavatelé přímo zasílají správcům.

Kromě rozšíření navržených autorem rozšířila několik prací Smlouvu o síťovém protokolu. Jedním z problémů, které vyvolává, je skutečnost, že manažer nemůže přesně určit, co si nejvíce váží. Musí si vybrat z návrhů, které obdrží od dodavatelů. V případě, že každý dodavatel může předložit řadu návrhů, může to vést k neoptimálním řešením. K řešení tohoto problému FIPA rovněž navrhuje iterovanou verzi protokolu, ve kterém může manažer uskutečnit novou výzvu k předkládání návrhů u některých dodavatelů, kteří na ni odpověděli, a odmítnout ostatní, případně jednoho z nich přijmout. Výsledný protokol lze porovnat s iterovanými aukčními protokoly. Jako CNP lze tento protokol představovat jako AUML diagram [8]

Diagram AUML s iterovanou smlouvou Čistý protokol

Dalším problémem protokolu je ve skutečnosti řešení úkolu. V původním protokolu se dodavatel, který předloží návrh, zaváže k provedení úkolu, na který předložil návrh, ať už bude trvat cokoli. Selhání úkolu je bráno v úvahu pouze prostřednictvím zrušení zpráva informující manažera, že úkol nebude vyřešen, bez jakékoli sankce pro dodavatele. V případě, že jsou agenti sobečtí, mohou mít motivaci podat co nejvíce návrhů a splnit pouze ty nejziskovější. V kontextu spolupráce agent nemá žádný způsob, jak zjistit, zda je odhlášení z úkolu za účelem spáchání jiného úkolu dobré pro celý systém. V roce 1995 zveřejnili rozšíření protokolu Tuomas Sandholm a Victor Lesser aby bylo možné tyto prvky zohlednit a předem definovat náklady na závazky, které má dodavatel zaplatit, pokud nemohou splnit úkol.[9]

Reference

  1. ^ Smith (prosinec 1980). „Protocol Net Protocol: Komunikace a kontrola na vysoké úrovni v distribuovaném řešení problémů“. Transakce IEEE na počítačích. C-29 (12): 1104–1113. doi:10.1109 / TC.1980.1675516. ISSN  0018-9340.
  2. ^ Horling, Bryan; Lesser, Victor (11.11.2005). "Průzkum organizačních paradigmat více agentů". Recenze znalostního inženýrství. 19 (4): 281. doi:10.1017 / S0269888905000317. ISSN  0269-8889.
  3. ^ „Specifikace protokolu FIPA Net Net Interaction Protocol“. fipa.org. Citováno 2019-04-09.
  4. ^ Chen, L .; Xue-song, Q .; Yang, Y .; Gao, Z .; Qu, Z. (červenec 2012). Msgstr "Algoritmus přidělování úkolů na základě smlouvy pro bezdrátovou síť senzorů". 2012 IEEE Symposium on Computers and Communications (ISCC). str. 000600–000604. doi:10.1109 / ISCC.2012.6249362. ISBN  978-1-4673-2713-8.
  5. ^ Grabovskis, Arvids; Lavendelis, Egons; Liekna, Aleksis (08.11.2012). „Experimentální analýza síťového protokolu kontraktu při přidělování úkolů více robotům“. Aplikované počítačové systémy. 13 (1): 6–14. doi:10.2478 / v10312-012-0001-7.
  6. ^ Sandholm, Tuomas (1993). „Implementace protokolu čisté smlouvy na základě výpočtu mezních nákladů“ (PDF). Sborník AAAI-93. str. 256–262.
  7. ^ (Roger) Jiao, Jianxin; Ty, Xiao; Kumar, Arun (červenec 2006). „Rámec založený na agentech pro kolaborativní vyjednávání v globální síti dodavatelského řetězce ve výrobě“. Robotika a výroba integrovaná do počítače. 22 (3): 239–255. doi:10.1016 / j.rcim.2005.04.003.
  8. ^ „FIPA Iterated Contract Net Interaction Protocol Specification“. fipa.org. Citováno 2019-04-09.
  9. ^ Sandholm, Tuomas; Lesser, Victor (1995). „Problémy v automatizovaném vyjednávání a elektronickém obchodování: Rozšíření rámce čisté smlouvy“ (PDF). Sborník z první mezinárodní konference o multiagentních systémech. 328–335.

Viz také