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:
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:
NORTH
), jih (SOUTH
), východ (EAST
) a západ (WEST
).
START
), překážka (OBSTACLE
), zlato (GOLD
) a volné místo (EMPTY
).
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).
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ů:
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í:
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ě.
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). |
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.
python3 simulation.py
.
VISUALIZATION_OBJECT_MAPPING
v souboru visualization.py
.
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).