Prostředky umělé inteligence Řešení úloh ve stavovém prostoru II. © 2004, doc. RNDr. Ing. Tomáš Březina, CSc. Neinformované metody prohledávání Metody neinformovaného prohledávání se dělí z hlediska pořadí, v jakém jsou uzly expandovány, na: • slepé prohledávání do šířky o nejdříve se expanduje uzel s nejmenší hloubkou, o nalezne nejmenší řešení (s nejmenším počtem operátorů - nejkratší cestu). • slepé prohledávání do hloubky o nejdříve se expanduje uzel s největší hloubkou, o má nižší nároky na paměť (uchovává pouze uzly na cestě od počátečního stavu ke stavu právě expandovanému), o často spojeno s omezením maximální prohledávané hloubky, při jejím dosažení se používá mechanismu navracení. Pozn.: Hloubka uzlu = počet hran od počátečního uzlu k uzlu. Neinformované metody prohledávání Kompromis mezi prohledáváním do šířky a do hloubky: Algoritmus DFID (algoritmus iterativního prohlubování) Úplné prohledávání do hloubky tak, že se v každé iteraci zvyšuje povolená hloubka prohledávání o 1. • První nalezené řešení je optimální (ve smyslu nejkratší délky cesty). Pozn.: Neinformované metody jsou použitelné jen v nejjednodušších úlohách. • Nepoužívání znalostí o úloze vede na prohledávání příliš velkých částí stavového prostoru. Představují metodologický podklad pro složitější, informované strategie. Informované metody prohledávání Hodnotící funkce f: • pro každý uzel stromu řešení určí jeho ohodnocení, i hodnoty se používají pro výběr uzlu k expanzi, • pokud hodnotící funkce dobře postihují vlastnosti a charakter úlohy, budou vždy expandovány „nejperspektivnějšr1 uzly a zabrání se prohledávání cest, které nevedou k cíli, • čím kvalitnější heuristické znalosti o dané úloze se v f využijí, tím efektivnější bude prohledávání. Informované metody prohledávání Gradientníalgoritmus Vždy se expanduje ten uzel, který měl dosud nejlepší hodnotící funkci, a vyhodnocují se jeho následníci. • „Rodič" stejně jako „sourozenci" tohoto uzlu jsou okamžitě zapomenuty. Pracuje se pouze s právě expandovaným uzlem. • Hledání je zastaveno, když je dosaženo stavu, který má lepší ohodnocení funkcí / než jeho následníci. Pozn.: Základní nevýhodou všech gradientních metod je riziko uvíznutí v lokálním extrému. • Není vyloučeno zacyklení (pohyb po nekonečně dlouhé cestě, např. s konstantním ohodnocením). Informované metody prohledávání Algoritmus uspořádaného prohledávání Je gradientní algoritmus rozšířený o paměť. • Expandují se stavy s minimální hodnotou funkce / . • Používá obvyklé seznamy: o OPEN - seznam neexpandovaných stavů o CLOSED - seznam již expandovaných stavů Prvky seznamů jsou trojice (jméno uzlu, f, jméno rodičovského uzluj stavu do seznamu označuje zápis uvedené trojice). (zápis 1 Informované metody prohledávání 1. Počáteční stav zapiš do seznamu OPEN, seznam CLOSED je prázdný. 2. Pokud je seznam OPEN prázdný, řešení neexistuje, ukonči prohledávání. 3. Ze seznamu OPEN vyber stav i s nejmenší hodnotou f [i]. V případě většího počtu stavů se stejnou minimální hodnotou f (i) prověř, zda některý z těchto stavů není stavem cílovým, v takovém případě jej vyber; jinak vyber mezi stavy se stejnou minimální hodnotou f[i] libovolně. 4. Vymaž stav i ze seznamu OPEN a zařaď jej do seznamu CLOSED. 5. Je-li stav i cílovým stavem, řešení je nalezeno, ukonči prohledávání. 6. Expanduj stav i; pro každého následníka j stavu i vypočítej hodnotu f ave , řeše í je alezeo, ko každého následníka j stavu i vypočítej hodnotu f [jj. Pokud stav j není ani v seznamu OPEN, ani v seznam CLOSED, zařaď jej do seznamu OPEN. Pokud je stav j v seznamu OPEN nebo CLOSED, avšak s ohodnocením větším než právě vypočtené f (j), změň jeho ohodnocení na f [[/), změň jméno rodičovského uzlu v zápisu uzlu a zařaď ho do seznamu OPEN. 7. Pokračuj krokem č.2. Informované metody prohledávání Pozn.: Algoritmus uspořádaného prohledávání má celou řadu modifikací. Velmi známý je: Algoritmus paprskového prohledávání • pracuje se seznamem OPEN konečné délky m, do seznamu OPEN se zapisují pouze ty nově expandované uzly, které mají lepší ohodnocení než uzly dosud obsažené v seznamu. • To má za následek značnou redukci expandovaného stromu, ale nemusí vést k nalezení cílového stavu. Informované metody prohledávání Algoritmus A jde o algoritmus uspořádaného prohledávání s hodnotící funkcí f ('I = g (i) + , kde g li) je cena přechodu z počátečního stavu sQ do stavu i, kli) je cena optimální cesty ze stavu i do některého z cílových stavů sec. Pozn.: Funkci f (i) lze chápat jako cenu přechodu z počátečního stavu do cílového stavu přes stav i . Informované metody prohledávání Ve většině úloh g[i), h[i) není známo, používá se jejich odhadů g*[i), h*[i). Funkci g (i) odhadneme minimální dosud zjištěnou cenou g*[i) přechodu z počátečního stavu do stavu i • Funkci h[i) nahrazujeme funkcí h*[i), která kvantitativně vyjadřuje náš odhad ceny cesty z uzlu i do některého z cílových stavů. Odhad vyjadřuje naši heuristickou znalost o tom, jaké jsou šance nalézt (optimální) řešení, pokračovali-li bychom expanzí daného uzlu. Funkce h*(i) je proto nositelem heuristické informace a bývá proto nazývána heuristickou funkcí. Pozn.: Heuristická funkce je pro efektivnost prohledávání podstatná. Informované metody prohledávání Řekneme, že algoritmus prohledávání je přípustný, jestliže vždy nalezne optimální cestu, pokud tato cesta existuje. Algoritmus A s přípustnou heuristickou funkcí je algoritmus A*. Heuristická funkce je přípustná, je-li h* (/)> 0 a h*[i) < hli), pro všechny uzly i (tj. h* je nezáporný dolní odhad h). Čím je h* lepším dolním odhadem h, tím menší část stavového prostoru se prohledává při hledání optimálního řešení (při h* = h expanduje algoritmus A* pouze stavy na cestě k cílovému stavu). Říkáme, že algoritmus je lépe informovaným algoritmem než A^, jestliže pro každý stav i je h*(i)>h*(i). Aj pak expanduje všechny stavy, které expanduje A£. Mohou existovat stavy, které expanduje A^ a neexpanduje A^. stav však Informované metody prohledávání Funkce g* (i) Ul IM.C g \tj i Umožňuje vybírat stavy k expanzi na základě posouzení jak „dobrá" byla cesta z počátečního do daného stavu. Tj. ne vždy jsou k expanzi vybírány uzly, které se zdají být nejblíže k cíli. » Velmi důležitá, pokud nejde pouze o nalezení řešení, ale i o optimalizaci procesu nalézání řešení. Pro nalezení řešení jakýmkoliv způsobem stačí volba g*=a 2 Informované metody prohledávání Funkce h* (i) Algoritmus se stejnoměrnou cenou h*[i)=a (prohledávání řízeno pouze funkcí «•(')) • Algoritmus větví a mezí je algoritmus se stejnoměrnou cenou, který si po nalezení cílového stavu zapamatuje jeho cenu a pokračuje v prohledávání. Ze seznamu OPEN však automaticky vyřazuje uzly z vyšší cenou, než je zapamatovaná cena cílového stavu. Pokud je nalezen cílový uzel s nižší cenou, pamatuje se nižší cena a algoritmus pokračuje až do okamžiku, kdy je seznam prázdný. • Algoritmus náhodného prohledávání g*(/) = a , /?*(/) = b Při g* (i)=hloubka(i), h*(i)=0 degeneruje algoritmus A* na algoritmus slepého prohledávání do šířky. Informované metody prohledávání • Nelze ověřit, že jde o A* (tj. podmínku přípustnosti 0 0)a (cB > 0)a(cB * 4)} -- {A->} Vylej .4 \(cA > 0) A (cB > 0) A (cA * a)} -- JB -} Vylej B < d)A (cB * 4)a ((cA = 0)v (cB * 0))} - {- A} Naplň ^ \(cA* a)A(cB <4)a((cA*0)v(cB = 0))}-{-BJ Naplň B \(cA > 0)a (cB <4)a (cA+cB ŕ 4)} -- \a- BJ Přelej a do B j(cA < a) A (cB > 0) A (cA + cB ŕ a)} -> {A <- BJ Přelej B do ^ Metaznalosti jsou pravidla (metapravidla) používání pravidel definujících úlohu. Pozn.: Metapravidla mají nejčastěji tvar ■[situace -[preference AJ s interpretací „ Nastala - li v bázi dat situace s, preferuj pravidlo a ". Metoda generování a testování 'nalosti o úle generáto, t tester, kt omezení. Znalosti o úloze jsou rozděleny mezi generátor, který expanduje stav (nabízí jednotlivé stavy), a • tester, který stavy nabízené generátorem testuje a odmítá, nesplňují—li zadaná Pozn.: Velmi efektivní je metoda hierarchicky uspořádaného generování a testování, která umožňuje odmítnout stav na základě jenom jeho částečného popisu (jediným testem lze naráz zamítnout větší počet nevyhovujících stavů). Metoda užití analogie Řešení úlohy v prostoru I lze použít jako podklad pro řešení úlohy v prostoru II • je-li odhalena určitá podobnost mezi dvěma stavovými prostory pro dvě, jinak i zcela odlišné úlohy, nebo • byl-li řešen obdobný případ. Pozn.: Toho využívá tzv. usuzování na základě příkladů {případové usuzováni) 4 Rozklad úlohy na podúlohy Pro řadu úloh je velmi obtížné (ne—li nemožné) definovat heuristiky ve formě hodnotící funkce, pravidel, či metapravidel. Někdy je však možné získat heuristiky, kterými lze původní úlohu rozložit na (snadněji řešitelné) podúlohy. Není—li podúloha elementární, můžeme se ji znovu pokusit rozložit na podúlohy atd. Rozklad úlohy lze reprezentovat orientovaným AND/OR grafem, jehož uzly znázorňují úlohu a podúlohy. Uzly, které nejsou listy, mohou být typu: AND — představují konjunkci podúloh (k řešení úlohy je nezbytné, aby každá z podúloh byla řešitelná), • OR - představují disjunkci podúloh (k řešení úlohy stačí, aby aspoň jedna z podúloh byla ř st v řešitelná). Rozklad úlohy na podúlohy Jestliže víme, že výsledné řešení musí procházet jistým mezilehlým stavem (tzv. mostem), lze původní úlohu rozdělit na dvě podúlohy: podúlohu I s počátečním stavem sQ a cílovým stavem sM, • podúlohu II s počátečním stavem sM a cílovým stavem sceC. Pozn.: Uvažujeme-li právě 2 aplikovatelné operátory v každém ze stavů, je v nejhorším případě slepého prohledávání prostorů obou podúloh třeba vygenerovat 2ni + 2nn uzlů, kde rij, nn je přípustná hloubka stromu ve stavovém prostoru podúlohy I, resp. II. V nejhorším případě slepého prohledávání prostoru celé úlohy je třeba vygenerovat 2ni +nu uzlů. Protože 2Hj +2HjJ <2nj+nff , je výhodnější rozdělení úlohy, přičemž úspora generování může být značná. Rozklad úlohy na podúlohy Nechť je každý stav popsán R složkami (S,,rs,,i--S,,R )■ Potom lze úlohu U stručně zapsat jako 'S0Ji\ ^'^'■■■'^cfi ľ Úloha U bude vyřešena nalezením operátoru, který odstraňuje všechny diference. V případě • triviální úlohy, kdy sQr=sc r, r=\2,...,R,je úloha vyřešena okamžitě, t netriviální úlohy, kdy sQř^sCf., re{1,2,...,R}, tj. „existuje diference aspoň jedné z odpovídajících si složek", lze diference někdy měřit, jindy lze pouze konstatovat „diference existuje/neexistuje". Rozklad úlohy na podúlohy Nejjednodušší by bylo rozložit úlohu na R podúloh, z nichž by každá zajišťovala odstranění diference jedné složky. To není obecně použitelné díky možným vedlejším (postranním) efektům jednotlivých operátorů, kdy kromě odstranění diference jedné složky může operátor změnit i jiné diference. Předem není známo, která pravidla budou použita, proto díky vedlejším efektům není možno stanovit ani cílové stavy podúloh a počáteční stavy navazujících podúloh (mosty). Vedlejší efekt může navíc obnovit dříve odstraněnou diferenci. Řídicí algoritmus musí být schopen obecně formulovat podúlohy podle předchozího průběhu řešení úlohy. Rozklad úlohy na podúlohy / systém GPS Metoda analýzy prostředků a cílů (systém GPS) Používá procedury formulované na základě poznatků a psychologie lidského myšlení: • TRANSFORM sestavuje a řeší (znovu) podúlohu, tj. převedení současného stavu do cílového, • REDUCE vybírá pravidlo, které by odstranilo (zmenšilo) nejdůležitější diferenci mezi současným a cílovým stavem, • APPLY aplikuje vybrané pravidlo na daný stav. Rozklad úlohy na podúlohy / systém GPS Cílový stav poslední vyřešené podúlohy se nachází na vrcholu zásobníku. Poslední vyřešená podúloha měla za úkol odstranit jistou diferenci (v té době nejzávažnější). Vedlejší efekty však mohly způsobit vznik ještě závažnější diference. Takto vzniklá, nyní nejzávažnější má být odstraněna korekční podúlohou sestavenou prostřednictvím TRANSFORM. Vlastní řešení začíná pomocí REDUCE, která však nebere v úvahu vedlejší efekty vybraného pravidla. • Po vybrání pravidla se aktivuje APPLY. • Nejde—li pravidlo použít, je procedurou určeno proč a znovu použito REDUCE. Ta nyní hledá pravidlo, které by odstranilo diference bránící použití původně vybraného pravidla. 5 Rozklad úlohy na podúlohy / systém GPS Proces se rekurzívně opakuje tak dlouho, až je buď • možné celou sekvenci nalezených pravidel aplikovat (a tím odstranit diferenci pomocí TRANSFORM, tj. vyřešit danou úlohu) nebo • se prokáže, že úloha není řešitelná. Pozn.: Zásobník je struktura LIFO. Hlavní nevýhoda Je nutno definovat diference a uspořádat je podle závažnosti a dodat návod, jaká pravidla vybírat pro odstranění diferencí. Rozklad úlohy na podúlohy / systém STRIPS Má schopnost samostatně vybírat diference a pravidla. Sám zjišťuje diference mezi stavy, interpretuje je jako cílové a vybírá vhodná pravidla. Stavy jsou formulovány jako množiny formulí predikátové logiky. Každý operátor je tvořen trojicí kde By, je podmínka aplikovatelnosti operátoru, je množina klauzulí, které mají být ze stávající množiny vypuštěny, Fy je množina klauzulí, které mají být přidány. Rozklad úlohy na podúlohy / systém STRIPS Zadat je třeba pouze počáteční množinu platných formulí, cílovou formuli a množinu operátorů. V případě • triviální úlohy je cílová formule obsažena v počáteční množině formulí a úloha je vyřešena, • netriviální úlohy jsou hledány diference mezi množinou platných formulí a cílových formulí a pak je hledán vhodný operátor k odstranění. Je-li nalezen, je jeho podmínka aplikovatelnosti považována za nový podcíl, vzhledem k němuž se celý postup opakuje. Rozklad úlohy na podúlohy / systém PLANNER Explicitně využívá procedurální reprezentaci znalostí. Striktně odlišuje • Databázi obsahující fakta, která se týkají konkrétní, právě řešené úlohy a jsou reprezentována deklarativně, • Bázi znalostí obsahující obecné znalosti z problémové oblasti ve formě pravidel. Tato pravidla jsou vlastně procedury působící na databázi a představují procedurální reprezentaci znalostí. Pozn.: PLANNER nebyl nikdy implementován, pouze zjednodušené verze PROPLER, MICRO-PLANNER. V jistém smyslu na něj navazuje programovací jazyk PROLOG. • Systémy GPS, STRIPS, PLANNER nedosáhly praktického rozšíření, jsou teoretickým zdrojem prací v oblasti řešení úloh. větší důraz na využívání vysoce speciálních reprezentace znalostí. » Moderní systémy UI kladou daleko větší důraz znalostí. Do popředí vystupují mj. otázky efektivní r 6