Efektivní taktiky pro přežití - Zombie Apokalypsa

Honza Brázdil

Úvod

Cílem projektu bylo naprogramovat umělou inteligenci pomocí Goal/Utility based agentů. Jako problém byl zvolen konflikt mezi zombie a lidmi.

Implementace

K implementaci byl použit program NetLogo a jazyk Java. NetLogo je simulační program napsaný v Javě/Scale a rozšiřitelný Javovými doplňky. V samotném programu se využívá jazyka NetLogo, který je založený na jazyku Logo.

Prostředí NetLoga umožňuje jednoduše nastavovat parametry simulace, zobrazovat aktualní situaci, ovládat simualci a vykreslovat grafy.

V jazyce NetLogo bylo naimplementováno chování světa a důsledky rozhodnutí agentů. Samotná umělá inteligence je implementována v Javě jako rozšíření pro NetLogo.

Simulace

Simulace probíhá na svetě s obtočenými hranami (agent pohybující se vpravo z plochy se objeví vlevo). Ve svetě se pohybují 2 druhy agentů: zombie a lidé. Dále se ve světě nachází políčka s jídlem (zvlšť pro zombie, zvlášť pro lidi) a náboji.

Agenti můžou zjišťovat informace o světě pomocí několika senzorů: vidění, vidění polí a vicítění, ovlivnňovat svět můžou poté pomocí několika aktuátorů: pohyb, otočení, útok, jezení a výstřel.

Vidění

Vidění předá umělé inteligenci seznam agentů kteří se nacházejí před agentem. Dva parametry simulace určují úhel kuželu vidění a vzdálenost do které vidí.

Vidění polí

Obdobně jako vidění, ale vrací seznam polí před agentem.

Vicítění

Vicítění vrací buď počet zombií nebo počet lidí nacházející se v okolí kolem agenta. Velikost tohoto okruhu může být nastavena parametrem a zpravidla je menší než vzdálenost na kterou může agent vidět.

Pohyb

Pohyb posune agenta o krok vpřed.

Otočení

Otočení natočí agenta o zadaný úhel.

Útok

Pokusí se zaútočit na zadaného agenta. Útočící agent musí být v útočném dosahu (parametr simulace) k napadenému. Pokud útočí zombie na člověka, je možné že se tento člověk nakazí. Nakažení ovlivňují dva parametry: pravděpodobnost nakažení a doba infekce po které se nakažený člověk zmení na zombie.

Jezení

Pokusí se sníst jídlo nacházející se na políčku na kterém agent stojí. Pokud se na políčku nachází adekvátní jídlo pro agenta, jedno jídlo se z políčka odebere a agent si vyléčí určitý počet životů. Pokud by počet životů měl překročit výchozí počet životů, nastaví se počet životů na výchozí.

Počet polí s jídlem pro lidi se udává jako parametr simulace a tento počet polí se nepravidelně obnovuje.

Jídlo pro zombie vzniká při smrti člověka na políčku na kterém člověk zemřel.

Výstřel

Pokusí se vystřelit na zadaného agenta. Útočící agent musí být člověk a v dosahu střelby k napadenému. Musí také mít alespoň jeden náboj. Náboje se z polí s náboji berou prostým vstupem na toto pole.

Počet nábojů se kterýmy člověk začíná se určuje jako parametr simulace. Dalším parametrem je počet polí na kterých se ze začátku nalézají náboje.

Při smrti člověka všechny jeho nepoužité náboje vypadnou na políčko kde umřel.

Umělá inteligence

Bylo implementováno několik "mozků" - řídících algoritmů pro agenty. Základní jednoduché Basic Brain, komplikovanější Memory Brain a Chase Brain a mozek s využitím Goal/Utility based rozhodováné Goal Brain

Basic Brain

Tento mozek představuje primitivní rozhodování.
Pro člověka:

Pro Zombie:

Memory Brain

Tento mozek je určený pro člověka. Využívá pamatování si pozice zombií a počítá míru nebezpečí na pozicích kolem agenta. Míra nebezpečí se počítá ze vzdáleností zapamatovaných zombií k dané pozici. Po nalezení místa s nejmenším nebezpečím v okolí se agent vypraví tímto směrem.

Pokud v okolí agenta není žádný zombie, agent se otáčí dokola (rozhlíží se) čímž si aktualizuje vzpomínky na okolní zombie.

Chase Brain

Tento mozek je určený pro zombie. Obdobně jako Memory Brain využívá pamatování si pozice lidí. Hledá nejbližšího člověka na kterého má vzpomínku. Pokud žádného nenajde, ale v okolí agenta se nějaký nachází, agent se pootočí (pátrá po člověku v okolí). Pokud je nejbližšší člověk v útočné vzdálenosti tak agent zaútočí, pokud ne tak se vydá nejkratší cestou k němu.

