voriges Kapitel | Startseite | Inhalt | nächstes Kapitel

© 2001 François Bry
Dieses Lehrmaterial wird ausschließlich zur privaten Verwendung angeboten. Eine nichtprivate Nutzung (z.B. im Unterricht oder eine Veröffentlichung von Kopien oder Übersetzungen) dieses Lehrmaterials bedarf der Erlaubnis des Autors.

VIII. Produktionssysteme

  1. Produktionssysteme
  2. Auswertung
  3. Darstellung in PROLOG
  4. Ein grundlegender Auswerter für Produktionssysteme
  5. Konfliktauflösung

1. Produktionssysteme

Ein Produktionssystem besteht aus einem Ziel und einer (endlichen) Menge von Fakten und (Produktions)Regeln. Ein Produktionssystem kann angesehen werden als Erweiterung eines Systems zum Vorwärtsschließen um eine Steuerung. Mittels Fakten und Regeln spezifiziert ein Produktionssystem ein Verhalten. Es ist angebracht, die Produktionssysteme als Mittel anzusehen, imperative Algorithmen unter Verwendung von Regeln zu Spezifizieren.

Fakt:

Wir werden die Fakten eines Produktionssystem als Prolog-Fakten darstellen.

Regel:

Eine Produktionsregel hat die Gestalt:
wenn Bedingung-1, Bedingung-2, . . . Bedingung-n dann Aktion-1, Aktion-2, . . . Aktion-m
oder die Gestalt:
bei Ereignis wenn Bedingung-1, Bedingung-2, . . . Bedingung-n dann Aktion-1, Aktion-2, . . . Aktion-m
Diese zweite Form hat den Begriff ECA-Regel, für Event-Condition-Action-Regel, geprägt.
Eine Produktionsregel ist bereichsbeschränkt, wenn die Auswertung des Bedingungsteils alle im Aktionsteil vorkommenden Variablen bindet. Ein Produktionssystem ist bereichsbeschränkt, wenn seine Produktionsregeln bereichsbeschränkt und seine Fakten bereichsbeschränkt, also variablenfrei, sind.

Ereignis:

Ein Ereignis ist die Durchführung einer Aktion oder ein sogenanntes externes Ereignis, d.h. nicht im Regelformalismus dargestelltes Ereignis, wie etwa das Erreichen eines Datums.
Ereignisse werden in diesem Kapitel weder weiter besprochen noch implementiert.

Bedingung:

Die Bedingungen werden in einer logischen Sprache ausgedrückt. Hier werden wir PROLOG-Literale dafür verwenden. Der Bedingungsteil einer Produktionsregel ist also ein Literal oder eine Konjunktion von Literalen.

Aktion:

Als Aktionen werden wir betrachten:
  • Das Hinzufügen eines Faktums F.
  • Das Löschen eines Faktums F.
  • Die Änderung eines Faktums F in ein Faktum G.
In manchen Produktionssystemen kommen eventuell weitere Aktionen hinzu: das Hinzufügen oder Löschen von Produktionsregeln oder die Aufrufe von Programmen. Solche weiteren Aktionen werden im Folgenden nicht berücksichtigt.
Eine Sequenz A1, ..., An von Aktionen wird dadurch durchgeführt, daß die einzelne Aktionen in der Reihenfolge der Sequenz durchgeführt werden.

Ziel:

Ein Ziel eines Produktionssystems ist wie der Bedingungsteil einer Produktionsregel ein Literal oder eine Konjunktion von Literalen.

zum Seitenanfang

2. Auswertung

Die Auswertung eines Produktionssystems ähnelt dem Vorwärtsschließen aus einer Menge von bereichsbeschränkten Fakten und Regeln. Wesentliche Unterschiede liegen darin, daß
  1. beim Vorwärtsschließen alle herleitbaren Fakten hinzugefügt werden können, bei der Auswertung eines Produktionssystem aber jeweils nur der Aktionsteil einer Regelinstanz durchgeführt wird;
  2. Bedingungen negative Literale sein können;
  3. die Auswertung terminiert, sobald das Ziel erfüllt ist.
