Warning
This page is located in archive.

Markovské rozhodovací procesy

Stáhněte si aktualizovaný kuimaze balík kuimaze_mdp.zip. Úkolem je naimplementovat funkce find_policy_via_value_iteration(…) a find_policy_via_policy_iteration(…) s těmito vstupy a výstupy:

Vstupy: find_policy_via_value_iteration(problem, discount_factor, epsilon) a find_policy_via_policy_iteration(problem, discount_factor), kde:

  • problem je prostředí - objekt typu kuimaze.MDPMaze
  • discount_factor je z rozmezi (0,1)
  • epsilon je maximalní povolená chyba pro Value jednotlivých stavů (pouze pro value iteration)

Výstupy: Očekávaný výstup je slovník, kde klíčem je dvojice (x,y) tuple a hodnotou je optimální akce (stačí uvažovat dosažitelné stavy a pro terminální stavy nechť je výstup None).

Metody implementujte v souboru mdp_agent.py; který odevzdejte do Upload systému. V balíku kuimaze.zip je i soubor mdp_sandbox.py, který ukazuje základní práci s MDPMaze, můžete ho použít jako start k další implementaci (viz též popis Základních metod níže).

Timeout: na jednotlivé běhy value/policy iteration pro danou instanci problému máte časový limit 30s.

Bodové hodnocení a termíny

Termín odevzdání úlohy lze vidět v Upload systému.

Hodnocení je rozděleno následovně:

  1. Automatické hodnocení testuje správnost policy (match správných a vámi vrácených akcí pro všechny stavy) na vzorku prosředí a popř. s různými discount factory.
  2. Manuální hodnocení je založeno na hodnocení kódu (clean code).
Hodnocený výkon min max poznámka
Kvalita algoritmu value iteration 0 3 Ohodnocení algoritmu automatickým evaluačním systémem.
Kvalita algoritmu policy iteration 0 3 Ohodnocení algoritmu automatickým evaluačním systémem.
Kvalita kódu 0 2 Komentáře, struktura, elegance, čistota kódu, vhodné pojmenování proměnných…

Automatické hodnocení:

  • match v policy 95% a více (průměr na n testovaných bludištích): 3 body
  • match v policy 90%-95% : 2.5 bodu
  • match v policy 85%-90% : 2 body
  • match v policy 80%-85% : 1.5 bodu
  • match v policy 75%-80% : 1 bod
  • match v policy 70%-75% : 0.5 bodu
  • méně než 70% match: 0 bodů

Kvalita kódu (2 body):

  • vhodné komentáře, nebo kód je srozumitelný natolik, že komentáře nepotřebuje
  • rozumně dlouhé, respektive krátké metody/funkce
  • jména proměnných (podst. jména) a funkcí (slovesa) pomáhají čitelnosti a srozumitelnosti
  • kusy kódu se neopakují (žádné copy-paste)
  • rozumné šetření pamětí a procesorovým časem
  • konzistentní názvy i rozložení kódu v celém souboru (oddělovat slova ve všech metodách stejně, atp.)
  • přehledná struktura kódu (vyvarujte se např. nepythonovskému přiřazování mnoha proměnných v jednom řádku)

Můžete následovat pro Python určený PEP8. Většina editorů (jistě PyCharm) na nedostatky s ohledem na PEP8 i sám upozorňuje. Můžete se také inspirovat např. zde nebo si přečíst o idiomatickém pythonu na mediu či u pythonu.

Základní metody

Ke komunikaci s prostředím MDPMaze slouží následující metody:

get_all_states() : vrátí seznam všech dosažitelných stavů, tedy bez zdí. V tomto případě jsou to weighted stavy i s rewards, tedy (state.x, state.y, state.reward)

is_terminal_state(state) : True pokud ze stavu nevede cesta zpět - cílový dobrý, nebo naopak cílový špatný/nebezpečný - představte si propast, nebo minu.

get_actions(state) : Pro daný stav navrátí seznam možných akcí, které se typicky použijí v následující metodě. Akce je typu enum, ale tím se nemusíte zabývat, viz příklad použití v mdp_sandbox.py

get_state_reward(state): Obvykle není potřeba, vstupem je pojmenovaná dvojice (state.x, state.y).

get_next_states_and_probs(state, action) : pro daný stav a požadovanou akci navrátí seznam dvojic ( (state.x, state.y), probability ) ; např. [ ( (2,3), 0.3), ( (3,3), 0.2)]

state je pojmenovaná n-tice buď (state.x, state.y, state.reward) nebo (state.x, state.y).

visualise(dictlist=None) : bez parametru visualizuje obvyklé bludiště. Jinak očekává seznam slovníků {'x': x_coord, 'y': y_coord, 'value: val'}, kde val může být buď skalární hodnota, nebo seznam/n-tice o čtyřech prvcích. Zde můžete konkrétně využít k vizualizaci:

  1. rewards ci values přirazených jednotlivým stavům - viz env.visualise(get_visualisation_values(utils))
  2. policy - viz env.visualise(get_visualisation_values(policy))

Rovněž zůstávají k dispozici obvyklé metody render(), reset()

Základní příklad použítí je vidět v souboru mdp_sandbox.py

courses/b3b33kui/cviceni/sekvencni_rozhodovani/mdps.txt · Last modified: 2018/04/13 09:21 by hoffmmat