Prostředky umělé inteligence Řešení úloh ve stavovém prostoru I. © 2004, doc. RNDr. Ing. Tomáš Březina, CSc. Stavová reprezentace úloh Stavový prostorje (uspořádaná) dvojice £=(£>, OJ, kde D=\s\ je konečná množina stavů a Q)=UpX je konečná množina operátorů reprezentujících přechody mezi stavy. Pozn: • Každý operátor As\ m Orientovaná cesta (délky n) z s. do s. znamená posloupnost orientovaných hran, vedoucí z s. do s., . ' i i+n s. 1 pm ip)}->{->p)} „Není-li prázdné políčko u pravého okraje, hni políčkem napravo" {-é(D)}^{l(D)} „Není-li prázdné políčko u dolního okraje, hni políčkem dol ď {^P)}^P)} „Není-li prázdné políčko u levého okraje, hni políčkem nalevó" Řídicí strategie t postupně zkoušej produkční pravidla, nepřipusť cykly v použití pravidel a • STOP v okamžiku, kdy je dosaženo cíle. Pozn: • řídicích strategií může být více, např. s použitím předdefinovaných priorit pravidel. Produkční systém / příklad Přelévání vody Je dán neomezený zdroj vody a dvě nádoby, které nemají žádné označení míry. Větší z nich A má obsah a litrů, menší B má obsah b litrů. Na počátku řešení úlohy jsou obě nádoby prázdné (počáteční stav). Cílem řešení úlohy je dosáhnout toho, že nádoba A je prázdná a v nádobě B je např. 2[a-b) litrů vody. K dispozici jsou operace - vylití nádoby, naplnění nádoby a přelití vody z nádoby do nádoby. Úloha • Stav úlohy je usp. dvojice (cA,cB) (množství vody cA, cfí v nádobách A, B) • Počáteční stav je (0,0 • Jediný cílový stav (0,2[a—b • Přechod mezi stavy je použití povolené operace 'A' B S. 1 fyA(cfí\A->B\ A' 'B Produkční systém / příklad Produkční pravidla MbM Je-li Cj>0, vylej v4 {c*>(HM Je-li c„>0, vylej 5 \CA0)a(c5<í)}^{^^5} Je-li Cj>0 a cfí0)}^{^<-5} Je-li c ,0, přelej B ôo A Řídicí strategie viz stratégie v předchozím příkladu Složitost stavů X složitost operátorů Volba prvků stavového prostoru (stavy, přechody mezi nimi, množ. počátečních a cílových stavů), či adekvátního produkčního systému není úloha jednoznačná. Obecně platí, že • čím jednodušší strukturu mají stavy, tím méně obecná (a tudíž složitější) jsou pravidla, tj. jsou větší časové nároky na realizaci přechodu mezi stavy, • čím obecnější jsou pravidla, tím více je třeba zavést stavů (mnohdy lišících se v pouze detailech), tj. rozsáhlejší stavový prostor. Proto je nutný kompromis. Řešení úloh má obvykle nedeterministický charakter - není pevně definováno pořadí aplikace pravidel v případě, že na daný stav je možno aplikovat více pravidel (konfliktnímnožina pravidel). Výběr konkrétního pravidla řeší řídicí mechanismus. Prohledáváníje velmi důležitý postup vhodný pro řešení (složitých) úloh, které nelze řešit přímo známými výpočetními postupy. Prohledávání stavového prostoru Řídicí mechanismus realizuje řídicí strategii. Jde o algoritmus, který • poskytuje návod pro výběr pravidel z konfliktní množiny pravidel v každém kroku prohledávání stavového prostoru, • během prohledávání stavového prostoru generuje strom, který je podgrafem orientovaného grafu, reprezentujícího stavový prostor. Při přímém řízení se nejprve generuje a expanduje počáteční uzel s~, v dalším procesu prohledávání se pak expandují některé z dříve expandovaných uzlů. Je - li vygenerován uzel seC, prohledávání končí (ve stromu řešení existuje orientovaná cesta od s^ do s). Pozn.: Expanze uzlu znamená nalezení množiny všech možných bezprostředně následujících uzlů. Expanze uzlu / Přiklad Lišák i S. i 6 2 3 8 1 5 4 7 I s. i+\ ŤpjUÍTp)] ,ép)[^|lp)J k-PJM«-^ 6 2 3 5 8 1 4 7 ^■+2 2 3 6 8 1 5 4 7 5. , i+3 6 2 3 8 1 5 4 7 Expanze uzlu / Příklad Přelévám vody S. X (cA>0)A(cfí