====== Týmová úloha: Maze Keeper ======
V rámci týmové úlohy, která je obsahem posledních 2 cvičení RPH, je Vaším úkolem naprogramovat rozhodování pro agenta ztraceného v bludišti a generátor bludišť, které má vytvářet co nejzáludnější bludiště pro agenty.
Odevzdání týmové úlohy není povinné, ale můžete za ni získat až **15 bodů**, viz **Hodnocení úlohy**. Na úloze budete pracovat týmově, v každém týmu mohou být **maximálně 2 studenti**, kteří spolu na úloze mohou bezmezně spolupracovat, jejich práce bude hodnocena jako jeden celek.
====== Úkol ======
Vaším úkolem je vytvořit dvě doplňující se komponenty:
- Agenta, jehož úkolem je dojít neznámým bludištěm k cíli (kopci zlata), a pak se vrátit zpátky na start.
- Generátor bludišť pro skrývání cíle (kopce zlata) v bludišti.
Metrikou vašich řešení je **normalizovaný počet kroků** v bludišti. Čím menší počet kroků bude stačit vašemu agentovi v cizím bludišti, tím lépe pro vás, a čím větší počet kroků budou hledat cíl cizí agenti ve vašem bludišti, tím lépe pro vás.
**Normalizovaný počet kroků** je definován jako počet kroků, který agent bude potřebat na to, aby došel ze startu ke zlatu a zpět, vydělený dvojnásobkem délky nejkratší možné cesty od startu ke zlatu. Například, pokud agent udělá v bludišti 28 kroků cestou ke zlatu a 12 kroků cestou zpět, a nejkratší cesta je dlouhá 10 kroků, bude normalizovaný počet kroků v bludišti (28+12)/(2*10)=4. To znamená, že nejmenší možný normalizovaný počet kroků, který může agent v kterémkoliv bludišti udělat, je 1.
===== Agent a bludiště =====
Agent se pohybuje v bludišti, což je čtvercová mřížka. Pohyb v bludišti se řídí následujícími pravidly:
{{ :courses:b4b33rph:cviceni:rph-maze-keeper-maze_example.png?400|}}
* Agent má k dispozici čtyři akce pohybu ve čtyřech směrech, na sever (''NORTH''), jih (''SOUTH''), východ (''EAST'' ) a západ (''WEST'').
* Objekty v bludišti jsou startovní pozice (''START''), překážka (''OBSTACLE''), zlato (''GOLD'') a volné místo (''EMPTY'').
* Pokud agent použije akci posunu na políčko, na kterém je překážka, zůstane stát na místě. To samé platí pro pokus o přesun na souřadnici mimo bludiště.
* Bludiště je matice MxN, první index reprezentuje řádek (souřadnice r), druhý index sloupec (souřadnice c). Sloupce a řádky jsou indexovány od nuly.
* Simulace končí přesunem agenta na políčko ''START'' poté, co předtím prošel přes políčko ''GOLD'', nebo po ''step_limit'' krocích (krok je každé volání akce, i takové, při kterém se agent nepohne).
* Startovní pozice agenta a pozice zlata je určená bludištěm. Agent v každém kroku zná svou pozici i pozici zlata.
* Agent v každém kroku "vidí" (''vision''), zná svou vzdálenost k překážce nebo k okraji bludiště v každém směru (N, S, E, W).
Cílem agenta je dostat se ze své počáteční pozice na známou pozici zlata a zpátky na start v co nejmenším normalizovaném počtu kroků.
Tvůrce bludište se snaží vytvořit bludiště, ve kterém agent cestou ke zlatu a zpět udělá co nejvíce normalizovaných kroků.
==== Hodnocení ====
Hodnocení bude rozděleno na 3 části, za které můžete získat v celkovém součtu 15 bodů:
- **Chování agenta [5 bodů]** -
* 1 bod dostane agent, který donese zlato na start ve velmi jednoduchém bludišti;
* 2 body, pokud zlato donese v určitém normalizovaném počtu kroků;
* 3 body, pokud donese zlato na start ve složitějším bludišti;
* 4 body, pokud donese zlato na start v max 120% kroků referenčního agenta; a
* 5 bodů, pokud donese zlato v počtu kroků referenčního agenta nebo méně.
- **Generování bludišť [5 bodů]** -
* 1 bod dostane generátor bludišť, který bude generovat splnitelná bludiště a které bude obsahovat alespoň nějaké zdi a nebude mít zlato a start vedle sebe;
* 2 body, pokud navíc náhodný agent v průměru nenajde cíl v určitém počtu kroků;
* 3, resp. 4 bodů, pokud referenční agent ve vašem bludišti donese zlato ve více než 60% resp. 80% kroků referenčního bludiště; a
* 5 bodů, pokud referenční agent udělá více normalizovaných kroků ve vašem bludišti než v referenčním bludišti.
- **Turnaj bludišť a agentů [5 bodů]** se bude skládat ze dvou částí:
- V prvním turnaji bude měřítkem normalizovaný počet kroků, které váš agent potřeboval pro vyřešení všech cizích bludišť. Čím méně, tím lepší bude pořadí agenta.
- V druhém turnaji bude měřítkem úspěšnosti, kolik normalizovaných kroků stráví cizí agenti ve vašich bludištích. Čím více, tím lepší bude pořadí vašeho generátoru bludiště.
Pro turnaje bude zvoleno několik velikostí bludiště (větší než 5x5, ne nutně čtvercová bludiště, a menší než 70x70). Pokud agent v bludišti nenajde zlato, bude to bráno tak, že v bludišti strávil maximální možný počet kroků. Pokud vaše bludiště bude infeasible (nebude v něm existovat cesta od startu ke zlatu), bude to bráno jako že v něm cizí agenti strávili hledáním zlata 0 kroků.
Turnaj bude vyhodnocen offline po deadline úlohy.
==== Agent ====
Vaším úkolem je vytvořit v souboru ''agent.py'' třídu ''Agent'' s následující specifikací:
^ metoda ^ vstupní parametry ^ výstupní parametry ^ vysvětlení ^
| ''__init__'' | ''maze_size'', ''step_limit'', ''start_position'', ''gold_position''| |''maze_size'' je velikost bludiště zadaná jako 2-tuple, MxN kde M je počet řádků a N je počet sloupců. ''step_limit'' je počet kroků, po kterém bude hledání v bludišti ukončeno bez ohledu na to, zda agent zlato nalezl či nikoliv. ''start_position'' je pozice, na které agent začíná a kam se musí vrátit po nalezení zlata. ''gold_position'' je pozice zlata v bludišti jako 2-tuple (r,c).|
| ''select_action'' | ''observation'' | ''action'' | ''observation'' je pozorování agenta o stavu prostředí. Je to instance třídy ''Observation'' která má 2 členské proměnné: ''position'' a ''vision'' (viz níže). Metoda vrací akci, kterou chce agent v aktuálním stavu vykonat, tj. jeden z řetězců '''NORTH', 'SOUTH', 'WEST', 'EAST''' (též klíče ve slovníku ''ACTIONS'' v modulu ''maze_keeper.py''). |
Pozorování předávané agentovi je instance třídy ''Observation''. Instance třídy ''Observation'' má 2 členské proměnné:
- ''position'' je aktuální pozice agenta uložená jako 2-tuple (r,c), např. na obrázku je to ''(12,3)''
- ''vision'' je slovník, pod klíčem světového směru obsahuje počet políček k nejbližší překážce (Obstacle) nebo okraji bludiště. Na obrázku by to například bylo ''{'NORTH': 6, 'SOUTH': 1, 'WEST': 0, 'EAST': 6}.''
Pokud se agent pokusí posunout směrem do překážky nebo mimo bludiště, zůstane na místě. **Simulace končí po přesunu agenta na start (Start) po tom, co předtím agent prošel přes políčko se zlatem (Gold).**
Agent si smí (a je to doporučno) držet historii stavů a z ní budovat znalost bludiště.
==== Generátor bludiště ====
Vaším úkolem je vytvořit generátor bludiště ve funkci ''generate_maze'' v souboru ''maze_generator.py'' s následující specifikací:
^ funkce ^ vstupní parametry ^ výstupní parametry ^ vysvětlení ^
| ''generate_maze'' | ''maze_size'' | ''layout'' |''maze_size'' je velikost bludiště zadaná jaku 2-tuple, ''(M, N)'', kde M je počet řádků a N je počet sloupců. ''layout'' je plán bludiště. Plán je 2-D pole o rozměrech MxN, které obsahuje stringy '''EMPTY', 'OBSTACLE', 'GOLD', 'START'''. Hodnoty '''GOLD''' a '''START''' musejí být v plánu právě jednou. Bludiště vrácené touto metodou musí být "feasible", tzn. musí v nich existovat cesta po polích '''EMPTY''' z pole '''START''' na pole '''GOLD''' (přesuny po diagonále nejsou povoleny).|
==== Časové limity ====
V úloze zatím nejsou nastaveny žádné časové limity na krok nebo generování bludiště. Avšak celkem je na ohodnocení vašeho řešení 15 minut, během kterých jste vyzvání k vygenerování 5 bludišť o rozměrech od 5x5 do 70x70, a váš agent musí projít ~40 bludišti o rozměrech stejného rozsahu.
==== Zdrojové kódy a vizualizace====
{{:courses:b4b33rph:cviceni:rph-maze-keeper-sim_screenshot.png?400 |}}
Máte k dispozici zdrojové kódy simulátoru a kostry implementací agenta a generátoru bludiště: [[https://gitlab.fel.cvut.cz/RPH-student-materials/rph-maze-keeper|gitlab repo]]
Soubor obsahuje následující moduly:
* ''agent.py'' - sem vložte implementaci svého agenta.
* ''maze_generator.py'' - sem vložte implementaci svého generátoru bludiště.
* ''simulation.py'' - Tento modul můžete použít pro testování svého agenta a generátoru bludiště. Pokud chcete, můžete v konstruktoru zapnout také konzolovou vizualizaci průchodu agenta bludištěm.
* ''visualization.py'' - nástroje pro vizualizaci, tento soubor nemusíte modifikovat.
* ''maze_keeper.py'' - Odsud můžete importovat konstanty a třídu State. Třída MazeKeeper ovládá interakci agenta a bludiště. Tento soubor nemusíte modifikovat.
Agent smí s bludištěm interagovat POUZE pomocí třídy ''MazeKeeper''. Agent má zakázáno snažit se získat více informací o bludišti než je uvedeno ve specifikaci.
* Vizualizace nemusí dobře fungovat při spouštění přes Pycharm (kvůli nekompatabilitě funkce, která čistí výstup před dalším krokem). Pro "video-like" vizualizaci spouštějte váš skript v konzoli, např. pomocí ''python3 simulation.py''.
* Pokud chcete nahradit symboly použité ve vizualizacei za jiné, můžete modifikovat konstantu ''VISUALIZATION_OBJECT_MAPPING'' v souboru ''visualization.py''.
==== Odevzdání ====
Do BRUTE nahrajte soubor ''maze_keeper.zip'', který musí obsahovat soubor ''agent.py'' s třídou ''Agent'' a soubor ''maze_generator.py'' s funkcí ''generate_maze''. (Samozřejmě, pokud ve svém řešení využíváte nějaké další vlastní moduly, musíte nahrát i je).