====== 1. Prohledávání stavového prostoru ======
Vaším úkolem je naprogramovat [[https://en.wikipedia.org/wiki/A*_search_algorithm|algoritmus A*]] k prohledávání stavového prostoru [[https://en.wikipedia.org/wiki/State_space_search|State_space_search]].
Stáhněte si prostředí {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}}
===== Formulace úlohy =====
Naprogramujte algoritmus A*, který najde optimální cestu do cílového stavu. Pokud cesta neexistuje, výsledné řešení je ''None''.
K dispozici máte prostředí-bludiště ''kuimaze.InfEasyMaze'', blíže viz [[.:specifikace|Specifikace]].
Pro správnou funkčnost algoritmu je zapotřebí zvolit takzvanou heuristickou funkci. Popis jaký dopad mají různé návrhy této funkce na výsledné řešení je velice pěkně zpracován [[http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html|zde]].
===== Hodnocení =====
Bodové ohodnocení za rešení úlohy lze vidět v [[.:hodnoceni|hodnoceni]].
===== Odevzdání =====
Termín odevzdání úlohy lze vidět v [[https://cw.felk.cvut.cz/upload/|Upload systému]].
* Odevzdávat budete ZIP archív s vaším modulem ''agent.py'' a případně se všemi moduly, které tento modul importuje. **Tyto soubory musí být v kořeni archívu, archív nesmí obsahovat žádné adresáře!**
===== Instrukce pro úlohu =====
- Vytvořte si ve vašem oblíbeném IDE projekt a v něm soubor ''agent.py'' podle [[.:specifikace|specifikace]].
- Pro testování před odevzdáním využijte testovací prostředí {{:courses:b3b33kui:cviceni:prohledavani_stavoveho_prostoru:kuimaze_search.zip|kuimaze_search.zip}}.
- Zip soubor rozbalte do složky s Vaším projektem.
- Pro plné spuštění, včetně vizualizace, je zapotřebí mít nainstalované python3 balíčky AI-gym, numpy a pillow. Pro jejich instalaci použijte následující příkazy v terminálu:
pip3 install gym numpy
sudo apt-get install python3-pil.imagetk