Slovenská technická univerzita

Katedra informatiky a výpočtovej techniky, Fakulta elektrotechniky a informatiky

Ilkovičova 3, 812 19 Bratislava

 

 

 

 

 

RoboCup

Autori:

Radoslav Kováč

Dušan Lacko

Martin Pilka

 

 

 

 

 

Študijný odbor: Informatika

Ročník: 4

Predmet: Umelá inteligencia

Školský rok: 1999/2000

  1. Čo je to RoboCup?
  2. Snahou RoboCupu je podporovať vývoj rôznych technologických oblastí pomocou riešenia štandardných prolémov, pri ktorých je možné použiť veľké množstvo technológií. Na tento účel je ako problém zvolená hra futbal a je organizovaný turnaj RoboCup (Robot World Cup Soccer Games and Conferences). Základnou ideou je vytvoriť čo najviac dokonalých fyzických, ale i syntetických (programovo realizovaných) agentov, ktorí dokážu hrať futbal na vysokej úrovni. Míľnikom by malo byť zostrojenie tímu humanoidných robotov, ktorí by hrali proti najlepšiemu 'ľudskému' tímu podľa oficialných pravidiel FIFA, niekedy v polovici budúceho storočia.

    RoboCup Federation je medzinárodná nezisková organizácia zaregistrovaná v Ženeve za účelom podpory, propagácie a posilňovania RoboCup výskumu. Túto iniciatívu v súčasnosti nasleduje približne 1500 výskumníkov v 17 rôznych krajinách. Do súťaže sa môže zapojiť každý tím (resp. jednotlivec), bez ohľadu na to, či je alebo nie je zameraný na samotný výskum. Niektoré tímy sa zúčastnujú súťaže iba zo zábavy (najmä v simulačnej lige), iné sú zamerané na seriózny výskum, pričom svoje výsledky pravidelne publikujú.

    V súčasnosti má súťaž RoboCup nasledovné kategórie:

    · Simulačná liga pre syntetických (softvérových) agentov

    · Liga malých robotov (5 robotov na tím)

    · Liga malých robotov (11 robotov)

    · Liga stredne veľkých robotov (11 robotov)

  3. Simulačná liga
  4. V tejto práci sa budeme zaoberať výlučne simulačnou ligou. Simulačný systém funguje ako klient/server systém s centrálnym simulačným serverom, ktorý komunikuje s 22 klientami (hráčmi). Samotný simulátor je napísaný v jazyku C++ a môže byť preložený na množstve platforiem ako UNIX, SunOS, Solaris, Linux... Taktiež je k dispozícii verzia pre OS Windows. Server komunikuje s klientami pomocou UDP/IP protokolu. Na klienta teda nie sú okrem komunikačného protokolu kladené žiadne iné obmedzenia.

    Server posiela klientom vnemové informácie v pravidelných časových intervaloch. Každý klient prijíma informácie troch druhov:

    · vizuálne informácie

    · audio informácie

    · vnútorné informácie

    Vizuálne informácie informujú hráča o objektoch, ktoré vidí. Všetky informácie sú prepočítané z absolútnych súradníc na relatívne voči hráčovi. Ten sa teda môže dozvedieť napríklad to, že vo vzdialenosti 20 metrov v smere jeho pohľadu sa nachádza lopta, ale ak chce zistiť absolútne súradnice tohoto bodu na ihrisku, musí to urobiť vo vlastnej réžii. V tejto úlohe mu pomáhajú značky, ktoré sú rozmiestnené po obvode ihriska. Hráč vidí objekty, ktoré sa nachádzajú v jeho uhle pohľadu. Tento uhol si môže sám zmeniť na jednu z hodnôt (-45, 45), (-90, 90), alebo (-22.5, 22.5). Objekty vzdialené do 3 metrov od hráča sú takisto súčasťou vizuálnej informácie, ak sa však nenachádzajú v uhle pohľadu, potom hráč dostane iba informáciu o type objektu (lopta, hráč, bránka, značka), ale nedozvie sa jeho skutočný názov (napr. ktorý hráč?). A aby to nebolo príliš jednoduché, informácie sú zašumené, to znamená že s narastajúcou vzdialenosťou objektu klesá presnosť informácií, ktoré o ňom dostávame. V praxi môže maximálny 'šum' pri vzdialenosti 100m dosiahnuť asi 10m.

    Audio informácie informujú hráča o sluchových vnemoch. Hráč dostane informáciu o čase, kedy správu počul, a o smere, ktorým sa nachádza zdroj. Správu počujú iba hráči, ktorých vzdialenosť od zdroja nepresahuje určitú hodnotu, implicitne 50 metrov. Audio informácia predstavuje jediný povolený spôsob, ktorým sa môžu hráči navzájom dorozumievať. Treba však rátať s tým, že zakričanú správu počujú všetci v danom okolí, teda aj súper.

    Posledným typom informácii sú vnútorné. Na požiadanie informujú hráča o jeho momentálnej kondícii, šírke uhla pohľadu a pod. Hráč teda nemôže neustále bežať plnou silou za loptou, lebo by sa čoskoro unavil.

    Medzi príkazy, ktoré zasiela klient serveru patria turn (otočenie), dash (beh), kick (kopnutie), catch (chytenie lopty, môže použiť iba brankár), say (povedz) a niektoré ďalšie.

  5. Teoretický model hráča
  6. Ako už bolo povedané, server posiela klientom vnemové informácie v pravidelných časových intervaloch, implicitne 150 ms. Simulačný krok (spracovanie správ od klientov a vypočítavanie nových súradníc objektov) je však implicitne 100 ms. V praxi to znamená, že hráč sa musí rozhodovať o tom čo urobí častejšie, ako dostáva informácie o vonkajšom svete. Túto dôležitú skutočnosť musíme pri návrhu teoretického modelu zohľadniť.

    Nášho hráča by sme mohli realizovať dvoma funkciami. Prvá z nich bude mať za úlohu aktualizáciu vnútornej reprezentácie stavu vonkajšieho sveta. Jej volanie musíme zabezpečiť vždy, keď budeme mať k dispozícii nejaké nové informácie, nejaký vnem. V ideálnom prípade sa tak stane každých 150 ms, nesmieme však zabúdať na to, že komunikujeme pomocou UDP/IP protokolu, preto sa môže stať, že sa správa o zmene vonkajšieho sveta (vnem) jednoducho stratí. Zmienená funkcia by mohla vyzerať takto:

    FUNCTION Obnov-vnutornú-reprezentáciu(Aktuálna-vnútorná-reprezentácia,Vnem)

    Returns Nová-vnútorná-reprezentácia

    {

    Nová-vnútorná-reprezentácia = Vypočítaj-novú-vnútornú-reprezentáciu

    (Aktuálna-vnútorná-reprezentácia,Vnem);

    return Nová-vnútorná-reprezentácia;

    }

    Druhá funkcia bude vykonávať samotný výber najvhodnejšej akcie, ktorú hráč vykoná ako reakciu na danú situáciu. Jedná sa teda o “mozog“ hráča. Jej volanie sa vykoná raz za jeden simulačný krok, teda raz za 100 ms. Táto funkcia musí rátať s tým, že informácie, ktoré má k dispozícii o svete, už nie sú aktuálne. Vonkajší svet v skutočnosti vyzerá inak, ale server nám o tom ešte nedal vedieť. Neostáva teda nič iné, iba pokúsiť sa vonkajší svet “dopočítať“, aby sme mali čo možno najpresnejšie informácie, a mohli zodpovedne reagovať.

    FUNCTION Reaguj(Aktuálna-vnútorná-reprezentácia) Returns Akcia

    {

    Aktuálna-vnútorná-reprezentácia = Predpokladaj-novú-vnútornú-reprezentáciu

    (Aktuálna-vnútorná-reprezentácia);

    Akcia = Vyber-najlepšiu-akciu(Aktuálna-vnútorná-reprezentácia);

    return Akcia;

    }

  7. Východisková situácia
  8. V tejto kapitole bude opísaná situácia, v ktorej sa projekt nachádzal v okamihu, keď sme sa s ním začali zaoberať. Hneď od začiatku sme mali k dispozícii tzv. “Soccer monitor”, ktorý nám po pripojení na server dokázal v grafickej forme zobraziť všetky informácie o stave na ihrisku. Údaje posielané monitoru sú absolútne a neskreslené. Zároveň sme mali k dispozícii jednoduchého klienta vyvíjaného študentom Makulom na platforme OS Windows v programovacom jazyku Visual C++. Tento klient dokáže zobrazovať svoju vnútornú reprezentáciu vonkajšieho sveta v grafickej forme. Je postavený na jadre klienta od Klausa Dorera a doplnený o niektoré dôležité funkcie. Poskytuje abstrakciu od spôsobu, akým sú správy doručované serveru. Ďalej boli k dispozícii klienti tímov, ktorý v posledných rokoch dosiahli na medzinárodných súťažiach výrazné úspechy, ako MagmaFreiburg a CMUnited, spolu zo zdrojovými textami.

    Nakoniec sme sa rozhodli, že ako základ nášho budúceho klienta použijeme projekt vyvíjaný priamo na našej fakulte, pretože najlepšie vyhovuje našim kritériám. Zdrojové texty projektov ako MagmaFreiburg a CMUnited nám poslúžili ako zdroj inšpirácie, keďže ide o najdokonalejšie implementácie, aké boli doteraz urobené. Ďalším zdrojom inšpirácie boli záznamy futbalových stretnutí z minulých rokov, v ktorých sa vyskytujú veľmi zaujímavé ukážky stratégie jednotlivých tímov.

  9. Použitá inteligencia hráčov