Pokud agent neví o žádném člověku pohybuje se náhodnou procházkou.

Goal Brain

Tento mozek je určený jak pro zombie tak pro člověka. K rozhodnutí akce využívá Cílů a Utilit. Cíle vytvářejí plán akcí a tento plán ohodnotí prioritou (každý Cíl má výchozí prioritu pro plány co generuje). Utility poté analyzují plány a dále mění jejich prioritu. Plán s nejlepší prioritou je poté vybrán pro další jednání agenta.

Cíle

AvoidZombie - plán je pohyb směrem od zombií.
Attack - plán je pohyb k nepřátelskému agentu a útok. Pro každého nepřítele o kterém má agent vzpomínku se vygeneruje jeden plán.
Eat - plán je pohyb k políčku s jídlem a jezení. Pro každé políčko s jídlem o kterém má agent vzpomínku se vygeneruje jeden plán.
KillInfected - plán je pohyb směrem k nakaženému člověku a útok na něj.
PickupAmmo - plán je pohyb k políčku s náboji. Pro každé políčko s náboji o kterém má agent vzpomínku se vygeneruje jeden plán.
ShootZombie - plán je pohyb k zombie a výstřel. Pro každou zombii o které má agent vzpomínku se vygeneruje jeden plán.

Utility

DontStarve - utilita pro zombie. Penalizuje plány podle předpokládaného počtu životů na konci plánu. Čím méně životů na konci plánu je předpokládáno (dlouhý plán) tím větší penalizace. Čím více životů na konci plánu je předpokládáno (zombie sní jídlo) tím menší penalizace.
Stay - utilita pro člověka. Penalizuje plány obsahující pohyb.
SaveAmmo - utilita pro člověka. Penalizuje plány obsahující střelbu.
Fear - utilita pro člověka. Penalizuje plány na základě zdraví agenta a míře nebezpečí. Míra nebezpečí je počítána z hustoty a blízkosti zombií k učitému bodu.

Použití

Pro použití je neprve potřeba stáhnout a nainstalovat program NetLogo (http://ccl.northwestern.edu/netlogo/).

Zdrojový kód simulace je ve složce projektu umístěn v netlogo/ets-za.nlogo. Rozšíření je klasický mavenový projekt umístěn v ets-za. Pro zkompilování je potřeba nakopírovat do složky ets-za/lib/ soubory NetLogo.jar a lib/scala-library.jar ze složky s programem NetLogo.

Po zkompilovaní je potřeba zkopírovat zabalené rozšíření do složky extensions/gbui ve složce s programem NetLogo.

Pro kompilaci a automatické nakopírování rozšíření do NetLoga je možné použít příkaz:

mvn clean install -DoutDir=/path/to/netlogo/extensions/gbui

Testovaní

Při testování se vyhodnocoval vliv nastavení priorit cílů a parametrů utilit na přežití lidí. Pro každý cíl/utilitu bylo otestováno 21 vzorků (cíle a parametr pro Fear rozmezí 0.0 - 1.0, SaveAmmo 0.0 - 5.0, Stay 0.0 - 20.0). Každý vzorek byl testován pomocí 50 simulací.

Simulace probíhala dokud jedna ze soupeřících stran nevymřela. Po skončení simulace se spočítal počet přeživších lidí nebo zombie a množství kroků které simulace trvala. Poté byl spočten průměr naměřených hodnot pro daný vzorek.

Pro testování byly hodnoty zrovna neměřeného parametru fixovány na:

Na následujících grafech jde vidět vliv parametru na měřené hodnoty. Osa X představuje hodnotu parametru, levá osa Y množství přeživších (červená lidé, zelená zombie), pravá osa Y počet kroků simulace (modrá).

Z grafů vyplívá následující nastavení parametrů:

Na následujících grafech je srovnání výkonosti jednotlivých mozků. Simulace probíhaly s rozdílným počátečním rozložením lidí a zombie. Osa X určuje počet zombie na začátku simulace. Počet lidí je 100 - počet zombie. Levá osa Y určuje procento přeživších z výchozího počtu, pravá osa Y určuje počet kroků simulace.

Spolupráce

Na projektu jsem spolupracoval s Jakubem Senkem. Jakub pracoval na simulační části v jazyce NetLogo, já se zaměřil na umělou inteligenci v Javě.

Odkazy

Projekt na Githubu - https://github.com/janinko/ETS-ZA (lokálně - ETS-ZA.zip)
Video ukázka - http://youtu.be/mmhKPYfJs1A