Zápisnica č.	Dátum	Miesto	Čas
6	12. 11. 2008	Softvérové štúdio	15.00

Zúčastnení členovia	Bc. Juraj Ligocký Bc. Michal Hrubý Bc. Gabriel Pán Bc. Ján Hric Bc. Marek Polák
Pedagóg	Ing. Ivan Kapustík
Zapisovateľ	Bc. Marek Polák

Program stretnutia

1. Pokyny a informácie k odovzdávaniu dokumentácie
2. Zhodnotenie predchádzajúcich úloh v moderovanej diskusii
3. Rozdelenie nových úloh na ďalšie stretnutie

Priebeh stretnutia

1. Pokyny a informácie k odovzdávaniu dokumentácie

- JH oznámil fakt, že dokumentácia je takmer hotová, GP dodá svoju časť dokumentácie na zapracovanie do večera.

- Prostredníctvom konta na GG sa s nami spojil konkurenčný tím, JL bude mať na starosti komunikáciu s nimi.

- IK spomenul, že je vhodné vypracovať preberacie protokoly pre vedúceho ako aj pre posudzujúci tím.

2. Zhodnotenie predchádzajúcich úloh v moderovanej diskusii

- GP otestoval výkon hráčov napísaných v Jave na dvoch rozlične výkonných strojoch. Na každom vykonal šesť simulácií, polčas simulácie stanovil na 1 000 taktov. Priemernú dĺžku taktu vyčíslil na cca. 160 ms. Úplné výsledky testov budú uvedené v technickej dokumentácii projektu.

- JH rozdelil členom jednotlivé časti dokumentácie, ktoré majú spísať. Sám sa s dobrými výsledkami podieľal na jej tvorbe, dokumentácia je takmer hotová a pripravená na odovzdanie. Okrem toho sa venoval kompilácii zdrojových kódov pod Linuxom. Zistil, že hráča na serveri novších verzií nie je možné spustiť, chybou je nedefinovaná premenná v heterotypoch.

- MH pokračoval v analýze zápasov. Nahral na stránku tímu simulácie zápasov vo formáte SWF, a to celé zápasy ako aj zaujímavé momenty. Skúmal, aké sú možnosti logovania hráčov a čo sa z logov dá zistiť. Opísal logy pre potreby dokumentácie a skúmal funkcionalitu Simulation Monitora.

- JL vytvoril príručku prechodu z Javy na C++. Zahŕňa stavbu kódu, základné techniky správneho písania kódu ako aj opis architektúry hráča Jahodových princov. Obsahuje základný diagram tried a opis ich činnosti, ako aj vzájomné závislosti medzi nimi.

- MP študoval dokumentáciu k agresívnemu správaniu tímu Brainstormers. Opísal typ a architektúru neurónovej siete, vstupný vektor a použité algoritmy. Nejasným ostáva spojenie viacerých techník učenia ako aj ohodnocovanie siete. Výstupom analýzy je kapitola technickej dokumentácie k projektu.

3. Rozdelenie nových úloh na ďalšie stretnutie

- JL má na starosti spojiť sa s členmi tímu Jahodových princov a s ich pomocou navrhnúť, čo je nutné zlepšiť, dokončiť a odladiť v algoritme eliminácie premenných. Zároveň bude pokračovať v dokumentácii zdrojového kódu Jahodových princov.

- GP sa bude v nasledujúcich týždňoch venovať hráčovi napísanom v Jave. Konkrétne má za úlohu analyzovať hotové a použiteľné časti hráča a zistiť, ktoré časti je nutné implementovať, aby hráč dokázal odohrať zápas. Na budúcom stretnutí má predviesť jednoduchú akciu hráča.

- MH má za úlohu opísať a zhodnotiť Java-monitor oproti ostatným riešeniam. Zaujímavý je hlavne jeho prínos, klady oproti iným monitorom. Súčasťou bude aj špecifikácia monitora, opis jeho funkcií.

- MP má za úlohu kontaktovať členov tímu Brainstormers so stručne a presne definovanými otázkami ohľadom ich riešenia. Okrem toho je jeho úlohou vypracovanie posudku konkurenčnému tímu.

- JH má do budúceho týždňa nájsť chybu v komunikácii hráč - server. Jeho úlohou je prejsť zoznamy zmien v serveroch, spísať možné dôvody chyby a nakoniec identifikovať jej príčinu.