Skutočnosť, že simulačný krok je menší ako interval, v ktorom server posiela klientom informáciu o stave na ihrisku, značne komplikuje situáciu. Vzhľadom na rozsah tohoto projektu a množstvo času, ktoré máme naň k dispozícii, sme pristúpili ku dohode s členmi konkurenčného tímu a vedúcim tohoto projektu. Konfiguračné súbory serveru sme upravili tak, aby stačilo na situáciu reagovať iba v okamihu, keď server zašle infromáciu o stave vonkajšieho sveta. Takýmto spôsobom sme odstránili nutnosť prepočítavať predpokladaný stav vonkajšieho sveta a tým si čiastočne zjednodušili situáciu. Ďalším zjednudušením je, že hráči sa nemôžu vyčerpať, hrajú teda stále na plný výkon.

Samotná realizácia inteligencie hráča je reprezentovaná troma vrstvami:

  1. Prvá, najnižšia vrsta, je závislá od architektúry komunikačného rozhrania servera – zabezpečuje prijímanie, odosielanie, dekódovanie a vytváranie správ. Nespracuváva údaje, ale poskytuje ich 2. vrstve. Má za úlohu realizáciu elementárnych príkazov typu “utekaj silou 20” odoslaním príslušných správ na server.
  2. Druhá vrstva spracúva údaje so senzorickými informáciami, ktoré získava od prvej vrstvy a vytvára si vnútorný obraz situácie na ihrisku. Jej hlavnou úlohou je určenie pozície samotného hráča na ihrisku a vypočítanie absolútnych súradníc a rýchlostí všetkých videných pohyblivých objektov. V tejto vrstve sú implementované zložitejšie operácie, ktoré sa podľa aktuálnej situácie transformujú na postupnosť príkazov pre prvú vrstvu. Pri vykonávaní týchto operácií je napríklad potrebné zabezpečiť obchádzanie iných hráčov na ihrisku a často treba počítať s relatívnou rýchlosťou lopty. Príkaz pre túto vrstvu môže byť napríklad “utekaj na absolútnu pozíciu X,Y”.
  3. Tretia, najvyššia vrstva realizuje celkovú stratégiu tímu. Na tejto vrstve sa rozhoduje o konkrétnych akciách jednotlivých hráčov a ich pozíciách vo formácii. Určuje hráčovi, kedy má utekať za loptou, kedy je naopak výhodnejšie držať si pozíciu, kedy má ísť hodiť aut a pod. Rozhodovanie by malo vychádzať z ohodnotenia aktuálnej situácie a predpokladanej úspešnosti vykonania akcie druhou vrstvou.

 

