Prohledávání stavového prostoru

Vaším úkolem je naprogramovat algoritmus A* k prohledávání stavového prostoru State_space_search.

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.

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

Bodové ohodnocení za rešení úlohy lze vidět v hodnoceni.

Termín odevzdání úlohy lze vidět v 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!

1. Vytvořte si ve vašem oblíbeném IDE projekt a v něm soubor agent.py podle specifikace.
2. Pro testování před odevzdáním využijte testovací prostředí kuimaze_search.zip.
   1. Zip soubor rozbalte do složky s Vaším projektem.
   2. 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