01 Úvod, Prohledávání

Po tomto cvičení student

• ví, kde si říct o pomoc, když se zasekne (na cvičení, na diskusním fóru, na Discordu, emailem učiteli);
• rozumí způsobu, jakým bude v předmětu hodnocen;
• rozumí pravidlům pro použití AI a pro předcházení plagiarismu;
• rozezná diskrétní prohledávací problém, umí identifikovat stavy a akce, umí ohodnotit kandidátské řešení/plán;
• rozumí pojmům úplný a optimální;
• má nainstalovaný Python a prostředí kuimaze2;
• chápe zadání první povinné úlohy 02-search;
• umí použít veřejné rozhraní prostředí kuimaze2.SearchProblem;
• umí odevzdat řešení úlohy do BRUTE.

• Požadavky a hodnocení předmětu
• Pravidla samostatné práce a pravidla pro použití nástrojů AI
• Počítačové laboratoře a užitečné služby
  • počítačové laboratoře na K133 a bezpečnost práce
  • https://www.cesnet.cz/sluzby/owncloud/
  • https://gitlab.fel.cvut.cz
• Instalace Pythonu

• vysvětlení
• budeme diskutovat, jak hledat, když nevím jak je cíl daleko
• co znamená, že algoritmus prohledávání je úplný, optimální.

• Stáhněte a zprovozněte si prostředí KUIMaze
• Projděte si sekci Jak na to v popisu úlohy 1. Prohledávání stavového prostoru
• Vytvořte si prostředí SearchProblem, tj. instanci třídy kuimaze2.SearchProblem, s mapou danou obrázkem v souboru maps/easy_intro/easy_intro_1.png:

>>> from kuimaze2 import SearchProblem, State
>>> from kuimaze2.map_image import map_from_image
>>> map_path = 'maps/easy_intro/easy_intro_1.png'
>>> env = SearchProblem(map_from_image(map_path), graphics=True)

• Vykreslete si prostředí metodou render():

>>> env.render()

• Zkuste použít různé metody, které prostředí nabízí:

>>> start = env.get_start()
>>> start
State(r=0, c=1)
>>> env.get_goals()
[State(r=2, c=4)]
>>> actions = env.get_actions(start)
>>> actions
[<Action.UP: 0>, <Action.RIGHT: 1>, <Action.DOWN: 2>, <Action.LEFT: 3>]
>>> new_state, trans_cost = env.get_transition_result(start, actions[1])
>>> new_state
State(r=0, c=2)

• Zkuste zavolat env.render() znovu. Změnilo se zobrazení nějak?
• Zkuste přidat do volání metody render() další parametry:

>>> texts = {State(0,0): "S", State(0,1): "1"}
>>> env.render(texts = texts, current_state=State(0,0), next_states=[State(1,0)])

• Prozkoumejte example_search.py a zkuste pochopit, co se tam děje.
• Zkuste manuálně zkonstruovat cestu ze startu do cíle a vrátit ji z metody Agent.find_path().
• Zkuste si takového agenta odevzdat do BRUTE do úlohy 01-easy_search.

• Ačkoli jste mnozí již netrpěliví se rovnou vrhnout na implementaci algoritmu A*, zkuste napřed jednodušší algoritmy (BFS, UCS) a jednoduchá bludiště. Je to menší problém, bude se vám snáz krokovat a debugovat, ověříte si správné zacházení s prostředím.
• Rozmyslete si trochu nad papírem datové struktury, které budete potřebovat. Zkuste implementovat různé strategie/algoritmy. Pokud je implementujete dostatečně obecným způsobem, většina vašeho kódu půjde použít i pro algoritmus A* (což je první povinná úloha).
• Zkuste svůj algoritmus v modulu agent.py odevzdat do BRUTE a prozkoumejte, jakou zpětnou vazbu vám hodnoticí skript poskytl.
• Část bodů je za nalezení validní cesty do cíle, část za nalezení optimální cesty; za prozkoumání větší oblasti než je potřeba jsou naopak bodové srážky. Ale pozor: co stačilo v této úloze nemusí stačit v první povinné úloze! Tam jsou kritéria přísnější!

• V povinné úloze 1 je vaším úkolem naimplementovat algoritmus A*, který vám bude představen nejpozději na druhé přednášce. Pokud jste ale předchozí prohledávací rozcvičku zvládli rychle a nedělá vám potíže programovat v Pythonu, můžete začít pracovat na první povinné úloze.
• Nezapomeňte, že cena za přechod z jednoho stavu do jiného nemusí být pro všechny stavy stejná.

• visualizace různých prohledávacích algoritmů demonstrována na problému n-1 puzzle

• Rozchodit prostředí kuimaze2 v Pythonu.
• Dokončit úlohu 01-easy_search.
• Začít pracovat na úloze 02-search.