Multi-agent systems/cs

Průzkumný agent NASA zvaný Super Ball Bot.

Multiagentní systémy jsou tvořeny mnoha navzájem interagujícímí samostatnými výpočetními jednotkami, jenž nazýváme agenty. Tito agenti jsou autonomní jednotky s rozdílnými informacemi, které jsou schopné kooperace, soutěživosti, komunikace mezi sebou a s prostředím, učení se a flexibilního chování. Agenti mohou mít rozdílné zájmy a cíle, popřípadě společně řeší problémy, které by žádný z nich sám nevyřešil. Díky tomu multiagentní systémy umožňují široké využití distribuované výpočetní technologie a paralelního zpracování dat.

Příklady reálné aplikace multiagentních systémů můžeme nalézt od architektury internetu, výrobního průmyslu, lékařství, až po vesmírný program. NASA například multiagentní systémy využívá pro konstelaci satelitů či pro zkoumání povrchu cizích planet.

Charakteristika multiagentního systému

Multiagentní systém je propojená síť entit řešící nějaký problém (agentů), kteří spolupracují za účelem nalezení odpovědí na problémy, které svou náročností přesahují limity každého z agentů jakožto jednotlivce. Fakt že spolu agenti spolupracují naznačuje, že mezi agenty se musí vyskytovat nějaká forma kooperace. Multiagentní systémy jsou také někdy chápány jako nejslabší forma umělé inteligence . To je nejspíš zapříčiněno tím, že narozdíl od klasických výpočetních algoritmů, jenž vedou k predikovatelným výsledkům, vznikají v multiagentnich systémech spontánní jevy připomínající živé ekosystémy a projevují určitou inteligenci. Pro systémy tohoto typu jsou charakteristické následující skutečnosti:

• Systém jako celek není nijak globálně řížen.
• Každý agent je majitelem pouze části informací celkové problematiky modelu.
• Každý agent má své cíle a funguje asynchronně.

Agenti

Toto je pouze stručný úvod do teorie agentů, podrobnější výklad lze nalézt v dedikovaném textu o agentech.

Agent je cokoli, co pomocí senzorů vnímá své okolí a pomoci efektorů na ně zpětně reaguje. Podle této definice je agent entitou (ať už fyzickou nebo virtuální), která vnímá své okolí a reaguje na něj. Virtuální entitou můžeme chápat jako kus zrojového kódu, který přijímá nějaké vstupy z prostředí a produkuje výstupy. Často jsou ale agenti kombinací fyzických a virtuálních částí, jako například chytrý vysavač. Mimo to, že agenti vnímají prostředí, ve kterém se nacházejí, mají i své cíle, které se klidně mohou lišit od cílů ostatních agentů. Díky svým cílům a možnosti reagovat na okolí - tedy i na jiné agenty - považujeme agenty za autonomní entity. To znamená, že agent operuje na základě své vlastní logiky, nikoli na povel od někoho jiného, a mají tím pádem určitou kontrolu nad svým jednáním.

Prostředím agenta rozumíme prostředí, ve kterém se agenti nacházejí, pohybují a ze kterého přijímají signály. Podrobnější výklad je k nalezení v dedikovaném textu o prostředí.

Uvažování agenta

Jelikož má agent své cíle, kterých chce dosáhnout, jeho rozhodnutí směřují čistě racionálně za jejich dosáhnutím. K tomu agent užívá buď užitkovou funkci nebo logickou dedukci na základě jeho individuálních znalostí a zkušeností. Více o uvažování agenta si můžete přečíst zde.

Reálné aplikace

Servisní roboti, transportační systémy, průzkum nebezpečných prostředí, obrana státu, či záchranné akce při mimořádných událostech, to všechno jsou oblasti, ve kterých se v dnešní době využívají multiagentní systémy. Zajímavým příkladem je třeba DARPA Grand Challenge, což je závod autonomních vozidel pouštní krajinou sponzorovaný americkým ministerstvem obrany za účelem urychlení vývoje autonomních vozidel.

Dalším příkladem může být například veletrh RoboCup, což je každoroční soutěž a přehlídka autonomních robotů. Cílem sponzorů této přehlídky je do roku 2050 sestavit robotický fotbalový tým, který bude schopen konkurovat lidskému týmu. V roce 2016 se této události zúčastnilo 45 zemí.

Satelitní monitorovací roboti

NASA například k údržbě satelitů a jiných vesmírných těles používá tým autonomních robotů. Ti jsou schopni pracovat jak samostatně, tak v asistenci s astronautem. Posádky létající na oběžnou dráhu země za účelem údržby satelitů a drobných oprav se obvykle skládají ze tří až čtyř astronautů a množství práce, které na ně na oběžné dráze čeká, je ohromné. Proto jsou tyto lidské posádky podpořeny několika roboty o velikosti baseballového míčku, kteří dokáží satelit a jiná zařízení zkontrolovat a konstatovat, zda jsou v pořádku či nikoliv.

