Vysoké učení technické v Brně Fakulta elektrotechniky a informatiky Ústav biomedicínského inženýrství
EXPERTNÍ SYSTÉMY praktická cvičení Ing. Ivo Provazník, Ph.D., Ing. Jana Bardoňová
2000
Obsah 1
Úvod --------------------------------------------------------------------------------------------------3
2
Reprezentace znalostí ---------------------------------------------------------------------------5
3
Strategická hra----------------------------------------------------------------------------------- 17
4
Analýza procesu--------------------------------------------------------------------------------- 21
5
Symbolická analýza ---------------------------------------------------------------------------- 25
6
Plánování strategie ----------------------------------------------------------------------------- 28
7
Fuzzy expertní systémy------------------------------------------------------------------------ 36
8
Fuzzy řízení procesu --------------------------------------------------------------------------- 40
9
Informace o CLIPSu ---------------------------------------------------------------------------- 48
10 Literatura ------------------------------------------------------------------------------------------ 49
Předmluva Skriptum "Expertní systémy - praktická cvičení" je textem, který navazuje na práci autorů Provazník I, Kozumplík J: "Expertní systémy", VUTIUM Brno, 1999. Obsahem skript Expertní systémy byl úvod do reprezentace znalostí, popis struktury expertních systémů založených na pravidlech, a také popis jazyka CLIPS pro tvorbu expertních systémů. Text byl řazen do následujících kapitol: Úvod do expertních systémů, Principy expertních systémů, Neurčitost a nepřesná inference, Fuzzy inference, Programovací jazyk CLIPS, a Efektivita jazyků založených na pravidlech. Skriptum předkládané čtenáři obsahuje řešené příklady z příslušné oblasti umělé inteligence a může sloužit k několika účelům. Jednak je možné jej použít jako návod pro cvičení univerzitního kurzu Umělá inteligence nebo Expertní systémy. Dále umožňuje lépe proniknout do podstaty jazyka CLIPS díky popisu jednotlivých částí řešení příkladů. Příklady je také možné použít jako vzor řešení obecných problémů pomocí expertních systémů, kde je vyžadována aplikace principů deklarativního programování. Při přípravě skript byly použity příklady, které jsou volně dostupné na různých pracovištích distribuujících jazyk CLIPS, dále vlastní příklady autorů a příklady, které vznikly v rámci předmětu Expertní systémy, zajišťovaném Ústavem biomedicínského inženýrství. Autoři děkují především kolegům Jiřímu Kozumplíkovi a Petru Fedrovi, kteří přispěli při přípravě cvičení a poskytli cenné rady. Poděkování patří i frekventantům uvedeného předmětu, kteří svými dotazy iniciovali nejeden nápad použitý v textu.
Jana Bardoňová a Ivo Provazník Brno 2000
2
1
Úvod
Klasické programovací jazyky jako Pascal a C jsou navrženy a optimalizovány pro procedurální manipulaci s daty ve formě čísel, polí a pod. Člověk ale řeší složité problémy s použitím abstraktního symbolického přístupu, který není vhodný pro implementaci v klasických jazycích. Abstraktní informace může být těmito jazyky modelována, více se však využívá transformace informace do vhodnějšího formátu. Jedním z výsledků výzkumu v oblasti umělé inteligence (UI) je právě vyvinutí neprocedurálních technik modelování informací na vyšších úrovních abstrakce. Tyto techniky jsou zabudovány v jazycích a nástrojích umožňujících vytvoření programů, které jsou ve své struktuře blízké lidské logice a snadněji se proto rozvíjejí a udržují. Tyto programy se nazývají expertní systémy (ES) [14]. Expertní systémy představují nástroj k úspěšnému řešení klasických problémů umělé inteligence. Prof. Edward Feigenbaum ze Stanfordské university, který patří mezi první pracovníky v oboru expertních systémů, definuje ES jako ”... inteligentní počítačové programy, které využívají znalostí a inferenčních mechanismů k řešení problémů, které jsou natolik obtížné, že by vyžadovaly řešení lidským expertem”. To znamená, že ES je počítačový systém, který emuluje schopnost lidského experta rozhodovat. Termín emulovat zde představuje vlastnost systému - snahu jednat stejně jako člověk ve všech ohledech [15]. Snadná dostupnost nástrojů jako je CLIPS umožnila zrychlit a zlevnit vývoj expertních systémů, a umožnila tak jejich praktické nasazení v různých oborech, např. v medicíně [1]. Tyto nástroje většinou zahrnují programování založené na pravidlech, které je v oblasti expertních systémů nejvíce rozšířené. Programování založené na pravidlech je paradigma, které specifikuje akce, které mají být provedeny v určité situaci. Pravidla jsou tvořena z částí když ... potom (if ... then). Část když obsahuje posloupnost tzv. obrazů specifikované fakty (daty). V procesu splňování pravidla se expertní systém snaží nalézt odpovídající obrazy a fakty v bázi faktů. Tento proces se nazývá inferencí (usuzování). Část potom pravidla obsahuje posloupnost akcí, které mají být provedeny kdykoliv inferenční mechanismus prokáže splnitelnost pravidla. Inference probíhá tak dlouho, dokud neexistuje žádné splnitelné pravidlo. Expertní systémy se skládají z následujících hlavních částí [9]: • uživatelský interface - spojovací modul, který zabezpečuje komunikaci uživatele s ES, • vysvětlovací modul - popisuje a vysvětluje postup usuzování ES uživateli, • modul získávání znalostí - modul pro vkládání nových znalostí do ES, • pracovní paměť - databáze faktů používaných pravidly, • inferenční mechanismus - provádí inferenci (proces usuzování). Vytváří prioritní seznam pravidel, aplikuje pravidla podle seznamu a rozhoduje, která pravidla jsou splněna předloženými (existujícími) fakty, • agenda - seznam pravidel s přiřazenou prioritou vytvořený inferenčním mechanismem, • báze znalostí - databáze pravidel. Následující text je určen jako návod pro praktická cvičení, proto obsahuje pouze stručná shrnutí nejdůležitějších principů a metod používaných v umělé inteligenci - expertních systémech. Více prostoru je věnováno řešeným příkladům s komentovanými výpisy programů jazyka CLIPS a ukázkami výstupů programů. Po úvodu následuje druhá kapitola, která je nejrozsáhlejší a obsahuje shrnutí způsobů reprezentace znalostí v expertních systémech. Reprezentace znalostí je vedle inferenčních mechanismů stěžejním faktorem určujícím vlastnosti ES. Kapitola je doplněna
3
příklady z oblasti prohledávání stavového prostoru a predikátové logiky. Třetí kapitola je popisem klasické strategické hry a doplňuje problematiku stavového prostoru s definicí hodnotící funkce. Ve čtvrté kapitole je nastíněna další z aplikačních oblastí ES - analýza procesu s následným vyhodnocením. Pátá kapitola prezentuje ES jako nástroje pro řešení obecných problémů prostřednictvím příkladu symbolické analýzy. Šestá kapitola postihuje další důležitou aplikaci ES - plánování. Příklad plánování strategie (postupu) je ukázkou reprezentace znalostí s plně odděleným popisem dat a algoritmu. V sedmé kapitole jsou přiblíženy principy fuzzy expertních systémů jako důležitého nástroje při rozhodování s neúplnou informací. Vše je doplněno v osmé kapitole reálným příkladem fuzzy řízení jednoduchého procesu. Pro úplné pochopení příkladů v předkládaném textu je nutné znát alespoň základy programování v jazyku CLIPS. Ty je možné získat ve skriptu [23], literatuře [11] a [9], a dále v originálních příručkách [3] - [7] volně dostupných na Internetu (viz kapitola 10 Literatura).
4
2
Reprezentace znalostí
Reprezentace znalostí představuje formu vyjádření určitých informací. Hlavním cílem současného výzkumu v oblasti umělé inteligence (UI) je vytvoření takové reprezentace znalostí, která je dostatečně obecná, tzn. umožňuje zahrnout širokou oblast znalostí, a systému s UI umožní použití dostatečně efektivní metody řešení. Požadované informace se organizují do takové formy, aby byly snadno přístupné pro programy, které vykonávají rozhodnutí, plánují činnost, rozpoznávají předměty, analyzují scény či jiné zajišťují funkce [10]. Znalosti by měly obecně informovat o vnitřním modelu prostředí. Jedná se o vkládání informací získané analýzou scény do modelu prostředí, udržování vlastního obsahu modelu prostředí a zpřístupnění jeho obsahu pro další činnost. Pro reprezentaci znalostí se používají různá schémata [22]: • • •
deklarativní schémata, procedurální schémata, rámcová schémata.
Obecné požadavky na schémata jsou tyto [21]: • • • • • • •
2.1
možnost aplikace různých operací (řízení, prohledávání, porovnávání, použití), všeobecnost a abstraktnost (široké použití), strukturovanost (struktura základních jednotek vědomostí), zpřístupnitelnost (přístupné jednoduchým způsobem), modulárnost (efektivně přidat i odstranit znalosti), přirozenost a srozumitelnost, praktická realizovatelnost.
Deklarativní schémata
V deklarativních schématech pracujeme s těmito základními množinami: • množina specifických, navzájem nezávislých faktů, která popisuje dané prostředí, • množina všeobecných procedur pro manipulaci s obsahem množiny specifikovaných faktů. Specifická fakta jsou v těchto schématech použita jako axiómy, manipulační procedury slouží jako procedury dokazování, tzn. umožňují odvozovat z axiómů nové znalosti. Podstata deklarativních schémat spočívá v popisu těch aspektů reprezentovaného prostředí, které určují, co fakt vyjadřuje. Mezi deklarativní schémata patří např. schémata, která jsou založená na matematické logice, algebře, relačních strukturách, grafech a pod. Deklarativní schémata se vyskytují v různých typech. Jde především o • • •
sémantická schémata (sémantické sítě), schémata založená na koncepci stavového prostoru, logická schémata (predikátová logika 1. řádu).
2.1.1 Sémantické sítě Sémantická síť umožňuje popisovat realitu jako objekty, které jsou navzájem v nějakých vztazích (relacích). Grafickou reprezentací je ohodnocený orientovaný multigraf, jehož uzly odpovídají entitám (konkrétní předměty, pojmy, vztahy) daného prostředí, a hrany odpovídají sémantickým vztahům mezi entitami. Sémantickým sítím však dosud chybí exaktní matematická formalizace.
5
Entity sémantické sítě představují zejména: • pojmy (konstanty reprezentovaného prostředí), • události (změny a jejich realizace v prostředí), • vlastnosti (zpřesnění pojmů). Vztahy v sémantické síti jsou především tyto: • kvantifikační (hodně, málo, několik), • lingvistické (slovesné charakteristiky, barva, ...), • logické (negace, konjunkce, disjunkce, implikace), • množinové (množinové operace). Různorodost sémantických sítí se odráží i v různorodosti mechanismů odvozování znalostí. Jeden z přístupů je založený na porovnávání síťových struktur - báze znalostí. Druhá síťová struktura, vstupující do procesu porovnávání, vznikne transformací vstupního výroku (otázky) do tvaru sítě, přičemž některé uzly mohou být neznámými entitami - proměnnými. Inferenční metody realizují operace porovnávání i operace prohledávání s cílem najít ty znalosti, které jsou relativní k vstupní otázce. Oblast sémantické sítě, která obsahuje relevantní informace se nazývá kontext. Určení kontextu a jeho zpřístupnění pro další zpracování je hlavní činností inferenčního mechanismu.
2.1.2 Stavový prostor Stavový prostor realizuje strukturu problémů pomocí alternativ, které jsou přípustné v daném stavu. Prostředí se může nacházet v různých stavech a operátory představují akce na množině stavů. Stavy a operátory vytvářejí schémata na reprezentaci znalostí, stavový prostor. Pro tento typ úloh vycházíme ze znalosti o počátečním stavu prostředí, cílovém stavu a jednotlivých akcích, které mohou být provedeny. Na daný stav nemůže být použit libovolný operátor, ale jen takový, pro který jsou v daném stavu splněny podmínky aplikovatelnosti. Řešením úlohy je každá posloupnost operátorů, která transformuje počáteční stav na cílový. Úloha může mít samozřejmě více řešení. Stavový prostor: SP = <S,O> S neprázdná množina (všeobecně i nekonečná) množina stavů O neprázdná konečná množina operátorů (stavy a operátory vytvářejí schémata na reprezentaci znalostí např. pro robota, tj. stavový prostor). Cílová úloha ve stavovém prostoru: <s0,G> s0 počáteční stav, s0 je prvkem S, G konečná množina cílových stavů. Řešením úlohy se nazývá každá posloupnost operátorů o1, pro kterou existuje posloupnost stavů s1, s2, ..., sn s vlastnostmi:
o2,
...,
on ,
s1 = o1(s0) s2 = o2(s1) = o2(o1(s0)) = (o1o2)(s0) . . . sn = on(sn-1) = on(on-1( … (o1(s0)))) = (o1o2 … on)(s0)
přičemž sn náleží G. Stav je tedy deklarativním popisem prostředí nebo jeho určité části, operátory jsou zobrazení množiny stavů do sebe, přičemž na daný stav nemůže být použit libovolný operátor.
6
Na základě vnitřního modelu prostředí a zadaného cíle se systém snaží samostatně najít plán jako uspořádaný soubor operátorů, jejichž realizace povede k dosažení daného cíle. Když je zadán stavový prostor SP a cílová úloha, potom se při jejím řešení postupuje tak, že z počátečního stavu s0 se postupnou aplikací operátorů generují další prvky stavového prostoru. Tento postup se opakuje do té doby, dokud není dosažený cílový stav. Graf odpovídající SP se nazývá stavový graf. Jednotlivé stavy odpovídají uzlům, na které se postupně aplikují všechny možné operátory. Nově vzniklý uzel se nazývá generovaný, uzel, na nějž jsou aplikovány všechny operátory, se nazývá expandovaný, jsou tedy generováni všichni jeho následovníci. Obecný postup při prohledávání stavového grafu je následující: • počáteční uzel grafu odpovídá popisu počátečního stavu, • aplikací některého z operátorů získáme bezprostředního následovníka, tedy nový stav reprezentovaný generovaným uzlem, u každého uzlu se v procesu řešení úlohy vytvářejí a uchovávají směrníky k rodičovskému uzlu, které po dosažení cíle dovolují nalézt řešení úlohy, • po vytvoření všech bezprostředních následovníků daného uzlu, použitím všech aplikovatelných operátorů se uskutečňuje test, zda některý z následovníků neodpovídá cílovému stavu. Jestliže daný uzel mezi následovníky neexistuje, proces hledání řešení pokračuje expanzí dalšího uzlu. V opačném případě je možno pomocí směrníků získat informace o tomto řešení. Prohledávání stavového grafu může být rozděleno na dva základní typy podle toho, zda máme k dispozici bližší informace o pořadí expandovaných uzlů: • neinformované prohledávání - prohledávání do šířky, při kterém jsou uzly expandovány v takovém pořadí, v jakém byly generovány, - prohledávání do hloubky, ve kterém je vždy expandován ten uzel, který byl generován jako poslední, • informované prohledávání, při kterém algoritmus musí vyhovovat dvěma základním kritériím: - má produkovat nejkratší cestu k cíli, - při hledání cesty k cíli má expandovat co nejmenší počet uzlů. Pokud jsou bližší informace o řešení známé díky zkušenostem, hovoříme o využití heuristických informací. Hodnotící funkce Hodnotící funkce se využívá v informovaném prohledávání stavového prostoru a slouží k vyjádření heuristických znalostí. Toto kritérium nám umožňuje uspořádat uzly tak, aby bylo možné před každou expanzí vybrat nejvhodnější uzel. Funkce může být zvolena podle: • pravděpodobnosti, zda uzel leží na optimální cestě, • různých způsobů měření vzdálenosti mezi daným uzlem a množinou cílových uzlů, • různých druhů diference mezi uzly, které jsou dané vlastnostmi řešené úlohy, • analogie, která spočívá v nacházení podobnosti mezi uzly, případně stavovými prostory tak, že řešení úlohy v jednom stavovém prostoru se využije jako podklad k řešení úlohy v druhém stavovém prostoru. Příklad: Zadání: Navrhněte expertní systém, který bude řešit klasický problém umělé inteligence. K dispozici jsou dvě nádoby, které mají obsah 5 litrů a 3 litry. Odměřte přesně 4 litry. Nádoby lze doplnit, vyprázdnit nebo lze obsah přelévat z jedné nádoby do druhé, ale jen do plného obsahu.
7
Řešení: Řešení je provedeno pomocí prohledávání stavového prostoru, je znám počáteční stav, cílový stav a také operace, které mohou být provedeny: • počáteční stav: obě nádoby jsou prázdné, • aplikovatelné operátory: - doplnit nádobu, - vylít celý obsah nádoby, - přelít část obsahu z jedné nádoby do druhé, tedy doplnit jednu nádobu a částečně nebo úplně vyprázdnit nádobu druhou, • cílový stav: 4 litry v jedné nádobě. Následující schéma obsahuje uzly, ve kterých jsou graficky znázorněny stavy v obou nádobách s uvedením obsahu. Z uzlu vychází hrana s uvedením značky operátoru, který je na daný stav aplikován. Ve schématu jsou rozkresleny téměř všechny možné postupy, které jsou dány možnostmi povolených operací. Horního uzel reprezentuje počáteční stav. Na něj lze aplikovat pouze operátor plnění nádob. Protože zde existují dvě možnosti, schéma se dělí do dvou základních větví. Na nově vzniklé uzly lze opět aplikovat operátory, v tomto případě budou využity všechny operace, které jsou povoleny. V dalším řádku jsou nově generované uzly. Na některé uzly již nejsou aplikovány žádné operátory, protože bylo dosaženo již dříve získaného řešení. To je ve schématu znázorněno zpětnou smyčkou vedoucí k zacyklení. Ve schématu je zobrazena pouze jedna zpětná smyčka jako příklad, další nejsou vykreslené z důvodu zachování přehlednosti schématu. Postupnou aplikací operátorů na jednotlivé stavy jsou nalezena dvě řešení. Cesta k cílovému řešení je vykreslena výrazněji. Jedno z řešení je získáno v sedmi krocích, druhé řešení je získáno po osmi krocích. Stavový prostor může být prohledáván třemi způsoby. Při prohledávání do šířky jsou na jeden uzel aplikovány všechny možné operátory. Po úplné expanzi uzlu se zjišťuje, zda některý z nových uzlů nereprezentuje cílový stav a pokud ne, operátory jsou aplikovány na uzly v nově vzniklé vrstvě a to ve stejném pořadí, jak uzly vznikly. Ve schématu to odpovídá pohybu po celé šířce ve směru dolů. Při prohledávání do hloubky se na nově vzniklý uzel aplikuje pouze jeden operátor. Pokud nový uzel není reprezentací cílového stavu, bude na něj aplikován opět jeden operátor. Tento postup se opakuje do té doby, pokud se již s nově vzniklým uzlem nedají provádět žádné operace nebo byl nalezen cílový stav. Pokud byla tato cesta řešení neúspěšná, řešení se vrací o krok zpět a je aplikován jiný operátor. Ve schématu to odpovídá pohybu do hloubky (dolů) a po té dále do šířky. Tento postup bývá méně přehledný a je náročnější na uchovávání informací o předchozích postupech, než je tomu u metody prohledávání do šířky. Pokud o řešeném problému existuje bližší informace, je možné ji vhodně interpretovat a využít pro informované prohledávání. Ve skutečnosti jde o upravené prohledávání do šířky. Po aplikaci všech operátorů na daný uzel je vypočtena tzv. hodnotící funkce podle jejíž hodnoty je vybrán nejvhodnější uzel pro další expanzi. Toto řešení vede k nalezení optimální cesty (nejrychlejší, nejkratší) vzhledem k definici hodnotící funkce.
8
aplikovatelné operátory: naplnit (popř. doplnit) nádobu vyprázdnit jednu nádobu 0
doplnit druhou nádobu
3
0
3
5
0
5
3
3
3
0
0
3
0
0
0
3
0
0
5
3
3
0
0
1
5
3
5
3
0
0
3
3
5
1
0
0
5
0
1
3
0
1
5
0
0
1
0
3
1
0
5
0
0
0
4
3
5
0
1
3
0
Obr. 2.1 Levá část stromu stavového prostoru řešení příkladu.
9
aplikovatelné operátory: naplnit (popř. doplnit) nádobu vyprázdnit jednu nádobu 0
0
doplnit druhou nádobu
0
5
3
5
2
3
0
0
5
0
5
2
0
0
0
0
2
5
0
0
0
2
0
0
3
2
3
5
0
5
3
0
0
3
0
0
5
3
2
3
3
5
3
4
0
5
2
0
3
5
3
0
0
4
2
5
Obr. 2.2 Pravá část stromu stavového prostoru řešení příkladu.
10
2.1.3 Predikátová logika Systémy umělé inteligence (a tedy i expertní systémy) používají určité metody automatického sestavování plánu činnosti. Model prostředí, který je uvažován (je předmětem činnosti systému), musí být vytvořený na principech logických schémat. Logické schéma pro reprezentaci znalostí je vyjádřené pomocí matematické logiky, především pak jazykem predikátové logiky [17]. Základním výrazem jazyka predikátové logiky je formule. Základními prvky jazyka jsou: • logické hodnoty, • logické spojky, • logické kvantifikátory, • individuové konstanty a proměnné, • funkční symboly, • predikátové symboly. logické hodnoty T pravda (true) F nepravda (false)
individuové konstanty a proměnné malá písmena (např. a, b, c, ...)
logické spojky ' negace ∧ konjunkce ∨ disjunkce ⇒ implikace ⇔ ekvivalence = rovnost
logické kvantifikátory ∀ univerzální ∃ existenční
funkční symboly malá písmena a řetězce (např. f, g, h, zdvihni, ...)
predikátové symboly velká písmena a řetězce (např. A, B, C, ODKRYTÝ, ...) Ze základních prvků jazyka predikátové logiky jsou složeny tyto výrazy: termy, atomické formule a formule. Uvedené výrazy jsou definovány takto:
♦ ♦
♦ ♦ ♦
♦ ♦ ♦
termy každá individuová konstanta a individuová proměnná tvoří term f(t1,t2,t3, ...) je term, kde f je funkční symbol a ti jsou termy atomické formule logické hodnoty T a F jsou atomické formule P(t1,t2,t3, ...) je atomická formule, kde P je predikátový symbol a ti jsou termy výraz t1=t2 je atomická formule, kde ti jsou termy formule každá atomická formule je formule A', A∧B, A∨B, A⇒B a A⇔B jsou formule, kde A i B jsou formule ∀x(a) a ∃x(a) jsou formule, kde x je individuová proměnná a A je formule
Význam základních prvků jazyka je dokumentován na následujícím příkladu. Jsou dány jednoduché formule A a B ve tvaru A = ∀x(P(x)⇒Q(x)) 11
B = ∀x((KVÁDR(x)∧ZDVIHNUTÝ(x))⇒POLOŽENÝ'(x)) Formule A je obecná a vyjadřuje fakt, že pro každé x, pro které platí P(x), vyplývá platnost predikátu Q(x). Formule B reprezentuje skutečnost, že každý objekt x, který je kvádrem a současně je zdvihnutý, už nemůže být položený. KVÁDR, ZDVIHNUTÝ, POLOŽENÝ jsou jednomístné predikáty. x představuje individuovou proměnnou a je možné za ní dosadit název kvádru, např. a, b nebo c. Základní výraz predikátové logiky, formule, je jen posloupností symbolů. Svůj význam dostává až interpretací. Interpretace je vztah mezi syntaktickými objekty jazyka (soustava formulí) a některou jeho interpretační strukturou (stav prostředí, ve kterém je řešen problém). Formule, které jsou pravdivé ve všech interpretacích se nazývají logicky pravdivé. Právě prokázání logické pravdivosti je řešením problému, bohužel však z praktického hlediska není možné, aby bylo ověření provedeno ve všech interpretacích. Predikátová logika však poskytuje prostředky, jak se takovému postupu vyhnout [25]. Použití predikátové logiky včetně prokazování platnosti lze ukázat na následujících dvou příkladech. V prvním z nich je řešen jednoduchý problém; budou zde zavedeny pojmy tautologie a modus ponens. Příklad Zadání: Cena počítačových čipů roste pouze tehdy, když sílí yen (japonská měna). Yen sílí pouze tehdy, když dolar oslabuje a dolar oslabuje, když yen sílí. Dokud cena čipů roste, dolar musí klesat. Prokažte platnost/neplatnost tvrzení. Řešení: Logické proměnné jsou definovány takto: C = cena čipů roste Y = yen sílí D = dolar oslabuje Problém je zapsán takto: C ⇒ Y (Y ⇒ D) ∧ (Y ⇒ D) C_________________ ∴ D
-
1. premisa 2. premisa 3. premisa výrok
Druhá premisa může být zjednodušena: C ⇒ Y Y ⇔ D C_____ ∴ D Premisa Y ⇔ D dovoluje provést substituci D za Y v premise C ⇒ Y C ⇒ D Y ⇔ D C_____ ∴ D a potom platí C ⇒ D C_____ ∴ D
12
což je tzv. modus ponens. Modus ponens lze interpretovat tak, že když z tvrzení C vyplývá tvrzení D a tvrzení C platí, potom platí i tvrzení D. V našem příkladu postupným zjednodušováním vznikl modus ponens, který je podle výše uvedené interpretace vždy platný a zadání je splněno. Jinými slovy, ze tří definovaných premis skutečně plyne proklamovaný výrok. Tvrzení, které je platné ve všech interpretacích, se nazývá tautologií. Modus ponens je tedy tautologií. V druhém příkladě je dokumentován postup odvozování, běžně používaný v programech umělé inteligence i v expertních systémech. Konkrétně jde o použití rezolučního pravidla, které je aplikováno na analyzované tvrzení. Hlavním úkolem rezoluční metody je inferovat (tzn. odvodit) nové klauzule1, tzv. rezolventy, ze dvou rodičovských klauzulí. Rezolventy by měly mít méně literálů2 než rodičovské klauzule. Poslední rezolventa je nesplnitelná klauzule. V expertních systémech se používá varianty s kontradikcí. Jde o prokázání platnosti negace teorému. Prakticky pak jde o testování dvojice klauzulí, kde v jedné se vyskytuje literál a ve druhé jeho negace. Prokázání platnosti formule kontradikcí (tedy prokázání její neplatnosti) se nazývá vyvrácení a za použití rezoluční metody pak rezoluční vyvrácení [23]. Příklad Zadání: Je definováno tvrzení pomocí dvou premis a výroku: Někteří programátoři nemají rádi chyby. Všichni programátoři mají rádi jakýkoliv úspěch. ∴ Žádná chyba není úspěch. Prokažte platnost/neplatnost tvrzení. Pozn. Pravidla českého jazyka dovolují použití dvojitého záporu ve větě. Tím může dojít k dezinterpretaci a špatnému přepisu do predikátů. Například výrok "Žádná chyba není úspěch." vlastně znamená "Všechny chyby nejsou úspěchem." Řešení: Definujme predikáty: P(x) = F(x) = S(x) = H(x,y)
x x x =
je programátor je chyba je úspěch x nemá rádo y
Zadání pak může být přepsáno takto:
∃x (P(x) ∧ ∀y (F(y) ⇒ H(x,y))) ∀x ((P(x) ⇒ (∀y (S(y) ⇒ H'(x,y))) ∀y' (F(y) ⇒ S'(y)) kde výrok byl již negován pro následující rezoluci. První premisa výše uvedeného tvrzení
∃x (P(x) ∧ ∀y (F(y) ⇒ H(x,y))) je postupně upravována následovně. Nejprve je použito eliminace implikace použitím ekvivalence p ⇒ q ≡ p' ∨ q. 1
Klauzule je logické spojení literálů (viz níže). Literál je atomický výraz nebo negovaný atomický výraz a nesmí obsahovat logická spojení (kvantifikátory, logické spojky).
2
13
∃x (P(x) ∧ ∀y (F'(y) ∨ H(x,y))) Dále jsou eliminovány existenční kvantifikátory ∃ použitím Skolemovy funkce. Je zavedena Skolemova konstanta a s takovou hodnotou, aby formule byla splněna. (P(a) ∧ ∀y (F'(y) ∨ H(a,y))) Formule je převedena do prenexové formy, která je tvořena sekvencí kvantifikátorů následovaných kombinací predikátů. ∀y (P(a) ∧
(F'(y) ∨ H(a,y)))
Dále jsou odstraněny univerzální kvantifikátory přiřazením hodnot všem proměnným. P(a) ∧
(F'(y) ∨ H(a,y))
První premisa je tedy převedena do dvou klauzulí P(a) (F'(y) ∨ H(a,y)) Podobně lze odvodit, že druhá premisa je převedena do klauzule P'(x) ∨ S'(y) ∨ H'(x,y) a negovaný výrok do dvou klauzulí F'(y) ∨ H(a,y) F(b) Nyní je nutné nalézt vhodné substituční případy (hodnoty proměnných) procesem unifikace. ”Vhodné” hodnoty pro unifikaci jsou takové, pro které jsou příslušné klauzule platné. První substitucí je y→b, která umožní odvodit platnost dvojice klauzulí F'(y) ∨ H(a,y) a F(b). Celý unifikační strom je uveden na obrázku níže. Výsledkem unifikace je klauzule nil, což znamená, že negované tvrzení neplatí a původní tvrzení je platné.
F'(y)∨H(a,y)
F(b)
P(a)
H(a,b)
P'(x)∨S'(y)∨H'(x,y)
S'(y)∨H'(a,y)
S'(b)
S(b)
nil
14
2.2
Procedurální schémata
Procedurální přístup k reprezentaci znalostí je založený na předpokladu, že znalosti typu vědět jak jsou primární v modelování procesů odvozování. Procedurální schémata kladou proto důraz na popis takových aspektů reprezentovaných znalostí, které hovoří o tom, jak objekty používat a jaké akce s nimi možno realizovat. Znalosti jsou reprezentované jako procedury (části programů), které určují možné akce s objekty prostředí a vztahy mezi nimi. V realizovaných systémech využívajících procedurálních schémat se dnes uplatňují tyto přístupy [21]: • •
•
Vyjádření řídící informace ve formě speciálních výrazů, tzv. teorém, které jsou součástí báze znalostí a reprezentují výpovědi o objektech a vztazích, které se vyskytují v prostředí. Vytvoření jazyka pro reprezentaci řídící informace, který je součástí schématu na reprezentaci znalostí. Tento jazyk je vytvářený na nižší úrovni, než samotné schéma, ale uživatel má přístup k množině jeho mechanismů, které umožňují specifikovat řídící proces. Vytvoření samostatného jazyka na reprezentaci řídící informace, který je používaný paralelně se schématem pro reprezentaci ostatních znalostí. Tato myšlenka tvoří základ přístupů k logickému programování.
Produkční systémy Produkční systémy jsou procedurální technikou reprezentace znalostí, která je založena na operaci s obrazci [22]. Produkční systém je nejčastěji lineárně uspořádaná dvojice pravidel, které se nazývají produkce, vyjádřená dvojicí: podmínka (situace) −> akce. Aplikace pravidla se uskuteční provedením akce, pokud v bázi údajů nastala daná situace. Produkční pravidla operují nad pracovní pamětí, která může být organizována různými způsoby. Produkční systém je tvořen třemi základními složkami: • souborem produkčních pravidel, které tvoří vlastní bázi znalostí, • bázi údajů, která reprezentuje konkrétní konzultovaný případ, • interpretem pravidel, který představuje řídící (inferenční, odvozovací) mechanismus. Přímé produkční systémy Přímé produkční systémy začínají svou činnost s určitým počátečním stavem pracovní paměti, který je činností produkčního systému postupně rozšiřován do té doby, dokud není dosažený zadaný cíl. Inferenční mechanismus postupuje od faktů k cíli a realizuje tzv. přímé (dopředné) řetězení znalostí. Rozpoznávací cyklus pracuje následujícím způsobem: • nalezení všech pravidel, jejichž podmínkové části jsou splněny, • vyřazení takových pravidel, jejichž aplikace vede k výsledkům již v paměti obsažených, • použití rozpoznávacího cyklu pro výběr nejvhodnějšího produkčního pravidla. Pokud takové pravidlo neexistuje, nastává konec postupu, jinak je celý postup opakován (nalezení všech pravidel). Zpětné produkční systémy Zpětné produkční systémy pracují s inferenčním mechanismem, který postupuje od cíle, tj. hypotézy, k faktům a realizují tak zpětné řetězení. Hypotézu reprezentuje tvrzení, které má produkční systém verifikovat s použitím báze znalostí. Rozpoznávací cyklus pracuje následovně: • pokud je hypotéza v bázi znalostí, je vytvořeno jádro hypotézy a nalezena všechna produkční pravidla, jejichž akční části obsahují formy ekvivalentní s jádrem hypotézy, • výběr nejvhodnějšího pravidla strategií řešení konfliktů,
15
•
2.3
realizace pravidla po ověření jeho aplikovatelnosti; pokud podmínky aplikovatelnosti nejsou splněny, jsou zapsány do hypotézy a celý postup se opakuje do nalezení řešení.
Rámcová schémata
Rámce jsou dalším schématem reprezentace znalostí, které je používáno k popisovaní objektů v bázi znalostí. Základními prvky těchto schémat jsou tzv. rámce, které umožňují vyjádřit statické znalosti. V průběhu užívání rámce nabývají položky konkrétních hodnot. Vazba mezi rámci se dá znázornit grafem. Uzly rámcových schémat mají svou vnitřní strukturu, což je odlišné od sémantických sítí. Rámce jsou obvykle doplněna o pravidla, která umožňují odvozovat v bázi znalostí.
Auto
typ: vozidlo pohon: motor …
Auto
Auto
typ: auto pohon: motor účel: přeprava osob …
typ: auto pohon: motor účel: přeprava nákladu …
Ford
typ: osobní auto pohon: motor účel: přeprava osob výrobce: Ford … …
Obr. 2.3 Příklad rámců.
16
3
Strategická hra
Níže uvedený příklad strategické hry je ukázkou možností jednoduchého expertního systému vytvořeného v CLIPSu. Jde o problém soupeření uživatele a počítače formou hry, jejíž strategie je dokazatelná a především může být analyticky popsána. Popis strategie má formu množiny faktů ve tvaru "vykonej akci, když nastanou určité podmínky". Hra je velmi jednoduchá, jde o střídavé odebírání 1 až 3 zápalek z hromádky. Vstupními hodnotami je počet zápalek v hromádce, a určení začínajícího hráče. Strategie se řídí velikostí zbytku po celočíselném dělení zbývajících zápalek číslem 4. Při vhodně zvoleném počtu zápalek tedy nemůže začínající hráč prohrát (dodrží-li strategii), naopak nezačínající hráč pak může vyhrát jen po chybě začínajícího. Hra musí být spuštěna z určitého definovaného bodu, což je zajištěno vložením inicializačního faktu (faze vybirani-hrace). Fakt je níže použit v pravidle vyber-hrace. (deffacts inicializacni-faze (faze vybirani-hrace))
Následuje vložení čtyř faktů, určujících taktiku počítače. (deffacts pocty-zapalek (pocitac-bere 1 jestlize-zbyva-zbytek (pocitac-bere 1 jestlize-zbyva-zbytek (pocitac-bere 2 jestlize-zbyva-zbytek (pocitac-bere 3 jestlize-zbyva-zbytek
1) 2) 3) 0))
Další pravidlo zahajuje běh systému - bude tedy splněno jako první prostřednictvím již vloženého faktu (faze vybirani-hrace). Pravidlo vypíše na obrazovku monitoru zprávu Kdo bere prvni (pocitac: c clovek: h)? a očekává vstup znaku z klávesnice. Správnost vloženého znaku je kontrolována pravidly dobry-vyber-hrace a spatny-vyber-hrace. (defrule vyber-hrace (faze vybirani-hrace) => (printout t "Kdo bere prvni (pocitac: p (assert (vyber-hrace =(read))))
clovek: c)? ")
Pravidlo dobry-vyber-hrace zkontroluje, zda byl ve fázi vybírání hráče (reprezentované faktem (faze vybirani-hrace)) vložen znak c nebo h, a v kladném případě odstraní nepotřebné fakty. Dále je určeno, který hráč je na tahu (fakt (hraje-hrac h) nebo (hraje-hrac c)), a je iniciována další fáze běhu programu vložením faktu (faze vyber-pocet-zapalek). (defrule dobry-vyber-hrace ?faze <- (faze vybirani-hrace) ?vyber <- (vyber-hrace ?hrac&p | c) => (retract ?faze ?vyber) (assert (hraje-hrac ?hrac)) (assert (faze vyber-pocet-zapalek)))
Pravidlo spatny-vyber-hrace ošetřuje případ vložení nepovolených znaků tak, že dochází k opětovnému dotazu na začínajícího hráče pravidlem dobry-vyber-hrace znovuvložením faktu (faze vybirani-hrace).
17
(defrule spatny-vyber-hrace ?faze <- (faze vybirani-hrace) ?vyber <- (vyber-hrace ?hrac&~p&~c) => (retract ?faze ?vyber) (assert (faze vybirani-hrace)) (printout t "Vyber p nebo c." crlf))
Fáze výběru počtu zápalek je zajištěna pravidlem volba-poctu-zapalek. V něm je proveden výpis na obrazovku (dotaz na počet) a vstup zvoleného čísla z klávesnice. Číslo je zaznamenáno vložením faktu (volba-poctu-zapalek xxx). (defrule volba-poctu-zapalek (faze vyber-pocet-zapalek) => (printout t "S kolika zapalkami chcete zacit? ") (assert (volba-poctu-zapalek =(read))))
Pro zajištění korektního vstupu je vložené číslo testováno v pravidle dobry-pocetzapalek. Je-li vložené číslo celé a větší než 0, dojde k inicializaci další fáze programu vložením faktu (zbyva-zapalek xxx). Tento fakt představuje hypotetickou hromádku zápalek, ze které se bude odebírat. (defrule dobry-pocet-zapalek ?faze <- (faze vyber-pocet-zapalek) ?vyber <- (volba-poctu-zapalek ?pocet&:(integerp ?pocet)&:(> ?pocet 0)) => (retract ?faze ?vyber) (assert (zbyva-zapalek ?pocet)))
V pravidle spatny-pocet-zapalek je definováno, jak se bude postupovat v případě špatného zadání. Je-li zvolený počet necelé číslo nebo je menší než 0, je znovu aktivována fáze výběru počtu zápalek. (defrule spatny-pocet-zapalek ?faze <- (faze vyber-pocet-zapalek) ?vyber <- (volba-poctu-zapalek ?pocet&~:(integerp ?pocet)|:(<= ?pocet 0)) => (retract ?faze ?vyber) (assert (faze vyber-pocet-zapalek)) (printout t "Vyberte cele cislo vetsi nez 0." crlf))
Systém pracuje v cyklu, který je ukončen prohrou hráče-člověka nebo počítače. Prohra počítače je ošetřena pravidlem pocitac-prohral. Pro prohru počítače musí být splněny dvě podmínky: zbývající počet zápalek je roven 1 a na tahu je hráč označený p. (defrule pocitac-prohral (zbyva-zapalek 1) (hraje-hrac p) => (printout t "Pocitac musi vzit posledni zapalku!" crlf) (printout t "Pocitac prohral!" crlf))
Prohra hráče je ošetřena pravidlem clovek-prohral. Pro prohru hráče musí být splněny dvě podmínky: zbývající počet zápalek je roven 1 a na tahu je hráč označený c.
18
(defrule clovek-prohral (zbyva-zapalek 1) (hraje-hrac c) => (printout t "Musite vzit posledni zapalku!" crlf) (printout t "Prohral jste!" crlf))
Smyčka programu je tvořena pravidly, ve kterých je zajištěno odebírání zápalek, t.j. vstup zvoleného počtu zápalek z klávesnice (v případě hráče), nebo generování počtu podle taktiky (v případě počítače). Pravidlo clovek-bere je splněno v případě, že na tahu je hráč označený c a zbývá více než jedna zápalka. Následuje dotaz na počet a vložení příslušného faktu se zadaným číslem. (defrule clovek-bere (zbyva-zapalek ?pocet&:(> ?pocet 1)) (hraje-hrac c) => (printout t "Kolik zapalek chcete vzit? ") (assert (clovek-bere =(read))))
Vložený počet zápalek musí být opět testován (číslo od 1 do 3). To je zajištěno pravidlem clovek-bere-dobre, které pracuje podobně jako pravidlo dobry-pocet-zapalek. Je-li pravidlo splněno, je odstraněn fakt (zbyva-zapalek xxx) obsahující počet zbývajících zápalek a vložen nový fakt s již odečteným počtem odebraných zápalek. Vše je doprovázeno výpisem na obrazovku. Jako poslední je vložen fakt (hraje-hrac p), čímž se předává tah počítači. (defrule clovek-bere-dobre ?zapalky <- (zbyva-zapalek ?pocet) ?tah <- (clovek-bere ?vyber) ?kdo-bere <- (hraje-hrac c) (test (and (integerp ?vyber) (>= ?vyber 1) (<= ?vyber 3) (< ?vyber ?pocet))) => (retract ?zapalky ?tah ?kdo-bere) (bind ?novy-pocet (- ?pocet ?vyber)) (assert (zbyva-zapalek ?novy-pocet)) (printout t ?novy-pocet " zapalek zbyva." crlf) (assert (hraje-hrac p)))
Došlo-li k nesprávnému vstupu (vložení nepovoleného čísla hráčem), je znovu iniciován dotaz na počet odebíraných zápalek znovuvložením faktu (hraje-hrac c). To způsobí znovusplnění pravidla clovek-bere. (defrule clovek-bere-spatne (zbyva-zapalek ?pocet) ?tah <- (clovek-bere ?vyber) ?kdo-bere <- (hraje-hrac c) (test (or (not (integerp ?vyber)) (< ?vyber 1) (> ?vyber 3) (>= ?vyber ?pocet))) => (printout t "Pocet zapalek musi byt 1 az 3." crlf) (retract ?tah ?kdo-bere) (assert (hraje-hrac c)))
19
Tah počítače je zajištěn pravidlem pocitac-bere. Zde samozřejmě nedochází k dotazu na počet jako v případě hráče, ale potřebné číslo je "vypočteno" podle výše popsané strategie. Nejprve je vypočítán zbytek xxx po celočíselném dělení (modulo), a ten je použit pro výběr jedno ze 4 faktů (pocitac-bere yyy jestlize-zbyva-zbytek xxx). Číslo yyy pak určuje, kolik zápalek počítač odebere. Splněním pravidla pro příslušný fakt opět vyvolá změnu v aktuálním počtu zbývajících zápalek (vložením faktu (zbyvazapalek zzz)). Jako poslední je vložen fakt (hraje-hrac c), čímž se předává tah hráči. (defrule pocitac-bere ?kdo-bere <- (hraje-hrac p) ?zapalky <- (zbyva-zapalek ?pocet&:(> ?pocet 1)) (pocitac-bere ?cislo jestlize-zbyva-zbytek =(mod ?pocet 4)) => (retract ?kdo-bere ?zapalky) (bind ?novy-pocet (- ?pocet ?cislo)) (printout t "Pocitac bere " ?cislo " zapalek." crlf) (printout t ?novy-pocet " zapalek zbyva." crlf) (assert (zbyva-zapalek ?novy-pocet)) (assert (hraje-hrac c)))
Funkci programu lze předvést na následující jednoduché ukázce. Předpokládejme, že člověk začne jako první brát zápalky a že počáteční počet zápalek je 9. Program je nejdříve spuštěn příkazy CLIPSu (reset) a (run). Po té již probíhá komunikace (viz níže uvedený výpis z obrazovky). CLIPS> (reset) CLIPS> (run) Kdo bere prvni (pocitac: p clovek: c)? c S kolika zapalkami chcete zacit? 9 Kolik zapalek chcete vzit? 3 6 zapalek zbyva. Pocitac bere 1 zapalek. 5 zapalek zbyva. Kolik zapalek chcete vzit? 1 4 zapalek zbyva. Pocitac bere 3 zapalek. 1 zapalek zbyva. Musite vzit posledni zapalku! Prohral jste! CLIPS>
20
4
Analýza procesu
Následující příklad popisuje část analýzy procesu startování motoru auta. Kód obsahuje deklaraci 6 globálních proměnných: citac_experta, citac_pokrocileho, citac_zacatecnika, citac_bez_odezvy, cas_startu, maximalni_cas. Proměnné mají následující význam: • • • • • •
citac_experta - počet pokusů o nastartování motoru na úrovni experta (zkušeného řidiče), citac_pokrocileho - počet pokusů o nastartování motoru na úrovni pokročilého, citac_zacatecnika - počet pokusů o nastartování motoru na úrovni začátečníka, citac_bez_odezvy - počet neúspěšných pokusů o nastartování motoru, cas_startu - čas startování motoru, maximalni_cas - maximální doba povolená k nastartování motoru.
Dále jsou v programu definovány dva nesetříděné fakty stavy_auta a akce, každý s několika sloty (položkami). Pro uvedenou část programu je významný druhý fakt, který obsahuje sloty typ, hodnota, cas, casova_znacka. V bázi faktů se tak za běhu programu může vyskytovat například fakt (akce (typ pas) (hodnota 1) (casova_znacka 3)). Fakt představuje akci (úkon), kterou provedl řidič v čase t=3, přičemž se jednalo o uvedení (bezpečnostních) pásů do stavu 1 (zapnutí). Funkce programu je dokumentována na pravidle expert_startuje_motor. Pravidlo je splněno za dvou podmínek: 1. byly provedeny potřebné akce, 2. akce byly provedeny ve správném pořadí. Splnění pravidla odpovídá nastartování motoru. (defrule expert_startuje_motor "Uroven experta" (declare (salience 3)) ?f1 <- (akce (typ pas) (hodnota 1) (casova_znacka ?t)) ?f2 <- (akce (typ rucni_brzda_zatazena) (hodnota 0) (casova_znacka ?t1)) ?f3 <- (akce (typ brzda) (hodnota 1) (casova_znacka ?t2)) ?f4 <- (akce (typ spojka) (hodnota 1) (casova_znacka ?t3)) ?f5 <- (akce (typ razeni) (hodnota 0) (casova_znacka ?t4)) ?f6 <- (akce (typ klicek_zapalovani) (hodnota 1) (casova_znacka ?t5)) ?f7 <- (motor nestartuje) (test (= (+ ?t 1) ?t1)) (test (= (+ ?t 2) ?t2)) (test (= (+ ?t 3) ?t3)) (test (= (+ ?t 4) ?t4)) (test (= (+ ?t 5) ?t5)) => (assert (motor startuje)) (retract ?f1 ?f2 ?f3 ?f4 ?f5 ?f6 ?f7) (bind ?*citac_experta* (+ ?*citac_experta* 1)) (printout evaluation "ULOHA: nastartovani motoru" crlf) (printout evaluation "CAS: " (- (integer (time)) ?*cas_startu*) " vterin" crlf) (printout evaluation "CHYBY: 0" crlf crlf) )
Vysvětlení LHS (levostranné části) pravidla: 1. Pravidlu je přiřazena relativně nejvyšší priorita ve vztahu k ostatním pravidlům (viz celkový výpis níže). Nejvyšší priorita zajišťuje, že systém se bude snažit splnit toto pravidlo jako první, jinými slovy nejprve zjišťuje, zda bylo auto nastartováno na "expertní" úrovni.
21
2. Zjišťuje se přítomnost faktu (akce (typ pas) (hodnota 1) (casova_znacka xxx)) v bázi faktů. Existuje-li fakt, je do proměnné t uložena hodnota xxx odečtená z příslušného slotu (význam: čas zapnutí pásů). Adresa faktu je uložena do proměnné f1. 3. Podobně jako v bodě 2. je zjištěna existence dalších 6 faktů, odpovídajících těmto akcím: povolení ruční brzdy, sešlápnutí brzdového pedálu, sešlápnutí pedálu spojky, zařazení neutrálu, otočení klíčkem zapalování. Příslušné časové okamžiky provedení jednotlivých akcí jsou uloženy v proměnných t1 až t5, adresy faktů jsou uloženy do proměnných f2 až f7. 4. Zjištění existence faktu (motor nestartuje), který odpovídá stavu nenastartovaného motoru. 5. Ověření, jestli platí následující rovnice: t+1=t1, t+2=t2, t+3=t3, t+4=t4, t+5=t5. Prakticky to znamená, že t
?*citac_experta* = 0*) ?*citac_pokrocileho* = 0*) ?*citac_zacatecnika* = 0*) ?*citac_bez_odezvy* = 0*) ?*cas_startu* = 0*) ?*maximalni_cas* = 10*)
(deftemplate stavy_auta "Konstanty pouzite v rizeni auta" (slot brzda) (slot rucni_brzda_zatazena) (slot spojka) (slot klicek_zapalovani) (slot razeni) (slot pas) ) ;sablona stavy_auta (deftemplate akce "Akce ridice pri rizeni" (slot typ) ;typ akce (slot hodnota) ;hodnota akce (slot cas) ;cas akce (slot casova_znacka) ;poradi akce ) ;sablona akce ; pravidla pro nastartovani motoru (defrule expert_startuje_motor "Uroven experta" ; hodnota salience je nejvyssi mei 4 aktivnimi pravidly (declare (salience 3)) ; tato cast pravidla zajistuje, ze budou provedeny vsechny dilci akce pri
22
; startu motoru ; prvni akce je zapnuti bepecnostnich pasu ?f1 <- (akce (typ pas) (hodnota 1) (casova_znacka ?t)) ; dalsi akce je odbrzdeni rucni brzdy ?f2 <- (akce (typ rucni_brzda_zatazena) (hodnota 0) (casova_znacka ?t1)) ; dalsi akce je seslapnuti brzdoveho pedalu ?f3 <- (akce (typ brzda) (hodnota 1) (casova_znacka ?t2)) ; dalsi akce je seslapnuti pedalu spojky ?f4 <- (akce (typ spojka) (hodnota 1) (casova_znacka ?t3)) ; dalsi akce je zarazeni neutralu ?f5 <- (akce (typ razeni) (hodnota 0) (casova_znacka ?t4)) ; dalsi akce je otoceni klickem zapalovani ?f6 <- (akce (typ klicek_zapalovani) (hodnota 1) (casova_znacka ?t5)) ?f7 <- (motor nestartuje) ; Nasleduje test spravnosti poradi provedenych akci. Spravne poradi je: ; zapnuti pasu, uvolneni rucni brzdy, seslapnuti brzdoveho pedalu, ; seslapnuti pedalu spojky, zarazeni neutralu, otoceni klickem zapalovani (test (= (+ ?t 1) ?t1)) (test (= (+ ?t 2) ?t2)) (test (= (+ ?t 3) ?t3)) (test (= (+ ?t 4) ?t4)) (test (= (+ ?t 5) ?t5)) => ; Nasledujici vlozeni faktu oznacuje, ze byl ucinen pokus o nastartovani (assert (motor startuje)) ; akce byly zaznamenany a jsou odstraneny z baze faktu (retract ?f1 ?f2 ?f3 ?f4 ?f5 ?f6 ?f7) ; inkrementace citace pokusu experta (bind ?*citac_experta* (+ ?*citac_experta* 1)) (printout evaluation "ULOHA: nastartovani motoru" crlf) (printout evaluation "CAS: " (- (integer (time)) ?*cas_startu*) " vterin" crlf) (printout evaluation "CHYBY: 0" crlf crlf) ) ; expert_startuje_motor (defrule pokrocily_startuje_motor "Uroven pokrocileho" ; hodnota salience je nizsi nez u experta ale vyssi nez u zacatecnika (declare (salience 2)) ?f1 <- (akce (typ pas) (hodnota 1) (casova_znacka ?t)) ?f2 <- (akce (typ rucni_brzda_zatazena) (hodnota 0) (casova_znacka ?t1)) ?f3 <- (akce (typ brzda) (hodnota 1) (casova_znacka ?t2)) ?f4 <- (akce (typ spojka) (hodnota 1) (casova_znacka ?t3)) ?f5 <- (akce (typ razeni) (hodnota 0) (casova_znacka ?t4)) ?f6 <- (akce (typ klicek_zapalovani) (hodnota 1) (casova_znacka ?t5)) ?f7 <- (motor nestartuje) ; Nasleduje test spravnosti poradi provedenych akci. Spravne poradi je: ; zapnuti pasu, uvolneni rucni brzdy, seslapnuti brzdoveho pedalu, ; seslapnuti pedalu spojky, zarazeni neutralu, otoceni klickem zapalovani ; Mezi nutnymi akcemi mohou byt provedeny dalsi. (test (> ?t1 ?t)) (test (> ?t2 ?t1)) (test (> ?t3 ?t2)) (test (> ?t4 ?t3)) (test (> ?t5 ?t4)) => ; Nasledujici vlozeni faktu oznacuje, ze byl ucinen pokus o nastartovani (assert (motor startuje)) ; akce byly zaznamenany a jsou odstraneny z baze faktu (retract ?f1 ?f2 ?f3 ?f4 ?f5 ?f6 ?f7)
23
; inkrementace citace pokusu pokrocileho (bind ?*citac_pokrocileho* (+ ?*citac_pokrocileho* 1)) (printout evaluation "ULOHA: nastartovani motoru" crlf) (printout evaluation "CAS: " (- (integer (time)) ?*cas_startu*) " vterin" crlf) (printout evaluation "CHYBY: 1 nebo vice" crlf) (printout evaluation "VYSVETLENI: Pri startu byly provedeny dalsi akce." crlf ) ) ; pokrocily_startuje_motor (defrule zacatecnik_startuje_motor "Uroven zacatecnika" ; hodnota salience je mensi nez u pokrocileho ale vyssi nez u urovne ; "nenastartovani" (declare (salience 1)) ; Nasleduje test, zda byy provedeny vsechny nutne akce ?f1 <- (akce (typ pas) (hodnota 1) (casova_znacka ?t)) ?f2 <- (akce (typ rucni_brzda_zatazena) (hodnota 0) (casova_znacka ?t1)) ?f3 <- (akce (typ brzda) (hodnota 1) (casova_znacka ?t2)) ?f4 <- (akce (typ spojka) (hodnota 1) (casova_znacka ?t3)) ?f5 <- (akce (typ razeni) (hodnota 0) (casova_znacka ?t4)) ?f6 <- (akce (typ klicek_zapalovani) (hodnota 1) (casova_znacka ?t5)) ?f7 <- (motor nestartuje) ; Akce nemusi byt provedeny v urcitem poradi. Pouze musi byt vsechny ; provedeny. => ; Nasledujici vlozeni faktu oznacuje, ze byl ucinen pokus o nastartovani (assert (motor startuje)) ; akce byly zaznamenany a jsou odstraneny z baze faktu (retract ?f1 ?f2 ?f3 ?f4 ?f5 ?f6 ?f7) ; inkrementace citace pokusu zacatecnika (bind ?*citac_zacatecnika* (+ ?*citac_zacatecnika* 1)) (printout evaluation "ULOHA: nastartovani motoru" crlf) (printout evaluation "CAS: " (- (integer (time)) ?*cas_startu*) " vterin" crlf) (printout evaluation "CHYBY: 1 nebo vice" crlf) (printout evaluation "VYSVETLENI: Akce byly provedeny v nespravnem poradi." crlf) ) ; zacatecnik_startuje_motor (defrule motor_se_nenastartoval "Motor se ne a ne nastartovat" ; Kontrola, zda byl motor startovan (motor nestartuje) ; Kontrola, zda cas prekrocil casovy limit (test (> (integer (time)) (+ ?*maximalni_cas* ?*cas_startu*))) => ; inkrementace citace nenastartovani motoru (bind ?*citac_bez_odezvy* (+ ?*citac_bez_odezvy* 1)) (printout evaluation "Motor se nenastartoval" crlf) (printout evaluation "CAS: " (- (integer (time)) ?*cas_startu*) "vterin" crlf crlf) ) ; motor_se_nenastartoval
24
5
Symbolická analýza
Další příklad je ukázkou symbolické analýzy pomocí expertního systému. Jde o řešení hádankářského problému, tzv. slovního puzzle. Zadání problému tvoří rovnice představující součet dvou šesticiferných čísel. Číslice jsou ovšem nahrazeny symboly - písmeny. Úkolem je přiřadit písmenům číslice tak, aby rovnice platila. GERALD + DONALD -----= ROBERT Základem řešení problému v CLIPSu je generování všech možných kombinací dvojic číslic 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 a písmen G, E, R, A, L, D, O, N, B, T ve formě faktů. Nejprve je však nutné zajistit vložení faktů (cislo x) a (pismeno y), kde x a y jsou výše uvedené číslice a písmena. Vložení faktů probíhá v pravidle start, které je vždy splněno. (defrule start => (printout t t "Zadani problemu:" t t) (printout t " GERALD" t) (printout t " + DONALD" t) (printout t " ------" t) (printout t " = ROBERT" t t) (assert (cislice 0) (cislice 1) (cislice 2) (cislice 3) (cislice 4) (cislice 5) (cislice 6) (cislice 7) (cislice 8) (cislice 9) (pismeno G) (pismeno E) (pismeno R) (pismeno A) (pismeno L) (pismeno D) (pismeno O) (pismeno N) (pismeno B) (pismeno T)))
Kombinace dvojic číslice-písmeno jsou generovány pravidlem generuj_kombinace tak, že jsou vloženy fakty (kombinace x y). (defrule generuj_kombinace (cislice ?x) (pismeno ?a) => (assert (kombinace ?a ?x)))
25
Vlastní řešení probíhá v LHS (levostranné části) pravidla nalezni-reseni. V pravidle jsou postupně zadány vztahy mezi písmeny (číslicemi) zprava daného vztahu: 1. 2. 3. 4. 5. 6.
je zvoleno číslo d odpovídající písmenu D, je zvoleno číslo t odpovídající písmenu T tak, že není rovno d, čísla jsou zkontrolována tak, že musí platit (d+d) mod 10 = t, je zvoleno číslo l odpovídající písmenu L tak, že není rovno l, d, ani t, je zvoleno číslo r odpovídající písmenu R tak, že není rovno r, d, t, ani l, čísla jsou zkontrolována tak, že musí platit (d+d+10*l+10*l) mod (10*r+t), 7. ...
100
=
V RHS (pravostranné části) výkonného pravidla je pak proveden výpis nalezených čísel ve formátu zadání. V případě, kdy zadání nemá řešení, nebude pravidlo naleznireseni splněno a program bude ukončen bez jakéhokoliv upozornění. K řešení příkladu je potřeba poznamenat, že se jedná o použití paměťově náročného algoritmu. Je to dáno množstvím obrazů v LHS, které je potřeba splnit (najít jejich protějšky v existujících faktech), přičemž faktů je vygenerováno značné množství (kombinace písmen a číslic). (defrule nalezni-reseni (kombinace D ?d) (kombinace T ?t&~?d) (test (= (mod (+ ?d ?d) 10) ?t)) (kombinace L ?l&~?d&~?t) (kombinace R ?r&~?d&~?t&~?l) (test (= (mod (+ ?d ?d (* 10 ?l) (* 10 ?l)) 100) (+ (* 10 ?r) ?t))) (kombinace A ?a&~?d&~?t&~?l&~?r) (kombinace E ?e&~?d&~?t&~?l&~?r&~?a) (test (= (mod (+ ?d ?d (* 10 ?l) (* 10 ?l) (* 100 ?a) (* 100 ?a)) 1000) (+ (* 100 ?e) (* 10 ?r) ?t))) (kombinace N ?n&~?d&~?t&~?l&~?r&~?a&~?e) (kombinace B ?b&~?d&~?t&~?l&~?r&~?a&~?e&~?n) (test (= (mod (+ ?d ?d (* 10 ?l) (* 10 ?l) (* 100 ?a) (* 100 ?a) (* 1000 ?r) (* 1000 ?n)) 10000) (+ (* 1000 ?b) (* 100 ?e) (* 10 ?r) ?t))) (kombinace O ?o&~?d&~?t&~?l&~?r&~?a&~?e&~?n&~?b) (kombinace G ?g&~?d&~?t&~?l&~?r&~?a&~?e&~?n&~?b&~?o) (test (= (+ ?d ?d (* 10 ?l) (* 10 ?l) (* 100 ?a) (* 100 ?a) (* 1000 ?r) (* 1000 ?n) (* 10000 ?e) (* 10000 ?o) (* 100000 ?g) (* 100000 ?d)) (+ (* 100000 ?r) (* 10000 ?o) (* 1000 ?b) (* 100 ?e) (* 10 ?r) ?t))) => (printout t "Reseni je:" t t) (printout t " G = " ?g t) (printout t " E = " ?e t)
26
(printout (printout (printout (printout (printout (printout (printout (printout (printout (printout (printout (printout (printout
t t t t t t t t t t t t t
" R = " ?r t) " A = " ?a t) " L = " ?l t) " D = " ?d t) " O = " ?o t) " N = " ?n t) " B = " ?b t) " T = " ?t t) t) " " ?g ?e ?r " + " ?d ?o ?n " " "------" " = " ?r ?o ?b
?a ?l ?d t) ?a ?l ?d t) t) ?e ?r ?t t t))
Funkci programu lze předvést na následující jednoduché ukázce. Po spuštění je na obrazovku vypsáno zadání problému ve formě rovnice. Po relativně rychle provedeném řešení (t<1 sec na Pentium Celeron/400) jsou vypsány odpovídající dvojice písmeno - číslice. Na závěr je vypsáno řešení ve tvaru zadání s nahrazenými písmeny. CLIPS> (reset) CLIPS> (run) Zadani problemu: GERALD + DONALD -----= ROBERT Reseni je: G E R A L D O N B T
= = = = = = = = = =
1 9 7 4 8 5 2 6 3 0
197485 + 526485 -----= 723970 CLIPS>
27
6
Plánování strategie
Následující příklad řeší další klasický problém umělé inteligence. Jde o plánování ve formě hledání cesty (zde cesta opice k banánům). Vstupem je popis prostředí, skládajícího se z 5 místností, 3 pohovek (zelená, modrá a červená), velkého polštáře, 3 klíčů (zelený, modrý a červený), a žebříku. Opice a věci mají následující vlastnosti a jsou rozmístěny takto: 1. 2. 3. 4. 5. 6. 7. 8.
opice je v místnosti 3 na zelené pohovce a nic nedrží, zelená pohovka je těžká, červená pohovka je v místnosti 3 a je těžká, velký polštář je na červené pohovce, červená truhla obsahuje žebřík a odemyká se červeným klíčem, modrá truhla je v místnosti 4 na stropě, obsahuje banány a odemyká se modrým klíčem, modrá pohovka je v místnosti 5 a je těžká, zelená truhla je v místnosti 5 na stropě, obsahuje modrý klíč a odemyká se červeným klíčem, 9. červený klíč je v místnosti 1, 10. cílem opice je najíst se banánů.
Problém je poměrně složitý, protože vyžaduje řešení mnoha situací, např. přesun do jiné místnosti, odemykání truhly, zdvihání předmětů, lezení po žebříku, a pod. Proto je i následující výpis zdrojového kódu dlouhý, začíná se však svou strukturou podobat profesionálním expertním systémům. V programu je opět zřetelně vidět přednost deklarativního programování, kdy data jsou oddělena od algoritmu. Algoritmus se stává obecným (v rámci daných vlastností použitých objektů). Stejný algoritmus lze použít pro řešení stejného problému v naprosto odlišném prostředí, daném použitím jiných faktů (počet místností, rozmístění předmětů, a pod). Následující šablony s názvy opice, vec, truhla a cil-je předepisují formát faktů, použitých v programu k vyjádření postavení opice (její poloha, stojí-li na něčem, drží-li něco), vlastností věcí (název, poloha, je-li na něčem, hmotnost), vlastností truhel (barva, obsah, je-li zamknuta) a konečně k vyjádření aktuálního cíle (najíst se banánů, dojít pro klíč, atd.). (deftemplate opice (slot pozice (type SYMBOL) (default zelena-pohovka)) (slot na-cem (type SYMBOL) (default podlaha)) (slot drzet (type SYMBOL) (default vubec-nic))) (deftemplate vec (slot jmeno (type SYMBOL) (default ?NONE)) (slot pozice (type SYMBOL) (default ?NONE)) (slot na-cem (type SYMBOL) (default podlaha)) (slot vaha (type SYMBOL)
28
(allowed-symbols lehky tezky) (default lehky))) (deftemplate truhla (slot jmeno (type SYMBOL) (default ?NONE)) (slot obsah (type SYMBOL) (default ?NONE)) (slot odemknuta (type SYMBOL) (default ?NONE))) (deftemplate cil-je (slot akce (type SYMBOL) (allowed-symbols drzet odemknout jist posunout na jit-do) (default ?NONE)) (multislot argumenty (type SYMBOL) (default ?NONE)))
K manipulaci s truhlou slouží následující pravidla. Cílem je odemknout truhlu a vyjmout z ní předmět, který je nezbytný k dalšímu postupu. Vezměme například pravidlo drzet-truhlu-polozit-na-podlahu. To má sloužit k tomu, aby opice uchopila truhlu. V LHS pravidla jsou celkem čtyři obrazy. První z nich představuje fakt, že se opice má snažit odemknout truhlu. Prakticky to znamená, že musí existovat fakt, jehož šablona je nazvaná cil-je, ve svém prvním slotu s názvem akce obsahuje hodnotu odemknout a druhý slot s názvem argumenty má obsahovat označení truhly. Toto označení je pak uloženo v proměnné truhla. Druhý obraz předpokládá existenci faktu, jehož šablona je nazvána vec, první slot je nazván jmeno (hodnota může být jakákoliv a je následně přenesena do proměnné truhla), druhý slot je nazván na-cem a má hodnotu různou od hodnoty podlaha, poslední slot je nazván vaha a musí mít hodnotu lehky. Pro vysvětlení konstatujme, že musí existovat truhla, která je lehká a neleží na podlaze, přičemž se jedná o stejnou truhlu jako v prvním obraze. To je zajištěno unifikací proměnných truhla. Třetí obraz zajišťuje, že bude existovat fakt s šablonou opice a slotem drzet, jehož hodnota se nerovná hodnotě proměnné truhla. Poslední obraz zajišťuje, že dříve nebyl stanoven cíl (akce držet) pro uvažovanou truhlu, aby nedošlo k cyklickému splňování pravidla. Jsou-li nalezeny fakty odpovídající všem čtyřem obrazům v LHS pravidla, je provedena RHS pravidla. Konkrétně to znamená vložení faktu (cil-je (akce drzet) (argumenty ?truhla))), který zajistí další postup plánování s partikulárním cílem uchopení truhly. (defrule drzet-truhlu-polozit-na-podlahu "" (cil-je (akce odemknout) (argumenty ?truhla)) (vec (jmeno ?truhla) (na-cem ~podlaha) (vaha lehky)) (opice (drzet ~?truhla)) (not (cil-je (akce drzet) (argumenty ?truhla))) => (assert (cil-je (akce drzet) (argumenty ?truhla))))
Následující pravidla polozit-truhlu-na-podlahu, vzit-klic-k-odemknuti, jit-k-truhle-s-klicem a odemknout-truhlu-klicem tvoří zbývající nástroje pro manipulaci s truhlou. (defrule polozit-truhlu-na-podlahu "" (cil-je (akce odemknout) (argumenty ?truhla))
29
?opice <- (opice (pozice ?misto) (na-cem ?na) (drzet ?truhla)) ?vec <- (vec (jmeno ?truhla)) => (printout t "Opice hazi " ?truhla " z " ?na " na podlahu." crlf) (modify ?opice (drzet nic)) (modify ?vec (pozice ?misto) (na-cem podlaha))) (defrule vzit-klic-k-odemknuti "" (cil-je (akce odemknout) (argumenty ?obj)) (vec (jmeno ?obj) (na-cem podlaha)) (truhla (jmeno ?obj) (odemknuta ?klic)) (opice (drzet ~?klic)) (not (cil-je (akce drzet) (argumenty ?klic))) => (assert (cil-je (akce drzet) (argumenty ?klic)))) (defrule jit-k-truhle-s-klicem "" (cil-je (akce odemknout) (argumenty ?truhla)) (opice (pozice ?mmisto) (drzet ?klic)) (vec (jmeno ?truhla) (pozice ?cmisto&~?mmisto) (na-cem podlaha)) (truhla (jmeno ?truhla) (odemknuta ?klic)) (not (cil-je (akce jit-do) (argumenty ?cmisto))) => (assert (cil-je (akce jit-do) (argumenty ?cmisto)))) (defrule odemknout-truhlu-klicem "" ?cil <- (cil-je (akce odemknout) (argumenty ?jmeno)) ?truhla <- (truhla (jmeno ?jmeno) (obsah ?obsah) (odemknuta ?klic)) (vec (jmeno ?jmeno) (pozice ?misto) (na-cem ?na)) (opice (pozice ?misto) (na-cem ?na) (drzet ?klic)) => (printout t "Opice otevira " ?jmeno " pomoci " ?klic " a objevuje " ?obsah "." crlf) (modify ?truhla (obsah vubec-nic)) (assert (vec (jmeno ?obsah) (pozice ?misto) (na-cem ?jmeno))) (retract ?cil))
Následující pravidla ošetřují manipulaci s objekty během cesty. Jde o vyjmutí věci z truhly, použití žebříku, uchopení věci a odložení věci. K tomu jsou definována tato pravidla: odemknout-truhlu-a-vzit-vec, pouzit-zebrik-a-vzit, vylezt-na-zebrik-avzit, vzit-vec-ze-zebriku, vylezt-a-vzit, jit-a-vzit, pustit-a-vzit, uchopit-vec, a pustit-vec. Pravidla jsou velmi podobná předcházejícím, proto je není nutné podrobně vysvětlovat. (defrule odemknout-truhlu-a-vzit-vec "" (cil-je (akce drzet) (argumenty ?obj)) (truhla (jmeno ?truhla) (obsah ?obj)) (not (cil-je (akce odemknout) (argumenty ?truhla))) => (assert (cil-je (akce odemknout) (argumenty ?truhla)))) (defrule pouzit-zebrik-a-vzit "" (cil-je (akce drzet) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem strop) (vaha lehky)) (not (vec (jmeno zebrik) (pozice ?misto))) (not (cil-je (akce posunout) (argumenty zebrik ?misto))) => (assert (cil-je (akce posunout) (argumenty zebrik ?misto))))
30
(defrule vylezt-na-zebrik-a-vzit "" (cil-je (akce drzet) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem strop) (vaha lehky)) (vec (jmeno zebrik) (pozice ?misto) (na-cem podlaha)) (opice (na-cem ~zebrik)) (not (cil-je (akce na) (argumenty zebrik))) => (assert (cil-je (akce na) (argumenty zebrik)))) (defrule vzit-vec-ze-zebriku "" ?cil <- (cil-je (akce drzet) (argumenty ?jmeno)) ?vec <- (vec (jmeno ?jmeno) (pozice ?misto) (na-cem strop) (vaha lehky)) (vec (jmeno zebrik) (pozice ?misto)) ?opice <- (opice (pozice ?misto) (na-cem zebrik) (drzet nic)) => (printout t "Opice bere " ?jmeno "." crlf) (modify ?vec (pozice held) (na-cem held)) (modify ?opice (drzet ?jmeno)) (retract ?cil)) (defrule vylezt-a-vzit "" (cil-je (akce drzet) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem ?na&~strop) (vaha lehky)) (opice (pozice ?misto) (na-cem ~?na)) (not (cil-je (akce na) (argumenty ?na))) => (assert (cil-je (akce na) (argumenty ?na)))) (defrule jit-a-vzit "" (cil-je (akce drzet) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem ~strop) (vaha lehky)) (opice (pozice ~?misto)) (not (cil-je (akce jit-do) (argumenty ?misto))) => (assert (cil-je (akce jit-do) (argumenty ?misto)))) (defrule pustit-a-vzit "" (cil-je (akce drzet) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem ?na) (vaha lehky)) (opice (pozice ?misto) (na-cem ?na) (drzet ~nic)) (not (cil-je (akce drzet) (argumenty nic))) => (assert (cil-je (akce drzet) (argumenty nic)))) (defrule uchopit-vec "" ?cil <- (cil-je (akce drzet) (argumenty ?jmeno)) ?vec <- (vec (jmeno ?jmeno) (pozice ?misto) (na-cem ?na) (vaha lehky)) ?opice <- (opice (pozice ?misto) (na-cem ?na) (drzet nic)) => (printout t "Opice bere " ?jmeno "." crlf) (modify ?vec (pozice held) (na-cem held)) (modify ?opice (drzet ?jmeno)) (retract ?cil)) (defrule pustit-vec "" ?cil <- (cil-je (akce drzet) (argumenty nic)) ?opice <- (opice (pozice ?misto) (na-cem ?na) (drzet ?jmeno&~nic))
31
?vec <- (vec (jmeno ?jmeno)) => (printout t "Opice poklada " ?jmeno "." crlf) (modify ?opice (drzet nic)) (modify ?vec (pozice ?misto) (na-cem ?na)) (retract ?cil))
Následující pravidla řeší problém přemístění objektů. Všechna pravidla jsou opět ve formátu podobném předcházejícím, kde v LHS je několik jednoduchých obrazů a v RHS je většinou vložení nového faktu, určujícího nový krok v plánu. Pravidla jsou nazvána odemknout-truhlu-to-posunout-vec, drzet-vec, premistit-vec, pustit-vec-2 a premistena-vec. (defrule odemknout-truhlu-to-posunout-vec "" (cil-je (akce posunout) (argumenty ?obj ?)) (truhla (jmeno ?truhla) (obsah ?obj)) (not (cil-je (akce odemknout) (argumenty ?truhla))) => (assert (cil-je (akce odemknout) (argumenty ?truhla)))) (defrule drzet-vec "" (cil-je (akce posunout) (argumenty ?obj ?misto)) (vec (jmeno ?obj) (pozice ~?misto) (vaha lehky)) (opice (drzet ~?obj)) (not (cil-je (akce drzet) (argumenty ?obj))) => (assert (cil-je (akce drzet) (argumenty ?obj)))) (defrule premistit-vec "" (cil-je (akce posunout) (argumenty ?obj ?misto)) (opice (pozice ~?misto) (drzet ?obj)) (not (cil-je (akce jit-do) (argumenty ?misto))) => (assert (cil-je (akce jit-do) (argumenty ?misto)))) (defrule pustit-vec-2 "" ?cil <- (cil-je (akce posunout) (argumenty ?jmeno ?misto)) ?opice <- (opice (pozice ?misto) (drzet ?obj)) ?vec <- (vec (jmeno ?jmeno) (vaha lehky)) => (printout t "Opice poklada " ?jmeno "." crlf) (modify ?opice (drzet nic)) (modify ?vec (pozice ?misto) (na-cem podlaha)) (retract ?cil)) (defrule premistena-vec "" ?cil <- (cil-je (akce posunout) (argumenty ?obj ?misto)) (vec (jmeno ?obj) (pozice ?misto)) => (retract ?cil))
Plánovací systém musí pro řešení daného problému obsahovat pravidla pro přemisťování. To je zajištěno pravidly jiz-na-miste, sestoupit-na-podlahu, jit-a-nic-nedrzet a jit-a-drzet-vec, ve standardním formátu. (defrule jiz-na-miste "" ?cil <- (cil-je (akce jit-do) (argumenty ?misto)) (opice (pozice ?misto)) =>
32
(retract ?cil)) (defrule sestoupit-na-podlahu "" (cil-je (akce jit-do) (argumenty ?misto)) (opice (pozice ~?misto) (na-cem ~podlaha)) (not (cil-je (akce na) (argumenty podlaha))) => (assert (cil-je (akce na) (argumenty podlaha)))) (defrule jit-a-nic-nedrzet "" ?cil <- (cil-je (akce jit-do) (argumenty ?misto)) ?opice <- (opice (pozice ~?misto) (na-cem podlaha) (drzet nic)) => (printout t "Opice jde do " ?misto "." crlf) (modify ?opice (pozice ?misto)) (retract ?cil)) (defrule jit-a-drzet-vec "" ?cil <- (cil-je (akce jit-do) (argumenty ?misto)) ?opice <- (opice (pozice ~?misto) (na-cem podlaha) (drzet ?obj&~nic)) => (printout t "Opice jde do " ?misto " a drzi " ?obj "." crlf) (modify ?opice (pozice ?misto)) (retract ?cil))
Následující pravidla řeší problémy přemísťování opice z podlahy na objekt a zpět. Objektem je zde například truhla nebo žebřík. Konkrétní pravidla jsou pojmenována skocit-na-podlahu, jit-na-misto-a-vylezt, pustit-a-vylezt, vylezt-neprimo, vylezt-primo a na-veci. (defrule skocit-na-podlahu "" ?cil <- (cil-je (akce na) (argumenty podlaha)) ?opice <- (opice (na-cem ?na&~podlaha)) => (printout t "Opice seskakuje z " ?na " na podlahu." crlf) (modify ?opice (na-cem podlaha)) (retract ?cil)) (defrule jit-na-misto-a-vylezt "" (cil-je (akce na) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto)) (opice (pozice ~?misto)) (not (cil-je (akce jit-do) (argumenty ?misto))) => (assert (cil-je (akce jit-do) (argumenty ?misto)))) (defrule pustit-a-vylezt "" (cil-je (akce na) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto)) (opice (pozice ?misto) (drzet ~nic)) (not (cil-je (akce drzet) (argumenty nic))) => (assert (cil-je (akce drzet) (argumenty nic)))) (defrule vylezt-neprimo "" (cil-je (akce na) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem ?na)) (opice (pozice ?misto) (na-cem ~?na&~?obj) (drzet nic)) (not (cil-je (akce na) (argumenty ?na))) =>
33
(assert (cil-je (akce na) (argumenty ?na)))) (defrule vylezt-primo "" ?cil <- (cil-je (akce na) (argumenty ?obj)) (vec (jmeno ?obj) (pozice ?misto) (na-cem ?na)) ?opice <- (opice (pozice ?misto) (na-cem ?na) (drzet nic)) => (printout t "Opice splha na " ?obj "." crlf) (modify ?opice (na-cem ?obj)) (retract ?cil)) (defrule na-veci "" ?cil <- (cil-je (akce na) (argumenty ?obj)) (opice (na-cem ?obj)) => (retract ?cil))
Cílem opice je najíst se. To je řešeno dvěma pravidly: drzet-a-jist a uspokojit-hlad. První z nich je splněno ve chvíli, kdy je vložen cíl "jíst", přičemž opice nedrží banány. Druhé z pravidel je splněno ve chvíli, kdy existuje cíl "jíst" a opice již drží banány. (defrule drzet-a-jist "" (cil-je (akce jist) (argumenty ?obj)) (opice (drzet ~?obj)) (not (cil-je (akce drzet) (argumenty ?obj))) => (assert (cil-je (akce drzet) (argumenty ?obj)))) (defrule uspokojit-hlad "" ?cil <- (cil-je (akce jist) (argumenty ?jmeno)) ?opice <- (opice (drzet ?jmeno)) ?vec <- (vec (jmeno ?jmeno)) => (printout t "Opice ji " ?jmeno "." crlf) (modify ?opice (drzet nic)) (retract ?cil ?vec))
Inicializace celého expertního systému je provedena vložením série faktů pravidlem start. Tím je a) úplně popsáno prostředí, ve kterém se opice bude pohybovat, a b) je vložen cíl celého plánu - opice se musí najíst (viz poslední argument RHS pravidla). (defrule start "" => (assert (opice (pozice mistnost-3) (na-cem zelena-pohovka) (drzet nic))) (assert (vec (jmeno zelena-pohovka) (pozice mistnost-3) (vaha tezky))) (assert (vec (jmeno cervena-pohovka) (pozice mistnost-2) (vaha tezky))) (assert (vec (jmeno velky-polstar) (pozice mistnost-2) (na-cem cervenapohovka))) (assert (vec (jmeno cervena-truhla) (pozice mistnost-2) (na-cem velkypolstar))) (assert (truhla (jmeno cervena-truhla) (obsah zebrik) (odemknuta cervenyklic))) (assert (vec (jmeno modra-truhla) (pozice mistnost-4) (na-cem strop))) (assert (truhla (jmeno modra-truhla) (obsah banany) (odemknuta modryklic))) (assert (vec (jmeno modra-pohovka) (pozice mistnost-5) (vaha tezky))) (assert (vec (jmeno zelena-truhla) (pozice mistnost-5) (na-cem strop))) (assert (truhla (jmeno zelena-truhla) (obsah modry-klic) (odemknuta cerveny-klic)))
34
(assert (vec (jmeno cerveny-klic) (pozice mistnost-1))) (assert (cil-je (akce jist) (argumenty banany))))
Výstupem procesu je popis cesty - plán akce. Postup řešení lze dokumentovat spuštěním programu a výpisem z obrazovky. V jednotlivých pravidlech jsou vloženy příkazy tisku, na obrazovce se tedy objevují hlášení tak, jak je plán cesty postupně tvořen. V expertním systému je však množství dalších pravidel, která představují mezikroky v plánu. Pro úplnou představu funkce systému je nutné sledovat postup splňování pravidel v ladícím módu CLIPSu. CLIPS> (reset) CLIPS> (run) Opice seskakuje z zelena-pohovka na podlahu. Opice jde do mistnost-2. Opice splha na cervena-pohovka. Opice splha na velky-polstar. Opice bere cervena-truhla. Opice hazi cervena-truhla z velky-polstar na podlahu. Opice seskakuje z velky-polstar na podlahu. Opice jde do mistnost-1. Opice bere cerveny-klic. Opice jde do mistnost-2 a drzi cerveny-klic. Opice otevira cervena-truhla pomoci cerveny-klic a objevuje zebrik. Opice poklada cerveny-klic. Opice splha na cervena-truhla. Opice bere zebrik. Opice seskakuje z cervena-truhla na podlahu. Opice jde do mistnost-4 a drzi zebrik. Opice poklada zebrik. Opice splha na zebrik. Opice bere modra-truhla. Opice hazi modra-truhla z zebrik na podlahu. Opice seskakuje z zebrik na podlahu. Opice bere zebrik. Opice jde do mistnost-5 a drzi zebrik. Opice poklada zebrik. Opice splha na zebrik. Opice bere zelena-truhla. Opice hazi zelena-truhla z zebrik na podlahu. Opice seskakuje z zebrik na podlahu. Opice jde do mistnost-2. Opice bere cerveny-klic. Opice jde do mistnost-5 a drzi cerveny-klic. Opice otevira zelena-truhla pomoci cerveny-klic a objevuje modry-klic. Opice poklada cerveny-klic. Opice splha na zelena-truhla. Opice bere modry-klic. Opice seskakuje z zelena-truhla na podlahu. Opice jde do mistnost-4 a drzi modry-klic. Opice otevira modra-truhla pomoci modry-klic a objevuje banany. Opice poklada modry-klic. Opice splha na modra-truhla. Opice bere banany. Opice ji banany. CLIPS>
35
7
Fuzzy expertní systémy
Pro práci s neurčitostí a nejistotou byla vyvinuta v National Research Council Canada zdokonalená verze systému CLIPS, která byla nazvaná FuzzyCLIPS. Hlavním požadavkem při její implementaci bylo doplnění možnosti reprezentace fuzzy množin a fuzzy pravidel, jakož i manipulace s nimi. FuzzyCLIPS umožňuje vyjádřit a využívat pro rozhodování jak jednoznačné tak i fuzzy fakty. Znalostní inženýr může formulovat pravidla s použitím svých vlastních fuzzy hodnot a podle potřeby zavádět do faktů a pravidel také nejistotu. Použití těchto rozšíření je volitelné, takže lze systém FuzzyCLIPS použít i k tvorbě standardních programů bez neurčitých a nejistých poznatků. Fuzzy expertní systém se skládá z kolekce funkcí příslušností a fuzzy pravidel, které použitím fuzzy logiky popisují zkoumanou část reality [19]. Tato pravidla spolu s různými typy funkcí příslušnosti, se pak používají k fuzzy usuzování (neboli inferenci) o daných datech (fakty o realitě). Na rozdíl od běžných expertních systémů, které jsou založeny převážně na inferenčních mechanismech, využívajících symbolickou úroveň uvažování, fuzzy expertní systémy používají navíc velmi často numerické výpočty. Základní operace fuzzy expertních systémů • •
• •
Fuzzifikace – převod vstupních dat, zatížených neurčitostí, na fuzzy množiny charakterizované konkrétními funkcemi příslušnosti. Inference – k daným fuzzifikovaným faktům se hledají předpoklady fuzzy pravidel systému, které nejlépe odpovídají těmto faktům a odvozují se důsledky těchto faktů v podobě fuzzy množin. Výsledkem operace inference je obecně několik fuzzy množin, představujících fuzzy množiny důsledků použitých (neboli aktivovaných) pravidel. Každé z těchto pravidel v jistém smyslu doporučuje jinou fuzzy množinu zkoumané vstupní veličiny. Agregace – výsledkem je jediná fuzzy množina pro akční veličinu, která vznikla složením (agregací) fuzzy množin důsledků použitých pravidel. Defuzzifikace – transformace agregované fuzzy množiny akční veličiny nebo jejích významných bodů na reálné číslo. Nejčastěji se používají dvě základní metody: - defuzzifikace pomocí těžiště plochy pod funkcí příslušnosti výsledné fuzzy množiny (metoda těžiště – angl. center of balance - COB), - defuzzifikace pomocí střední hodnoty lokálních maxim funkce příslušnosti výsledné fuzzy množiny (metoda středu maxima – angl. middle of the maximum – MOM).
Fuzzifikace Pro specifikaci fuzzy množiny je nutné určit její funkci příslušnosti. Pokud lze nějakým způsobem kvantifikovat hodnoty veličin vyjádřené slovním popisem, je nutné jako jeden z prvních kroků transformovat konkrétní hodnoty do tzv. normalizovaného tvaru (např. uzavřený interval 0 až 1). V dalším kroku je pak každé ostré hodnotě přiřazen stupeň příslušnosti do jedné nebo více fuzzy množin, které odpovídají významu základních termů. Zde je nutné beze zbytku pokrýt celé normalizované univerzum zvolenými nosiči jednotlivých fuzzy množin. Pak již následuje určení konkrétně použitých funkcí příslušnosti. Tvar funkce příslušnosti je zvolen tak, aby byl co nejjednodušší, tedy složen z co nejmenšího počtu lineárních úseků [20]. Před definováním pravidel ve FuzzyCLIPSu je nutné definovat fuzzy šablony (jazykové proměnné) a fuzzy fakty. Existují dva základní způsoby: párové reprezentace prvků a jejich míry příslušnosti k fuzzy množině, nebo standardní funkce (L, Λ, Π, Γ − viz Obr. 7.1). Definování funkce příslušnosti ve fuzzy šabloně může být tedy provedeno pomocí reprezen-
36
tace jazykové proměnné diskrétními hodnotami nebo reprezentace jazykové proměnné standardními funkcemi. Λ − funkce
L – funkce L( x, α , β ) =
1
0
x <α
= (α − β ) /( β − α ) α ≤ x ≤ β 0
Π - funkce
Λ( x , α , β , γ ) =
x>β
Γ - funkce
Π( x, α , β , γ , δ ) =
x <α
0
x <α
Γ( x, α , β ) =
( x − α ) /( β − α ) α ≤ x ≤ β ( x − α ) /( β − α ) α ≤ x ≤ β = =1 β ≤ x ≤γ (α − x ) /(γ − β ) β ≤ x ≤ γ (α − x ) /(γ − β ) γ ≤ x ≤ δ 0 x >γ 0 x >δ
µ
µ
µ
1
1
1
1
α β
x
0
α β γ
0 α β
x
γ
δx
x>β
1
µ
0
x <α
0
= ( x − α ) /( β − α ) α ≤ x ≤ β
0
α β
x
Obr. 7.2 L – funkce, Λ - funkce, Π - funkce, Γ - funkce.
Reprezentace jazykové proměnné diskrétními hodnotami Má-li být fuzzy funkce popsána seznamem prvků, je třeba pro každou hodnotu zadat stupeň její příslušnosti do dané množiny [24]. Množina pak bude určena následovně: n
A =
U (x µ ) i
i
i =1
kde xi je prvek definované fuzzy množiny, který pochází z univerza U, µi je číslo charakterizující stupeň příslušnosti prvku xi k fuzzy množině A. Stupně příslušnosti prvků, které se v tomto seznamu nenacházejí, jsou vypočteny interpolací ze stupňů příslušností nejbližšího levého a pravého prvku. Reprezentace jazykové proměnné standardními funkcemi Dalším způsobem definování jazykové proměnné je použití některé ze standardních funkcí FuzzyCLIPSu (viz Obr. 7.3). Neurčitost vyjádřená pravděpodobností Nejistotu lze v expertních systémech vyjádřit pro jednotlivá fakta i v pravidlech, která budou na fakta aplikována. Každé tvrzení (tedy fakt) může být předloženo se subjektivní mírou jistoty, kterou bude vyjádřena číselně. Ve faktu je zadána jako tzv. činitel jistoty CF (angl. certainity factor), jehož hodnota je z intervalu 0 až 1. Například Fakt1 CF 0,9 vyjadřuje víru ve skutečnost, že Fakt1 nastane v 9 případech z 10. V pravidlech vyjádřená míra nejistoty je vyhodnocena jak na straně levé, tak na straně pravé. Zápis pravidla může tvar: když Fakt1 CF F1 a Fakt2 CF F2 a F1>0.5 a F2>0.7 pak důsledek CF 0.95. Interpretace pravidla zní: jestliže předpokládáme, že Fakt1 nastane s mírou jistoty větší než 0.5 a zároveň Fakt2 s jistotou větší než 0.7, pak platí důsledek s jistotou 0.95.
37
Ζ − funkce
S – funkce S(u, a, c ) = 0
= 2[(u − a ) /(c − a )]
2
Π(u, d , b ) =
u ≤α
α < u ≤ (a + c ) / 2 u>c
1
Π - funkce
Z (u, a, c ) =
=
= 1 − S(u, a, c )
µ
µ
µ
1
1
1
0
a
c
u
0
a
c
u
S(u, b − d , b ) u ≤ b S(u, b, b + d ) u > b
0 b-d b b+d
u
Obr. 7.4 Standardní funkce pro reprezentaci jazykových proměnných ve Fuzzy CLIPSu.
Vkládání fuzzy proměnných do paměti Hodnota činitele jistoty pro fakty je vkládána do paměti při běhu programu pomocí příkazu assert. Součástí vkládání může být také deklarace faktu. Jazykové operátory a výrazy FuzzyClipsu FuzzyClips má k dispozici sadu jazykových operátorů umožňujících požadovanou modifikaci fuzzy hodnot pro snadnější manipulaci s jazykovými proměnnými. V následující tabulce je uveden seznam těchto operátorů spolu s odpovídajícím českým ekvivalentem a výrazem, který se použije k modifikaci hodnoty funkce příslušnosti. modifikátor not very somewhat more-or-less extremely intensify2 intensify2 plus norm slightly
význam v češtině není velmi do jisté míry více-méně extrémně výrazně výrazně více normalizováno nepatrně
modifikační výraz 1-y y2 y0,33 y0,5 y3 y2, jestli 0 ≤ y ≤ 0.5 1-2(1-y)2, jestli 0 < y ≤ 0.5 y1,25 y/ymax intensify (norm(plus A))
Inference Způsob vyhodnocování pravidel ve FuzzyClipsu je závislý na mnoha faktorech, jako je například použití fuzzy proměnných v LHS (levostranných, předpokladových či podmínkových částech) nebo RHS (pravostranných, důsledkových či výkonných částech) pravidel, na tom, zda pravidla obsahují vícenásobné předpoklady nebo důsledky, zda fakt, který byl vložen do báze faktů, využívá tutéž fuzzy proměnnou, kterou již využívá jiný fakt, apod. Jednoduchá pravidla Inference v pravidlech, obsahující jednu entitu (jednoznačnou nebo fuzzy), jak v LHS tak v RHS pravidla.
38
Pravidlo: když F1 pak F2 s činitelem jistoty CFr • LSH obsahuje fakt F1 s údajem o činiteli jistoty CFF1, výsledný důsledek F2 má činitel jistoty CFF2 vypočtený podle vztahu: CFF2=CFr*CFF1. • LHS obsahuje fuzzy entitu, činitel jistoty závěru je vypočten podle vztahu: CFF2=CFr*CFF1’*S, kde S je míra shody fuzzy množiny předpokladu F1 s fuzzy množinou zkoumaného faktu F1. Výpočet S je komplikovaný a lze jej najít v [11]. • LHS i RHS pracuje s fuzzy entitami. V LHS se s fuzzy fakty zachází stejně jako v předešlém případě. V RHS dochází k propojení předpokladu a důsledků do vzájemné relace R=F1*F2, kde F1 je fuzzy množina předpokladu F1 a F2 je fuzzy množina důsledku F2. Výsledný činitel jistoty je dán součinem činitelů jistoty pravidla a faktu: CFF2=CFr*CFF1. Prahová hodnota míry jistoty Prahová hodnota (angl. threshold value) je systémový parametr ve FuzzyCLIPSu, který umožňuje vyloučit z dalšího zpracování ta pravidla, u kterých vypočtená hodnota činitele jistoty nedosáhla požadované úrovně. Standardně je velikost prahové hodnoty nulová, vyhodnocují se tedy všechna pravidla. Nastavení prahové hodnoty činitele jistoty pro omezení spuštění pravidel na požadovanou hodnotu umožňuje funkce set-threshold. Defuzzifikace Jedná se o převod výsledku rozhodování, který obdržíme ve tvaru fuzzy množiny, na konkrétní jednoznačnou číselnou hodnotu. Pro tuto transformaci agregované fuzzy množiny se nejčastěji používají dvě základní metody: •
Metoda těžiště (COG). Metodu těžiště je možné formalizovat vztahem pro výpočet x–ové souřadnice těžiště plošného geometrického útvaru pomocí momentů. Geometrická plocha útvaru je ohraničena zdola osou x, shora křivkou funkce příslušnosti. Zleva a zprava je plocha ohraničena uzavřeným intervalem
. Funkce pro určení defuzzifikované hodnoty podle algoritmu COG má tvar: (moment-defuzzify ?<promenna_s_faktem>|).
•
Metoda středu maxima (MON). Metoda středu maxima bere v úvahu pouze x-ové souřadnice bodu, u kterého dosahuje funkce příslušnosti daného fuzzy faktu maxima. Funkce pro určení defuzzifikované hodnoty podle algoritmu MOM má tvar: (maximum-defuzzify ?<promenna_s_faktem>|).
Další fuzzy rozšíření FuzzyCLIPSu Pro fuzzy aplikace můžeme použít další příkazy a funkce, které nám FuzzyClips nabízí. Jedná se například o funkce zjišťující vlastnosti definiční množiny univerza (všechny funkce se jménem get –u), dále o funkce pro zjištění vlastností nějaké konkrétní fuzzy množiny (všechny funkce se jménem get –fs). Pro nastavení a zjištění aktuální prahové úrovně činitele jistoty pro spouštění pravidel jsou určeny funkce set-treshold a get-treshold. Podobně je možné obsluhovat režimy max-min, max-prod pro inferenční metody (setfuzzy-inference-type, get-fuzzy-inference-type) nebo alfa hodnota určující hodnotu, od které se testuje překrývání fuzzy množin (set-alpha-value, get-alphavalue). Standardní nastavení uvedených úrovní je nulové a předvolený režim inference je max-min. Dále lze také nastavit a zjistit režimy vyhodnocování činitelů jistoty pravidel (setCF-evaluation, get-CF-evaluation) a jejich přesnost vyjádřenou počtem desetinných míst (set-fuzzy-display-precision, get-fuzzy-display-precision). Další skupinou jsou funkce pro vytvoření fuzzy hodnoty podle předchozí deklarace šablonou, seznamem dvojic prvků nebo standardní funkcí (create-fuzzy-value), funkce pro operaci sjednocení dvou fuzzy hodnot (fuzzy-union) a funkce pro průnik dvou fuzzy hodnot (fuzzy-intersection).
39
8
Fuzzy řízení procesu
Implementací teorie fuzzy množin do expertního systému lze získat výkonný nástroj na řešení reálných problémů, např. řízení procesu. Výhodou je možnost nepřesného (neurčitého) zadání, například označení teploty vody pojmy "studená", "OK", "teplá". Protože i výstupy fuzzy expertního systému jsou nepřesně vyjádřené, pro účely řízení se provádí tzv. defuzzifikace. Tím jsou získány konkrétní hodnoty nutné při nastavování řídících prvků. V následujícím příkladě je použit expertní systém FuzzyCLIPS v řešení problému nastavení teploty vody sprchy. Na počátku jsou stanoveny hodnoty teploty a toku vody, kterých má být dosaženo. To lze číselně vyjádřit pomocí globálních proměnných takto: ?*optimalniTepMin* ?*optimalniTepMax* ?*optimalniTokMin* ?*optimalniTokMax*
= = = =
34.0 38.0 11.0 13.0
kde optimalniTepMin a optimalniTepMax obsahují hodnotu minimální, resp. maximální, přípustné teploty vody, optimalniTokMin a optimalniTokMin obsahují hodnotu minimálního, resp. maximálního, přípustného toku vody. Protože však pracujeme s fuzzy teorií, jsou tyto hodnoty převedeny do fuzzy množin definicí pojmů studeny (10-35 °C), OK (36±2 °C), a horky (37-60 °C). Jednotlivé fuzzy množiny se plynule překrývají z důvodů nejasné hranice např. mezi vysokou a vyhovující teplotou. Definice fuzzy množin teploty vody je provedena pomocí šablony vystupniTeplota (deftemplate vystupniTeplota 5 65 Celcius ((studeny (z 10 35)) (OK (pi 2 36)) (horky (s 37 60))))
Čísla 5 a 65 představují hranice oboru hodnot množin, termín Celsius je názvem jednotky. Funkce příslušnosti pojmu studeny je definována jako Z funkce. To znamená, že je rovna 1 mezi hodnotami teploty 5 a 10, dále monotónně klesá až po teplotu 35, a od hodnoty teploty 35 je funkce nulová. Funkce příslušnosti pojmu OK je definována jako Π funkce, která nejprve roste z hodnoty 0 (při teplotě 34) k hodnotě 1 a poté symetricky klesá na hodnotu 0 (při teplotě 38). Maxima dosahuje na hodnotě teploty 36. Funkce příslušnosti pojmu horky je definována jako S funkce. To znamená, že je rovna 0 mezi hodnotami teploty 5 a 37, dále monotónně roste až po teplotu 60, a od hodnoty teploty 60 je funkce rovna 1. Podobně jsou definovány fuzzy množiny toku vody šablonou vystupniTlak (deftemplate vystupniTlak 0 100 litru/min ((nizky (z 3 11.5)) (OK (pi 1 12)) (vysoky (s 12.5 25))))
Cílem fuzzy expertního systému řízení sprchy je postupným ovládáním kohoutů dosáhnout optimální teploty vody a optimálního toku vody, přičemž takové hodnoty jsou označeny pojmem OK. Inicializační hodnoty globálních proměnných jsou definovány takto: (defglobal ?*studenyKohPoz* ?*horkyKohPoz* ?*studenyTep*
= 0.0 = 0.0 = 0.0
40
?*horkyTepl* ?*studenyTlak* ?*horkyTlak* ?*atmosferickyTlak* ?*iteracniFaktor*
= = = = =
0.0 0.0 0.0 30.0 1.0)
Níže uvedené šablony slouží k ovládání kohoutu studené (zmena_vc) a horké vody (zmena_vh). (deftemplate zmena_vc -1 1 ((NB (-0.5 1) (-.25 0)) (NM (-.35 0) (-.3 1) (-.15 0)) (NS (-.25 0) (-.15 1) (0 0)) (Z (-.05 0) (0 1) (.05 0)) (PS (0 0) (.15 1) (.25 0)) (PM (.15 0) (.3 1) (.35 0)) (PB (.25 0)(0.5 1)))) (deftemplate zmena_vh -1 1 ((NB (-0.5 1) (-.25 0)) (NM (-.35 0) (-.3 1) (-.15 0)) (NS (-.25 0) (-.15 1) (0 0)) (Z (-.05 0) (0 1) (.05 0)) (PS (0 0) (.15 1) (.25 0)) (PM (.15 0) (.3 1) (.35 0)) (PB (.25 0)(0.5 1))))
Pro řešení problému jsou dále nutné některé podpůrné (pomocné) funkce, zde uvedené s minimálním popisem. Jde o tyto funkce: • • • •
prectiCislo - zadání čísla v určeném rozsahu, zeptej-se - otázka s odpovědi z povolených hodnot, ano-nebo-ne-p - odpověď a nebo n na danou otázku, inicializaceSprcha - inicializuje některé globální proměnné, atd.
(deffunction prectiCislo (?otazka ?od ?do) (printout t ?otazka " [" ?od " do " ?do "]: ") (bind ?odpoved (read)) (while (not (and (numberp ?odpoved) (>= ?odpoved ?od) (<= ?odpoved ?do))) do (printout t "Prosim zvlozte cislo ve specifikovanem rozsahu" crlf ?otazka " [" ?od " do " ?do "]: ") (bind ?odpoved (read))) ?odpoved) (deffunction zeptej-se (?otazka $?povolene-hodnoty) (printout t ?otazka) (bind ?odpoved (read)) (if (lexemep ?odpoved) then (bind ?odpoved (lowcase ?odpoved))) (while (not (member ?odpoved ?povolene-hodnoty)) do (printout t ?otazka) (bind ?odpoved (read)) (if (lexemep ?odpoved) then (bind ?odpoved (lowcase ?odpoved)))) ?odpoved)
41
(deffunction ano-nebo-ne-p (?otazka) (bind ?reakce (zeptej-se ?otazka ano ne a n)) (if (or (eq ?reakce ano) (eq ?reakce a)) then TRUE else FALSE))
Hlavní funkce systému Simuluj zajišťuje především nastavování kohoutů vody tak, aby bylo dosaženo zvoleného optima. Zároveň jsou ošetřeny některé chybové stavy. Pro vysvětlení jsou hlavní body funkce okomentovány (viz text). (deffunction Simuluj (?studenyKohoutekZmena ?horkyKohoutekZmena) (if (and (= ?*studenyKohPoz* 1.0) (> ?studenyKohoutekZmena 0.0) (>= ?horkyKohoutekZmena 0.0)) then (printout t crlf "Kohoutek je naplno - zastaveni simulace" crlf) (bind ?*iteracniFaktor* 1.0) (halt)) (if (and (= ?*horkyKohPoz* 1.0) (> ?horkyKohoutekZmena 0.0) (>= ?studenyKohoutekZmena 0.0)) then (printout t crlf "Kohoutek je naplno - zastaveni simulace" crlf) (bind ?*iteracniFaktor* 1.0) (halt)) (if (and (= ?*studenyKohPoz* 0.0) (< ?studenyKohoutekZmena 0.0) (< (abs ?horkyKohoutekZmena) 0.000001)) then (printout t crlf "Nelze udrzet dostatecne vysokou teplotu" crlf ) (bind ?*iteracniFaktor* 1.0) (halt)) (if (and (= ?*horkyKohPoz* 0.0) (< ?horkyKohoutekZmena 0.0) (< (abs ?studenyKohoutekZmena) 0.000001)) then (printout t crlf "Nelze udrzet dostatecne nizkou teplotu" crlf ) (bind ?*iteracniFaktor* 1.0) (halt)) (if (and (= ?*horkyKohPoz* 0.0) (< ?horkyKohoutekZmena 0.0) (= ?*studenyKohPoz* 1.0)(> ?studenyKohoutekZmena 0.0)) then (printout t crlf "Nelze udrzet dostatecne nizkou teplotu" crlf ) (bind ?*iteracniFaktor* 1.0) (halt)) (if (and (= ?*horkyKohPoz* 1.0) (> ?horkyKohoutekZmena 0.0) (= ?*studenyKohPoz* 0.0)(< ?studenyKohoutekZmena 0.0)) then (printout t crlf "Nelze udrzet dostatecne vysokou teplotu" crlf ) (bind ?*iteracniFaktor* 1.0) (halt)) ;; ;; ;; ;; ;;
vypocet nové pozice kohoutu studene a horke vody podle doporuceni pro zmenu (viz nize pravidlo defuzzifikace-a-rizeni) je pouzit skalovaci faktor na zaklade zjisteni, ze zmena nastaveni pri hodne otevrenych kohoutech ma mensi efekt nez tataz zmena pri malo otevrenych kohoutech
(if (or (<> ?studenyKohoutekZmena 0.0) (<> ?horkyKohoutekZmena 0.0)) then (bind ?*studenyKohPoz* (max 0.0 (min 1.0 (+ ?*studenyKohPoz*
42
(* (* (max 0.1 ?*studenyKohPoz*) ?*iteracniFaktor*) ?studenyKohoutekZmena))))) (bind ?*horkyKohPoz* (max 0.0 (min 1.0 (+ ?*horkyKohPoz* (* (* (max 0.1 ?*horkyKohPoz*) ?*iteracniFaktor*) ?horkyKohoutekZmena))))) (format t "Pozice studeneho kohoutku = %5.3f, pozice horkeho kohoutku = %5.3f %n" ?*studenyKohPoz* ?*horkyKohPoz*)) (bind ?horkyTnizky (* ?*horkyKohPoz* (- ?*horkyTlak* ?*atmosferickyTlak*))) (bind ?studenyTnizky (* ?*studenyKohPoz* (- ?*studenyTlak* ?*atmosferickyTlak*))) (bind ?vystupniTlak (+ ?horkyTnizky ?studenyTnizky)) (if (= ?vystupniTlak 0.0) then (assert (Sprcha je vypnuta)) (bind ?vystupniTeplota 5.0) else (bind ?vystupniTeplota (/ (+ (* ?studenyTnizky ?*studenyTep*) (* ?horkyTnizky ?*horkyTepl*)) ?vystupniTlak))) (format t "Vystupni tok je %6.3f litru/sec%n" ?vystupniTlak) (if (= ?vystupniTlak 0.0) then (format t "Vystupni teplota je 'neznama' %n") else (format t "Vystupni teplota je %6.3f stupnu C%n" ?vystupniTeplota) ) ;; nasledujici test lze provest jen kdyz jsou oba kohouty zavreny (if (!= ?vystupniTlak 0.0) then ;; jestlize je horka voda zavrena a teplota je prilis vysoka NEBO ;; studena voda je zavrena a teplota je prilis nizka (if (and (= ?*horkyKohPoz* 0.0) (> ?vystupniTeplota ?*optimalniTepMax*)) then (printout t crlf "Vodu nelze udrzet dostatecne studenou " crlf ) (bind ?*iteracniFaktor* 1.0) (halt)) (if (and (= ?*studenyKohPoz* 0.0) (< ?vystupniTeplota ?*optimalniTepMin*)) then (printout t crlf "Vodu nelze udrzet dostatecne teplou" crlf ) (bind ?*iteracniFaktor* 1.0) (halt))) ;; jestlize je vystupni tok i vystupni teplota v mezich optima, system se ;; dotaze na zmenu vstupnich parametru nebo na ukonceni systemu (if (and (and (> (< (and (> (< then
?vystupniTlak ?*optimalniTokMin*) ?vystupniTlak ?*optimalniTokMax*)) ?vystupniTeplota ?*optimalniTepMin*) ?vystupniTeplota ?*optimalniTepMax*)))
43
(printout t "Sprcha je pod kontrolou!" crlf) (bind ?*iteracniFaktor* 1.0) (if (ano-nebo-ne-p "Chcete zmenit nektere parametry? ") then (bind ?*studenyTep* (prectiCislo "Nova teplota studene vody?" 5 65)) (bind ?*horkyTepl* (prectiCislo "Nova teplota horke vody?" 5 65)) (bind ?*studenyTlak* (prectiCislo "Novy tlak of studene vody?" 42 100)) (bind ?*horkyTlak* (prectiCislo " Novy tlak of horke vody?" 42 100)) ;; prepocet toku a teploty podle novych vstupu (bind ?horkyTnizky (* ?*horkyKohPoz* (- ?*horkyTlak* ?*atmosferickyTlak*))) (bind ?studenyTnizky (* ?*studenyKohPoz* (- ?*studenyTlak* ?*atmosferickyTlak*))) (bind ?vystupniTlak (+ ?horkyTnizky ?studenyTnizky)) (if (= ?vystupniTlak 0.0) then (assert (Sprcha je vypnuta)) (bind ?vystupniTeplota 5.0) else (bind ?vystupniTeplota (/ (+ (* ?studenyTnizky ?*studenyTep*) (* ?horkyTnizky ?*horkyTepl*)) ?vystupniTlak))) (format t "Vystupni tok je %6.3f litru/sec%n" ?vystupniTlak) (if (= ?vystupniTlak 0.0) then (format t "Vystupni teplota je neznama %n") else (format t " Vystupni teplota je %6.3f stupnu C%n" ?vystupniTeplota) ) else (bind ?*iteracniFaktor* 1.0) (halt))) ;; iteracni faktor se snizuje v kazdem cyklu (if (> ?*iteracniFaktor* 0.1) then (bind ?*iteracniFaktor* (* ?*iteracniFaktor* .96))) ;; vlozeni fuzzifikovanych hodnot vystupniho toku a teploty (if (= ?vystupniTlak 0.0) then (assert (vystupniTlak (0.0 1.0) (0.5 0.0))) else (if (= ?vystupniTlak 100.0) then (assert (vystupniTlak (99.5 0.0) (100.0 1.0))) else (assert (vystupniTlak ((max 0.0 (- ?vystupniTlak 0.5)) 0.0) (?vystupniTlak 1.0) ((min 100.0 (+ ?vystupniTlak 0.5)) 0.0) )))) (if (= ?vystupniTeplota 5.0)
44
then (assert (vystupniTeplota (5.0 1.0) (5.1 0.0))) else (if (= ?vystupniTeplota 65.0) then (assert (vystupniTeplota (64.9 0.0) (65.0 1.0))) else (assert (vystupniTeplota ((max 5.0 (- ?vystupniTeplota 0.1)) 0.0) (?vystupniTeplota 1.0) ((min 65.0 (+ ?vystupniTeplota 0.1)) 0.0) )))))
Funkce inicializaceSprcha je využita pro počáteční nastavení hodnot pozice kohoutů studené a horké vody, teploty a tlaku studené a horké vody na vstupu. Dále je provedena simulace nastavení sprchy do optima. Pravidlo start pak slouží k spuštění simulace. (deffunction inicializaceSprcha () (bind ?*studenyKohPoz* (prectiCislo "Pocatecni pozice studeneho kohoutku?" 0.0 1.0)) (bind ?*horkyKohPoz* (prectiCislo "Pocatecni pozice horkeho kohoutku?" 0.0 1.0)) (bind ?*studenyTep* (prectiCislo "Teplota vstupni studene vody ve stupnich Celsia?" 5 65)) (bind ?*horkyTepl* (prectiCislo "Teplota vstupni horke vody ve stupnich Celsia" 5 65)) (bind ?*studenyTlak* (prectiCislo "Tlak vstupni studene vody v kPa?" 42 100)) (bind ?*horkyTlak* (prectiCislo "Tlak vstupni horke vody v kPa?" 42 100)) (Simuluj 0.0 0.0) ) (defrule start => (inicializaceSprcha))
Následující pravidla slouží k řízení sprchy pomocí fuzzy inference. K tomu jsou využity fakty definované pomocí šablon zmena_vc a zmena_vh. (defrule sprcha_vypnuta ?off <- (Sprcha je vypnuta) => (assert (zmena_vh Z)) (assert (zmena_vc NB)) (retract ?off)) (defrule studeny_nizky (vystupniTeplota studeny) (vystupniTlak nizky) => (assert (zmena_vh PB)) (assert (zmena_vc Z))) (defrule studeny_OK (vystupniTeplota studeny) (vystupniTlak OK) => (assert (zmena_vh PM)) (assert (zmena_vc Z)))
45
(defrule studeny_vysoky (vystupniTeplota studeny) (vystupniTlak vysoky) => (assert (zmena_vh Z)) (assert (zmena_vc NB))) (defrule OK_nizky (vystupniTeplota OK) (vystupniTlak nizky) => (assert (zmena_vh PS)) (assert (zmena_vc PS))) (defrule OK_vysoky (vystupniTeplota OK) (vystupniTlak vysoky) => (assert (zmena_vh NS)) (assert (zmena_vc NS))) (defrule horky_nizky (vystupniTeplota horky) (vystupniTlak nizky) => (assert (zmena_vh Z)) (assert (zmena_vc PB))) (defrule horky_OK (vystupniTeplota horky) (vystupniTlak OK) => (assert (zmena_vh NM)) (assert (zmena_vc Z))) (defrule horky_vysoky (vystupniTeplota horky) (vystupniTlak vysoky) => (assert (zmena_vh NB)) (assert (zmena_vc Z)))
Pokud byla všechna pravidla splněna a byla určena změna nastavení kohoutů, je nutné přistoupit k defuzzifikaci a nové hodnoty postoupit funkci Simuluj. (defrule defuzzifikace-a-rizeni (declare (salience -1)) ?f1 <- (zmena_vc ?) ?f2 <- (zmena_vh ?) ?f3 <- (vystupniTeplota ?) ?f4 <- (vystupniTlak ?) => (bind ?studenyZmena (moment-defuzzify ?f1)) (bind ?horkyZmena (moment-defuzzify ?f2)) (retract ?f1 ?f2 ?f3 ?f4) (Simuluj ?studenyZmena ?horkyZmena))
Pro ukázku funkce fuzzy řídícího systému byl zvolen příklad, kde počáteční nastavení kohoutů je "zavřeno", teplota vstupní studené, resp. horké, vody je 15, resp. 55, stupňů Celsia, tlak vstupní studené, resp. horké, vody je 56 kPa, resp. 60 kPa. Na výpisu je možné 46
sledovat, jak systém postupně nastavoval kohouty a jaký to mělo vliv na tok a teplotu výstupní vody. CLIPS> (reset) CLIPS> (run) Pocatecni pozice studeneho kohoutku? [0.0 do 1.0]: 0 Pocatecni pozice horkeho kohoutku? [0.0 do 1.0]: 0 Teplota vstupni studene vody ve stupnich Celsia? [5 do 65]: 15 Teplota vstupni horke vody ve stupnich Celsia [5 do 65]: 55 Tlak vstupni studene vody v kPa? [42 do 100]: 56 Tlak vstupni horke vody v kPa? [42 do 100]: 60 Vystupni tok je 0.000 litru/sec Vystupni teplota je neznama Pozice studeneho kohoutku = 0.000, pozice horkeho kohoutku = 0.061 Vystupni tok je 1.822 litru/sec Vystupni teplota je 55.000 stupnu C Pozice studeneho kohoutku = 0.062, pozice horkeho kohoutku = 0.061 Vystupni tok je 3.447 litru/sec Vystupni teplota je 36.148 stupnu C Pozice studeneho kohoutku = 0.074, pozice horkeho kohoutku = 0.073 Vystupni tok je 4.107 litru/sec Vystupni teplota je 36.193 stupnu C Pozice studeneho kohoutku = 0.086, pozice horkeho kohoutku = 0.084 Vystupni tok je 4.741 litru/sec Vystupni teplota je 36.224 stupnu C Pozice studeneho kohoutku = 0.096, pozice horkeho kohoutku = 0.095 Vystupni tok je 5.349 litru/sec Vystupni teplota je 36.248 stupnu C Pozice studeneho kohoutku = 0.107, pozice horkeho kohoutku = 0.105 Vystupni tok je 5.933 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.118, pozice horkeho kohoutku = 0.116 Vystupni tok je 6.524 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.129, pozice horkeho kohoutku = 0.127 Vystupni tok je 7.145 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.140, pozice horkeho kohoutku = 0.138 Vystupni tok je 7.794 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.153, pozice horkeho kohoutku = 0.150 Vystupni tok je 8.468 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.165, pozice horkeho kohoutku = 0.162 Vystupni tok je 9.164 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.178, pozice horkeho kohoutku = 0.175 Vystupni tok je 9.880 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.191, pozice horkeho kohoutku = 0.188 Vystupni tok je 10.615 litru/sec Vystupni teplota je 36.265 stupnu C Pozice studeneho kohoutku = 0.205, pozice horkeho kohoutku = 0.201 Vystupni tok je 11.368 litru/sec Vystupni teplota je 36.265 stupnu C Sprcha je pod kontrolou! Chcete zmenit nektere parametry? n CLIPS>
47
9
Informace o CLIPSu
Veškeré informace o CLIPSu jsou dostupné na adrese http://www.ghg.net/clips/CLIPS.html. Zde je možné získat: • • • •
základní údaje o CLIPSu, zdrojové soubory pro platformy MS-DOS, MS Windows 3.1, MS Windows 9x, XWindows, MacOS, spustitelné soubory pro MS-DOS, MS Windows 3.1, MS Windows 9x, MacOS, a dokumentaci (Basic Programming Guide, Advanced Programming Guide, Interfaces Guide, User's Guide, Architecture Manual) ve formátu Portable Document Format (PDF).
Dokumenty jsou čitelné pomocí programu Adobe Acrobat Reader, který je k dispozici zdarma na adrese http://www.adobe.com.
48
10 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25]
Literatura Bemmel, J. H. van, Grémy, F., Zvárová, J. (eds.): Medical Decision Making: Diagnostic Strategies and Expert Systems. Elsevier Science Publishers B.V., 393 str., 1985. Berka, P. a kol.: Expertní systémy, skriptum VŠE, Praha, 1998. CLIPS Architecture Manual. NASA, Lyndon B. Johnson Space Center, Software Technology Branch, 1998. CLIPS Reference Manual. Volume I, Basic Programming Guide. NASA, Lyndon B. Johnson Space Center, Software Technology Branch, 1998. CLIPS Reference Manual. Volume II, Advanced Programming Guide. NASA, Lyndon B. Johnson Space Center, Software Technology Branch, 1998. CLIPS Reference Manual. Volume III, Interfaces Guide. NASA, Lyndon B. Johnson Space Center, Software Technology Branch, 1998. CLIPS User's Guide. NASA, Lyndon B. Johnson Space Center, Software Technology Branch, 1998. Feigenbaum, E.A.: Knowledge Engineering in the 1980's. Stanford University, Stanford, USA, 1982. Giarratano, J., Riley, G.: Expert Systems. Principles and Programming. PWSPublishing Company, Boston, 632 str., 1998. Gonzalez, A. J., Dankel, D. D.: Engineering of Knowledge-based Systems: Theory and Practice. Prentice Hall, 1993. Kelemen, J., Kubík, A., Lenharčík, I., Mikulecký, P.: Tvorba expertních systémů v prostředí CLIPS. Grada Publishing, 1999. Kosko, B.: Fuzzy Engineering. Prentice-Hall, 1997. Krishnamoorthy, C. S., Rajeev, S.: Artificial Intelligence and Expert Systems for Engineers. CRC Press, 1996. Mařík, V., Štěpánková, O., Lažanský, J.: Umělá inteligence (1). Academia Praha, 1993. Mařík, V., Štěpánková, O., Lažanský, J.: Umělá inteligence (2). Academia Praha, 1997. Mettrey, W.: A Comparative Evaluation of Expert System Tools. Computer, February 1991. Molnár, L, Češka, M., Melichar, B.: Gramatiky a jazyky. Alfa, vydavatelstvo technickej a ekonomickej literatúry, SNTL, Nakladatelství technické literatury, Bratislava, 192 str., 1987. Molnár, L, Návrat, P.: Programovanie v jazyku LISP. Alfa, vydavatelstvo technickej a ekonomickej literatúry, Bratislava, 264 str., 1988. Nguyen, H. T., Walker, E. A.: A First Course in Fuzzy Logic. CRC Press, 1997. Novák, V.: Fuzzy množiny a jejich aplikace. Matematický seminář, SNTL, Praha 1986. Olej, P., Petr, P.: Expertní systémy. Skriptum, Pardubice, 1997. Popper, M., Kelemen, J.: Expertné systémy. Alfa, vydavatelstvo technickej a ekonomickej literatúry, Bratislava, 360 str., 1989. Provazník, I., Kozumplík, J.: Expertní systémy. Skriptum VUT v Brně, VUTIUM, 1999. Zadeh, L. A.: Fuzzy sets. Inf. & Control, 8, 1965, s.338-353. Zbořil, F., Hanáček, P.: Umělá inteligence. Nakladatelství Vysokého učení technického v Brně, 125 str., 1991.
49
