1 Stavový prostor Po áte ní období výzkumu v oblasti um lé inteligence (50. a 60. léta) bylo charakterizováno p edstavou, že n kolik jednoduchých ale mocných technik umožní vytvá et inteligentní „vše ešící“ programy. Používané techniky byly založeny na vnit ním (strojovém) modelu sv ta a na schopnosti vytvá et v tomto modelu plán pro ešení dané úlohy. Model sv ta byl obvykle založen na stavovém prostoru.
1.1 Základní definice Def. 1.1: Stavový prostor Sp = (S, ) je dvojce tvo ená 1. množinou stav
S = {s}
2. množinou operátor (p echod mezi stavy) sk =
={ }
ki(si)
(sk se nazývá následník, si se nazývá p edch dce) P íkladem stavového prostoru jsou možná rozložení disk u hlavolamu „Hanojské v že“. Tento hlavolam je tvo en t emi ty kami, na kterých je navle eno n kolik r zn velikých disk . Jeden stav tohoto prostoru je vid t na Obr. 1.1. Velikost stavového prostoru tohoto hlavolamu samoz ejm záleží na po tu disk , pro n disk je to 3n (každý z n disk m že být na jedné ze t í ty ek), pro t i disky je stavový prostor znázorn n na Obr. 1.2. Použitý formalismus kóduje pozicí velikost disku (první zleva je nejv tší disk) a íslem ty ky (1 je levá krajní ty ka).
Obr. 1.1 Hanojské v že (stav (112))
Obr. 1.2 Stavový prostor hanojských v ží
Operátory se odvodí na základ pravidla, že se postupn p esouvají disky mezi ty kami, p i emž: 1. m že se p esouvat vždy jeden disk, 2. v tší disk se nem že položit na menší. Celkem je k dispozici 6 operátor : z k na i.
12,
13,
21,
23,
31,
32,
kde
ki
znamená p esu volný disk
Jiným p íkladem je rozložení osmi íslic v m ížce 3x3 u hlavolamu „lišák“ (Obr. 1.3). Tento stavový prostor obsahuje 9! = 362880 stav . 2 8 3 1 6 4 7 _ 5 Obr. 1.3 Lišák
V tomto stavovém prostoru jsou definovány 4 operátory: •
1:
•
2
•
3:
když _ není v levém sloupci, p esu _ vlevo
•
4:
když _ není v pravém sloupci, p esu _ vpravo
když _ není v horním ádku, p esu _ nahoru
když _ není v dolním ádku, p esu _ dol
Def. 1.2: Úloha ve stavovém prostoru (Sp, s0, G) je definována jako stavový prostor, tj. 1. množina stav
S = {s}
2. množina p echod mezi stavy
={ }
plus 3. po áte ní stav s0 4. množina koncových stav
G = {g}
V p ípad Hanojské v že je po áte ní stav na Obr. 1.4 a (jediný) koncový stav na Obr. 1.5.
Obr. 1.4 Hanojské v že - po áte ní stav
Obr. 1.5 Hanojské v že - koncový stav
V p ípad lišáka je po áte ním stavem libovolné uspo ádání íslic a jediným koncovým stavem stav z Obr. 1.6. 1 2 3 8 _ 4 7 6 5 Obr. 1.6 Lišák - koncový stav
V p ípad , že pomocí stavového prostoru chceme reprezentovat šachy, bude po áte ním stavem výchozí rozložení figurek na šachovnici a množinou koncových stav nap . všechny pozice, ve kterých bílý dává mat. Velikost stavového prostoru je asi 35100 (pr m rn 35 možností v každém tahu, pr m rná délka partie 50 tah ). Def. 1.3: ešení úlohy ve stavovém prostoru je nalezení posloupnosti operátor takových, že s1 = 1(s0) s2 =
2(s1)
s3 =
3(s3)
1
2…
d
... g=
d(sd-1)
neboli nalezení cesty z po áte ního stavu s0 do n kterého z koncových stav g (d je délka cesty).
Def. 1.4:
ídící strategie je algoritmus, který v každém kroku volí vhodný operátor:
•
musí vést k prohledávání (musí zabra ovat cykl m)
•
musí být systematické
Def. 1.5: Strom ešení úlohy je grafová reprezentace procesu hledání ešení kde uzly odpovídají stav m a hrany odpovídají p echod m mezi stavy daným aplikací operátor . Ve chvíli, kdy pro n jaký stav je použitelných více operátor se stává klí ovou otázka, který operátor zvolit. Pro volbu prvního operátoru v p ípad hanojských v ží ukazuje p íslušný podstrom Obr. 1.7, pro volbu prvního operátoru v p ípad hlavolamu lišák ukazuje p íslušný podstrom Obr. 1.8. Volba operátoru pro daný stav m že být založena na myšlence postupn zkusit aplikovat všechny použitelné operátory, m že být založena na n jakém kritériu, které hodnotí vhodnost jednotlivých operátor , nebo m že být volba operátoru náhodná.
Obr. 1.7 První krok Hanojské v že
Obr. 1.8 První krok lišák
1.2 Prohledávání stavového prostoru Metody prohledávání lze d lit do t í základních skupin: •
slepé - úplné prohledávání nevyužívající žádné dodate né informace – zde postupn aplikujeme všechny použitelné operátory,
•
heuristické - úplné nebo áste né prohledávání využívající hodnocení zvolené cesty – zde operátory vybíráme na základ n jakého kritéria,
•
náhodné – zde volíme operátory náhodn .
Systematické (nenáhodné) strategie (resp.algoritmy) jsou založeny na expanzi (rozvinutí) daného stavu (uzlu). Rozvinutím uzlu se myslí aplikace všech použitelných operátor ; získáme tak všechny následníky daného uzlu. Algoritmy obvykle využívají dva seznamy: seznam rozvinutých uzl ROZVIN a seznam nerozvinutých uzl NEROZVIN.
1.2.1 Slepé prohledávání 1.2.1.1 Prohledávání do ší ky P i prohledávání do ší ky jsou následníci vybíráni pro expanzi ze seznamu typu fronta (Obr. 1.9). Postupn procházíme strom ešení po vrstvách a prohledáme všechny uzly, které mají menší hloubku než je hloubka koncového stavu. Každý uzel p itom navštívíme nejvýše jednou. Schematicky je tento zp sob znázorn n na Obr. 1.10, postup algoritmu pak na Obr. 1.11. P i tomto zp sobu prohledávání máme jistotu, že vždy nalezneme optimální ešení (koncový stav s nejmenší hloubkou).
Obr. 1.9 Algoritmus prohledávání do ší ky
Obr. 1.10 Schéma prohledávání do ší ky
krok 1 2 3 4 Konec
NEROZVIN A B, C C, D, E D, E, F, G, H
ROZVIN Ø A A, B A, B, C
Obr. 1.11 Postup algoritmu „do ší ky“
Obr. 1.12 Lišák - prohledávání do ší ky (p evzato z 1)
1.2.1.2 Prohledávání do hloubky P i prohledávání do hloubky jsou následníci vybíráni pro expanzi ze seznamu typu zásobník (Obr. 1.13). Na rozdíl od prohledávání do ší ky m žeme n kterými uzly procházet vícekrát, nebo se asto musíme navracet (tzv. backtracking). Schematicky je tento zp sob znázorn n na Obr. 1.14 , postup algoritmu na Obr. 1.15. P i tomto zp sobu prohledávání nemusíme nalézt optimální ešení (koncový stav s nejmenší hloubkou) a dokonce žádné ešení (pokud má stavový prostor nekone nou v tev, do které „zabloudíme“). Pro úlohy s kone ným stavovým prostorem a s jedním koncovým stavem ale nalezneme stejné ešení jako p i prohledávání do ší ky.
Obr. 1.13 Algoritmus prohledávání do hloubky
Obr. 1.14 Schéma prohledávání do hloubky
krok 1 2 3 4 5 6 7 8 Konec
NEROZVIN A B, C D, E, C I, J, E, C J, E, C E, C C F, G, H
ROZVIN Ø A A, B A, B, D A, B, D, I A, B, D, I, J A, B, D, I, J, E A, B, D, I, J, E, C
Obr. 1.15 Postup algoritmu "do hloubky"
Všimn me si, že pokud bychom p i slepém prohledávání do hloubky místo „první zleva“, tak jak je znázorn no na Obr. 1.14 zvolili strategii „první zprava“, Nalezli bychom koncový stav podstatn rychleji (Obr. 1.16).
krok 1 2 3 Konec
NEROZVIN A C, B H, G, F, B
ROZVIN Ø A A, C
Obr. 1.16 Postup algoritmu "do hloubky" – zprava
Obr. 1.17 Lišák - prohledávání do hloubky (p evzato z 1)
1.2.1.3 Prohledávání se stejnou cenou (uniform cost) V každém kroku se expanduje uzel, který má nejmenší akumulovanou cenu (cenu cesty od po átku do tohoto uzlu). Jde o zobecn ní slepého prohledávání do ší ky (prohledávání do ší ky je prohledávání s jednotnou cenou, kde cena je hloubka uzlu).
1.2.1.4 Omezené prohledávání do hloubky Omezené prohledávání do hloubky se od klasického prohledávání do hloubky liší pouze v tom, že je dána maximální hloubka, do které se prohledává. Uzly této hloubky se již dále nerozvíjejí. Tímto zp sobem lze eliminovat problémy s nekone nou v tví.
1.2.1.5 Iterativní prohlubování Iterativní prohlubování je vlastn omezené prohledávání do hloubky, pro které se postupn zv tšuje maximální hloubka, do které se prohledává. Prohledává se tedy (do hloubky) nejprve stavový prostor hloubky 1, pak do hloubky 2, pak do hloubky 3 atd. Tato varianta dokáže odstranit i druhý problém klasického prohledávání do hloubky, nebo nalezne optimální ešení (pokud existuje).
1.2.2 Heuristické prohledávání Heuristické prohledávání je založeno na kritériu (heuristice), které umož uje posoudit vhodnost použití jednotlivých operátor aplikovatelných na daný stav. Vhodnost operátoru m žeme intuitivn chápat jako to, do jaké míry nás použití operátoru p iblíží ke koncovému stavu ( ešení úlohy). Jako bychom nap íklad s využitím mapy plánovali trasu pro cestu z m sta A (Praha) do m sta B (Pelh imov) s cílem minimalizovat délku cesty.
Obr. 1.18 Plánování cesty Praha - Pelh imov
Def. 1.6: Heuristická funkce je funkce, která každému stavu s p i adí íslo, vyjad ující jeho kvalitu z hlediska ešení úlohy. Vhodnost operátoru (a tedy kvalita p íslušného následníka) m že být v dané úloze definována r zn . R zné podoby kritéria samoz ejm ovlivní volbu operátor a tím i dobu (po et krok ) pot ebných k nalezení ešení. Vra me se k hlavolamu lišák (Obr. 1.8), kde m žeme jako možné heuristiky uvažovat nap .: H1: po et chybn umíst ných íslic, H2: Manhattan vzdálenost od koncového stavu. Význam první heuristiky je z ejmý. Druhá heuristika vyjad uje, kolik tah (ve sm ru vodorovném resp. svislém) je každá chybn umíst ná íslice vzdálena od své správné pozice. Podíváme-li se na volbu operátoru pro první tah dle Obr. 1.8, pak kvalitu stav 1 až 4 pro ob heuristiky vidíme v Tab. 1.1. Ob heuristiky vyhodnotí jako nejlepší tah 1 → 3. Pro druhý tah už budou „doporu ení“ obou heuristik odlišná (Tab. 1.2). Zatímco heuristika H1 vyhodnotí jako stejn kvalitní tahy 3 → 6 i 3 → 7 (a m li bychom tedy uvažovat ob možnosti), heuristika H2 vyhodnotí jako nejlepší tah 3 → 7, což je tah, skute n vedoucí nejrychleji k ešení úlohy. stav 1 stav 2 stav 3 stav 4 H1 4 5 3 5 H2 5 5 4 7 Tab. 1.1 Lišák - heuristiky pro první tah
H1 H2
stav 3 stav 6 stav 7 stav 8 3 3 3 4 4 5 3 5
Tab. 1.2 Lišák - heuristiky pro druhý tah
Heuristika musí být volena tak, aby umož ovala správné fungování prohledávacích algoritm . To vyjad uje následující definice a v ta. Def. 1.7: Algoritmus heuristického prohledávání se nazývá p ípustný jestliže pro libovolný ohodnocený graf ukon í svoji innost nalezením optimální cesty k cíli. V ta 1.1: Jestliže heuristická funkce každému uzlu p i adí hodnotu, která je nezáporným dolním odhadem skute né ceny, pak algoritmus je p ípustný (a p íslušná funkce se nazývá p ípustná). ím blíže jsme se svým odhadem skute n cen , tím lepší bude náš algoritmus (tím mén uzl musíme prohledat, abychom nalezli ešení). Def. 1.8: Algoritmus využívající (p ípustnou) heuristickou funkci H1 je informovan jší než algoritmus využívající (p ípustnou) heuristickou funkci H2, práv když ∀s∈S: H1(s) ≥ H2(s) ∧ ∃si∈S: H1(si) > H2(si) O heuristice H1 pak ekneme, že dominuje heuristice H2.
1.2.2.1 Paprskové prohledávání (beam search) Heuristické omezené prohledávání do ší ky kde heuristikou je odhad vzdálenosti ke koncovému stavu. Jako p i prohledávání do ší ky za azujeme následníky do fronty ale tu pak uspo ádáme dle heuristiky a vybereme jen ur itý po et nejlépe hodnocených uzl .
Obr. 1.19 Algoritmus paprskového prohledávání
1.2.2.2 Gradientní prohledávání (hill climbing) Heuristické prohledávání do hloubky, kde heuristikou je odhad vzdálenosti ke koncovému stavu. Následníky rozvinutého uzlu nejprve uspo ádáme dle heuristiky a pak za adíme do zásobníku.
Obr. 1.20 Gradientní prohledávání
Lokální varianta tohoto algoritmu je založena na tom, že pro daný stav volíme dle heuristiky nejlepšího následníka a pracujeme pouze s ním. Seznam NEROZVIN je tedy jednoprvkový. Tato varianta tedy hledá „pouze“ lepší uzel, než je ten sou asný. To m že zp sobit adu problém : •
uváznutí v lokálním extrému (žádný následník není lepší než rozvíjený uzel, který ale nep edstavuje ešení problému),
•
problém plošiny (rozvíjený uzel i jeho následníci jsou stejn kvalitní – není tedy jasné kterým sm rem postupovat).
Problém uváznutí v lokálním extrému ilustruje na p íklad hlavolamu lišák Obr. 1.22. Žádný z následník uvedeného stavu není ve smyslu heuristiky H1 lepší. Prohledávání by tedy skon ilo.
Obr. 1.21 Lokální varianta gradientního prohledávání
a 2 b 8 _ 4 c 6 d Obr. 1.22 Lokální extrém hlavolamu lišák
1.2.2.3 Uspo ádané prohledávání (best-first) Úplné heuristické prohledávání do hloubky- dopln ní gradientního prohledávání o pam . Pro další krok vybíráme nejlepší uzel z celého seznamu NEROZVIN. V p ípad , že heuristikou je odhad vzdálenosti ke koncovému stavu, se tomuto zp sobu prohledávání rovn ž íká greedy search.
Obr. 1.23 Uspo ádané prohledávání
1.2.2.4 Algoritmus A* Algoritmus A* je založen na myšlence, že nejkratší cesta z po átku do cíle p es stav s se skládá z nejkratší cesty z po átku do stavu s a z nejkratší cesty ze stavu s do cíle. Jsme-li p i ešení úlohy ve stavu s, pak cestu z po átku do tohoto stavu známe (ozna me g(s)), zbývá nalézt nejkratší cestu do cíle. Cena p echodu z po áte ního stavu p es stav s do koncového stavu je tedy definována jako f(s) = g(s) + h(s) kde heuristika h(s) je dolní odhad ceny p echodu ze stavu s do koncového stavu. Pro h(s) = 0 realizuje algoritmus A* prohledávání do ší ky. Pro hlavolam lišák je na Obr. 1.25 znázorn n strom ešení úlohy pro funkci f(s) = g(s) + h(s) kde
g(s) je hloubka uzlu h(s) je po et chybn umíst ných íslic.
íslo v kroužku udává pro každý uzel s hodnotu f(s).
Obr. 1.24 Algoritmus A*
Obr. 1.25 Lišák - algoritmus A* (p evzato z 1)
1.2.3 Hodnocení jednotlivých strategií Prohledávací strategií budeme rozum t po adí, v jakém jsou expandovány jednotlivé uzly. Strategie m žeme hodnotit podle (AI Berkeley kap 3): • •
úplnosti – zda strategie vždy nalezne ešení, pokud existuje asové složitosti – po et uzl , které jsou expandovány
•
prostorové složitosti – maximální po et uzl , které jsou sou asn uloženy v pam ti
•
optimality – zda nalezené ešení je vždy nejlepší (má nejnižší cenu)
asovou a prostorovou složitost budeme vyjad ovat jako funkci: •
maximálního v tvícího faktoru ve stromu ešení (ozna me b),
•
hloubky nejlepšího ešení (ozna me d),
•
maximální hloubky stavového prostoru – m že být nekone ná (ozna me m).
algoritmus do ší ky do hloubky uniform cost omezené do hloubky l iterativní prohlubování
úplnost ano ne ano ano pro l>d ano
as O(bd+1) O(bm) O(b(C/ε)) O(bl) O(bd)
prostor O(bd+1) O(bm) O(b(C/ε)) O(bl) O(bd)
optimalita ano ne ano ne ano
paprskové greedy A*
ne ano
O(bd) O(bd) ne O(bm) O(bm) ne exponenciální všechny uzly v pam ti ano Tab. 3 Hodnocení prohledávacích algoritm
1.3 Systémy pro ešení úloh ve stavovém prostrou 1.3.1 General Problem Solver (GPS) Jak už název systému napovídá, jde o algoritmus pro obecné ešení úloh (ve stavovém prostoru). Algoritmus který byl svými autory A. Newellem a H. Simonem poprvé prezentován v roce 1957 pat í do zlatého fondu um lé inteligence. Teoretickým východiskem algoritmu je tzv. analýza prost edk a cíl (means and end analyzis). Jde o metodu postupného rozkladu úlohy na podúlohy metodou výpo tu diferencí. Dekompozice úlohy na podúlohy, které je možno ešit samostatn , je pom rn astý zp sob ešení složitých problém ve chvílích, kdy náklady na dekompozici problému a ešení obou podúloh jsou menší, než náklady na ešení p vodní úlohy. Schématicky vidíme dekompozici hanojských v ží na Obr. 1.26. První podúlohou je p esun dvou disk na prost ední ty ku, pak následuje tah (122) -> (322), a pak ešíme podúlohu p edunu dvou disk na pravou ty ku. Pokud podúloha není elementární úlohou (tj. úlohou, kterou lze vy ešit použitím jediného operátoru), op t ji rozložíme na podúlohy, atd. P i ešení úlohy se tedy využívá i rekurze.
Obr. 1.26 Dekompozice hanojských v ží
General Problem Solver využívá t i základní procedury: TRANSFORM, REDUCE a APPLY. Procedura TRANSFORM se snaží transformovat stav s na stav s’, procedura REDUCE redukuje odchylku d mezi stavem s a s‘ a procedura APPLY aplikuje operátor na stav s. Popis procedur uvádíme dle (Havel, 1980). Procedura TRANSFORM(s,s‘) 1. vyhledej všechny odchylky mezi stavem s a s‘ (jestliže žádná neexistuje, je úloha vy ešena). Nech d je nejzávažn jší odchylka. 2. použij proceduru REDUCE(d,s,s”). Nech výsledkem redukce odchylky je stav s” 3. použij proceduru TRANSFORM(s”,s’) Obr. 1.27 Procedura TRANSFORM
Procedura REDUCE(d,s,s’) 1. vyhledej operátor který je schopen zmenšit odchylku d 2. ov , zda je použitelný na stav s . Pokud ne, vra se ke kroku 1. 3. použij proceduru APPLY( , s) a p ejdi do stavu s’ Obr. 1.28 Procedura REDUCE
Procedura APPLY( ,s) 1. porovnej podmínku aplikovatelnosti operátoru se stavem s a nalezni nejd ležit jší odchylku d. Je-li aplikovatelný, vra s’= (s) , jinak a. použij proceduru REDUCE(d,s,s”) pro redukci odchylky. Nech výsledkem redukce je stav s”. b. použij proceduru APPLY( , s”) a vydej výsledný stav Obr. 1.29 Procedura APPLY
Jak je vid t, všechny procedury jsou do sebe zano eny. Procedura TRANSFORM realizuje (zhruba e eno) prohledávání do ší ky, procedura REDUCE realizuje (zhruba e eno) prohledávání do hloubky a procedura APPLY realizuje (zhruba e eno) navracení. Následující p íklad ilustruje použití systému GPS na hanojské v že o t ech discích. P íslušný stavový prostor byl již d íve uveden na Obr. 1.2. ešení této úlohy má tedy podobu volání TRANSFORM((111),(333)) Odchylky mezi stavy budeme zepisovat ve tvaru DIFF(disk, aktuální_ty ka, cílová_ty ka). Mezi stavy (111) a (333) jsou tedy t i odchylky, v po adí dle závažnosti: DIFF(nejv tší_disk, 1, 3) DIFF(prost ední_disk, 1, 3) DIFF(nejmenší_disk, 1, 3) Zavolá se tedy REDUCE(DIFF(nejv tší_disk, 1, 3),(111),(311))). Vhodným operátorem by byl 13, který je p edán procedu e APPLY. Tento operátor ale nelze použít, nebo na nejv tším disku leží zbývající dva disky. Mezi stavem (111) a stavem, kdy lze použít operátor 13 na nejv tší disk (jde o stav (122)) jsou dv odchylky: DIFF(prost ední_disk, 1, 2) DIFF(nejmenší_disk, 1, 2). Nejzávažn jší z nich je t eba odstranit procedurou REDUCE(DIFF(prost ední_disk, 1, 2), (111), (122))). Vhodným operátorem by byl 12, který je p edán procedu e APPLY. Tento operátor ale nelze použít, nebo na prost edním disku leží nejmenší disk. Mezi stavem (111) a stavem, kdy lze použít operátor 12 na prost ední disk (jde o stav (113)) je jediná odchylka DIFF(nejmenší_disk, 1, 3).
Tuto odchylku lze odstranit procedurou REDUCE(DIFF(nejmenší_disk, 1, 3), (111), (113))). Procedurou APPLY m žeme p ímo aplikovat operátor 13 na nejmenší disk a ze stavu (111) p ejdeme do stavu (113). Nyní se vrátíme k otázce, jak p ejít do stavu (122). Mezi aktuálním stavem (113) a stavem (122) jsou dv odchylky: DIFF(prost ední_disk, 1, 2) DIFF(nejmenší_disk, 3, 2). Nejzávažn jší odchylku je t eba odstranit procedurou REDUCE(DIFF(prost ední_disk, 1, 2), (113), (122))). Vhodným operátorem je 12, který je p edán procedu e APPLY. Tento operátor m žeme p ímo aplikovat a dostaneme se tak do stavu (123). Mezi stavem (123) a (122), který je naším podcílem je jediná odchylka DIFF(nejmenší_disk, 3, 2). Procedura REDUCE(DIFF(nejmenší_disk, 1, 2), (123), (122))) zjistí, že vhodným operátorem je 32, který je aplikován procedurou APPLY. Získáme tak stav (122) a m žeme se vrátit k nejv tšímu disku. Mezi stavem (122) a cílovým stavem (333) jsou t i odchylky DIFF(nejv tší_disk, 1, 3) DIFF(prost ední_disk, 2, 3) DIFF(nejmenší_disk, 2, 3) Nejzávažn jší odchylku je t eba odstranit procedurou REDUCE(DIFF(nejv tší_disk, 1, 3), (122), (333))). Vhodným operátorem je 13, který je p edán procedu e APPLY. Tento operátor m žeme p ímo aplikovat a dostaneme se tak do stavu (322). a.t.d.
P ipome me si ješt , jak lze hlavolam hanojské v že vy ešit (s využitím stejné základní myšlenky dekompozice na podúlohy a rekurze) s využitím programovacích jazyk LISP a Prolog. Podoba programu v LISPu je na Obr. 1.30 a podoba programu v Prologu je na Obr. 1.31.
(DEFUN HANOJ (LAMBDA (N) (PRESUN_VEZ N ' A' B' C) )) (DEFUN PRESUN_VEZ (LAMBDA (K X Y Z) ((EQ K 0)) (PRESUN_VEZ (DIFFERENCE K 1) X Z Y) (TAH X Z) (PRESUN_VEZ (DIFFERENCE K 1) Y X Z) )) (DEFUN TAH (LAMBDA (X Z) (PRIN1 "Presun disk z ") (PRIN1 X) (PRIN1 " na ") (PRIN1 Z)) Obr. 1.30 Hanojské v že v LISPu
hanoj(N) :presun_vez(N,a,b,c). presun_vez(0,_,_,_) :- !. presun_vez(N,X,Y,Z) :M is N-1, presun_vez(M,X,Z,Y), tah(X,Z), presun_vez(M,Y,X,Z). tah(A,B) :write([A, -->, B]),nl. Obr. 1.31 Hanojské v že v Prologu
1.3.2 STRIPS Systém STRIPS (Stanford Research Institute Problem Solver) byl vyvinut na po . 70. let jako následník systému GPS. Vývoj systému byl inspirován oblastí robotiky, jeho algoritmus má ale obecné použití. Stavy ešené úlohy jsou popsány formulemi predikátové logiky 1. ádu v klauzulárním tvaru. Pravidla pro p echody mezi stavy jsou popsána trojicemi (C,D,A), kde C je podmínka aplikovatelnosti pravidla, D je množina klauzulí, které budou odstran ny z popisu aktuálního stavu, A je množina klauzulí, které budou k popisu aktuálního stavu p idány. Místo o odstra ování diferencí se v systému STRIPS mluví o spl ování cíl ; objeví-li se nová odchylka, vznikne nový podcíl, který je t eba splnit. ešení úlohy za íná tak, že se systém snaží splnit zadaný cíl úlohy. Vybírá tedy takové pravidlo, v jehož seznamu se vyskytl fakt odpovídající zadanému cíli. Najde-li takové pravidlo, pokra uje stejným zp sobem v pln ní cíl uvedených v samostatném seznamu cíl pravidla. Tento rekurzivní proces kon í tehdy, když jsou spln ny všechny cíle (popis systému dle [Z U]).
1.3.3 Planner Systém Planner byl vyvíjen na MIT (Massachusetts Institute of Technology) paraleln k systému STRIPS. Systém rozlišuje dva typy dat: tvrzení (konkrétní poznatky o konkrétních p edm tech – tedy fakty) a teorémy (obecné poznatky chápané jako procedury). Soubor všech tvrzení je uložen v bázi fakt – tato tvrzení jsou považována za pravdivá. I systém PLANNER je zam en cílov , tzn. Že jednotlivé p íkazy jsou volány cílem jehož má být dosaženo (tvrzením, které má být dokázáno). Vyhodnocování p íkaz je založeno na mechanismu navracení (backtracking), p i kterém se zaznamenává úsp ch i neúsp ch p i dosažení díl ích cíl – oproti rekurzivního ízení využívajícího zásobník PLANNER využívá stromovou strukturu.
1.3.4 SOAR SOAR (State, Operator And Result) je další systém založený na prohledávání. Jedná se o stále živý systém vyvinutý v 80 letech na Carnegie Mellon University. V sou asnosti je SOAR chápaný jako integrovaná architektura pro ešení problém , u ení a interakci s okolím, vše s využitím znalostí reprezentovaných v podob pravidel (ai.eecs.umich.edu/soar/).
Cvi ení:
1) Koza, vlk, zelí. Jde o známou historku o sedlákovi, který má p es eku p evézt kozu, vlka a zelí. Na lo ku se s ním vejde pouze jeden p evážený objekt. P itom nesmí nechat bez dozoru vlka a kozu ani kozu a zelí. Navrhn te formalismus ešení této úlohy ve stavovém prostoru (stavy, operátory) a najd te ešení. 2) Misioná i a kanibalové. Nemén známá historka o t ech misioná ích a t ech kanibalech, kte í se pot ebují p epravit p es eku. Naleznou lo ku, do které se ale vejdou pouze dv osoby. P itom na žádném b ehu nesmí z stat více kanibal než misioná . Navrhn te formalismus ešení této úlohy ve stavovém prostoru (stavy, operátory) a najd te ešení. 3) Japonský p evozník. Modifikace p edcházející úlohy. P es eku se pot ebuje p epravit rodina (otec, matka dva synové a dv dcery), a policista eskortující v zenkyni. P itom: •
Na prám smí maximáln dv osoby.
•
Otec nesmí být s žádnou z dcer bez p ítomnosti matky.
•
Matka nesmí být s žádným ze syn bez p ítomnosti otce.
•
V zenkyn nesmí být sama s žádným lenem rodiny.
•
Pouze policajt a rodi e mohou ídit prám.
Navrhn te formalismus ešení této úlohy ve stavovém prostoru (stavy, operátory) a najd te ešení. 4) Garsonka (Jiroušek). Po malování garsoniéry z stal nábytek rozmíst n tak, že v obývacím pokoji je postel a k eslo a v ložnici je st l a sk í . Úkolem je umístit st l a k eslo do obývacího pokoje a do ložnice postel a sk í . P itom: •
Kuchy ského koutu se vejde pouze sk í
•
Do obývacího pokoje i do ložnice se najednou vejdou jen dva kusy nábytku
•
K eslo neprojde dve mi do ložnice
•
Do zádve í se vejde pouze k eslo
•
P i p emis ování nábytku musí z stat uli ka volná
Navrhn te formalismus ešení této úlohy ve stavovém prostoru (stavy, operátory) a najd te ešení.
Literatura: 1. Havel I.: Robotika. SNTL Praha 1980. 2. Jiroušek R.: Metody reprezentace a zpracován.ní znalostí v um lé inteligenci. Skripta VŠE, 1995 3. Ma ík V., Št pánková O., Lažanský J.: Um lá inteligence XXXXX 4. Um lá inteligence a rozpoznávání. Skripta Z U, 1998.
