Pre ďalšie generácie študentov a záujemcov o oblasť AI, zverejňujem moje poznámky z predmetu Základy umelej inteligencie. Tieto poznámky dokumentujú oblasť známu taktiež aj ako prehľadávania stavového priestoru.

Na čo je to dobré? Stavový priestor môže byť čokoľvek. Pre matematikov sú známe predovšetkým asi grafy a ich prechody. Pre bežných smrtelníkov to môžu byť mapy, bludiská na konci novín alebo sudoku (CSP problém). Niektorý možno poznajú hlavolami ako Problém N dám, Loydova osmićka, Hanoyské veže a pod.

Nie je tu popísané strojové učenie, genetické algoritmy alebo rozpoznávanie obrazu a reči. Aj keď sme to na predmete prebrali, prepisovanie poznámok do elektronickej podoby je zdĺhavá robota a zrovna som na tom dosť zle s časom, tak že pokračovanie bude asi len v prípade že nespravím najblizší termín :D

Metódy riešenia problémov prehľadávaním stavového priestoru

<link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.0.13/css/all.css" integrity="sha384-DNOHZ68U8hZfKXOrtjWvjxusGo9WQnrNx2sqG0tfsghAvtVlRW3tvkXWZh58N9jp" crossorigin="anonymous"> <table> <tr> <th>Metóda</th> <th>Optimálnosť</th> <th>Úplnosť</th> <th>Časová zložitosť</th> <th>Priestorová zložitosť</th> </tr> <tr> <th>BFS</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th>Exp</th> <th>Exp</th> </tr> <tr> <th>DFS</th> <th><i class="fas fa-times"></i></th> <th><i class="fas fa-times"></i></th> <th>Exp</th> <th>Lin</th> </tr> <tr> <th>DFS+</th> <th><i class="fas fa-times"></i></th> <th><i class="fas fa-check"></i></th> <th>Exp</th> <th>Lin</th> </tr> <tr> <th>DLS</th> <th><i class="fas fa-times"></i></th> <th><i class="fas fa-times"></i></th> <th>Exp</th> <th>Lin</th> </tr> <tr> <th>IDS</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th>Exp</th> <th>Lin</th> </tr> <tr> <th>BS</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th>Exp</th> <th>Exp</th> </tr> <tr> <th>UCS</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th>Exp</th> <th>Exp</th> </tr> <tr> <th>Backtracking</th> <th><i class="fas fa-times"></i></th> <th><i class="fas fa-times"></i></th> <th></th> <th>Extrémne nízka</th> </tr> <tr> <th>Backtracking pre CSP</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th></th> <th></th> </tr> <tr> <th>Forward checking</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th></th> <th></th> </tr> <tr> <th>Min conflict</th> <th>Nedokázaná</i></th> <th>Nedokázaná</th> <th></th> <th></th> </tr> <tr> <th>Greedy search</th> <th><i class="fas fa-times"></i></th> <th><i class="fas fa-check"></i></th> <th>Exp</th> <th>Exp</th> </tr> <tr> <th>A*</th> <th><i class="fas fa-check"></i></th> <th><i class="fas fa-check"></i></th> <th>Variabilná</th> <th>Variabilná</th> </tr> <tr> <th>HillClimb search</th> <th><i class="fas fa-times"></i></th> <th><i class="fas fa-times"></i></th> <th>Lin</th> <th>Konštantná</th> </tr> <tr> <th>Simmulated Annealing</th> <th><i class="fas fa-times"></i> - pre realne použitie</th> <th><i class="fas fa-times"></i> - pre realne použitie</th> <th>Extrémne vysoká</th> <th>Extrémne nízka</th> </tr> </table>

Úplnosť * hovorí o tom, či daný algoritmus nájde riešenie ak existuje

Optimálnosť * je vlastnosť algoritmu, pri ktorom vrátené riešenie je to najlepšie zo všetkých možných riešení * PRÍKLAD: * Z Brna do Nitry môžete ísť trasou: * Brno->Bratislava->Nitra * ale taktiež aj trasou: * Brno->Praha->Viedeň->Budapešť->Košice->Katovice->Zvolen->Nitra