Die Schritte der Auswertung eines Produktionssystems sind die Folgenden:
  1. Auswertung des Zieles.
    Wenn das Ziel erfüllt ist, dann terminiert die Auswertung erfolgreich. Sonst gehe zu 2.
  2. Matching.
    Berechnung aller Regelinstanzen sigma(B ---> A), deren Bedingungsteil sigma(B) erfüllt ist. Man sagt auch, daß diese Regelinstanzen anwendbar sind oder feuern können.
  3. Konfliktauflösung.
    Auswahl einer einzigen Regelinstanz aus der beim Matching berechneten Menge.
  4. Feuern der ausgewählten Regelinstanz.
    Wurde die Regelinstanzen sigma(B ---> A) ausgewählt, so wird nun der Aktionsteil sigma(A) durchgeführt.
  5. Zurück zu 1.
Die Auswertung eines Produktionssystems benutzt zwei Speicher:
  • einen Produktionsregelspeicher, der die Produktionsregeln enthält;
  • einen Arbeitsspeicher, der die Fakten enthält.
Der Einfachheit halber werden wir für beide Speicher die PROLOG-Datenbank verwenden.

zum Seitenanfang

3. Darstellung in PROLOG

Fakten:

Dargestellt als PROLOG-Fakten.

Produktionsregeln:

_ : Bedingungsteil *--> Aktionssequenz
Die Stelle vor dem : wird für unten erläuterte Zusatzinformationen verwendet, etwa für einen Regelidentifikator.

Bedingungsteil:

Der Bedingungsteil ist eine PROLOG-Anfrage ohne Systemprädikate und ohne Cut, also ein Literal oder eine Konjunktion von Literalen. Negierte Atome sind im Bedingungsteil zulässig.

Aktionssequenz:

Eine einzige Aktion oder eine PROLOG-Konjunktion von Aktionen.

Aktionen:

  •      + F          das Faktum F hinzufügen.
  •      - F          das Faktum F löschen.
  •      F -> G    das Faktum F durch das Faktum G ersetzen.

zum Seitenanfang

4. Ein grundlegender Auswerter für Produktionssysteme

76
:- op(1200, xfx, :), op(1190, xfx, *-->). auswerten(Ziel) :- Ziel. auswerten(Ziel) :- konfliktmenge(Menge), auswaehlen((_ : _ *--> A), Menge), durchfuehren(A), auswerten(Ziel). konfliktmenge(Regelinstanzen) :- setof( (I : B *--> A), ( (I : B *--> A), B ), Regelinstanzen ). durchfuehren( (A1,A2) ) :- !, durchfuehren(A1), durchfuehren(A2). durchfuehren(+F) :- F, !. %%% optional durchfuehren(+F) :- !, assert(F). durchfuehren(-F) :- retract_all(F), !. durchfuehren(F -> G) :- !, durchfuehren(-F), durchfuehren(+G). durchfuehren(Programmaufruf) :- Programmaufruf. retract_all(X) :- retract(X), fail. retract_all(_).
Die als optional markierte PROLOG-Klausel vermeidet mehrfache Vorkommen eines Faktums. Es hängt vom Produktionssystem ab, ob dies erwünscht ist. Manche Systeme lassen mehrfache Vorkommen eines Faktums zu und messen solchen "Redundanzen" eine Bedeutung zu. Für solche Produktionssysteme müßte die Klausel entfallen
Im Programm P76 ist das Prädikat auswaehlen nicht definiert. Der nächste Abschnitt beschäftigt sich damit.

zum Seitenanfang
P76

5. Konfliktauflösung

