Autonóm robotok kooperatív irányítása stratégiai célok megvalósításához Szerző: Albrecht Domonoks Konzulens: Dr. Harmati István
Feladat ismertetése: Egy meglévő szimulációs környezetben, csapat stratégiát fejleszteni, a cél eléréséhez. Jelen esetben az egységekkel (tankok) elfoglalni és biztosítani egy bázispontot.
Szimulátor: A szimulátort Szarka Lajos és Kisfaludi Péter hozta létre, amit később módosítottak. A jelenlegi verziót (Art of War 3.0) utoljára Tóth János módosította, én ezzel a verzióval dolgoztam. „A szimulátor azzal a céllal íródott, hogy képes legyen egy adott környezetben különböző kooperatív csapatstratégiák egymással szembeni tesztelésére, és a csapatszintű döntések megfigyelésére és nyomon követésére a további fejlesztések érdekében.”
Szabályok: Egy négyzetrácsos térképen (rácspontokon), helyezkednek el egységek, akadályok bázispontok és szabad mezők. Az akadályokra és bázispontokra nem léphet egység. Illetve két egység nem lehet egy azon mezőn. Az egységek egy alap beállításnak megfelelő mennyiségű élettel és lőszerrel indulnak, véletlenszerű pozícióból. Az egységek lőhetnek egymásra, ilyenkor fogy a lőszer, és ha talált, akkor csökken az ellenfél élete. Ha egy egység kifogyott a lőszerből, akkor azt a saját bázispontnál újra töltheti. Ha az élete fogyott el, akkor megsemmisül a tank és lekerül a játéktérről.
A kapott szimulátor
A játék menete: A játék körökre van osztva. Minden körben minden egységhez ki kell adni egy parancsot (fordul, lő,stb...) ami a kör végén végrehajtásra kerül. Két csapat versenyzik a bázis pontok birtoklásáért. Egy pontot úgy lehet elfoglalni, hogy egy egység mellé áll. Ha elfoglalta az egyik csapat a pontot, akkor az egészen addig az övé lesz, amíg a másik csaptat el nem foglalja, tehát nem kell folyamatosan a pont mellett állomásoztatni egységet. Amennyiben két csapat egysége is a pont mellett helyezkedik el, felváltva birtokolják azt, vagyis egyik körben az egyiké, a másik körben a másiké. Minden kör végén a birtokolt bázispontoknak megfelelően, pontot kapnak a csapatok. Akkor van vége a játéknak, ha az egyik csapat eléri a győzelemhez szükséges pont mennyiséget, vagy ha az egyik csapat összes tankja megsemmisül.
Változtatások a szimulátoron: Stratégiafejlesztéshez lecsökkentettem a pálya méretét. 15x24-es helyett csak 6x7-es pályán dolgoztam. Ennek megfelelően a tankok számát az akadályok és a bázis pontok számát is csökkentettem. Továbbá az akadályok és bázispont helyzetét rögzítettem, a tesztelhetőség érdekében. A pálya módosítását a platform_template.m file megfelelő módosításával könnyen megvalósítható.
A változtatások után
A módosítások viszont problémákat vetettek fel, ugyanis sok helyen a pálya méretére, és a tankok számára, nem egy változóval hivatkoztak, hanem konstans, számmal beírt, értéknek vette.
Az eredetileg 10-10 egységet egy DB nevű változóval helyettesítettem.
Ezen felül az egységek véletlenszerű elhelyezése nem működött, mert egymásra rakta az egységeket. Ezt is javítottam. A probléma az volt, hogy vizsgálta, hogy az adott mező, amire le akarja rakni, üres mező, de ha üres mezőt talált, beállította hogy arra a mezőre rakja le az egységet, de ténylegesen nem rakta le. Csak később az egységek elhelyezése után egyszerre írta be a megfelelő helyre. Így egy mezőt többször is megtalált és egymásra rakta az egységeket.
TR mátrixban a harmadik oszlop jelöli az adott mezőhöz, hogy foglalt-e. Ha 0 az értéke akkor az adott mező szabad.
Úgy módosítottam, hogy egy segéd mátrixban, jelöltem, hogy az adott mezőre, lehelyezett-e már egységet.
Stratégia: Ha az ember ránéz egy állásra (a szimulátoron, vagy akár máshol is), nagyjából el tudja dönteni, hogy mik lehetnek a fontos pontok az adott szituációban. Persze nem mindig tudja pontosan, de nagyjából eltalálja. Ilyenkor olyan szempontokra figyel, hogy az adott pont mennyire biztonságos (közel van az ellenség vagy a csapattárs), milyen hatása van a környezetre (támad vagy védekezik) és ezek alapján ki tudja választani. Ez a gondolatmenetet próbáltam megfogalmazni úgy, hogy azt egy program végre tudja hajtani. Tehát minden mezőhöz rendeltem egy számértéket. Ilyenkor figyelembe vettem a bázisponttól való távolságát, hogy ellenség vagy saját egység áll-e az adott mezőn, és hogy épp ki birtokolja a bázist. Ezek után csak ki kell választani, és megszerezni a legmagasabb értékű (legfontosabb) mezőket.
A stratégia megvalósítása: Mezők értékének meghatározása: Távolság alapján: Ehhez szükséges ismerni minden mezőről, hogy milyen messze van a bázispontoktól. Ezt egy "terülő" algoritmussal határoztam meg (distance(...) függvény). Kezdő pont(ok)ból az első körben a szomszédos mezőkbe jut el. A következő körben a szomszédok szomszédjaiba, stb... Először felveszi az összes mezőt, egy "nem megtalált" tömbbe, ahonnan magát rögtön ki is veszi. Megkeresi a kiinduló mező szomszédjait. Ezekhez hozzá rendeli, hogy hányadik körben találta meg, majd kiveszi a "nem megtalált" tömbből, és átrakja egy "most megtalált" tömbbe. Növel egyet a körök számán és a "most megtalált" tömb elemeivel megint lefut. Ez egészen addig fut, amíg van elem a "nem megtalált" tömbben. Persze minket az érdekel, hogy hány mező távolságra van az adott pont, de az akadályokon nem tudunk átmenni, így ha az algoritmus megtalál egy akadályt, a távolságát "-1"-re állítja, ezzel jelzi, hogy akadályt talált, és ezt a mezőt, nem rakja be a "most megtalált tömbbe", hogy innen ne folytatódjon a keresés. Ez problémát is okozhat, ha véletlen az akadályok elhelyezése és körbezárják a bázist, akkor nem tudja bejárni, az összes mezőt, így végtelen ciklusba kerül. Ha megvan a távolság, akkor a mező értéke a következő: ert=max(tav)+1-mezotav. Tehát a legtávolabbi mező értéke lesz 1, vagyis a legkevésbé fontos. Ez egy alap érték, ami pályafüggő, de egy játék során nem változik.
A terülő algoritmus működése
További módosító hatások: Ha miénk a bázis, akkor a bázis körüli mezők értékét csökkentem, ha pedig az ellenségé, akkor növelem. Ezen felül, annak a mezőnek, amin ellenség van, szintén növekszik az értéke. Így meg lehet állapítani, hogy ha az ellenség foglalja a bázist, melyik mezőn kell keresni.
Cél kiválasztása: Egyszerűen egy ciklussal végig megy mezőkön, és kiválasztja, az "n" legnagyobb értékkel rendelkező mezőt (ahol "n" a saját egységeink számát jelöli). Ezután csökkenő sorba rendezem a cél mezőket.
Cél mezőkhöz az egységek hozzárendelése: Minden célmezőhöz megpróbáljuk a legközelebb lévő egységet hozzárendelni. Ehhez szintén ismerni kell a távolságokat, így minden célmezőre egy ciklus segítségével sorban meghívjuk, a "terülő" algoritmust, azzal a módosítással, hogy a kiinduló pont (cél) értéke 0 legyen, és addig fut, amíg az összes egységhez meg nem állapítja a távolságot. Az összes többi mező értéke „-1”. Ezt később annyiban módosítottam, hogy ha egy olyan mező a cél, ahol egy ellenség van, akkor oda lehetőleg, egy olyan egységink induljon el, amelyiknek még van lőszere.
Útvonaltervezés: Ehhez a cél kiválasztásakor kiszámolt eredményeket használtam fel. A terülő algoritmus végén minden mezőhöz, ami a cél és az egység között van, hozzá van rendelve a távolság. Így útvonaltervezésnél, ha mindig kisebb távolságra lévő mezőkre lépünk, eljutunk a célhoz, vagyis a „0”-ás mezőhöz. Ehhez szükséges, hogy a nem bejárt mezők ne 0 értéket kapjanak. Ezt az „utazo” függvény annyiban egészíti ki, hogy először mindig előre fele próbál menni, ha az nincs közelebb, akkor vizsgálja a szomszédos mezőket. Így a lehető legkevesebb fordulással eljut a célig, tehát így a leggyorsabb. A függvény mindig az aktuális paranccsal tér vissza, ami a következő mező eléréséhez kell.
A tényleges parancs kiadása: A tényleges parancsok kiadása úgy történik, hogy az összes egységnek a várakozás kódját állítom be alapértelmezett parancsként, mert a szimulátornak mindenképp szüksége van az összes egységhez egy parancsra, amit utána kiértékel és végrehajt, ha nincs semmi korlátozó tényező. Ezek után végignézzük az összes egységet, és ha tudunk, kiadunk valami értelmes parancsot. Például ha az adott egységnek elfogyott az élete, nem tud más parancsot hozzárendelni, mint a „vár”. Ha van ellenség az adott tank előtt, és még van lőszere, akkor rálő. Ha ezek az eseteket megvizsgálta, és még nem rendelt az egységhez egy értelmes parancsot, akkor meghívja az útkereső funkciót, majd annak a visszatérési értékét adja át parancsként a szimulátornak. Ha elakadt az egység, vagy elérte a célját, meghívja az „őrködés” funkciót, ami figyeli, hogy valamelyik irányból jön-e ellenség.
Működés:
Ez a demó, azt mutatja be, hogy ha az ellenség foglalja a bázist, akkor megtalálja és a lehető legrövidebb úton kiiktatja a foglaló egységet.
Egy tényleges játék lefutása: A sárga csapat az általam fejlesztett stratégia szerint cselekszik, a piros csapat véletlen szerűen kapja az utasításokat.
Kiinduló helyzet.
Azok az egységek, amik előtt volt ellenség, megpróbáltak rálőni az ellenségre. Itt látszik, hogy az egyiknek sikerült egyből megsemmisíteni a célt (vízszintes lövés), a másik csak sebezte az ellenséget (függőleges lövés).
A játék során kezd felül kerekedni a sárga csapat.
Látszik, hogy az egységek csoportosulnak a bázispont körül és az ellenséges egységeket megpróbálják kiiktatni. Egy másik játék során: Megfigyelhető, hogy ha már elérték a kívánt pozíciót, akkor figyelik, a közeledő ellenséget, és ennek megfelelően fordulnak és lőnek.
A bázisnál lévő egység, ami mellett ellenség van, a következő körben oda fog fordulni.
Idő közben elment az ellenség, így a másik egységgel került egy vonalba. Így az is oda fog fordulni.
Mire ráfordult az ellenségre, azt megsemmisítették, ilyenkor várakozik, mert a megfelelő helyen van, de nincs kiadható parancsa.
A türelem meghozta gyümölcsét, mert lőtávolba került az ellenség és rá tudott lőni.
Tapasztalatok: A stratégiám az egyszerű (buta) stratégiákat kb 90%-ban legyőzi, ami mutatja, hogy van mit finomítani rajta. Olyan esetben tud nyerni a buta stratégia, amikor „beszorulnak” az egységeim. Ilyenkor vagy saját csapattárs gátolja az egységet a mozgásban, vagy elfogyott a lőszere, és nem tudja kilőni az ellenséget, ami blokkolja.
Ezen a két képen látható, hogy a megjelölt egység, nem tud tovább haladni, mert blokkolja az ellenség. Kilőni sem tudja mert elfogyott a lőszere (ez most így nem látszik a képen). Fejlettebb, hallgatók írta stratégiák ellen nem sikerült letesztelni, a stratégiámat. Ennek oka, hogy sok helyen szintén nem változóként hivatkoztak a pálya méretére vagy az egységek számára, hanem „bedrótozott” konstans értékkel számoltak. Így az általam létrehozott kicsinyített pályán nem működtek. Az általam írt stratégia elvileg mindent paraméteresen tartalmaz, viszont a terülő algoritmus miatt túl sok számítást kéne elvégezni egy nagyobb pályán, ezt az otthoni számítógépem nem tudja végrehajtani.
Következtetés: Túl nagy számítási igénye lett a stratégiának. Ezek helyett, valami hatékonyabb útkeresést kell megvalósítani, ha nagyobb pályán is használni szeretnénk a stratégiát. Az elakadó egységek lényegében kiesnek egy időre a játékból.
Fejlesztési lehetőségek: Hatékonyabb útkeresési algoritmust kéne implementálni és figyelni, hogy az út során ne kerüljön veszélybe az egység. A mezők értéke meghatározásakor további szempontokat figyelembe venni, mint például melyik mezőket lehet biztosítani az adott mezőről, és az egységek helyzetének figyelembe vétele. Az elakadó egységek segítséget kérhetnek egy adott mezőre. Ezeket a kéréseket figyelembe venni a cél meghatározásakor. Illetve összehangolt támadás indítására felhasználni. Predikciót beépíteni a stratégiába, támadás/védésnél és az érték meghatározásánál.
A szimulátort annyiban lehetne fejleszteni, hogy a megsemmisült egységek roncsként akadállyá válnak. Ez tovább bonyolítaná a rendszert, de sokkal valóságosabb lenne a rendszer. Illetve lehetne elhelyezni fedezékeket, ahonnan kilőni könnyen lehet, viszont a fedezék mögötti tankot sokkal nehezebb eltalálni.