Slepé metódy

BFS - Breadth First Search

1. zostroj frontu OPEN a umiestni do nej počiatočný uzol
2. ak je fronta OPEN prázdna, uloha nemá riešenie (fail)
3. vyber z fronty open prvý uzol
4. ak je uzol cieľovým, ukonči prehľadávanie ako úspešne (success)
5. vybraný uzol expanduj a všetky nové uzly umiestni do fronty OPEN
6. pokračuj od bodu 2

Reálne sa však používa verzia, kde bod 5 vyzerá nasledovne: * vybraný uzol expanduj a všetky nové uzly, ktoré ešte nie su vo fronte OPEN ani v zozname CLOSED umiestni do fronty OPEN. Expandovaný uzol umiestni do zoznamu CLOSED

Táto verzia sa nazýva BFS so zoznamom CLOSED

DFS - Depth First Search

1. zostroj zásobník OPEN a umiestni do neho počiatočný uzol
2. pokiaľ je zásobník OPEN prázdny, úloha nemá riešenie (fail)
3. vyber zo zásobníku prvý uzol
4. pokiaľ je uzol cieľový, ukonči prehľadávanie ako úspešné (success)
5. vybraný uzol expanduj a všetky nové uzly umiestni do zásobníku OPEN
6. pokračuj od bodu 2

Pre úplnosť (stále je však neoptimálna) sa bod 5 upraví nasledovne: * vybraný uzol expanduj, a všetky nové uzly, ktoré ešte v zásobníku nie su a taktiež nie su ani predkami (t.j. uzly, ktoré sa už rozgenerovali) umiestni do zásobníku OPEN

V tabuľke som túto metódu nazval DFS+, v skutočnosti je to DFS s elimínaciou rovnakých stavov v OPEN

DLS - Depth Limited Search

Podobné metóde DLS popísanej vyšie, len bod 5 sa mení a pridáva sa podmienka, že uzly sa rozgenerujú, len ak je úroven zanorenia nižšia, ako je maximálna povolená hĺbka.

Preto je limited, nakoľko sa na začiatku nadefinuje maximálna hĺbka.

IDS - Iterative Deepening Search

Podobná metóde DLS a vlastne celý princíp spočíva v tom, že sa volá DLS s hĺbkou zanorenia 1, a postupne sa hlbka zanorenia inkrementuje. Ak metoda DLS skončí neuspechom, ale nebol rozvinutý uzol, pretože sa narazilo na max zanorenie, inkrementuje sa maximálne zanorenie a DLS sa spustí znova. Ak sa DLS skončilo, pretože je zásobník prázny, a limit nebol hitnutý, uloha nemá riešenie. Pravda že keď DLS skončí úspechom, tak máme riešenie a končíme prehľadávanie.

BS - Bidirectional Search

V tomto prípade vieme kde sa nachádza cieľový stav. Spustime teda dve prehľadávania: * Začiatok -> Cieľ * Cieľ -> Začiatok

Pre výpočet sa môže pou%ziť BFS, ale aj UCS alebo A* (skripta BS nazývajú aj ako obojsmerný BFS). Výpočet sa končí vtedy, keď obe prehľadávania narazia na ten istý uzol.

UCS - Uniform Cost Search

Vo svojej podstate je to BFS s tým, že každá cesta je ohodnotená. Vieme taktiež použiť UCS verziu so zoznamom CLOSED a v prípade že máme viacero uzlov s rovnakým ohodnotením, nechávame len uzol s najnižším ohodnotením (najnižšou cenou). V prípade že by ceny všetkých ciest boli rovnaké, UCS degraduje na BFS. Z toho dôvodu taktiež nie je algoritmus vhodný, ak optimálna cesta vedie cez malý poćet uzlov s vysokým ohodnotením. V takom prípade sa prechádza zbytočne veľké mnoźstvo lacnejších ciest (tento problém rieši A*), ale algoritmus stále najde optimálnu cestu.