Die Konfliktauflösung ist die Auswahl einer Regelinstanz, deren Aktionssequenz durchzuführen ist, aus der Konfliktmenge. Im Programm P76 führt der Prädikat auswaehlen die Konfliktauflösung durch.
Folgende Ansätze zur Konfliktauflösung sind vorgeschlagen worden:
  1. Kontextuelle Einschränkung:

    Das Regelsystem wird so definiert, daß zu jeder Zeit höchstens eine Regelinstanz anwendbar ist, also feuern kann.

    Dazu werden bestimmte Fakten ausgezeichnet, die einen sogenannten Kontext beschreiben. Für jeden Kontext gibt es kontextspezifische Regeln, die das Vorhandensein der entsprechenden Fakten in ihrem Bedingungsteil testen. Andere Regeln dienen dazu, den Kontext zu wechseln, indem sie die entsprechenden Fakten austauschen.

    Betrachten wir das Beispiel eines medizinischen Diagnosesystems. Ein Kontext entspricht der Untersuchung einer Hypothese. Beim Symptom "verstopfte Nase" kann zum Beispiel jede der Hypothesen "Allergie" und "Erkältung" einen Kontext bilden. In derartigen Anwendungen erweist sich der Ansatz der kontextuellen Einschränkung oft als natürlich und sinnvoll.

  2. Ordnung über die Regelinstanzen:
    1. Durch eine statische Ordnung über die Regeln.
    2. Durch eine Ordnung über die Aktionen der anwendbaren Regelinstanzen.
    3. Durch eine statische Ordnung über die Bedingungsteile der Regeln oder Regelinstanzen.
      • Das Spezifitätsprinzip legt fest, daß eine anwendbare Regelinstanz, deren Bedingungsteil eine echte Obermenge der Bedingungsteile anderer anwendbarer Regelinstanzen ist, bevorzugt wird.
      • Nach dem Neuheitsprinzip werden die Regelinstanzen bevorzugt, deren Bedingungsteile zuletzt erfüllt wurden. Dazu müssen die generierten Fakten mit dem Zeitpunkt ihrer Erzeugung markiert werden.
    4. Durch eine dynamische Ordnung über die Regeln: Vorrang hat die Regel, die am längsten nicht gefeuert hat.

    Diese Vorgehensweise kann durch das Refraktionsprinzip ergänzt werden. Nach diesem Prinzip darf eine "gleiche" Regelinstanz nicht zweimal feuern. Die Gleichheit, die dabei berücksichtigt wird, unterscheidet oft "gleiche" Fakten nach den Zeitpunkten ihrer Generierung.

  3. Implementierung der Refraktions-, Neuheits- und Spezifitätsprinzipien:

    Zur Implementierung des Refraktionsprinzips werden wir ein Faktum F darstellen als:

    faktum(Id, F).

    wobei Id ein Identifikator (englisch "tag") des Vorkommens von F sein wird. Die Fakten des Produktionssystems können entweder alle denselben Identifikator 0 erhalten, oder verschiedene Identifikatoren. Später generierte Fakten werden dann natürliche Zahlen als Identifikatoren erhalten: je größer die Zahl, desto neuer das Vorkommen des Faktums.

Das folgende Programm P77 ist eine Anpassung des Prädikats durchfuehren an diese Darstellung der Fakten:
77
:- dynamic(faktum/2), dynamic(id_zaehler/1). durchfuehren( (A1,A2) ) :- !, durchfuehren(A1), durchfuehren(A2). durchfuehren(+F) :- faktum(_, F), !. %%% optional durchfuehren(+F) :- !, neu_id(Id), asserta(faktum(Id, F)). durchfuehren(-F) :- retract_all(faktum(_, F)), !. durchfuehren(F -> G) :- !, durchfuehren(-F), durchfuehren(+G). durchfuehren(Programmaufruf) :- Programmaufruf. id_zaehler(1). neu_id(I) :- retract( id_zaehler(I) ), Iplus1 is I + 1, assert( id_zaehler(Iplus1) ).
Im Folgenden wird ein Auswerter für Produktionssysteme implementiert, der auf dem Refraktions-, Neuheits- und Speizifitätsprinzip beruht, wobei das Neuheitsprinzip den Vorrang vor dem Spezifitätsprinzip haben soll.
Zur Vereinfachung sei angenommen, daß die Bedingungsteile der Produktionsregeln negationsfrei sind.

Implementierung des Refraktionsprinzips:

