AGENTY A MULTIAGENTOVÉ SYSTÉMY Architektury multi-agentových systémů Obsah přednášky 1. Hierarchie 2. Holarchie 3. Koalice 4. Týmy 5. Kongregace 6. Society 7. Federace 8. Trhy 9. Matice 10. Složené organizace 2 Úvodní poznámka ■ Tato přednáška byla zpracována na základě článku: Horling, B., & Lesser, V. (2004). A survey of multi-agent organizational paradigms. The Knowledge Engineering Review, 19(04), 281-316. ■ Článek doporučuji přečíst v jeho plné podobě, měl by být k dispozici jako „open access“ ke stažení na internetu, a měl by být i v univerzitní knihovně (resp. databázích) 3 ARCHITEKTURY MAS Architektury MAS ■ Volba organizační struktury systému má významný dopad na efektivitu jeho fungování ■ Neexistuje jedna univerzální, „správná“ architektura ■ Struktura systému musí být uzpůsobena řešenému problému ■ Základní myšlenka – mít systém implementačně co nejjednodušší, ale současně takový, aby již stačil řešit určený problém 5 Kompletní agenty ■ Kompletní agent – disponuje senzory, aktuátory, vnitřní reprezentací, autonomií rozhodování… ■ Samostatné entity, vysoká míra autonomie ■ V praxi spíše vzácný případ ■ Architektury upravují jak koordinovat práci velkého množství agentů současně ■ Základní myšlenka – skupinová práce by měla být efektivnější než kdyby byl problém řešen jednotlivci 6 Architektura #1 - Hierarchie Klíčové znaky ■ Typicky stromová struktura ■ Standardně neexistují laterální vazby ■ Může vznikat latence z důvodu nutnosti vertikálního předávání informací ■ Uzly umístěné výše pracují s širším spektrem informací než uzly umístěné níže Schematické zobrazení 7 Hierarchie – hlavní charakteristiky ■ Velké množství problémů dovoluje využít hierarchické strukturování ■ Architektura je přehledná, intuitivně jasné je její fungování ■ Uzlům mohou být přiřazovány v rámci řešení role ■ Efektivita – úzce spjatá se schopností dekomponovat problém ■ Fungování systému v rámci hierarchie může mít tyto dopady: – Nižší množství interakcí mezi agenty (mají dané úlohy) – snížení komunikační zátěže a výpočetní náročnosti oproti řešení skrze individuální agenty – Možnost vytvářet omezení (constraints)pro chování agentů, definicí rolí se lépe prosazuje chování v rámci negociačních protokolů, atd. – Lze diverzifikovat informace poskytované agentům na základě jejich rolí a umístění v hierarchii 8 Hierarchie – využití ■ Kontraktační síť – úkol je rozložen na podúkoly, pro jejich řešení jsou uzavírány krátkodobé kontrakty s agenty nižších úrovní ■ Práce může být přidělována formou aukce – Řešitelské agenty vyhodnotí možnost participace a zda bude podána nabídka – Řešitelské agenty popíší své možnosti a kapacity k řešení (což dovoluje rozlišit jednotlivé nabídky) – „Hlavní“ agent rozdělí podle stanovených kriterií práci dále ■ Řešitelský agent může opět vyhodnotit zda úkol zvládne sám nebo zda bude potřeba dalších subdodavatelů (proces by se pak opakoval) 9 Princip fungování kontraktační sítě ■ Dvě skupiny agentů – Řešitelské agenty (RA) – zdrojově omezené, specializované na jednu oblast – Manažerský agent (MA) – zadává úkoly, kontroluje jejich plnění ■ Řešitelský agent – 4 části – Lokální báze dat a poznatků – poznatky o řešení specifických problémů, aktuální stav negociací – Řešitelský modul – Kontraktační modul – vedení negociací s MA – Komunikační modul – posílání/příjímání zpráv 10 Formální zápis kontraktační sítě 11 Kontraktační protokol 12 Grafické zobrazení protokolu 13 Architektura #2 – Holarchie Klíčové znaky ■ Organizace více systémů současně ■ Základní prvek – holon – Částečně autonomní – Skládá se z podřízených entit – Může patřit do nadřízeného holonu Schematické zobrazení 14 Struktura holonické organizace ■ Uvnitř holonu hierarchické uspořádání (indikováno šipkami) ■ Holony jsou ohraničené celky (hranice jsou indikovány kružnicí) ■ Příklady – nadnárodní koncern, národní pobočka, divize, pracovní skupina ■ Holony mohou reprezentovat rozdělení práce tak, jak probíhá v reálném světě ■ Schopnosti jsou přiřazeny jednotlivým holonům (namísto agentům) ■ Umožněny interakce se skupinou jako jednou funkční jednotkou ■ Prakticky speciální typ hierarchie 15 Autonomie v holarchii ■ Předpoklad – autonomie nedosahuje extrémů: – Úplná autonomie – výsledek by vedl k uspořádání typu neorganizovaná skupina – Žádná autonomie – pak se jedná o čistě hierarchické uspořádání 16 Holarchie - charakteristiky ■ Cíle mohou být dekomponovány pro zadání jednotlivým holonům ■ Výhody – Zapouzdření holonů – Částečná autonomie holonů (pomáhá určit jak nejlépe uspokojit dané požadavky – holon má flexibilitu při plnění úkolu) ■ Zadavatel úkolu - nemusí vědět jak holon úkol bude řešit – snížení informační zátěže ■ Holon – uspořádání dovoluje poměrně adaptabilní přístup při řešení úkolů ■ Nevýhoda – bez bližší znalosti o řešení se obtížně odhaduje výkonnost systému 17 Holarchie – formování struktury ■ Nutno rozhodnout jaké individuální agenty budou do holonu patřit – Holon musí být užitečný při plnění úkolů v kontextu celé organizace – Členské agenty holonu musí být při plnění úkolů efektivní ■ Úkol je zpravidla reprezentován dynamickým facilitačním agentem – mediátorem (dynamic mediator holon) – Dočasný, orientovaný na konkrétní problém – Vydává instrukce, kombinuje informační objekty, koordinuje práci se zdroji – Je zrušen po dokončení úkolu ■ Existují i jiné způsoby formace holarchie… 18 Architektura #3 - Koalice Klíčové znaky ■ Orientované na cíl ■ Obvykle dočasné ■ Plochá struktura (může mít „vedoucího“ agenta pro komunikaci za skupinu) ■ Koalici lze brát (po zformování) jako jednu entitu ■ Mohou se překrývat Schematické zobrazení 19 Koalice - charakteristiky ■ Agenty v koalici by měly koordinovat své aktivity tak, aby sloužily cíli koalice ■ Krom problému vytvoření samotné koalice je nutno vyřešit: – Jak má být úkol svěřený koalici vlastně řešen – Jak rozdělit plnění případných dílčích cílů – Pokud je součástí řešení také odměna (např. virtuální) – jak bude dělena mezi členy koalice ■ Očekávání spojené s koalicí – přidaná hodnota z práce ve skupině (např. schopnost řešit problémy přesahující možnosti jednotlivých agentů) ■ Příliš velká koalice – organizační potíže s jejím udržováním mohou přesáhnout kritickou mez – nutno najít optimální velikost koalice 20 Koalice - formování ■ Obtížnější v dynamických prostředích ■ Koalice se mohou překrývat – problém s konfliktními zájmy ■ Princip – najít společné cíle a postupovat při jejich naplňování jako skupina ■ Naplnění cíle – koalice může zaniknout a zformovat se jiná 21 Architektura #4 - Týmy Klíčové znaky ■ Skupina kooperujících agentů pracujících společně na dosažení cíle ■ Užitek skupiny je prioritní ■ Individuální akce mají být koordinovány tak, aby byly v souladu s cílem týmu ■ Poměrně arbitrární uspořádání ■ Agenty v rámci řešení problému přijímají role (1 i více), mohou se v průběhu řešení měnit Schematické zobrazení 22 Týmy - charakteristka ■ Srovnání s koalicemi – agenty maximalizují užitek týmu (dosažení cíle), ne individuální prospěch ■ Týmy obvykle disponují reprezentací sdílených cílů, vzájemnou důvěrou a tvoří plány na týmové úrovni ■ Přínos – ve skupině mohou agenty řešit komplexnější problémy ■ Inter-agentové interakce jsou založeny na rolích, které se mohou měnit – flexibilní uspořádání, které dovoluje adaptovat se lépe na změny 23 Týmy - formování ■ Tři principiální problémy: – Jak budou agenty rozvrženy (a přiděleny role) aby mohly řešit problémy na týmové úrovni – Jak udržet konzistenci vztahů mezi agenty v průběhu řešení problému – Jakým způsobem revidovat strukturu týmu při změnách prostředí nebo populace agentů ■ Kontraktační síť ■ Matchmaker 24 Matchmaker ■ Efektivní hledání agentů s požadovanými schopnostmi nebo poskytující specifikované služby ■ Matchmaker vytváří komunikační spojení mezi informaci/službu hledajícími agenty a informaci/službu poskytujícími agenty ■ Matchmaker má bázi údajů s adresami, schopnostmi aj. údaji o agentech 25 Komunikace přes matchmakera 26 Poznámky ■ Proces připomíná inzerci firem ■ Matchmaker poskytuje údaje za (virtuální) poplatek nebo na požádání agentů ■ Transakce probíhají za (virtuální) poplatek 27 Architektura #5 - kongregace Klíčové znaky ■ Dlouhotrvající, plochá struktura ■ Obvykle se netvoří pro plnění jednoho konkrétního úkolu, nejsou dočasné ■ Agenty mají podobné nebo komplementární charakteristiky, mohou facilitovat proces hledání vhodného spolupracovníka ■ Jednotlivé kongregace mají heterogenní účely Schematické zobrazení 28 Kongregace - charakteristiky ■ Agenty jsou individuálně racionální ve smyslu maximalizace dlouhodobého užitku – členství přináší větší užitek než samostatnost ■ Členství ve (správné) kongregaci určuje užitnou hodnotu ■ Příslušnost ke kongregaci se může měnit ■ Struktura musí být do určité míry stabilní, aby měla smysl ■ Pomáhají redukovat limity interakcí a složitost vyhledávání jiných agentů ■ Mezi kongregacemi neprobíhá komunikace, ale mohou se teoreticky překrývat 29 Kongregace - formování ■ Kongregace trpí podobnými negativy jako koalice – příliš velké množství agentů může být kontraproduktivní (kvůli vysokým nákladům na udržování organizované struktury) ■ Možnost utváření kongregací pomocí tzv. štítků (label) – deskriptivní tag sloužící dvěma účelům: – Odlišuje danou kongregaci od ostatních – Slouží jako reklama pro ostatní agenty – popisuje charakteristiky členů 30 Architektura #6 – society (společnosti) Klíčové znaky ■ Otevřené systémy ■ Agenty mohou volně přicházet/odcházet, societa slouží jako prostředí, v němž se mohou setkávat ■ Definují strukturu a řád, ale konkrétní interakce jsou poměrně flexibilní ■ Society definují určitá pravidla, normy, konvence nebo omezení – poskytuje to konzistentnost chování pro všechny členy a společný komunikační rámec Schematické zobrazení 31 Society - charakteristiky ■ Příklady – elektronické tržiště, pravidla silničního provozu, atd. ■ Potíž při definici pravidel – musí být spravedlivá, užitek skupiny uživatelů musí být ohodnocen spravedlivě (nesmí existovat diskriminace) z hlediska užitečnosti pro jednotlivé účastníky ■ Většina MAS obsahuje nějakou formu pravidel v každém případě, i když se nejedná o případ society ■ Díky jednotnému systému pravidel je chování agentů vzájemně předvídatelnější – snazší komunikace a výměna informací 32 Society - formování ■ Problémy – Definice pravidel a omezení – Struktura (pravidla, atd.) musí být formálně popsána – případní účastníci tak mohou ověřit, zda jsou s pravidly kompatibilní – Jaké konvence aplikovat ■ Fungování society může být poměrně sofistikované – agenty musí vědět jak a kdy používat dílčí služby v rámci society 33 Architektura #7 - federace Klíčové znaky ■ Také ozn. federované systémy ■ Skupiny agentů, které předají část své autonomie zástupci, který je jako skupinu reprezentuje ■ Analogie s fungováním politického uspořádání zemí (autonomie obcí a krajů a centrální vláda) ■ Členové skupiny komunikují pouze se svým zástupcem, mezi skupinami komunikace probíhá přes zástupce Schematické zobrazení 34 Federace - charakteristiky ■ Informace od členů skupiny – Popis dovedností a schopností – Zadání úkolů – Informace o statutu – Aj. ■ Mezi skupinami – Zadání úkolů – Oznámení volných kapacit k řešení ■ Výhoda – členové skupin nemusí disponovat sdíleným jazykem společným pro všechny agenty v systému 35 Federace - formování ■ Nastavení společného komunikačního jazyka pro facilitační agenty ■ Možnost využít ACL nebo jiné formáty ■ Příklad - broker 36 Broker ■ Úlohou brokera je nejen nalézt adresu agenta, ale také poskytnout službu žádajícím agentům ■ Žádající agent akceptuje transakční náklady ■ Broker se zavazuje vyřešit delegovaný úkol ■ Broker hledá co nejlepší shodu mezi specifikací úkolu a schopnostmi zaregistrovaných agentů 37 Schéma komunikace s brokerem 38 Poznámky k nepřímé komunikaci ■ Adresy matchmakerů a brokerů musí být veřejně známé ■ Obvykle jsou přímo uloženy v prostředích ve formě veřejně přístupné databáze 39 Architektura #8 – Trhy Klíčové znaky ■ Kupující (bílá) – poptávají – Zdroje – Úkoly – Služby – Zboží ■ Prodejci (černá) zpracovávají poptávky, určují vítěze ■ Analogie - aukce Schematické zobrazení 40 Trhy - charakteristiky ■ Výhodné pro alokační úlohy a cenotvorbu ■ Obvykle se určuje oblast zájmu (pro prodávající i kupujícící) a společný negociační formát ■ Dvoustranná aukce – obě strany činí kompromis ■ Jednostranná aukce – jedna ze stran udržuje fixní cenu ■ Negativa – Potenciální složitost při odhadu vývoje aukce (a finální ceny) – nutno zabránit ovlivňování průběhu aukce (counterspeculation) – Bezpečnost – zajištění validity aukce (dohoda účastníků a umělé snížení/zvýšení ceny) 41 Trhy - formování ■ Obvykle předdefinované struktury – není nutno vytvářet při běhu systému, ale lze je formovat i dynamicky (méně časté) ■ Lze kombinovat s jinými organizačními paradigmaty – např. kongregacemi 42 Architektura #9 – maticové organizace Klíčové znaky ■ Redukce strukturovaného vedení 1-1 (1agent (bílá) má 1 manažera (černá)) ■ Více (nejen manažerských) agentů může ovlivňovat individuální agenty současně ■ Analogie s lidskými organizacemi – člověk je ovlivňován více vlivy najednou Schematické zobrazení 43 Maticové organizace - charakteristiky ■ Sdílení zajišťuje vyšší využití schopností individuálních agentů ■ Nutno hledat kompromisy při řešení – plnění více požadavků najednou ■ Efektivní činnost předpokládá schopnost vyhodnocovat (řadit) závazky a určitou autonomii při řešení konfliktů na lokální úrovni (problém lze eskalovat) 44 Architektura #10 – složené organizace Klíčové znaky ■ Některé organizační struktury vyžadují použití několika organizačních systémů současně ■ Příklad na obrázku – hierarchická struktura kombinovaná s množinou koalic Schematické zobrazení 45 Složené organizace - charakteristiky ■ Pozitiva a negativa jsou odvozeny z použitých komponent – záleží na tom, jaká paradigmata jsou kombinována ■ Složené organizace mohou generovat nečekané problémy – např. pozor na překrývání činností u facilitačních agentů 46 SHRNUTÍ 47 Paradigma Charakteristika Přínosy Negativa Hierarchie Dekompozice Hodí se na velké množství úloh, dobré škálování Mohou se vytvářet úzká hrdla Holarchie Dekompozice s autonomií Využívá autonomii funkčních jednotek Nutno organizovat holony, nepredikovatelná výkonnost Koalice Dynamické, orientované na cíl Využívá početní síly Krátkodobé přínosy nemusí převážit náklady na formování koalice Týmy Soudržnost na skupinové úrovni Řeší málo granulované problémy, ukolověcentrický přístup Zvýšená komunikační zátěž Kongregace Dlouhodobé, orientované na užitek Facilitace hledání agentů Skupiny mohou být příliš restriktivní Society Otevřené systémy Veřejné služby, dobře definované konvence Potenciálně příliš složité, agenty mohou potřebovat speciální dovednosti pro začlenění Federace Zprostředkovatelské agenty Matchmaking, brokering, facilitace dynamické skupiny agentů Zprostředkovatelé mohou být úzkým hrdlem Trhy Konkurence skrze cenotvorbu Efektivní alokace, vyšší užitek při centralizovanosti, aukce Možné zneužívání aukčních mechanismů, potenciálně vysoká rozhodovací složitost Matice Více manažerů Sdílení zdrojů, více vlivů na chování agenta Možné konflikty, nutnost využívat sofistikovanějších agentů Složené org. Více organizačních schémat současně Přínosy z kombinace více organizačních struktur Vyšší složitost, možné nevýhody kombinování více organizačních struktur DĚKUJI ZA POZORNOST Použité zdroje [1] Horling, B., & Lesser, V. (2004). A survey of multi-agent organizational paradigms. The Knowledge Engineering Review, 19(04), 281-316. [2] Kubík, A.: Inteligentní agenty – tvorba aplikačního software na bázi multiagentových systémů 50