Backtracking

Algoritmus je pre zemnu podobný DFS ale s menšóu úpravou: 1. Zostroj zásobník OPEN a umiestno do neho počiatočný uzol 2. Ak je zásobník OPEN prázdny, úloha nemá riešenie (fail) 3. Ak je možné na uzol na vrchole zásobníku aplikova prvý/ďalśí operátor, tak ho aplikujte, inak odstránte daný uzol s vrcholu zásobníku a pokračujte bodom 2. 4. Ak je vygenerovaný uzol uzlom cieľovým tak sme našli riešenie (success), inak sa nový uzol vloží na vrchol zásobníku a pokraćuje sabodom 2.

Rozdiel oproti DFS je v tom, že DFS pri rozgenerovaní uzlov vložilo na zásobník všetky nové uzly, zatiaľ čo backtracking vloží na zásobnik vždy len jeden nový uzol, a pri spätnom navrátení (narazilo na slepu cestu) rozgeneruváva dalsie uzly.

Znova je možné algoritmus upraviť podobne ako pri DFS a to že sa na zásobník nevložia uzly, ktoré uź v zásobníku sú obsiahnuté, alebo su predkami práve expandovaného (rozgenerovaného) uzla.

Backtracking pre CSP

Čo je CSP?

CPS je skratka pre Constraint satisfactory problem. Čo to je?

Ak ste niekedy hrali sudoku, tak určite viete pravidlá. Postupne dosadzujete čísla 1 - 9 do voľných políčok pričom každé číslo sa môže nachádzať len raz v: * každom riadku * každom stpĺci * každom 3x3 štvorci

No a presne to je CSP. Problém s obmedzujúcimi pravidlami.

VSUVKA: Sudoku som pred predmetom IZU nikdy v živote nehral. Zrovna pri bodovanom cvičení z Forward checkingu a Min-conflictu som sa naučil ako pravidlá, tak aj ako aplikovať dané algoritmy na riešenie sudoku :) (neodporúčam, dané algoritmy sú pre PC. Manuálne je to zdlhavé s možnostou zavedenia chyby)

Backtracking a CSP

Nič sa oproti základnému algoritmu nemení, ak by daná aplikácia operátoru (napr. dosadenie čísla na políćko) poruśovala obmedzujúce podmienky/pravidlá, tak sa operátor považuje za neaplikovateľný

Forward checking (CSP)

• Pre každú premennú i(i=1, ..., n) (políčka v sudoku napríklad) sa priradí množina prípustných hodnôt.
• Zavolá sa procedúra forwardChecking(1)

forwardChecking(int i)

1. Odstránte prvú hodnotu z množiny S(i) a priradte tuto hodnotu premennej x(i), nech X je nový stav tvorený hodnotami všetkých premenných x(i), kde i = <1,n>
2. Ak je stav X cieľový tak ukončíme algoritmus uspechom (success)
3. Odstránte z množín S(j), kde j = <i+1, n> všetky hodnoty, ktoré sú v konflikte s doteraz priradenými hodnotami
4. Ak je niektorá množina S(j) prázdna, obnovte pôvodný stav množín S(j) pred bodom 3 a prejdite na bod 7.
5. Zavolajte frowardChecking(i+1)
6. Skončí predchádzajúca procedúra úspechom, skončite taktiež úspechom (success)
7. Ak nie je množina S(i) prázdna, pokračujte bodom 1, inak (fail)