Pri implementácii tohoto trojvrstvového modelu sme narazili na niektoré principiálne problémy. Implementačný jazyk Visual C++ je jazykom procedurálnym. Vynára sa však otázka, či je tento problém typicky procedurálnym problémom. Zoberme si následovný príklad – tretia vrstva sa rozhodla, že nastala ideálna situácia pre útok na súperovu bránu. Vydá pokyn “zaútoč na bránu“, ktorý začne druhá vrstva realizovať a posielať prvej vrstve postupnosť príkazov. Medzitým však súperov brankár vybehne, vykopne loptu a súper sa dostáva do útoku. Tretia vrstva vydá pokyn “zaujmite obrannú pozíciu“. Pôvodný povel však ešte nebol dokončený. Dokonca nie je ani žiadúce, aby bol dokončený. Nevystačíme tu teda s predstavou typu “ak ... potom...inak...“. Musíme neustále vyhodnocovať situáciu a podľa nej prispôsobovať plán postupu. A toto nemá s klasickým procedurálnym programovaním veľa spoločného. Možno by pre riešenie takéhoto typu problému poslúžil lepšie tzv. simulátor. Ten by neustále vyhodnocoval naplánované udalosti. Predchádzajúca situácia by teda mohla vyzerať takto: 3. vrstva naplánuje s relatívnym časom 0 (t.j. okamžite) akciu “zaútoč na bránu“. Zároveň však naplánuje ďalšiu udalosť s relatívnym časom 100 ms, a síce “skontroluj oprávnenosť vykonávanej komplexnej akcie“. Počas tých 100 ms by sa vykonal daný príkaz, a potom by prišlo ku prehodnoteniu celej akcie na základe nových informácii. Podľa výsledku by sa rozhodlo, či treba v pôvodnom zámere pokračovať, alebo či radšej vymyslieť nový postup.

