Algorithms for Mean-Payoff and Energy Games
Jakub Chaloupka · 2011
Mean-payoff game (MPG) je hra dvou hraců hrana na konecnem ohodnocenem orientovanem grafu. Tito dva hraci, Max a Min, do nekonecna pohybuji žetonem po hranach grafu. Maxův cil je maximalizovat průměrnou hodnotu projitých hran, zatimco Min ji chce minimalizovat. Energy game (EG) je take hrana na konecnem ohodnocenem orientovanem grafu, ale hra je obohacena neohraniceným citacem. Citac ma nějakou danou nezapornou pocatecni hodnotu a hodnota každe projite hrany je k němu přicitana. Maxův cil je udržet citac nezaporný, zatimco Min chce aby sel pod nulu. EGs můžou být zobecněny pro k citaců, kde k je libovolne přirozene cislo. Ohodnoceni hran jsou k-tice celých cisel a každa komponenta každe projite hrany je přictena k přislusnemu citaci. Max chce vsechny citace udržet nezaporne, zatimco Min chce alespoň jeden poslat pod nulu. Mean-payoff a energy games jsou silným nastrojem s mnoha aplikacemi, zejmena v synteze, analýze a verifikaci pocitacových systemů. Napřiklad, EG může být použita pro modelovani robota v nepřatelskem prostředi. Hodnoty hran v teto EG reprezentuji ziskanou/spotřebovanou energii -- v zavislosti na znamenku, a hodnota citace reprezentuje uroveň energie robota. Pokud ma Max výherni strategii v teto EG, potom je robot schopen v nepřatelskem prostředi přežit ve smyslu, že jeho energie nikdy neklesne pod nulu. Systemy ktere potřebujeme analyzovat jsou casto velmi složite, a tudiž musime být schopni řesit velmi velke hry. Toto je možne pouze v připadě, že mame k dispozici efektivni algoritmy. V teto praci zhodnotime existujici algoritmicke techniky pro řeseni mean-payoff a energy games a take navrhneme nove techniky, ktere rozsiřuji aplikovatelnost těchto her. Pokud jde o mean-payoff games, vsechny dřive navržene algoritmy pro MPGs jsou sekvencni, a tudiž limitovane výkonem jednoprocesoroveho pocitace. V teto praci navrhneme několik paralelnich algoritmů založených na sekvencnich, a tak rozsiřime aplikovatelnost algoritmů pro MPGs na větsi hry. Pokud jde o energy games, zlepsime horni složitostni odhad pro řeseni EGs a take navrhneme nový algoritmus pro EGs založený na technice zlepsovani strategie. Složitost tohoto noveho algoritmu neni stejna jako nas zlepsený složitostni odhad, ale algoritmus je velmi rychlý v praxi, což take rozsiřuje aplikovatelnost EGs. Nakonec zlepsime horni složitostni odhad pro řeseni zobecněných EGs se dvěma citaci z EXPTIME na P, což otevira cestu pro efektivni algoritmy pro tyto zobecněne EGs. Vsechny algoritmy navržene v teto praci jsou zhodnocene v experimentalni studii. Tato prace take prezentuje výsledky naseho výzkumu paralelnich algoritmů pro rozklad grafů na jejich silně souvisle komponenty (SCCs). Jednou motivaci pro tento výzkum byl fakt, že rozklad na SCCs může být použit jako předzpracovani při řeseni MPGs za ucelem zrychleni výpoctu. Ackoliv použiti paralelismu pro toto předzpracovani se ukazalo zbytecne, rozklad na SCCs ma velkou skalu dalsich aplikaci, a tak jsme se rozhodli v teto větvi výzkumu pokracovat. Konkretně jsme navrhli nový paralelni algoritmus pro rozklad grafů na jejich SCCs urcený pro prostředi s distribuovanou paměti. Tento algoritmus jsme potom zhodnotili v rozsahle srovnavaci studii s ostatnimi znamými paralelnimi algoritmy.