Aplikované na sudoku: * pre každe políčko v sudoku zistite ake všetky hodnoty je moźné do daného políćka vloźiť a vytvorte mnoźinu týchto hodnôt * zoberte prvé políćko a prvú hodnotu z danej množiny (mnoźiny pre dané políćko) * Vložte ju do daného políćka * Prejdite všetky nasledujúce políčka a zistíte, ktoré hodnoty treba vyškrtnuť, lebo sa uź nedaju pre dané políćko pouźiť * Pokiaľ zistíte, že pre nejake polićko sa nedá pouźiť źiadna hodnota, daná hodnota prvého políčka sa nedá aplikovať, a teda sa zoberie dalsia hodnota preprve policko a skusi sa aplikovať * Pokiaľ pre každé ďalšie políčko ostala aspoň jedna hodnota, prejde sa na druhé políčko a pokraćuje sa rovnako ako pri prvom políćku. * Je možné že sa stane to, že v druhom políćku sa zrazu prejdu všetky hodnoty a ani jedna sa nebude dat aplikovať. V takom prípade sa zase vrátime na prvé políćko a zoberieme dalsiu hodnotu z mnoźiny. * Algoritmus zlyhá až v prípade že minieme všetky hodnoty z mnoźiny pre prvé políćko.

Heuristiky

Heuristiky pre Forward checking sa delia na dve skupiny: * ktorú premennú (políčko v sudoku) vybrať * Most constrained variable heuristic * premennú s najmenším mnoźstvom prípustných hodnôt * Most constraining variable heuristic * premennú s najväčším vplyvom na obmedzenie zvyšných volných premenných (farbenie obrazu, ak aplikujem tuto farbu, ovplyvni to moznosti v týchto x dalsich premenných (tvaroch)) * ktorú hodnotu vybrat z mnoziny pre danu premennu * Least constraining value heuristic * vybranie hodnoty, ktorá obmedzi najmenej hodnôt v dalsich premenných (ak na prve policko v sudoku viem aplikovat cisla 1,2,3 a vo vsetkych ostatných sa nachádza len 1,2 a 4,5 tak zvolim 3, nakolko ovplyvni najmenej hodnôt dalsich policok)

Min-conflict (CSP)

1. Prirad každej premennej x(i), kde i = <1,n> ) ľubovolnú hodnotu z množiny prípustných hodnôt. Nastav premenné i a j na 1.
2. Pre každú premennú x(i) spočítajte počet možných (vrátane teoretických) konfliktov
3. Pokiaľ existuje hodnota premennej x(i) kde je menší počet konfliktov tak ju použi (použije sa tá, kde je rozdiel najväčší). V prípade že vychádza rovnaký počet konfliktov, tak ju zmeň aj tak. A resetuj hodnotu premennej j na 1. Ak takáto hodnota neexistuje inkrementuj premennu j.
4. Pokiaľ sa j rovná počtu premenných, našli sme optimálne riešenie (prešli sa všetky premenne bez akejkoľvek zmeny). (success)
5. Inkrementuj premnnú i. Ak i > n, resetuj i na 1. Inak povedané, zační prechádzať premenné od znova.

Aplikované na sudoku: * do kazdeho volneho policka vlozime nahodne cislo z mnoziny pripustnych hodnôt. Cisla vlozime naraz, takze riesime len obmedzenia danne hodnotami, ktore su v sudoku od "výroby". * zoberieme teraz prve poličko takto vyplnenej sudoku. Pre každú jednu hodnotu v množine a aj tú, ktorú sme dosadili vypoćítame poćet konfliktov. Pozrieme sa na dané mnozstvá konfliktov pre dané hodnoty, a vyberieme to najmensie. Ak je najmensie cislo uz vlozene v sudoku, inkrementujeme premennu j. Pokial by vsak bola hodnota s rovnakym poctom konfliktov, alebo mensim, j-cko nastavime na 1 a pouzijeme ju. Teraz sa inkrementuje aj hodnota i (co je vlastne len index, ktorý nam hovorí, ktore policko premennej zrovna menime) * Ideme na druhe policko a absolvujeme rovnaky postup. * Dojdeme na posledne policko. Vtedy je i > n (pretoze matematici indexuju od jednicky a pri piatich prvkoch ma posledny index i=6, ale pocet n=5. Nic ine v tom nie je). Takze premennu i resetneme a zacneme teda znova od zaciatku. * Skôr ci neskôr, ked najdeme spravne riesenie pre sudoku. Hodnota j dosiahne urovne n, pretoze sme preiterovali cez vsetky policka sudoku a ani jedno nezmenili (t.j. premenna j nebola resetnuta). * A mame riesenie :)

