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.

Vaším úkolem je vytvořit dvě doplňující se komponenty:

1. 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.
2. 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.

Agent se pohybuje v bludišti, což je čtvercová mřížka. Pohyb v bludišti se řídí následujícími pravidly:

• 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í bude rozděleno na 3 části, za které můžete získat v celkovém součtu 15 bodů:

1. 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ě.
2. 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.
3. Turnaj bludišť a agentů [5 bodů] se bude skládat ze dvou částí:
   1. 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.
   2. 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ž 5×5, ne nutně čtvercová bludiště, a menší než 70×70). 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.

Vaším úkolem je vytvořit v souboru agent.py třídu Agent s následující specifikací:

Pozorování předávané agentovi je instance třídy Observation. Instance třídy Observation má 2 členské proměnné:

1. position je aktuální pozice agenta uložená jako 2-tuple (r,c), např. na obrázku je to (12,3)
2. 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ě.

Vaším úkolem je vytvořit generátor bludiště ve funkci generate_maze v souboru maze_generator.py s následující specifikací:

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 5×5 do 70×70, a váš agent musí projít ~40 bludišti o rozměrech stejného rozsahu.

Máte k dispozici zdrojové kódy simulátoru a kostry implementací agenta a generátoru bludiště: 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.

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).