01 Úvod, Prohledávání

• počítačové laboratoře na K133 a bezpečnost práce
• https://www.cesnet.cz/sluzby/owncloud/
• https://gitlab.fel.cvut.cz
• prohledávání: vysvětlení
• zadání první samostatné úlohy

• 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í.

V prostředí Prohledávání stavového prostoru naprogramujte nalezení nejlevnější cesty. Nezapomeňte, že cena přechodu mezi pozicemi nemusí být nutně všude stejná.

• Stáhněte a nainstalujte si prostředí KUIMaze
• Vytvořte prostředí bludiště, tedy instanci třídy kuimaze.InfEasyMaze s mapou danou obrázkem maps/easy_intro/easy_intro_1.bmp:

  >>> import kuimaze
  >>> MAP = 'maps/easy_intro/easy_intro_1.bmp'
  >>> env = kuimaze.InfEasyMaze(map_image=MAP)

• Zobrazte si mapu bludiště metodou render():

  >>> env.render()

  Měli byste vidět následující obrázek:

Okno s obrázkem si zatím nechte otevřené, nezavírejte ho!

• Zkuste odhadnout, co dělá metoda reset(). Porovnejte výsledek následujícího volání s obrázkem bludiště:

  >>> env.reset()
  ((1, 0, 0.0), (4, 2, 0.0))

• Zkuste odhadnout, co dělá metoda expand():

  >>> env.expand((1,0))
  [[(2, 0), 1.0], [(0, 0), 1.0]]

• Zkuste znovu zavolat env.render(). Změnil se nějak obrázek?
• Prozkoumejte easy_example.py a pokuste se pochopit, co se v něm děje.
• Zkuste zkonstruovat cestu ze startu do cíle ručně a upravte metodu Agent.find_path() tak, aby natvrdo vracela tuto vaši cestu.
• Zkuste tohoto svého Agenta odevzdat do BRUTE do úlohy 01-easy-search, viz níže.

Ačkoli mnozí jste již netrpěliví skočit na implementaci algoritmu A*, zkuste napřed hledání cesty v jednoduchém bludišti. 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 na jednodušším problému. Základní komunikační rozhraní je stejné, tedy

import kuimaze
MAP = 'maps/easy_intro/easy_intro_1.bmp'
env = kuimaze.InfEasyMaze(map_image=MAP)
observation = env.reset() # returns start_pos, goal_pos
position = observation[0][0:2] # start position
positions_with_costs = env.expand(position) # list of lists [pos,cost], i.e. [[pos1, cost1],[pos2,cost2],...]

Odevzdávat budete také modul agent.py, přesně podle specifikace. Vyzkoušejte různé strategie prohledávání. Pokud napíšete dostatečně obecně, stejný kód bude fungovat i pro případ algoritmu A*. Odevzdávat budete do Upload systému.

Rozmyslete si trochu nad papírem datové struktury, které budete potřebovat.

• Python queue nebo heapq vám mohou pomoci při ukládání uzlů prohledávacího stromu.

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