Plnenie úloh z predchádzajúcich stretnutí
Id	Opis	Zodpovedný	Termín	Stav
4.1	Rozdeliť členom tímu úlohy na dokumentácii.	Hric	7.11.2008	Splnená
4.2	Pokračovať v tvorbe dokumentácie.	Hric	12.11.2008	6.2
4.3	Výsledky spustenia simulácie v Jave aspoň na dvoch rôznych strojoch opísať v dokumentácii.	Pán	12.11.2008	Splnená
4.4	Logy dať na stránku, pokračovať v logovaní, prípadne analyzovať zmeny v nových verziách servera.	Hrubý	12.11.2008	Splnená
4.5	Dokumentácia zdrojového kódu Jahodových princov.	Ligocký	12.11.2008	Čiastočne splnená
4.6	Pokračovať v príprave neurónovej siete, písanie dokumentácie.	Polák	10.12.2008	Čiastočne splnená
4.7	Písanie dokumentácie.	všetci	12.11.2008	Splnená

Nové úlohy
Id	Opis	Zodpovedný	Termín
6.1	Analýza algoritmu eliminácie premenných, práca na dokumentovaní zdrojového kódu.	Ligocký	19.11.2008
6.2	Pokračovať v tvorbe dokumentácie.	Hric	10.12.2008
6.3	Analyzovať hotové a použiteľné časti javového hráča a zistiť, ktoré časti je nutné implementovať.	Pán	10.12.2008
6.4	Predviesť jednoduchú akciu hráča (nájdenie lopty, kop na bránku atď.).	Pán	19.11.2008
6.5	Opis a špecifikácia javového monitora, jeho porovnanie s inými riešeniami.	Hrubý	19.11.2008
6.6	Kontaktovať tím Brainstormers ohľadom neurónovej siete, písanie posudku konkurenčnému tímu.	Polák	19.11.2008
6.7	Prejsť changelogy serverov, identifikovať a opísať chybu v heterotypoch.	Hric	19.11.2008

Použité skratky:

JL Bc. Juraj Ligocký

MH Bc. Michal Hrubý

GP Bc. Gabriel Pán

JH Bc. Ján Hric

MP Bc. Marek Polák

IK Ing. Ivan Kapustík

GG Google Groups

Príloha A

Agresívne správanie hráča

Jedným z cieľov nášho tímového snaženie je implementácia agresívneho správania do hráča tímu Jahodových princov pre zlepšenie obranných schopností. Ako vzor slúži viacnásobný víťaz Robocup-u 2D, nemecký tím Brainstormers. Výsledkom práce bude navrhnutá, vytvorená a naučená neurónová sieť plus nevyhnutné rozhranie na jej použitie v zápasoch. Nasledujúce riadky obsahujú popis a vysvetlenie problému, ako a návrh riešenia.

Agresívne správanie

Agresívnym správaním sa rozumie snaha hráča prerušiť rozohrávku súperiaceho tímu tak, aby zabránil vzniku útočnej situácie a naopak získal loptu pre budovanie vlastného útoku. V praxi ide o obranné správanie: pristúpenie k hráčovi s loptou a jej odobratie povoleným spôsobom.

Väčšina tímov robotického futbalu rieši proces získania lopty naivným spôsobom: hráč najbližšie k protivníkovi s loptou sa snaží dostať na dosah lopty, aby ju mohol nahrať spoluhráčom. Táto stratégia často býva neúspešná, hlave ak súperiaci hráč je z tímu s dobre vyvinutou schopnosťou driblovať. [1]

Získanie lopty je vysoko netriviálna úloha, pričom jej zložitosť závisí vo veľkej miere na správaní súpera. Pri postupe klasickými programátorskými metódami môže byť problémom vytvorenie špecializovaného hráča, ktorý by fungoval dobre pri niektorých tímoch, ale pri iných vôbec. Okrem toho musí hráč pri procese získania lopty dbať aj na svoje postavenie a postavenie ostatných spoluhráčov, aby pri možnej strate lopty nedošlo k prečísleniu a súperiaci tím nezískal útočnú výhodu.

Riešenie, ktorým sa zaoberal viacnásobný víťaz Robocup-u 2D, nemecký tím Brainstormers, spočíva vo využití neurónových sietí, presnejšie „reinforcement learning“ metódy.

Reinforcement learning je metóda učenia sa vďaka interakcii s prostredím. Agent sa učí na základe výsledkov jeho predchádzajúcej činnosti. Nasledujúcu akciu vyberá z množiny predchádzajúcich výsledkov a nových možností, čiže postupuje metódou pokus- omyl. Učiacim signálom je numerická hodnota určujúca úspech akcie, pričom agent sa snaží vyberať v ďalších krokoch akcie, ktoré maximalizujú kumulovanú odmenu v priebehu času. [3]

Modelovanie problému

Stavový priestor robotického futbalu je mimoriadne rozsiahly a mení sa v každom takte hry. Z toho dôvodu je nutné určiť, ktoré parametre sú nutné na identifikáciu vhodnosti agresívneho správania. Tím Brainstormers sa rozhodol obmedziť problém na 9 dimenzií:

§ Vzdialenosť d medzi našim a súperiacim hráčom s loptou

§ Rýchlosť nášho hráča (v_x a v_y zložky pohybu)

§ Absolútna hodnota v_opp – rýchlosť súperiaceho hráča s loptou

