FIT ČVUT Course Pages
BI-ZUM — Základy umělé inteligence
Jdi na navigaci předmětu

1. Systematické prohledávání stavového prostoru

Datum poslední aktualizace: 22. 2. 2023
Editace a obsah (poslední úpravy): L. Smítková Janků

Úvod

V rámci této úlohy student implementuje PĚT METOD systematického prohledávání stavového prostoru a demonstruje funkčnost implementovaných algoritmů při řešení úlohy hledání cesty v bludišti. Programovací jazyk, ve kterém budou algoritmy implementovány, si volí student.

Zadání

Řešte úlohu hledání cesty v bludišti pomocí pěti metod systematického prohledávání stavového prostoru:

  • Náhodné prohledávání (Random Search),
  • Prohledávání do hloubky (DFS) bez omezení hloubky (rekurzivní nebo se zásobníkem - iterativní),
  • Prohledávání do šířky (BFS),
  • Hladové prohledávání (Greedy Search),
  • A* algoritmus
    1. buď a) s takovou heuristikou, aby vždy našel nejkratší cestu.
    2. nebo b) s jinou heuristikou - student musí schopen vysvětlit chování algoritmu

VSTUP: Bludiště pro testování algoritmů. Bludiště jsou dostupná ve formě textových souborů.

VÝSTUP: Jednoduchá vizualizace činnosti každého z algoritmů + výpis délky nalezené cesty + informace, která pole program započítává do délky cesty

Dílčí úkoly:

  1. Implementujte načtení bludiště z textového souboru.
  2. Navrhněte vhodné kódování problému hledání cesty bludištěm tak, aby bylo možné k řešení použít metody systematického prohledávání stavového prostoru.
  3. Implementujte 5 výše uvedených metod systematického prohledávání stavového prostoru.
  4. Implementujte jednoduchou vizualizaci činnosti algoritmů. Vizualizace spočí v tom, že algoritmus postupně vykresluje expandované stavy (uzly, pole v bludišti) tak, že je možné sledovat jeho činnost. Na závěr vykreslí nalezenou cestu.

Pseudokódy:

viz slajdy z přednášek

Datasety (bludiště):

  1. testovací dataset
  2. dataset pro hodnocení

Prezentace úlohy na cvičení Připravte si odladěný program. Stáhněte si bludiště v testovaci.data.zip.
Předveďte algoritmy na testovacích datech cvičícímu.
Prezentovaná implementace musí umožnit sledovat postupnou expanzi stavů (uzlů, polí v bludišti).

Nahrání kódu na Gitlab Před prezentací úlohy cvičícímu na cvičení nahrajte Vámi vytvořený program pro řešení úlohy do svého repozitáře zřízeného pro předmět BI-ZUM na fakultním gitlabu.
Nechte jej v repozitáři do konce zkouškového období.
Postup zřízení repozitáře je popsán na hlavní stránce cvičení.

Poznámky

  1. Je možné implementovat každý algoritmus pro prohledávání stavového prostoru jako samostatný program nebo je možné vytvořit program jeden a výběr algoritmu provádět z příkazové řádky.
  2. Pro zadávání parametrů potřebných pro běh programu (např. zadání názvu souboru s bludištěm, které má být použito) používejte přednostně standardní I/O nebo předávání parametrů při volání programu z příkazové řádky. Nepoužívejte editaci zdrojového kódu programu.
  3. Pokud chcete implementovat DFS s omezenou hloubkou (LDFS) nebo s omezenou hloubkou s iterativním prohlubováním, tak to udělejte jako přídavek (aktivitu navíc) ke klasickému DFS bez omezení hloubky.
  4. Vztah mezi políčky bludiště, na které může agent vstoupit, a uzly grafu, který reprezentuje stavový prostor je 1:1 (1 políčko = 1 uzel grafu).

Vstup

Formát bludiště:

XXXXXXXXXXXXX
X           X
X  XXXXXXX  X
X     X     X
X X X X XXX X
X X         X
XX  X XXXXX X
X   X       X
X X X XXX XXX
X           X
X XXX X   X X
X           X
XXXXXXXXXXXXX
start 1, 7
end 5, 3
  • X jsou neprůchozí stěny, mezery značí volný průchod.
  • poloha je udávána v kartézských souřadnicích, přičemž počátek souřadnicového systému je v levém horním rohu a kladná poloosa osy y je orientována směrem dolů.
  • start 1, 7 znamená, že začátek se nachází na souřadnicích [1,7].
  • Bludiště je vždy zadáno korektně, tj. bludiště je ohraničené stěnou a začátek ani konec bludiště nejsou umístěny "ve stěně".

Výstup

Požadovaným výstupem je jednoduchá vizualizace činnosti každého algoritmu. Bez splnění tohoto cíle nebude úloha hodnocena a nebude možné ji odevzdat. Implementujte jednoduchou vizualizaci, kdy v každé iteraci bude zobrazována činnost algoritmu v terminálu (krokování). Musí být vidět postupné otevírání uzlů a na závěr musí být zobrazena nalezená cesta. Po skončení algoritmu vypište počet expandovaných uzlů a délku cesty - počet kroků (hran) od startu do cíle.

Příklad výstupu:

XXXXXXXXXXXXX
X           X
X  XXXXXXX  X
X ###EX     X
X X#XoX XXX X
X Xooo#     X
XX#oX#XXXXX X
XSooX       X
X#X#X XXX XXX
X           X
X XXX X   X X
X           X
XXXXXXXXXXXXX
---------------------------------------
S Start
E End
# Opened node
o Path
X Wall
space Fresh node
---------------------------------------
Nodes expanded: 17
Path length: 8

Formální požadavky a odevzdání

  • Před prezentací úlohy cvičícímu na cvičení nahrajte úlohu do svého repozitáře zřízeného pro předmět BI-ZUM na fakultním gitlabu. Postup zřízení repozitáře je popsán na hlavní stránce cvičení.

Doporučená litearatura k úloze 1

[1] Depth-First Search (DFS) https://brilliant.org/wiki/depth-first-search-dfs/

[2] přednášky BI-ZUM (najdete v nich pseudokódy algoritmů)

[3] Norvig, Russel: Artificial Intelligence: A Modern Approach, PDF

[4] pseudokódy ke kapitolám z dané knihy http://aima.cs.berkeley.edu/algorithms.pdf