Produkční systém

Produkční systém je počítačový program, který se primárně skládá ze sady pravidel chování. Tato pravidla, nazývaná produkční pravidla, jsou základní reprezentací využívána např. v plánování nebo v expertních systémech. Produkční systém poskytuje mechanismus nutný pro provádění akcí za účelem dosažení nějakého zadaného cíle v zamýšleném systému (světě).

Produkční pravidla se skládají ze dvou částí: situace a akce. Situace (levá strana pravidla) popisuje podmínku, za které může být akce (pravá strana pravidla) vykonána. Pokud je tato podmínka splněna, může být vykonána akce. Produkční systém také obsahuje databázi, někdy nazývanou pracovní paměť, která udržuje informace o současném stavu systému, odvozené znalosti a inferenční stroj (také nazývaný interpret pravidel), který musí obsahovat mechanismus pro výběr akcí, pokud na zvolený stav systému můžeme aplikovat několik různých produkčních pravidel (tzv. řešení konfliktů).

Základní princip fungování

Inferenční stroj typicky využívá dopředného řetězení pro výběr produkčních pravidel za účelem splnění cíle, což může zahrnovat aktualizaci systémových dat. Podmínka každého produkčního pravidla (LHS, z anglického left hand side) je testována na současný stav světa v pracovní paměti.

V idealizovaných nebo datově orientovaných produkčních systémech je předpoklad, že všechna produkční pravidla, ve kterých podmínka odpovídá současnému stavu světa, by měla být vykonána. Následné akce (RHS, z anglického right hand side) aktualizují agentovi znalosti, odstraněním nebo přidáním dat do pracovní paměti. Produkční systém se zastaví, pokud uživatel přeruší smyčku dopředného řetězení, pokud počet smyček dosáhne zadaného limitu, systém se ocitne v cílovém stavu nebo pokud nelze aplikovat žádné produkční pravidlo.

Real-timové (operující v reálném čase) a expertní systémy, v kontrastu s idealizovanými systémy, často musejí vybírat mezi vzájemně výlučnými produkčními pravidly – protože vykonání akce zabírá čas – jen jedna akce může být vykonána nebo, v případě expertního systému, doporučena. V takovýchto systémech, inferenční stroj provádí následující operace v každém cyklu: výběr aplikovatelných produkčních pravidel, výběr jednoho z těchto aplikovatelných pravidel a jeho provedení.

Hledání aplikovatelných produkčních pravidel

Algoritmy pro hledání aplikovatelných produkčních pravidel se mohou značně odlišovat – od naivního, který zkouší všechna pravidla jedno po druhém, až po sofistikované, ve kterých jsou pravidla „zkompilována“ do sítě propojených podmínek (Rete algoritmus, používaný v systémech OPS).

Výběr z aplikovatelných produkčních pravidel

Produkční systémy se také mohou lišit v poslední fázi – ve výběru pravidla pro provedení. Množina všech pravidel, které lze aplikovat na daný stav systému se nazývá konfliktní množina a proces výběru jedné akce pro provedení se nazývá strategie řešení konfliktů.

Strategie jsou opět od jednoduchých – provedeme první pravidlo, které nalezneme; přiřadíme váhy nebo priority produkčním pravidlům – až po složité – setřídíme konfliktní množinu podle počtu, kolikrát již bylo dané pravidlo spuštěno; nebo podle počtu změn systému generované pravou stranou pravidla. Volba správné strategie pro řešení konfliktů je kritická pro efektivitu a úplnost (zdali nalezne řešení pokud existuje) produkčního systému.

Vyžití produkčního systému

Produkční systém má aplikace od jednoduchého přepisování řetězců až po modelování lidského chování.

Přepisování řetězců

Tento příklad ukazuje produkční systém pro obrácení řetězce nad abecedou, která neobsahuje znaky „$“ a „*“. Jedná se o čistě technickou pomůcku, stačí zvolit libovolné dva znaky, které abeceda neobsahuje – a ty jistě existují vždy.

P1: $$ → *
P2: *$ → *
P3: *x → x*
P4: * → null & zastav
P5: $xy → y$x
P6: null → $

V tomto příkladě jsou produkční pravidla vybírány v pořadí P1–P6. Pro každé pravidlo je vstupní řetězec prozkoumáván z levé strany do pravé s pohybujícím se oknem pro hledání levé strany pravidla. Pokud je nalezena shoda s levou stranou, shodující se podřetězec je nahrazen pravou stranou produkčního pravidla. V tomto produkčním systému jsou x a y proměnné, které odpovídají libovolnému znaku ve vstupní abecedě (tedy ne značkám „$“ a „*“). Po nahrazení se pokračuje znovu od pravidla P1.

Například řetězec „ABC“ prochází následující posloupností transformací:

$ABC (P6)
B$AC (P5)
BC$A (P5)
$BC$A (P6)
C$B$A (P5)
$C$B$A (P6)
$$C$B$A (P6)
*C$B$A (P1)
C*$B$A (P3)
C*B$A (P2)
CB*$A (P3)
CB*A (P2)
CBA* (P3)
CBA (P4)

Literatura

  • Brownston, L., Farrell R., Kant E. (1985). Programming Expert Systems in OPS5 Reading, Massachusetts: Addison-Wesley. ISBN 0-201-10647-7
  • Waterman, D.A., Hayes-Roth, F. (1978). Pattern-Directed Inference Systems New York: Academic Press. ISBN 0127375503
  • Klahr, D., Langley, P. and Neches, R. (1987). Production System Models of Learning and Development. Cambridge, Mass.: The MIT Press.
  • Mařík, Štěpánková, Lažanský, Umělá inteligence 1, Academia

Související články