Warning
This page is located in archive.

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 cizí agenty. Odevzdání týmové úlohy není povinné, ale můžete za ni získat až 9 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.

Úkol

Vaším úkolem je vytvořit dvě doplňující se součásti:

  1. Inteligence pro hledání cíle (kopec zlata) v neznámém bludišti
  2. Generátor bludišť pro skrývání cíle (kopce zlata) v bludišti

Hodnocení bude na základě toho, v kolika krocích dokáže váš agent v neznámém cizím bludišti najít svůj cíl a v kolika krocích najdou cizí agenti cíl ve vašem bludišti.

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:

  • 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 se zlatem 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 v co nejmenším počtu kroků. Tvurce bludište se snaží vytvořit bludiště ve kterém bude agent hledat zlato co nejdéle. Hodnoceni budete na základě toho, jak dlouho bude trvat vašemu agentovi najít zlato v cizím bludišti a jak dlouho bude cizím agentům trvat najít zlato ve vašem bludišti.

Hodnocení

Hodnocení bude na základě automatické evaluace proti benchmark řešení (až 5 bodů) a počtu bodů získaných ve dvou turnajích (až 4 body).

Pro turnaje bude zvoleno několik velikostí bludiště (ne nutně čtvercová bludiště).

  1. V prvním turnaji bude měřítkem počet kroků které váš agent potřebovat pro vyřešení všech cizích bludišťích. Čím méně, tím lepší bude pořadí agenta.
  2. V druhém turnaji bude měřítkem úspěšnosti kolik celkem stráví cizí agenti kroků ve vašich bludištích. Čím více, tím lepší bude pořadí tvůrce bludiště.

Pokud agent v bludišti nenajde zlato, bude to bráno jako že v bludišti strávil maximální možný počet kroků. Pokud vaše bludiště bude infeasible (nebude tam cesta), bude to bráno jako že v něm cizí agenti strávili hledáním zlata 0 kroků.

Turnaj bude vyhodnocen po deadline úlohy.

Agent (Agent)

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

metoda vstupní parametry výstupní parametry vysvětlení
__init__ maze_size, step_limit, gold_position, agent_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. gold_position je pozice zlata v bludišti jako 2-tuple (r,c) a agent_position je počáteční pozice agenta v bludišti jako 2-tuple (r,c).
action state action state je aktuální stav prostředí. Je to instance třídy State která má 2 parametry: position a vision (viz níže). Metoda vrací akci, kterou chce agent v daném stavu vykonat, jednu ze stringů 'NORTH', 'SOUTH', 'WEST', 'EAST', též klíče ve slovníku ACTIONS v modulu maze_keeper.py

Stav předávaný agentovi je instance třídy State. Instance třídy State má 4 parametry:

  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žší zdi 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 zlato (Gold). Agent si smí (a je to doporučno) držet historii stavů a z ní budovat znalost bludiště.

Tvůrce bludiště (Maze generator)

Vaším úkolem je vytvořit tvůrce bludiště v třídě MazeGenerator v souboru maze_generator.py s následující specifikací:

metoda vstupní parametry výstupní parametry vysvětlení
__init__ maze_size, step_limit maze_size je velikost bludiště zadaná jaku 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.
generate layout 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. Plány vracená touto metodou musí být “feasible”, tzn. musí v něm existovat cesta po polích 'EMPTY' z pole 'START' na pole 'GOLD' (přesuny po diagonále nejsou povoleny).

Zdrojové kódy a vizualizace

Máte k dispozici zdrojové kódy simulátoru a kostry implementace agenta a tvůrce bludiště: rph-maze-keeper.zip

Soubor obsahuje následující moduly:

  • agent.py - sem vložte implementaci svého agenta.
  • maze_generator.py - sem vložte implementaci svého tvůrce bludiště.
  • simulation.py - Tento modul můžete použít pro testování svého agenta a tvůrce 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 nepotřebujete 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 nemodifikujte.

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.

Odevzdání

Do BRUTE nahrajte soubor maze_keeper.zip který musí obsahovat soubor agent.py a maze_generator.py s třídami Agent a MazeGenerator. (Samozřejmě pokud ve svém řešení využijete import z některého dalšího modulu (např. maze_keeper), musíte nahrát i tento soubor).

PSA: MazeObjects

Kvůli problému s automatickou evaluací byl z template řešení odstraněn enum MazeObjects. Pokud vaše verze řešení obsahuje MazeObjects jako enum a ne jako dictionary, stahněte si novou verzi zadání. Pro opravu kódu pak stačí nahradit např. MazeObjects.GOLD stringem 'GOLD'

courses/b4b33rph/cviceni/maze_keeper.txt · Last modified: 2019/01/11 18:07 by mrkosja1