• 

  Autonomní vozidlo na soutěži DAPRA Grand Challenge.

• 

  Agenti hrající fotbal.

• 

  Satelitní monitorovací agent.

Program NetLogo

Ukázky simulací v prostředí NetLogo

NetLogo je programovatelné modelovací prostředí pro vytváření multiagentních simulací. Autorem aplikace je Uri Wilensky. Aplikace je napsána v Javě a díky tomu by měla bezproblémově fungovat na jakékoli platformě s nainstalovaným javovským prostředím. Netlogo je obvzlášť vhodné pro modelování komplexních systémů vyvíjejících se v čase. Uživatel může orchestrovat stovky či tisíce nezávislé operujících agentů. Tento fakt umožňuje provádět rozsáhlé simulace a ověřovat či vyvracet hypotézy, jejichž pravdivost bychom jinak posuzovali velmi složitě.

Netlogo má navíc vydatnou dokumentaci, navíc obsahuje knihovnu připravených modelů, se kterými si může uživatel hrát a objevovat tak funkčnosti prostředí. Se znalostmi ukrytými v dokumentaci je uživatel schopen zkoumat chování komplexního multiagentního systému za měnících se podmínek a z různých úhlů pohledu.

Netlogo je vhodné pro simulace z oblasti:

• Přírodních věd
  • Biologie
  • Chemie
  • Lékařství
• Matematiky
• Sociálních věd a sociální psychologie
• Ekonomie
• Informačních technologií

Řešený příklad

Vyzbrojeni nově nabytými vědomostmi se nyní můžeme pustit do řešení reálné simulace. Příklad se bude zabývat šířením viru na počítačové síti. Pro řešení příkladu si nejprve stáhněte program NetLogo.

Příprava prostředí

Před samotným programováním, na které se jistě všichni těšíte, si nejprve vytvořme proměnné a grafické komponenty, které nám celou simulaci obohatí o možnost ovlivňovat vstupní parametry a názorně sledovat tížený výsledek.

Proměnné

Začněme definováním vstupních parametrů, jenž budeme k naší simulaci potřebovat, jedná se o proměnné:

• number-of-nodes - počet počítačů
• average-node-degree - průměrný počet vazeb mezi počítači
• initial-outbreak-size - počáteční počet nakažených počítačů
• virus-spread-chance - riziko přenosu viru na jiný počítač
• virus-check-frequency - četnost antivirové kontroly (při použití hodnoty 1 bude ke kontrole docházet každé kolo)
• recovery-chance - šance odhalení viru na nakaženém počítači
• gain-resistance-chance - šance na získání imunity vůči viru, který počítač nakazil

Hodnoty výše uvedených proměnných můžete používat libovolné, ovšem pro účely tohoto příkladu budeme simulovat 150 počítačů s průměrnou vazbu na jiné počitáče s hodnotou 6, počátečním počtem virů tři, rizikem přenosu 2,5%, antivirovou kontrolou probíhající každé kolo a šancí na odhalení viru a získání imunity 5%.

Grafické komponenty

Dále vytvořme tlačítka a na ně navázané metody setup a go, u kterého navíc zaškrtněme checkbox Forever.

K dokonalosti už zbývá pouze graf, na kterém uvidíme závislost zranitelných, nakažených a imunních počítačů přehledněji, než v samotné simulaci. K tomuto účelu použijme komponentu Plot a do Plot pens definujme:

Color	Pen name	Pen update commands
	zranitelné	plot (count turtles with [not infected? and not resistant?]) / (count turtles) * 100
	nakažené	plot (count turtles with [infected?]) / (count turtles) * 100
	imunnní	plot (count turtles with [resistant?]) / (count turtles) * 100

Nyní by prostředí na záložce Interface mělo vypadat nějak takto:

Logika šíření viru a chování počítačů

Zbytek práce na nás čeká v záložce Code. Zde je nejprve nutné definovat naše agenty a společně s tím určíme i jejich vlastnosti, které označují, zda-li je počítač nakažený virem, zda je imunní a zda je čas provést antivirovou kontrolu:

turtles-own
[
  infected?           
  resistant?        
  virus-check-timer 
]

Procedura setup

Nyní vytvořme poměrně abstraktní proceduru setup, jenž vytvoří počítače, spojení mezi nimi a nakazí daný počet nodů virem.

to setup
  clear-all
  setup-nodes
  setup-spatially-clustered-network
  ask n-of initial-outbreak-size turtles
    [ become-infected ]
  ask links [ set color white ]
  reset-ticks
end

Dále implementujme proceduru, která vytvoří počítače dle zadaného parametru number-of-nodes, nastaví jim vizuální podobu kolečka, odsadí je od kraje okýnka simulace, nastaví je jako zranitelné a inicializuje hodnotu atributu virus-check-timer na náhodnou hodnotu se střední hodnotou zadaného parametru virus-check-frequency:

to setup-nodes
  set-default-shape turtles "circle"
  create-turtles number-of-nodes
  [
    setxy (random-xcor * 0.95) (random-ycor * 0.95)
    become-susceptible
    set virus-check-timer random virus-check-frequency
  ]
end

Tím pádem ještě potřebujeme samopopisnou proceduru become-susceptible:

to become-susceptible 
  set infected? false
  set resistant? false
  set color green
end

V rámci procedury setup zbývá ještě implementovat prolinkování mezi počítači:

to setup-spatially-clustered-network
  let num-links (average-node-degree * number-of-nodes) / 2
  while [count links < num-links ]
  [
    ask one-of turtles
    [
      let choice (min-one-of (other turtles with [not link-neighbor? myself])
                   [distance myself])
      if choice != nobody [ create-link-with choice ]
    ]
  ]
  repeat 10
  [
    layout-spring turtles links 0.3 (world-width / (sqrt number-of-nodes)) 1
  ]
end

Procedura go

Nyní můžeme implementovat proceduru go. Ta bude každé kolo kontrolovat, zda virus nevymřel, a pokud ano, simulaci ukončí. Dále zvýší hodnotu stopek, jenž určují, kdy provést antivirovou kontrolu. A nakonec zajistí šíření viru a provedení antivirových kontrol. Funkčnost může vypadat například takto:

to go
  if all? turtles [not infected?]
    [ stop ]
  ask turtles
  [
     set virus-check-timer virus-check-timer + 1
     if virus-check-timer >= virus-check-frequency
       [ set virus-check-timer 0 ]
  ]
  spread-virus
  do-virus-checks
  tick
end

Téměř na závěr zbývá už jen konkrétní implementace procedur spread-virus a do-virus-check:

to spread-virus
  ask turtles with [infected?]
    [ ask link-neighbors with [not resistant?]
        [ if random-float 100 < virus-spread-chance
            [ become-infected ] ] ]
end

to do-virus-checks
  ask turtles with [infected? and virus-check-timer = 0]
  [
    if random 100 < recovery-chance
    [
      ifelse random 100 < gain-resistance-chance
        [ become-resistant ]
        [ become-susceptible ]
    ]
  ]
end

S pomocnými procedurami pro úpravu stavu počítače:

to become-infected 
  set infected? true
  set resistant? false
  set color red
end

to become-resistant 
  set infected? false
  set resistant? true
  set color gray
  ask my-links [ set color gray - 2 ]
end

Nyní máme simulaci hotovou.

Výsledek

Výsledek simulace.

Po tvrdé práci máme v rukou fungující simulaci, ale co s ní teď? Nyní můžeme měnit vstupní její parametry, jako například šanci na nákazu či na získání imunity a pozorovat, jak provedené změny ovlivní průběh či konec simulace (parametry lze nastavit i tak, aby virus nikdy nevymřel a simulace stále běžěla). Na uvedeném grafu ještě vidět závislost zranitelných, nakažených a imunních počítačů. Na ose x se hromadí jednotlivá kola simulace a na ose y je uvedeno celkové procento počítačů, které se v daném čase nacházejí v daném stavu. Zelená osa značí zranitelné nody, červená označuje počítače nakažené virem a šedá pak imunní jedince. Nutné je ale vzít v potaz, že pro získání opravdu věrohodných výsledků bychom museli provést simulaci několikrát a jednotlivé výstupy průměrovat.

Kompletní projekt obsahující řešený příklad je možné stáhnout zde.

Samostatné cvičení

K upevnění znalostí ze společně řešeného příkladu si nyní můžete samostatně vyzkoušet rozšířit model o některou z následující skutečností:

Šíření viru emailem

Předpokládejme, že virus je obšťastněn schopností poslat sám sebe emailem všem kontaktům v adresáři. Jelikož existence kontaktu v nečím emailovém adresáři není oboustranná vazba, je potřeba model upravit tak, aby používal jednostranné vazby namísto oboustranných. Jak se po úpravě změnilo šíření viru?

Existence více druhů viru

V reálném světě ovšem neexistuje pouze jeden počítačový virus a pokud je nějaký počítač nakažen jedním virem, riziko nakažení dalším virem je vyšší. Zaneste do simulace další typ viru a upravte model tak, aby reflektoval skutečnost, že nakažený node je náchylnější k nákaze jiným mallwarem. Jakým způsobem spolu dva počítačové viry interagují?

Mutace viru

Tvůrcem nejhlubších vrásek na čele leckterého bezpečnostního technika jsou takzvané metamorfické viry. To jsou viry, které se umí transformovat, mutovat a přizpůsobovat se měnícím se podmínkám počítačové ochrany. V reálném světě to znamená, že virus může být imunní vůči antivirovým programům. V našem modelu to znamená nutnost upravit zdrojový kód tak, aby umožňoval znovu-nakažení počítače virem, který se cestou od dříve nakaženého nodu a zpět zmutoval. Jaký má tato skutečnost dopad na náš model?