§ Pozícia lopty na mape (b_x a b_y)

§ Natočenie tela hráča relatívne k súperovej pozícii (uhol α)

§ Natočenie tela útočiaceho hráča vzhľadom na našu bránku (uhol β)

§ Hodnota strategického uhla γ = GOM (kde G je pozíciou našej bránky, O pozíciou súpera a M pozíciou nášho hráča)

[1]

Hráčovi je povolené použiť príkazy dash(x) a turn(y) z ohraničených intervalov tak, že existuje 76 vykonateľných akcií. Intervaly pre jednotlivé príkazy sú:

§

§ y

Obr. 1 – a) Vymedzený priestor v okolí hráča s vyznačenými príkladmi umiestnení súpera (žlté kruhy) b) tréningové regióny na mape – obr. prevzaný z [2]

Tréningové stavy, slúžiace na učenie hráča, boli modelované podľa nasledujúceho modelu. V okolí hráča si možno predstaviť 2 polkruhy, jeden s polomerom 3m, druhý 5m. Polkruh s menším polomerom je orientovaný smerom k našej bránke, polkruh s väčším naopak k súperovej. Do takto vymedzeného priestoru je umiestnený súperiaci hráč a lopta, pričom lopta je v blízkosti súpera a má nulovú rýchlosť. Rýchlosti hráča a súpera, ako aj ich vzájomné natočenie sú zvolené náhodne.

Okrem toho tím Brainstormers vybral 4 tréningové regióny na mape. Jeden v strede ihriska, 2 v jednotlivých rohoch našej polovice ihriska a posledný v strede našej časti ihriska. Pri návrhu týchto pozícií vychádzali z idei, kadiaľ súperiace tímy vedú útok (všeobecne stredom, alebo po krídlach plochy).

Neurónová sieť, učiaci algoritmus

Navrhovaná sieť pozostáva z 28 neurónov pričom obsahuje 1 skrytú vrstvu (architektúra po vrstvách: 9-18-1). Ako aktivačná funkcia je použitá sigmoidálna funkcia a učiacim algoritmom je RPROP algoritmus (Resilient backpropagation). Za rýchlosť učenia α bola zvolená hodnota 1.0

Chybová funkcia RPROP algoritmu je:

Obr. 2 – Celková chybová funkcia RPROP – zdroj http://europa.eu.int/en/comm/eurostat/research/supcom.95/16/result/node23.html

Pričom out_k is výstupom siete, d_k je požadovaným výstupom, w_ij je j-tou váhou neurónu i a α parametrom váh.

Pri trénovaní siete sa jednotlivé stavy nevymazávajú, ale prebieha ich pretrénovanie po 250 spustených inštanciách.

Dosiahnuté výsledky Brainstormers

Tím pri vyhodnocovaní výsledkov identifikoval 5 možných koncových stavov:

1. úspech – Lopta sa dostala do hrateľnej oblasti nášho hráča, hráč obral súpera a môže nahrať voľnému spoluhráčovi.
2. neúspech – Neúspešná epizóda môže vzniknúť v dôsledku straty lopty hráčom, príp. keď lopta opustí hraciu plochu a pod.
3. súper spanikári – Prejavuje sa nezmyselným odkopnutím lopty súpera mimo svojho hracieho priestoru, často dopredu alebo do voľného priestoru. Takúto epizódu možno považovať aj za remízu.
4. chyba – Protihráč prešiel cez nášho atakujúceho hráča a je od neho vzdialený viac ako 7 metrov.
5. time-out – Počas trvania epizódy (35 krokov) nenastala ani jedna z vyššie uvedených situácií.

Tím dosiahol po naučení úspešnosť siete presahujúcu 80%, pričom množstvo chybových epizód sa držalo pod úrovňou 5%.

V priebehu klasických zápasov (6000 krokov) mali hráči približne 66 epizód, v ktorých použili agresívne správanie. Pri konzervatívnom odhade úspechu 50% to znamená viac ako 30 získaní lopty čím zabránili gólovým situáciám a naopak mohli prejsť do útoku.

Zdroje

1. Riedmiller M., et al.: Brainstormers 2D — Team Description 2008, Institute of Cognitive Science, Universität Osnabruck, www.ni.uni-osnabrueck.de/fileadmin/user_upload/publications/riedmiller. gabel.trost.bs08tdp.pdf

2. Riedmiller M., et al.: Brainstormers 2D — A Case Study on Improving Defense Behavior in Soccer Simulation 2D, Institute of Cognitive Science, Universität Osnabruck,www.ni.uos.de/fileadmin/user_upload/publications/gabel.riedml.trost. robocupsymposium08.pdf

3. Reinforcement learning - Florentin Woergoetter and Bernd Porr (2008), Scholarpedia, 3(3):1448., http://www.scholarpedia.org/article/Reinforcement_learning