|
|
Kooperativní hledání cest s protivníkem
Ivanová, Marika ; Surynek, Pavel (vedoucí práce) ; Mrázová, Iveta (oponent)
Předložená práce definuje a zkoumá problém kooperativního hledání cest s protivníkem (adversarial cooperative path finding - ACPF), který představuje zobecnění známé úlohy kooperativního hledání cest. Oproti standardní kooperativní verzi, v níž je úkolem najít nekolidující cesty pro několik agentů spojující jejich počáteční a cílové pozice, ACPF uvažuje navíc agenty ovládané protivníkem. Práce se zaměřuje jak na teoretické vlastnosti, tak na praktické techniky řešení uvažovaného problému. Úlohu ACPF zavádíme formálně pomocí pojmů z teorie grafů a zkoumáme její výpočetní složitost, kde ukazujeme, že úloha je PSPACE-těžká a patří do třídy EXPTIME. Představujeme a diskutujeme možné metody vhodné pro praktické řešení ACPF. Uvažované řešící postupy zahrnují hladové algoritmy, minimaxové metody, Monte Carlo Tree Search a adaptaci algoritmu pro kooperativní verzi. Z provedeného experimentálního vyhodnocení vyplývá mimo jiné překvapivě častá úspěšnost hladových metod a spíše slabší výsledky u Monte Carlo Tree Search. Powered by TCPDF (www.tcpdf.org)
|
host ::
RSS.