Informované metódy

BestFS

Pokiaľ dostanete popísať BestFS, popíšte princíp algoritmu UCS. Je to jedna z dvoch extrémnych variant BestFS. Druhá je Greedy Search. Prečo?

Pretože BestFS vypočítava hodnotu z funkcie "f(s(k))" z ceny cesty od počiatočného stavu ku rozgenerovanému uzlu "g(s(k))" a z hodnoty heuristickej funkcie (h(sk)). Povedané polopatisticky: * Cena cesty je vzdialenost, ktoru ste pri ohodnotenom grafe uz presli * Hodnota heuristiky je odhadovaná spodná vzdialenost do ciela (povedzme vzdusnou ciarou)

Keď teda odstranite heuristiku, BestFS degraduje na UCS, ktoré používa len cenu cesty. Keď odstranite cenu cesty a použijete len heuristiku tak vznikne...

Greedy Search

Áno, Greedy Search. Pri Greedy search je cena cesty v celom grafe nulová/konštantná a poćíta sa len s hodnotou heuristickej funkcie. A to je celé. Vlastne len zoberiete UCS, ale namiesto ceny cesty sa pozriete, ako daleko je to podla heuristiky z daneho uzla do ciela.

A* search

Pokiaľ zoberiete cenu cesty od pociatocneho stavu do aktuálneho uzla a pripocítate k tomu, hodnotu heuristickej funkcie daného uzla do ciela, vznikne vám z toho A. Na rozdiel od Greedy search, A je taktiez optimálnou a priestorová a ćasová náročnost je velmi závislá na pouźitej heuristickej funkcii. V najlepsom pripade sa bude blizit linearnej funkcii, v najhorsom prípade exponencionálnej (degraduje na UCS).

Metódy lokálneho prehľadávania

Hill Climbing

1. Vytvor uzol Current a uloz do neho pociatocny stav spolu s jeho ohodnotením (obvykle je ohodnotenie dané len heuristikou)
2. Expanduj uzol Current, a z nových uzlov vyber ten najlepsie ohodnotený a pomenuj ho Next
3. Ak je Current uzol lepší ako Next tak (success)
4. Inak nahrad uzol Current uzlom Next a pokracuj od bodu 2

Táto metóda sice nie je ani úplná, a ani optimálna, ale má extrémne nízku priestorovú (konštantnú) a ćasovú (lineárnu) náročnosť.

Simulated Annealing

1. Vytvor tabuľku s predpisom pre klesanie teploty v závislosti na kroku výpočtu.
2. Vytvor uzol Current, vloz do neho pociatocny stav s ohodnotením (zase obvykle len z heuristickej funkcie) a nastav krok výpoctu na nulu (k=0)
3. Z tabulky zisti aktuálnu teplotu pre daný krok. Ak je teplota nulová, ukonci riesenie a navráť uzol Current (success)
4. Expanduj uzol Current a z nových uzlov vyber náhodne jeden a nazvi ho Next
5. Vypoćítaj rozdiel uzlov Current a Next, a nazvi hodnotu ΔE (ΔE = hodnota(Current)-hodnota(Next)).
6. Ak je rozdiel väčší ako 0 (ΔE>0), nahrad Current uzlom Next, inak sprav túto zmenu s pravdepodobnostou e^(ΔE/T), kde T je teplota z tabulky
7. Inkrementuj krok výpočtu k a pokračuj od bodu 3

Algoritmus dokáže prekonať lokálne extrémy (maximá/minimá), ktoré zastavia Hill Climbing. Má taktiež extrémne malú priestorovú zloźitosť (konštantnú), ale je sakra pomalý a jeho uplnosť a optimálnosť preto v reálnych ćasových medziach nie je zarućená.