Prvá vrstva bola implementovaná už v samotnom základe, na ktorom je náš klient postavený.

    1. Operácie druhej vrstvy
    2. Prvý problém, ktorý bolo treba vyriešiť, bolo vypočítanie absolútnych súradníc objektov nachádzajúcich sa v zornom poli hráča. Absolútna pozícia hráča sa vypočítava podľa priesečníkov kružníc, ktoré majú svoj stred vo vlajkách, ktoré vidíme, a polomer rovný vzdialenosti hráča od danej vlajky (metóda TPerception::Localize()). Inšpirovali sme sa funkciou použitou v klientovi MagmaFreiburg. Kvôli presnosti je nutné vybrať vlajky, ktoré sa nachádzajú čo najďalej od seba (vybrané vlajky, na základe ktorých sa robí lokalizácia zobrazuje klient modrou farbou) – pozícia sa určuje len na základe vlajok, ktoré sa nachádzajú po obvode ihriska. Absolútne súradnice týchto vlajok sú dané, môžeme teda vyrátať absolútne súradnice hráča. Vzdialenosť objektov od hráča takisto poznáme, takže môžeme vyrátať aj ich absolútne pozície. Problém nastáva, keď nevidíme dostatočný počet vlajok na to, aby sme mohli svoju pozíciu určiť. Vtedy nám neostáva nič iné, iba otáčať sa dovtedy, kým uvidíme vlajok dostatok.

      Absolútna rýchlosť objektov sa vypočítava ako rozdiel absolútnych pozícií v aktuálnom a predchádzajúcom simulačnom kroku (metóda TMoveableObject::SetSpeed()). Keďže určenie rýchlosti lopty je veľmi dôležité, venovali sme jej presnému určeniu veľa úsilia. Nakoniec sme museli použiť jednoduchý filter, ktorý ignoruje veľké skokové zmeny v rýchlosti lopty. Experimentovali sme aj s vypočítavaním pozície podľa uhlov ku videným čiaram a podľa vektorov dirchange a distchange, ale tieto metódy sa nám videli nepresnejšie.

      Keď sme dokázali dostatočne presne určiť vektor rýchlosti lopty, rozhodli sme sa implementovať jednu zo základných funkcií druhej vrstvy – určenie najbližšieho miesta, kde sa môže hráč stretnúť s pohybujúcou sa loptou (metóda CBasePlayer::GetBallInterceptPos()). Dosadením rýchlosti lopty do simulačných rovníc, s ktorými počíta server, sa vypočíta predpokladaná poloha lopty na ďalších 20 krokov dopredu a zistí sa, v ktorom kroku najskôr sa do jej blízkosti môže dostať hráč. Určenie miesta stretnutia sa vykonáva vždy, keď sa hráč snaží dostať k lopte. V takom prípade hráč beží do miesta stretnutia namiesto toho, aby bežal priamo k nej. V opačnom prípade by mohlo dôjsť k tomu, že v snahe otočiť sa a bežať za pohybujúcou sa loptou, by sa hráč iba otáčal, aby ju udržal rovno pred sebou. Vďaka tejto funkcii je možné dobehnúť k pohybujúcej sa lopte skôr ako súper, ale prináša to tiež so sebou viacero problémov. V prípade, že sa rýchlosť vypočítava veľmi nepresne, tak pozícia miesta stretnutia môže dosť poskakovať a nie je možné do tohoto bodu utekať. Ďalej bod stretnutia sa môže nachádzať na takom mieste, že keď tým smerom hráč beží, tak bude mať loptu mimo svojho zorného poľa. Tento problém by sa mal riešiť otočením hlavy do smeru lopty a utekaním do miesta stretnutia. Lenže otáčanie hlavou sme neimplementovali, pretože so sebou prináša viaceré komplikácie – je potrebné pozmeniť niektoré vzorce súvisiace napríklad aj s lokalizáciou.

      Jednou z najzákladnejších operácií poskytovaných tretej vrstve je utekanie do konkrétneho miesta na ihrisku (metóda CBasePlayer::RunTo()). Pritom sa kontroluje, či je hráč správne natočený a či mu niekto nestojí v ceste. Obchádzanie hráčov sa realizuje tak, že hráč neuteká priamo do zadaného miesta, ale odkloní sa o vypočítaný uhol. Tento uhol sa určí ako najmenší uhol, o ktorý je nutné sa odchýliť od priameho smeru, tak aby sa obišli všetci hráči stojaci v ceste. Obchádza sa buď zľava alebo sprava podľa toho, z ktorej strany je hodnota tohto uhla menšia. Keď je určený smer, ktorým sa má utekať, tak sa zistí, či je hráč správne natočený. Ak je cieľový bod ďalej, tak je dovolená len malá odchýlka od správneho smeru (-8, +8) stupňov. V prípade, že je už blízko, tak môže byť tolerancia aj väčšia, ak zabezpečí, že hráč sa vzdiali od daného miesta maximálne o 1 (meter). Implementovaná funkcia tiež umožňuje utekanie smerom dozadu (cúvanie), ak sa výsledný smer nachádza v intervale (150, 210) stupňov.

      Funkcie realizujúce kopnutie lopty do zadaného smeru museli zabezpečiť, aby hráč nikdy nekopol loptu tak, žeby jej sám stál v ceste (metóda CBasePlayer::KickTo()). V takomto prípade si hráč najprv otočí loptu okolo seba v tesnej blízkosti, a keď ju má už v správnom smere, tak potom vystrelí. Funkciu realizujúcu otáčanie lopty (metóda CBasePlayer::TurnBallTo()) sme plánovali použiť aj na zabránenie súperovi v tom, aby dokázal zobrať loptu našemu hráčovi (takýto trik používajú aj klienti CMUnited). Avšak implementovať túto funkciu sa nám nepodarilo, pretože bez otáčania hlavy bolo ťažké sledovať súpera a dostatočne rýchlo reagovať na jeho pohyb. Napriek tomu sme úspešne implementovali funkciu realizujúcu kopnutie, ktoré počíta s aktuálnou rýchlosťou lopty a vypočíta smer i silu kopu tak, aby bola dosiahnutá požadovaná výsledná rýchlosť (metóda CBasePlayer::KickRel0()). Vďaka tejto funkcii dokážu naši klienti otáčať loptu v najvýhodnejšej vzdialenosti vo svojej tesnej blízkosti.

    3. Algoritmus útočníkov a obrancov
    4. Na turnaji používal náš tím okrem brankára dva typy hráčov. Štyroch hráčov so zadanou pozíciou vo formácií a jedného voľného hráča.

      1. Hráč so zadanou pozíciou
      2. Tento typ hráča má určenú pozíciu v blízkosti ktorej sa zdržiava, keď lopta nie je v jeho blízkosti. Pozícia hráča je určená jeho číslom. Každý hráč má zadefinované dva body. Aktuálna pozícia je medzi týmito bodmi lineárne interpolovaná podľa x-ovej súradnice lopty. Ak sa lopta nachádza bližšie k súperovej bránke, hráč sa presúva k prvému bodu, ak je lopta na našej polovici, hráč sa presunie k druhému bodu. Tento algoritmus umožňuje dynamickú zmenu formácie podľa fázy hry. Ak náš tím útočí, obrancovia sa môžu posunúť bližšie k stredu ihriska, aby mohli rýchlejšie zachytiť vykopnutú loptu, ak sa bránime, formácia sa môže stiahnuť smerom k našej bránke. V zohratom zápase však boli oba body nastavené na to isté miesto a hráči nemenili svoju pozíciu podľa pozície lopty. Obrázok ukazuje formáciu použitú počas zápasu.

         

         

        Hráč musí po prijatí vizuálnej informácie rozhodnúť akú činnosť vykoná v daný simulačný krok. Rozhoduje sa na základe prijatej vizuálnej informácie a stavu v ktorom sa nachádza. Informácia o stave hráča je uchovávaná v statických premenných. Najdôležitejšia stavová premenná hovorí, či sa hráč práve vracia na svoju pozíciu. Zjednodušený algoritmus hráča sa nachádza na obrázku.

        Ak hráč vidí loptu, rozhodne sa či je za ňu zodpovedný. Ak áno, rozbehne sa k nej a pokúsi sa ju kopnúť smerom ku súperovej bráne. Ak hráč nie je zodpovedný za loptu, vracia sa na svoju pozíciu. Hráč môže bežať späť na pozíciu a nevidieť loptu iba 8 ťahov. Potom sa znovu musí pozrieť na loptu, aby mohol prehodnotiť situáciu – zistiť či opäť nie je za ňu zodpovedný.

        Keď sa akcia “Pozri sa na loptu“ vykoná prvý krát po nejakej inej akcii, hráč sa najprv pozrie na poslednú známu pozíciu lopty. Ak ju tam neuvidí, tak sa v ďalších ťahoch začne otáčať a hľadať loptu.

      3. Zodpovednosť za loptu
      4. Pri určovaní zodpovednosti za loptu, hráč najprv vypočíta vzdialenosti všetkých hráčov (vlastných a súperových) od lopty. Hráč môže byť zodpovedný za loptu v dvoch prípadoch:

        a) tento hráč je z nášho tímu najbližšie k lopte,

        b) ak sú splnené dve nasledujúce podmienky:

        1. vzdialenosť medzi týmto hráčom, a hráčom nášho tímu, ktorý je najbližšie k lopte, je väčšia ako vzdialenosť tohoto hráča od lopty

        2. najbližšie k lopte je súperov hráč.

        Za loptu môžu byť súčastne zodpovedný dvaja hráči. Pravidlo b) dáva zodpovednosť za loptu hráčovi, ktorý má možnosť “obrať“ súpera o loptu spredu. Čo to znamená ukazujú nasledujúce obrázky.

        Za loptu je zodpovedný iba hráč 2, pretože je k nej najbližšie (pravidlo a)).

        Za loptu sú zodpovedný obaja hráči. Hráč 2 je najbližšie k lopte (pravidlo a)). Hráč 1 nemá prístup k lopte blokovaný súperom, a preto má väčšiu šancu zobrať mu loptu (pravidlo b)).

      5. Voľný hráč

      Voľný hráč nemá zadefinovanú svoju pozíciu a používa jednoduchší algoritmus.

      Funkcia “Najdi optimalny uhol“ vypočíta uhol, ktorý dáva lopte najväčšiu šancu dostať sa do bránky. Hráč najprv zistí uhly, pod ktorými sa nachádzajú okraje bránky. Potom vyhľadá všetkých hráčov, ktorí sa nachádzajú v tomto intervale a nájde medzi nimi (a okrajmi bránky) najväčšiu medzeru. Optimálny uhol smeruje do stredu tejto medzery.

    5. Algoritmus brankára