Zur Implementierung des Refraktionsprinzips muß über bereits gefeuerte Regelinstanzen Buch geführt werden. Dies erreichen wir folgendermaßen:
  1. Jede Regel erhält eine natürliche Zahl als eindeutigen Identifikator RId: RId : Bedingungsteil *--> Aktionssequenz
  2. Jede Regelinstanz erhält als Identifikator ein Paar (RId, Bedingungsteil-Id) wobei Bedingungsteil-Id die absteigend sortierte Liste der Identifikatoren der Fakten ist, mit denen der Bedingungsteil erfüllt wurde.
Beispiel: Die folgenden Regeln und Fakten
1 : s(X) *--> +t(X). 2 : p(X), q(X) *--> +u(X). 3 : p(X), q(X), r(X) *--> +v(X) 4 : q(X), r(X) *--> +w(X). faktum(2, q(a)). faktum(6, p(a)). faktum(7, s(a)). faktum(8, r(a)).
ergeben die folgenden Identifikatoren für Regelinstanzen:
(1, [7] ) : s(a) *--> +t(a). (2, [6,2] ) : p(a), q(a) *--> +u(a). (3, [8,6,2]) : p(a), q(a), r(a) *--> +v(a). (4, [8,2] ) : q(a), r(a) *--> +w(a).
Wird z. B. die Regelinstanz mit Identifikator (2, [6,2]) ausgewählt, dann wird in die PROLOG-Datenbank das PROLOG-Faktum hat_gefeuert(2, [6,2]) hinzugefügt.
Die Anpassung von P76 an diese Darstellung ergibt den folgenden Auswerter, der mit der Implementierung von durchfuehren aus P77 arbeitet.
78
:- op(1200, xfx, :), op(1190, xfx, *-->), dynamic(hat_gefeuert/2). auswerten(Ziel) :- faktum(_, Ziel). auswerten(Ziel) :- konfliktmenge(Menge), auswaehlen((RId, BId, ASeq), Menge), durchfuehren(ASeq), asserta( hat_gefeuert(RId, BId) ), auswerten(Ziel). konfliktmenge(RegelinstanzDeskriptoren) :- setof( (RId, BId, ASeq), B^( (RId : B *--> ASeq), erfuellt(B, [], BId), not hat_gefeuert(RId, BId) ), RegelinstanzDeskriptoren ). erfuellt( (B,C), L1, L) :- !, faktum(Id,B), einsortieren(Id, L1, L2), erfuellt(C, L2, L). erfuellt( not B, L, L) :- !, not erfuellt(B, _, _). erfuellt((X = Y), L, L) :- !, X = Y. erfuellt( B, L1, L) :- faktum(Id,B), einsortieren(Id, L1, L). einsortieren(E, [], [E]). einsortieren(E, [K|R], [E,K|R]) :- E > K, !. einsortieren(E, [K|R], [K|R]) :- E = K, !. einsortieren(E, [K|R], [K|S]) :- einsortieren(E, R, S).
Durch den Test not hat_gefeuert(RId,BId) bei der Berechnung der Konfliktmenge ist das Refraktionsprinzip implementiert. Das Prädikat auswaehlen ist noch nicht definiert, da es von den übrigen Prinzipien der Konfliktauflösung abhängt.

Implementierung der Neuheits- und Spezifitätsprinzipien:

Zur Konfliktauflösung nach diesen Prinzipien reicht es aus, aus den RegelinstanzDeskriptoren der Konfliktmenge, also aus den Tripeln (RId, BId, ASeq), dasjenige Tripel auszuwählen, dessen Bedingungsidentifikator BId maximal bezüglich der lexikographischen Ordnung ist. Dadurch bekommt das Neuheitsprinzip den Vorrang vor dem Spezifitätsprinzip.
Das kann man sich anhand des obigen Beispiels klarmachen. Nach dem Neuheitsprinzip haben die Regelinstanzen, deren Bedingungen mit dem neuesten Faktum erfüllt wurden, Vorrang vor allen anderen. Im Beispiel hat das neueste Faktum den Identifikator 8, so daß nur die Regelinstanzen mit den Identifikatoren (3, [8,6,2]) und (4, [8,2]) in Frage kommen. Nach dem Spezifitätsprinzip hat die Instanz der Regel 3 Vorrang vor der anderen. Da die Listen absteigend sortiert sind, ist die Liste, die weniger Element enthält, nach der lexikographischen Ordnung kleiner.
Unter Verwendung des PROLOG-Systemprädikats @< für die lexikographische Ordnung wird diese Konfliktauflösung durch folgende Definitionen geleistet:
79
auswaehlen(Max, [Max]). auswaehlen(Max, [K|R]) :- listmax(R, K, Max). listmax([K|R], Alt, Max) :- kleiner(K, Alt), !, listmax(R, Alt, Max). listmax([K|R], Alt, Max) :- listmax(R, K, Max). listmax([], Max, Max). kleiner(Tripel1, Tripel2) :- bedingungs_id(Tripel1, BId1), bedingungs_id(Tripel2, BId2), BId1 @< BId2. bedingungs_id( (_RId, BId, _ASeq), BId).
Je nachdem, ob das Refraktionsprinzip auch für die initialen Fakten des Produktionssystems gelten soll oder nicht, erhalten diese initialen Fakten alle den Identifikator 0, oder verschiedene Identifikatoren 1 bis n. Im ersten Fall muß der Identifikatorzähler id_zaehler für die hergeleiteten Fakten mit dem Startwert 1, im zweiten Fall mit dem Startwert n+1 definiert werden.
Die folgende Sitzung bezieht sich auf P77, P78, P79 mit Startwert 11 von id_zaehler.
:- [user]. 1 : s(X) *--> +t(X). 2 : p(X), q(X) *--> +u(X). 3 : p(X), q(X), r(X) *--> +v(X). 4 : q(X), r(X) *--> +w(X). faktum(2, q(a)). faktum(6, p(a)). faktum(7, s(a)). faktum(8, r(a)). yes. :- konfliktmenge(Menge). Menge = [ (1, [7], +(t(a))), (2, [6, 2], +(u(a))), (3, [8, 6, 2], +(v(a))), (4, [8, 2], +(w(a))) ] yes. :- auswerten( t(X) ). X = a More? (;) yes. :- listing(faktum/2), listing(hat_gefeuert/2). faktum(13, t(a)). faktum(12, w(a)). faktum(11, v(a)). faktum(2, q(a)). faktum(6, p(a)). faktum(7, s(a)). faktum(8, r(a)). hat_gefeuert(1, [7]). hat_gefeuert(4, [8, 2]). hat_gefeuert(3, [8, 6, 2]). yes.

zum Seitenanfang
P77, P78, P79

Die folgende Sitzung bezieht sich auf P77, P78, P79 mit Startwert 11 von id_zaehler.

:- [user]. 1 : s(X) *--> +t(X). 2 : p(X), q(X) *--> +u(X). 3 : p(X), q(X), r(X) *--> +v(X). 4 : q(X), r(X) *--> +w(X).
faktum(2, q(a)). faktum(6, p(a)). faktum(7, s(a)). faktum(8, r(a)).
yes.

Konfliktauflösung (2)

:- konfliktmenge(Menge). Menge = [ (1, [7], +(t(a))), (2, [6, 2], +(u(a))), (3, [8, 6, 2], +(v(a))), (4, [8, 2], +(w(a))) ] yes.
:- auswerten( t(X) ). X = a More? (;) yes.
:- listing(faktum/2), listing(hat_gefeuert/2). faktum(13, t(a)). faktum(12, w(a)). faktum(11, v(a)). faktum(2, q(a)). faktum(6, p(a)). faktum(7, s(a)). faktum(8, r(a)). hat_gefeuert(1, [7]). hat_gefeuert(4, [8, 2]). hat_gefeuert(3, [8, 6, 2]). yes.
voriges Kapitel | Startseite | Inhalt | nächstes Kapitel

Letzte Änderung: 18. August 1998

Valid XHTML 1.0!