Task 1: Plánování, algoritmus A*

Na cvičeních a přednáškách jste se zabývali problémem prohledávání stavového prostoru a jaké všechny úlohy do této kategorie spadají. Jako zakončení tématického bloku bude v první úloze vaším úkolem naimplementovat algoritmus A*, který patří mezi základní vybavení každého programátora znalého základů AI.

Naší motivací bude problém autonomního taxíku, který právě nabral zákazníka v bodě A a dostal za úkol ho dovézt do bodu B. Provozovatel taxíku chce samozřejmě co nejvíce vydělat, proto si vybral zrovna vás, abyste mu pro taxík naprogramovali software. Ten taxíku řekne, kudy se má do cíle dostat co nejrychleji a tedy s co nejmenší spotřebou benzínu (protože taxík je zatím hloupý a umí jet pouze jednou konstantní rychlostí a nestaví na světlech).

Protože za práci nabídl slušné peníze, kývli jste. Když jste ale dostali specifikace HW na kterém váš software poběží, tak to s vámi málem šlehlo, protože množství paměti, které máte k dispozici je těsně na hranici toho, aby se požadovaný algoritmus dal naprogramovat. Budete se muset snažit ji nepoužít příliš, protože by po nasazení v taxíku nefungoval. Zároveň vám bylo řečeno, že když váš algoritmus nebude dost rychlý, zákazník taxíku uteče ke konkurenci, a ve smlouvě máte napsáno, že vzniklou škodu po vás bude provozovatel vymáhat. Tak se budete muset snažit, jinak přijdete o kapesné.

Naprogramujte algoritmus, který s minimálními paměťovými nároky najde zaručeně optimální cestu ve váženém grafu. Zaměřte se na implementaci odpovídajících heuristik. Ale pozor, přestože mapa ve které plánujete je representovaná gridem, jsou dvě varianty - pohyb možný do 4 směrů a do 8. Toto musíte ve svém kódu zohlednit.

Vstupem vašeho programu bude startovní bod, bod cílový, mapa a typ pohybu ('N4', nebo 'N8').

K dispozici máte od zadavatele implementované rozhraní k mapě ve které se váš taxík pohybuje. Toto rozhraní pro vás implementuje funkci succesor, nazvanou neighbors(…), kterou musíte ve svém kódu použít.

Váš program bude testován na 10 skrytých mapách a to tak, že za každou instanci můžete získat až 1 b. Bod za instanci dostanete, pokud váš algoritmus nalezne optimální (nejkratší) cestu a zároveň počet expandovaných nodů nepřesáhne referenční implementaci o více než 5%.

Pro potřeby vašeho testování dostanete k dispozici 5 veřejných instancí. Výkon vašeho algoritmu na těchto instancích uvidíte vyhodnocený i v BRUTE.

Závislosti:

• numpy
• matplotlib

Zde naleznete template pro vaše řešení. Ten obsahuje:

• Veřejné instance pro vaše testování
• Základní evaluační skript evaluate.py včetně kódu pro vykreslení map a nalezených cest
• Doplňkové kódy:
  • GridMap.py - implementující rozhraní k mapám ve kterých budete plánovat
  • GridPlanner.py - template vašeho řešení. Vaším úkolem bude doimplementovat funkci a_star_search(…)

• Vaším úkolem bude implementovat pouze funkci a_star_search(…) v souboru GridPlanner.py! Pomocné funkce si samozřejmě dělat můžete, ale zasahováním do ostatního kódu riskujete jeho nekompatibilitu s evaluačním scriptem v BRUTE!
• Odevzdávejte pouze vlastní soubor GridPlanner.py, a to v kořenovém adresáři odevzdávaného archivu. Na ostatní soubory nebude brán zřetel.
• Ostatní kód který od nás máte k dispozici slouží k tomu, abyste lépe pochopili zadání a mohli si otestovat své řešení na veřejných instancích. V BRUTE budete ale mít k dispozici pouze funkci GridMap.neighbors(…) jakožto funkci successor. Žádné jiné funkce ani kód nebudete moci využít! (Ani se o to nesnažte, my to poznáme )