Stratégia brankára sa riadi niekoľkými jednoduchými pravidlami. Brankár si udržuje pozíciu v priesečníku úsečky a kružnice. Koncové body úsečky sú určené stredom brány a aktuálnou pozíciou lopty (bez predvídania). Kružnica má svoj stred v strede brány a polomer rovný polovici veľkosti brány. Situáciu zobrazuje obrázok:

Legenda: S – stred brány, P – pozícia brankára, L – aktuálna pozícia lopty (nie predvídaná)

V prípade, že brankár nevidí loptu, pozrie sa smerom, kde bola videná naposledy. Ak sa ani potom lopta nenachádza v jeho zornom uhle, natočí sa do pozície –70 stupňov (t.j. približne do pravého dolného rohu ihriska, ak chytá v ľavej bránke) a začne sa otáčať o uhol veľkosti 30 stupňov, až kým sa mu nepodarí loptu nájsť. Ak sa lopta nachádza v bránkovom pásme (ktorý je vyhradený obdĺžnikom o niečo menším ako “šestnástka”), a zároveň sa pohybuje smerom ku bráne, brankár vybehne. V prípade, že je možné loptu chytiť (nachádza sa v obdĺžniku okolo brankára, jeho strany sú špecifikované v konfiguračnom súbore servera, implicitne 2x1), brankár sa o to pokúsi. Po úspešnom zásahu (mód hry sa zmení na M_FREE_KICK_L, resp. M_FREE_KICK_R) sa brankár snaží nahrať loptu najbližšiemu spoluhráčovi. Otáča sa v rozmedzí absolútnych uhlov –70 až +70 stupňov s krokom 30. Pri prvom prechode (t.j. pri prvom natáčaní sa z pozície –70 stupňov na pozíciu +70 stupňov) nahrá loptu spoluhráčovi v prípade, že sa nachádza vo vzdialenosti menšej ako 10. Pri ďalších prechodoch sa minimálna vzdialenosť postupne zvyšuje na 15, 20, 25 a nakoniec opäť 25. Ak sa ani po piatom prechode nenašiel vhodný kandidát na nahrávku, lopta je vykopnutá smerom ku bráne súpera a brankár sa vráti späť na svoju pozíciu (spomínaný priesečník priamky a polkružnice). Uvedený algoritmus implementuje metóda AutoPlay3 triedy CBasePlayer, ktorá je uložená v zdrojovom súbore BaseAgent.cpp.

