1.
FELADAT.....................................................................................................................3 1.1. FELADATKITŰZÉS: ...................................................................................................3 1.2. PONTOSÍTÁS ............................................................................................................3 1.2.1. Térkép:............................................................................................................3 1.2.2. Alkalmazott mesterséges intelligencia algoritmusok ........................................3 1.3. ALRENDSZERDIAGRAM.............................................................................................3
2.
OSZTÁLYOK...............................................................................................................4 2.1. GUI ALRENDSZER(GYURI) .......................................................................................4 2.1.1. Osztálydiagram ...............................................................................................4 2.1.2. MainForm osztály ...........................................................................................5 2.1.3. GraphicPanel osztály ......................................................................................6 2.2. STATE ALRENDSZER .................................................................................................6 2.2.1. Osztálydiagram ...............................................................................................6 2.2.2. State osztály ....................................................................................................7 2.2.3. Car osztály ......................................................................................................7 2.3. CONTROLLER ALRENDSZER ......................................................................................8 2.3.1. Osztálydiagram ...................................................................................................8 2.3.2. Statistics osztály ..............................................................................................8 2.3.3. Parameters osztály ..........................................................................................8 2.3.4. Map osztály .....................................................................................................9 2.3.5. Field osztály ....................................................................................................9 2.4. AI ALRENDSZER .....................................................................................................10 2.4.1. Osztálydiagram .................................................................................................10 2.4.2. IDriver interfész ............................................................................................10 2.4.3. HumanDriver osztály.....................................................................................10 2.4.4. UniversalNeuralDriver osztály(Gyuri) ..........................................................11 2.4.5. SpecializedNeuralDriver osztály....................................................................11 2.4.6. RuleBasedDriver osztály ...............................................................................11 2.4.7. CrossEntropy osztály.....................................................................................11
3.
ALGORITMUSOK ....................................................................................................12 3.1. LÁTÁS ...................................................................................................................12 3.2. UNIVERZÁLIS VEZETŐ ............................................................................................12 3.2.1. Vezetés ..........................................................................................................12 3.2.2. Tanulás .........................................................................................................12 3.3. HIBRID VEZETŐ ......................................................................................................13 3.3.1. Vezetés ..........................................................................................................13 3.3.2. Tanulás .........................................................................................................13 3.4. SZABÁLYALAPÚ VEZETŐ ........................................................................................13 3.4.1. Vezetés ..........................................................................................................13 3.4.2. Tanulás .........................................................................................................13
4.
KEZELŐFELÜLET ...................................................................................................13
5.
PROJEKTTERV ........................................................................................................14 5.1. 5.2.
MUNKAMEGOSZTÁS ...............................................................................................14 HATÁRIDŐK ...........................................................................................................14
1. Feladat A cél egy tanulást támogató szimulációs rendszer és tanuló algoritmusok implementálása.
1.1. Feladatkitűzés: • Adott egy négyzethálós térkép, amin az egyik pontból el kell jutni egy másik pontba. A térkép minden négyzetéhez tartozik egy “járhatóság” érték. Ezen a térképen kell elvezetnie egy algoritmusnak egy járművet, úgy, hogy minél jobban az úton maradjon. • Javasolt MI módszerek: genetikus algoritmusok, neurális hálók. • Elkészítendő: moduláris felépítéssel GUI-s térkép generáló rész, jármű “kinematika” (kézzel vezetés), vezető algoritmus, vezetés megjelenítés.
1.2. Pontosítás 1.2.1.
Térkép:
Külön térképszerkesztő alkalmazás nem készül, Microsoft Windows Bitmap állományokból generálunk térképeket. Kitüntetett pontok a start és a cél.
1.2.2.
Alkalmazott mesterséges intelligencia algoritmusok
A tanulást három különböző algoritmussal is megvalósítjuk, így lehetőség nyílik a hatékonyságok összehasonlítására. Implementálunk egy tisztán neurális felépítésű ágenst, egy specializált neurális ágenst és egy szabály alapú következtetést használót.
1.3. Alrendszerdiagram
2. Osztályok 2.1. GUI alrendszer 2.1.1.
Osztálydiagram
2.1.2.
MainForm osztály
Az osztály egyetlen objektuma a program vezérlését és megjelenítési műveleteit végzi. class MainForm { private GraphiPanel myGraphicPanel; private State myState; private Driver myDriver; private Parameters myParameters; //vezető választását segítő objektumok private ListViewItem driverSelector; private Button driverSelectedButton; //főmenu private MenuBar MainMenu; //térkép betöltés, választás objektumai private Panel mapSelectionPanel; private Button mapSelectedButton; //statisztika fileba mentését segítő objektumok private ListViewItem StatListView; private Button statToFileButton; //a MI vezető indításá megállításához tartozó objektumok private Button startPauseButton; private Button stopButton; //a térkép frissítésere szolgáló fgv public void GraphRefresh(Pos carPos, Angle carAngle); //statisztika karbantartása public void StatRefresh(StatType s); //jelzés a programnak, felhasználónak, hogy az autó célba ért public void SetEnd(); //Inicialzáló fgvek public void InitDriverSelection(); public void InitMap(Map m); //futás alatt a nem szükséges formok letiltása public void SetAllFormState(bool l); //statisztika mentésa szöveges fájlba public void StatToFile(); }
2.1.3.
GraphicPanel osztály
A térkép és a járműgrafikus 2 dimenziós megjelenítéséért felelős osztály. class GraphicPanel { private Panel myGraphicPanel; private Map myMap private myCarModel //térkép frissítése public void RefreshMap(Pos carPos, Angel carAngle); //térkép betöltése a képernyőre public void setMap(Map myMap); //a grafikus megjelenítés alaphelyzetbe állítása public void ClearPanel(); //a panelre a térkép betöltése private void DrawMap(); //a jármű grafikájának betöltése private void DrawCar(); }
2.2. State alrendszer 2.2.1.
Osztálydiagram
2.2.2.
State osztály
Az osztály feladata: a játék állapotának tárolása, illetve a fizikai szimuláció végrehajtása. static class State { private Pair carPosition; // az autó koordinátái (m) private Pair carVelocity; // az autó sebességvektora (m/ms) private double carOrientation; // az autó orientációja (fok) private double throttle; // gáz- illetve fékállás (-100.0 .. +100.0) private double wheel; // kormányállás (-100.0 .. +100.0) public Pair CarPosition { get{ return carPosition; } } public double CarOrientation { get{ return carOrientation; } } public double Throttle { get{ return throttle; } set{ throttle=value; } } public double Wheel { get{ return wheel; } set{ wheel = value; } } public double CarSpeed { get{ return carVelocity.Abs()*3600.0; } } public void Simulate(double millisec); // a fizikai szimuláció elvégzése public void Reset(); // visszaállítás kezdőállapotba }
2.2.3.
Car osztály
Az autó fizikai jellemzőit, viselkedését tartalmazó osztály. class Car { public Pair<double> wheelNumber); // public Pair<double> // }
WheelPosition(double orientation, int egy adott kerék pozícióját adja meg Force(double throttle, double wheel); az autó által kifejtett erőt adja meg
2.3. Controller alrendszer 2.3.1.
Osztálydiagram
2.3.2.
Statistics osztály
A tanulás különböző fázisaiban mért köridők tárolására, lekérdezésére szolgál. Az ágensek slotokat igényelhetnek, melyekre később a köridőket küldhetik. A MainForm megfelelő metódusa képes grafikonok megjelenítésére, amivel elemezni lehet az ágensek fejlődését. public static class Statistics { public void RequireSlot(IDriver owner) // slot igénylése public void SendLapTime(IDriver sender, double lapTime) // köridő felvétele a listába public List<double> LapTimes(IDriver) // rögzített köridők lekérése private Dictionary
> storedData; // a slotot igényelt Idriverekhez köridők tárolása }
2.3.3.
Parameters osztály
Az osztály a konstansok file-ból való betöltésére, tárolására és lekérdezésére szolgál. Az univerzalitás miatt nem típusbiztos, a megfelelő konverziókat a felhasználás helyén kell végrehajtani. public static class Parameters { public void LoadFromFile(String path) // a paraméterek betöltése a megadott file-ból public Object GetParameter(String key); // paraméter lekérdezése private Dictionary<String,Object> parameters; // paraméterek }
2.3.4.
Map osztály
A map osztály kezeli a térképet. Gyakorlatilag egy számokból álló mátrix, melyben a számok egy-egy talajtípust jelentenek. Ezt a hozzárendelést egy Field típusú elemekből álló vektor hozza létre. class Map { public int[,] fields; public int mapSize; public Pair startPos; public Pair finishPos; public double finishRadius; }
2.3.5.
Field osztály
A talaj tulajdonságai összefüggenek, például az aszfaltos talaj nagy tapadást biztosít, viszonylag kis surlódást, magas sebességet. struct Field { public Color color; public double grip; public double friction; public double maxSpeed; public double penalty; // „büntetőpont”: }
// // // //
térképen megjelenő szín tapadás surlódás elérhető legnagyobb sebesség
mennyire „jó”, hogy ott haladunk
2.4. AI alrendszer 2.4.1.
Osztálydiagram
2.4.2.
IDriver interfész
Univerzális interfész a különböző tanuló ágensek implementációihoz. interface IDriver { void Init(); // kezdetekor inicializálás Pair<double> Think(); // következő lépés számítása, output: gáz és kormányállás }
2.4.3.
HumanDriver osztály
Az osztályobjektmának feladata, hogy a Mainformtól kapott inputot, a megfelelően lekezelje, és a State alrendszer objektumait a megfelelő állapotba állítsa. class HumanDriver { public void InputHandler(char s); private … }
2.4.4.
UniversalNeuralDriver osztály
class UniversalNeuralDriver: IDriver { public void Init(); // kezdetekor inicializálás public Pair<double> Think(); // következő lépés számítása, output: gáz és kormányállás private Matrix W; // neurális hálózat súlyozásai }
2.4.5.
SpecializedNeuralDriver osztály
class SpecializedNeuralDriver: IDriver { public void Init(); // kezdetekor inicializálás public Pair<double> Think(); // következő lépés számítása, output: gáz és kormányállás private Matrix W; // neurális hálózat súlyozásai }
2.4.6.
RuleBasedDriver osztály
A szabályalapú következtetést használó ágens. class RuleBasedDriver: IDriver { private Vector wheelParam; // a kormánykezelést megszabó paraméterek private Vector throttleParam; // a gázadást és fékezést megszabó paraméterek public void Init(); public Pair Think(); }
2.4.7.
CrossEntropy osztály
Az evolúciós algoritmust irányító osztály. class CrossEntropy { private RuleBasedDriver[] agents; private int agentsNum;
// a populáció ágensei // ágensek száma
public void Learn(); // a tanulási folyamat elindítása public EvolAgent GetBestAgent(); // az előállított legügyesebb ágens }
3. Algoritmusok 3.1. Látás A látás algoritmusa a specializált neurális és a szabály alapú ágens által használt metódus: a térképtől kapott mátrixot transzformálja. A térkép elküldi azt a részletét, amit éppen a vezető lát, viszont egy nekünk túl sok információ (lásd: Field). Ahogy az ember is értelmezi a látott kép alapján, hogy hol van az ideális út, és milyen ívet ír le, így a motiváció, hogy egy hasonló algoritmussal segítsük a beavatkozást és tanulást, illetve ezáltal tegyük még emberibbé ágenseinket. Két fázisból áll az algoritmus. 1. fázis: út széleinek megkeresése. Inputként megkapjuk a Map által szolgáltatott mátrixot, melyben az eljárásunk megkeresi az út széleit, és kimenetként ad egy bináris mátrixot. 2. fázis: az előző fázis outputja a bemenet, adott távolságonként „elmetszük” az utat egyenesekkel, és megjelöljük az út széleivel vett metszéspontokat. Outputban kiadjuk az ezen pontok közötti szakaszok felezőpontjait és az út szélétől vett távolságukat.
3.2. Univerzális vezető 3.2.1.
Vezetés
Input: • • • • Output: • •
látómező sebesség kormányállás autó jelenlegi helyzete és állapota sebesség kormányállás
A neuronok elsősorban a látómezőt tanulják meg felismerni, másodsorban pedig a pályát. Az aktuális kép alapján mindig lokális döntések születnek, így adódank az első eredmények.
3.2.2.
Tanulás
Input: • • • • • Output: •
előző kör eredménye látómező sebesség kormányállás autó jelenlegi helyzete és állapota globális stratégiák
A neuronháló lassan megtanulja a pályán lévő kanyarokat, így az aktuális és esetleg más pályákon is eredményes lehet.
3.3. Hibrid vezető 3.3.1.
Vezetés
A látás algoritmus által generált kontrollpontokból és út szélétől vett távolságokból álló vektort kapják meg a neuronok inputként, majd az első réteg az egymás utáni pontok távolságvektorait adja tovább. Ezek és az út szélétől vett távolság alapján számolja ki az adott pillanatban optimálisan vélt gáz/fékpedál-, és kormányállást.
3.3.2.
Tanulás
Az aktuális pozíció és az előző n db döntés alapján módosítjuk a neurális háló súlyozását. Azt kell megtanulni, hogy a gáz/fékpedál állása a következő kontrollpontoktól (illetve az azok közti vektoroktól) milyen súllyal függ. Ha út szélén vagyunk Ha úton vagyunk Ha lecsúsztunk
-> -> ->
nincs módosítás gázpedál növelés, ha nem lehet, kormányszög csökkentés kormányszög növelés, ha nem lehet, gázpedál csökkentés
3.4. Szabályalapú vezető 3.4.1.
Vezetés
Az ágens inputként a látómező látás algoritmussal feldolgozott adatait kapja meg, illetve a sebességet. Ezen inputok alapján alkalmazza a megfelelő szabályokat a kormányállás és a gázadás-fékezés output kiszámítására. p1 illetve p2 az ágens viselkedését meghatározó paraméterekt tartalmazó vektorok (az „evolúció” ezeken van értelmezve). Az input vektorból lineáris műveleteket használva számítja ki, mit tesz. Ha úton vagyunk -> k darab kontrollpont (a vektorban középtől való eltérés, k+1. komponens: sebesség) kormányállás: gázállás: 100.0 - (ahol b az a vektor, előjelek nélkül) Ha lecsúsztunk -> lassan megyünk az út felé
3.4.2.
Tanulás
Cross-Entropy módszer. Első iterációban előállítunk n egyedet a paramétereket véletlenszerűen kiválasztva egyenletes eloszlás szerint. Kiválasztjuk a k legjobb egyedet (2-10 %), majd a következő iterációban ezek eredményességének megfelelően módosítjuk a véletlenszerű kiválasztás sűrűségfüggvényét.
4. Kezelőfelület A kezelőfelület igényesen kivitelezett, felhasználó-barát, és egyszerű lesz. Funkcionalitások: • a térkép és a jármű 2D megjelenítése
• • • •
statisztikák megjelenítése, az eddig megtett utakról és időeredményekről, továbbá ezek mentése szöveges fájlokba térkép betöltése, melyet bmp fileokból lehet generáltatni az Mi vezetők indítása, megállítása menükön keresztül elérhető egyéb funkciók
Elrendezés: Előreláthatólag 2 részből fog állni a felület. A valódi grafika mellett megjelenítjük az autó állapot információit(sebesség, kormányállás, stb.). Egy másik panelen(sidebaron) pedig a már fent említett vezérlőfunkciók kapnak helyet.
5. Projektterv 5.1. Munkamegosztás Orosz György Vörös Gyula Zsiák Gergő Pál
-
GUI alrendszer, UniversalNeuralDriver osztály State alrendszer, BaseRuledDriver osztály Controller alrendszer, SpecializedNeuralDriver osztály
5.2. Határidők 2007. 10. 17. – GUI, fizika olyan mértékben kész, hogy az ágenseket tesztelni lehessen 2007. 11. 07. – prototípus 2007. 11. 21. – kész program 2007. 11. 28. – tesztelt program, dokumentáció
