プロダクションシステム
プロダクションシステムとは、振る舞いの規則から構成される一種の人工知能プログラムである。その規則はプロダクションと呼ばれ、自動計画、エキスパートシステム、行動選択などでよく使われた。プロダクションシステムは設定されたゴールを達成するためにプロダクションを実行するための機構を提供する。
プロダクションは2つの部分から構成される。知覚前提条件(IF文)とアクション(THEN)である。前提条件が現在の状態と適合することを、そのプロダクションは「始動; triggered」されたと言う。プロダクションのアクションが実行されることを、「点火; fired」すると言う。プロダクションシステムにはワーキングメモリと呼ばれるデータベースが内蔵され、その中に現在状態や知識や規則インタプリタが保持される。規則インタプリタは複数のプロダクションが始動されたときの優先順位を決定する機構を提供しなければならない。
規則インタプリタは前向き連鎖アルゴリズムを実行して実行するプロダクションを選択していき、とりあえずのゴールを目指す。ゴールとは、システムデータの更新だったり、信念の更新だったりする。規則の条件部をワーキングメモリ内の現在状態に照らして調べる。
理想的(あるいはデータ指向)プロダクションシステムでは、始動されるべき条件は全て実行されるべきであるという仮定がある。対応するアクションがエージェントの知識を更新し、ワーキングメモリにデータを追加したり、削除したりする。システムが処理を停止するのは、前向き連鎖ループにユーザーが割り込んだとき、事前に設定された回数のアクションを実行したとき、アクションとして「停止」が指定されていたとき、条件部が真となるプロダクションが存在しないときである。
一方、リアルタイム指向のプロダクションシステムやエキスパートシステムでは、しばしば相互排他的なプロダクションから選択しなければならない。アクションは時間がかかるので、1つのアクションしか実行できないか、(特にエキスパートシステムでは)単に推奨するだけに留める。そのようなシステムの規則インタプリタ(あるいは推論エンジン)は2つのステップからなるサイクルを実行する。データベースとプロダクションルールの照合をするステップと、マッチングしたルールからアクション部を実行するものを選択して実行するステップである。
プロダクションルールの条件部の表現能力はプロダクションシステムによって様々である。条件に適合するプロダクションルールを集めるパターンマッチアルゴリズムも同様に様々である。単純なもの(全ルールを順次検索して最初に適合したものを発見したところで停止)から最適化されたもの(ルールをコンパイルして相互に関連した条件のネットワークを形成する)まである。
後者は、1983年にチャールズ・フォーギーが設計したReteアルゴリズムで説明されたものであり、カーネギーメロン大学で開発された OPS と呼ばれる一連のプロダクションシステムで使用された。OPS は 80年代初期の OPS5 で頂点に達した。OPS5 はプロダクションシステムのプログラミングのための本格的なプログラミング言語でもある。
プロダクションシステムは実行(あるいは点火)すべきプロダクションルールの最終選択の面でも様々である。マッチングアルゴリズムが集めたルールは「競合集合; conflict set」と呼ばれ、そこからの選択処理は「競合解消戦略; conflict resolution strategy」とも呼ばれる。
この戦略もまた様々である。単純なものはプロダクションルールが書かれた順序、重み付け、優先度にしたがって競合集合をソートする。複雑なものでは、以前に各プロダクションルールが点火した時刻情報に従って競合集合をソートするか、アクション部が引き起こす変化の大きさにしたがってソートする。どのような競合解消戦略であっても、実装された手法はプロダクションシステムの効率と正確さに重大な影響を与える。
プロダクションシステムは、単純な文字列の書き換え、人間の認知プロセスのモデリング、項書き換え、リダクションシステム、エキスパートシステムなど様々な利用がある。
文字列を逆転させるプロダクションルールの例を以下に示す。ここで、文字列はアルファベットから構成され、"$" や "*" は含まれない(これらは、マーカー記号として使用)。
P1: $$ -> *
P2: *$ -> *
P3: *x -> x*
P4: * -> null & halt
P5: $xy -> y$x
P6: null -> $
この例では、プロダクションルールは上記リストに書かれた順に評価され選択される。各ルールについて、文字列は左から右に条件部にマッチするパターンがないか照合される。マッチした場合、マッチした部分文字列がプロダクションルールのアクション部で置き換えられる。このプロダクションシステムで x と y は「変数」であり、入力文字列の任意のアルファベットとマッチする。置換(文字列の逆転)が完了すると P1 によってマッチングが再開される。
文字列 "ABC" に上記プロダクションルールを適用して書き換えを行う様子を以下に示す。
$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)
このような単純なシステムでは、プロダクションルールの順序が重要である。制御構造がないため、プロダクションシステムの設計は困難となることが多い。もちろんプロダクションシステムのモデルで、推論エンジンやワーキングメモリに制御構造を導入することは可能である。
単純なシミュレーション世界で、部屋の中の猿が他のオブジェクトをつかんだり、その上に登ったりできるとする。以下の例は天井からつるされたオブジェクトをつかむプロダクションルールである。
(p Holds::Object-Ceiling
{(goal ^status active ^type holds ^objid <O1>) <goal>}
{(physical-object
^id <O1>
^weight light
^at <p>
^on ceiling) <object-1>}
{(physical-object ^id ladder ^at <p> ^on floor) <object-2>}
{(monkey ^on ladder ^holds NIL) <monkey>}
-(physical-object ^on <O1>)
-->
(write (crlf) Grab <O1> (crlf))
(modify <object1> ^on NIL)
(modify <monkey> ^holds <O1>)
(modify <goal> ^status satisfied)
)
この例では、ワーキングメモリ内のデータは構造化されており、変数は山括弧で囲まれて示される。"goal" や "physical-object" といったデータ構造名は条件部の最初のリテラルである。データ構造のフィールド名には "^" がプレフィックスとして付いている。"-" は条件の否定を表す。
OPS5 のプロダクションルールは、条件に適合し変数束縛を満たす全てのデータ構造のインスタンスに適用される。この例では天井からつるされたオブジェクトがいくつか存在し、手ぶらの猿の近くにはしごがあった場合、プロダクションルール "Holds::Object-Ceiling" からプロダクションルールのインスタンスが多数生成され、それらが競合集合となる。競合解消ステップでそれらインスタンスから点火すべきプロダクションインスタンスを選択する。
条件部でパターンマッチによって変数束縛された結果がアクション部で更新されたデータを参照するために使用される点に注意されたい。また、ワーキングメモリには「ゴール」データ構造のインスタンスの形で明確な制御構造データを含んでいる。この例では、猿がつるされたオブジェクトをつかんだら、ゴールの状態は満たされ、同じプロダクションルールは最初の条件が偽となるために必ず失敗する。