Pri testovaní brankára nebola venovaná dostatočná pozornosť jeho správnej funkčnosti na oboch stranách ihriska. Až počas záverečného verejného zápasu sme prišli na to, že na pravej strane (pri hre za červených) sa nespráva korektne. Výsledkom je, že výkon brankára je na pravej strane výrazne slabší. Veľmi dobre je to vidieť, ak postavíme proti sebe na hraciu plochu dva rovnaké tímy (rovnaký počet hráčov s rovnakými úlohami). Motkovia na ľavej strane vďaka brankárovi jednoznačne vyhrajú.

  1. Záverečné zhodnotenie
  2. Myšlienku realizácie tohoto projektu v rámci predmetu Umelá inteligencia hodnotíme veľmi pozitívne. Študenti majú jedinečnú príležitosť venovať sa problémom umelej inteligencie zaujímavou formou a v neposlednom rade vyskúšať si tímovú spoluprácu. Táto kapitola obsahuje niektoré postrehy a návrhy, ktoré by mohli dopomôcť k ďalšiemu rozvoju tohoto zaujímavého spôsobu vypracovávania zadaní v rámci predmetu Umelá inteligencia.

    Ako už bolo povedané v kapitole 5 (Použitá inteligencia hráčov), inteligencia hráčov je realizovaná prostredníctvom troch vrstiev. Najbližšie ku problémom umelej inteligencie má tretia vrstva, ktorá ma na starosti stratégiu celého tímu. Na tejto vrstve by sa dalo uvažovať napr. o prehľadávaní stavového priestoru a podobných algoritmoch. S poľutovaním musíme konštatovať, že vzhľadom na časovú obmedzenosť tohoto projektu sme sa k tejto časti dostali len minimálne. Význam tretej vrstvy vystupuje do popredia až po uspokojivej implementácii prvých dvoch vrstiev (je zbytočné určovať stratégiu tímu, ak nie sme schopný súperovi vziať loptu, čo má na starosti druhá vrstva). Preto by bolo veľmi užitočné, keby boli prvé dve vrstvy uspokojivo implementované, aby sa budúce tímy mohli venovať samotným problémom umelej inteligencie. Mali by obsahovať minimálne lokalizáciu hráča na ihrisku a komplexnú funkciu RunTo s obchádzaním prekážok a otáčaním hlavy tak, aby bola lopta v zornom uhle hráča. Napriek tomu, že dnes už máme relatívne presnú predstavu o spôsobe, akým by tieto veci mali fungovať, v rámci tejto práce nebola úloha uspokojivej implementácie prvých dvoch vrstiev splnená. Môžeme hovoriť iba o akomsi “prototype na zahodenie”. Postavenie opisovaného uspokojivého “základu” považujeme za najbližší cieľ.

  3. Možné rozšírenia do budúcnosti
  4. Do druhej vrstvy by bolo vhodné implementovať niektoré akcie, ktoré možno odpozorovať od skúsenejších tímov a ktoré podľa nášho názoru poskytujú veľkú výhodu. Ako príklad môže poslúžiť CMUnited, ktorý má špeciálne preddefinované hádzanie autu. Kým všetci jeho protihráči v čase hádzania nečinne postávajú, CMUnited zaujme špeciálnu pozíciu. Hráč sa vždy pokúsi nahrať svojmu spoluhráčovi, ktorý stojí na dohodnutom mieste (v relatívnych súradniciach vždy tom istom), ten nahrá ďalšiemu hráčovi pred bránou a ten vystrelí na bránu. Podľa našich štatistík asi 1/3 gólov CMUnited padne vďaka tejto stratégii.

     

  5. Použitá literatúra

· Makula, M. - Kucbel, M. - Mateffy, R. RoboCup. http://www.fornax.sk/soccer (1.6.2000). (c) 1999/2000

· Stone, P. Peter’s homepage. http://www.research.att.com/~pstone/ (1.6.2000). spoluautor implementácie klienta CMUnited.