JPH0348934A - プロダクション・システムの並列実行方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はプロダクション・システムの並列実行方式に係
り、特に、条件の照合した複数のルールを並列に実行す
るのに好適な並列実行解析方式に関する。

〔従来の技術〕

人工知能（ＡＩ）システムの実現方式として。

プロダクション・システムがある。プロダクション・シ
ステムは知識を記述した知識ベースと推論を行う推論エ
ンジンから構成される。

知識ベースは、事実に関する知識であるファクトと、規
則に関する知識であるルールからなる。

各々のファクトはワーキングメモリ要素（ＷＭ　Ｅ　）
として記述され、ワーキングメモリ（ＷＭ）に記憶され
る。また、各々のルールは条件を記述した条件部と実行
手続きを記述した実行部から成る。

すなわちルールは ｉｆ（条件部）　　ｔｈｅｎ（実行部）形式で記述され
ている。ルールの条件部は一つ以上の条件要素からなり
、条件要素には、一つ以上の条件式が記述される。実行
部は一つ以上の実行要素からなり、実行要素にはＷＭＥ
の更新・表示及び入力などの動作が記述される。ルール
の条件部の全ての条件要素の全ての条件式を満足するＷ
ＭＥ群が存在するとき１条件部はそのＷＭＥ群によって
満足されたという。

推論エンジンは、照合フェーズ・競合解消フェーズ・ル
ール実行フェーズの繰り返しによって推論を行う、この
一連の動作は認知サイクルと呼ばれる。この例を第２図
に示す、照合フェーズ１０１では、知識ベース１００に
おけるＷＭ内の全てのＷＭＥに対して、全てのルールの
条件部の条件要素に記述された条件式を満足するか否か
の照合を行う、照合フェーズにおいて生成された、条件
部を満足するＷＭＥ群とそれにより満足されたルールの
組をインスタンシェーション（ｉｎｓｔａｎｔｉａ−ｔ
ｉｏｎ）と呼び、インスタンシェーションから成る集合
を競合集合と呼ぶ、競合解消フェーズ１０２では、競合
集合から実行すべきイスンタンシエーションを一つだけ
選出する。ルール実行フェーズ１０３では、競合解消フ
ェーズ１０２で選択されたイスンタンシェーション中の
ＷＭＥ群に対して選択されたルールの実行部を作用させ
る。

従来、このようなプロダクション・システムを高速化す
るための実行方式として、競合集合の中から複数のイス
ンタンシェーションを選び、結果がある逐次実行結果と
一致するようにルールを並列実行する方式が提案されて
いる（電子情報通信学会論文誌Ｄ　ｖｏｌ、　Ｊ　７１
−Ｄ　＆３　ｐｐ、５６７−５７６　１９８８．３　　
石１）享：　「プロダクション・システムの並列実行可
能性の解析」）。

以下、この従来方式を簡単に説明する。

２つのルール、ルール１とルール２に、■　ルール１で
削除するＷＭＥをルール２で条件要素としている ■　ルール１で生成するＷＭＥをルール２でｎｏｔ条件
要素（そのＷＭＥがなければ成立する）としている ■　ルールｌで生成し、ルール２で削除する共通のＷＭ
Ｅがある の関係がある場合、ルール１はルール２に干渉すると呼
び、この関係を調べることを干渉検出と呼ぶ、ここで１
通常のプロダクション・システムでは、ルール実行フェ
ーズで削除するＷＭＥは条件要素の中の一要素でなけれ
ばならないので、■の関係はおこらない、そこで、■、
■の条件だけを考えると、ルール１がルール２に干渉し
なければ。

ルール１の実行に続いてルール２を逐次実行することが
できるので、これら２ルールは並列実行できる。競合集
合から複数の並列実行可能なイスンタンシェーションを
選択するときは、いがなる２ルールの間にも干渉が生じ
ないように選択すればよい。

従来方式では、競合集合中のイスンタンシェーションを
生成類などによりあらかじめ順序付けし、この順番にし
たがって、先に選択したイスンタンシェーションとの干
渉検出を行い、すべてのイスンタンシェーションが干渉
しないイスンタンシェーションを並列実行可能として選
択していた６〔発明が解決しようとする課題〕 複数ルールの並列実行は、あるルール類で逐次実行でき
れば並列実行可能となる。したがって、２ルールの場合
では、ルール１がルール２に干渉する場合でも、ルール
２がルール１に干渉しなければ、ルール２の実行に続い
てルール１が逐次実行できるので、これら２ルールを並
列実行することができる。ところが、イスンタンシェー
ションが３つ以上の並列実行解析はもっと複雑になる。

例えば、ルール３はルール１に干渉するが、ルール１は
ルール３に干渉せず、ルール２はルール３に干渉するが
、ルール３はルール２に干渉しない場合、これらの３ル
ールを並列実行可能とすると。

実際は、いかなるルール類にしても逐次実行ができない
ので矛盾する。つまり２ル一ル間だけでなく、ルールの
実行順を考えたルール全体の干渉検出を行ねなければな
らない。

そこで、前記従来方式では、先に選択したイスンタンシ
ェーションよりもあとで実行可能なイスンタンシェーシ
ョン、つまり、先に選択したイスンタンシェーションが
干渉しないイスンタンシェーションだけを選択すること
で並列実行解析を効率化している。このため、並列実行
解析を行うルール類によっては、実際は並列実行可能な
ルールが選択されていないことがあるという欠点があっ
た。これを次の３ルールを用いて説明する。

Ａ　：　ｉｆ　ａ、　ｂ　　ｔｈｅｎ　　ｄｅｌｅｔｅ
　ａＢ　　：　ｉｆ　ａ、ｃ　　ｔｈｅｎ　　ｃｒｅａ
ｔｅ　ｄＣ：　ｉｆ　　ｎｏｔ　　ｄ　　ｔｈｅｎ　　
　ｃｒｅａｔｅ　　ａルール順Ａ−Ｂ−Ｃで並列実行解
析を行う場合、まずＡを選択し１次にＡとＢの干渉検出
を行うが、ＡはＢに干渉するため、Ｂは選択されない、
続いてＡとＣの干渉検出を行い、ＡはＣに干渉しないの
でＣを選択する。したがって、このルール類では、Ａ、
Ｃの２ルールを選択する。一方、ルール類Ｃ−Ｂ−Ａで
並列実行解析を行う場合、まずＣを選択し、次にＣとＢ
の干渉検出を行い、ＣはＢに干渉しないのでＢを選択す
る０次にＣとＡの干渉検出を行い、ＣはＡに干渉せず、
さらにＢとＡの干渉検出を行い、ＢもＡに干渉しないの
で、Ａを選択できる。したがって、このルール類では３
ルールすべてを選択できる。この例では、ＢはＡに干渉
しないが、ＡはＢに干渉するため、Ｂが先に選択された
場合はＡを選択できるが、Ａを先に選択した場合は、Ｂ
は選択されない。

このように、従来方式では、先に選択したインスタンシ
ェーションが干渉しないインスタンシェ−ジョンだけを
選択していたため、並列実行解析を行うインスタンシェ
ーションの順番によって、本来は並列実行可能なルール
が選択されないことがあった。

さらに、前記従来方式では、全ての２ル一ル間について
干渉検出を行っている。ところがルール干渉の可能性は
、ルールの条件部と実行部の記述内容の比較からあらか
じめ判断できることがある。

例えば、実行要素が生成のみのルールは１条件部にｎｏ
ｔ条件要素を含まないルールには干渉しない。

このように、従来方式では、明らかに干渉を生じる可能
性がないルール間についても干渉検出を行うという無駄
があった。

本発明の目的は、複数のルールを並列実行するプロダク
ション・システムにおいて、このような従来の問題点を
解決し、干渉検出を行う必要があるルール間についての
み干渉検出を行うことによって、並列実行可能なルール
を高速に選択することにある。

〔課題を解決するための手段〕

上記目的を達成するために、請求項（１）では。

複数のルールを並列実行するプロダクション・システム
において、ルールにルールタイプを付加するルールデー
タ解析部と、競合集合中のインスタンシェーションから
ルールタイプを比較して並列実行可能なインスタンシェ
ーションを選択する並列実行解析部と、該選択したイン
スタンシェーションを格納する実行ルール集合部を設け
、該実行ルール集合部に格納されたインスタンシェーシ
ョンを並列に実行することを特徴とする。

また、請求項（２）では、ルールデータ解析部は、条件
要素にｎｏｔ条件要素を含まず、実行要素に削除と変更
を含まないルールにはルールタイプ１゜条件要素にｎｏ
ｔ条件要素を含まず、実行要素に削除あるいは変更を含
むルールにはルールタイプ２、条件要素にｎｏｔ条件要
素を含み、実行要素に削除と変更を含まないルールには
ルールタイプ３、条件要素にｎｏｔ条件要素を含み、実
行要素に削除あるいは変更を含むルールにはルールタイ
プ４のルールタイプを付加し。

並列実行解析部では、競合集合中のルールタイプｉ　　
（ｉ＝１〜４）が付加されているルールから構成される
タイプｉのインスタンシェーションのうち、タイプ１の
インスタンシェーション、タイプ２のインスタンシェー
ションでかつ実行ルール集合部に格納されたタイプ２の
インスタンシェーションと干渉しないインスタンシェー
ション、及び、タイプ３のインスタンシェーションでか
つ実行ルール集合部に格納されたタイプ３のインスタン
シェーションと干渉しないインスタンシェーションを選
択して実行ルール集合部に格納し、その後、タイプ４の
インスタンシェーションでかつ実行ルール集合部に格納
された全てのインスタンシェーションと干渉しないイン
スタンシェーションを選択して実行ルール集合部に格納
することを特徴とする 請求項（３）では、並列実行解析部は、競合集合中のイ
ンスタンシェーションのうち、タイプ１のインスタンシ
ェーションでかつ実行ルール集合部に格納されたタイプ
４のインスタンシェーションと干渉しないインスタンシ
ェーション、タイプ２のインスタンシェーションでかつ
実行ルール集合部に格納されたタイプ２とタイプ４のイ
ンスタンシェーションと干渉しないインスタンシェーシ
ョン、タイプ３のインスタンシェーションでかつ実行ル
ール集合部に格納されたタイプ３とタイプ４のインスタ
ンシェーションと干渉しないインスタンシェーション、
及び、タイプ４のインスタンシェーションでかつ実行ル
ール集合部に格納されたタイプ１．タイプ２．タイプ３
．タイプ４のインスタンシェーションと干渉しないイン
スタンシェーションを選択して実行ルール集合部に格納
することを特徴とする。

〔作　用〕

ルールデータ解析部において、各ルールにルールの条件
部と実行部の記載内容を表わすルールタイプを特徴する
請求項（２）、　（３）ではルールタイプは１〜４とし
１次のようなルール記述内容を表わすとしている。

ルールタイプ１：条件要素にｎｏｔ条件要素を含まず、
実行要素に削除と更新を含まない。

ルールタイプ２：条件要素にｎｏｔ条件要素を含まず、
実行要素に削除か更新を含む６ ルールタイプ３：条件要素にｎｏｔ条件要素を含み。

実行要素に削除と更新を含まない。

ルールタイプ４：条件要素にｎｏｔ条件要素を含み、実
行要素に削除か更新を含む。

上記のルールタイプの比較から２ル一ル間の干渉の可能
性が判断できる。第３図はルール１がルール２に干渉す
る可能性がない時を「○」、ある時を「×」で示したも
のである。

並列実行解析部では、ルールタイプを利用して競合集合
中のインスタンシェーションから並列実行可能なインス
タンシェーションを選択する０選択したインスタンシェ
ーションは実行ルール集合部に格納する。

まず、競合集合中のルールタイプ３が付加されているイ
ンスタンシェーション（タイプ３のインスタンシェーシ
ョンと呼ぶ）から選択を始める。

タイプ３のインスタンシェーションは同じタイプ３のイ
ンスタンシェーションと干渉する可能性があるので、実
行ルール集合部に格納されたタイプ３のインスタンシェ
ーションと干渉しないインスタンシェーションを実行ル
ール集合部に格納する。

次にタイプ１のインスタンシェーションの選択を行う、
実行ルール集合部に格納されているタイプ３のインスタ
ンシェーションはタイプ１のインスタンシェーションに
干渉する可能性がなく、タイプ１のインスタンシェーシ
ョンも同じタイプ１のインスタンシェーションに干渉し
ないので、タイプ１のインスタンシェーションはすべて
実行ルール集合部に格納する６次にタイプ２のインスタ
ンシェーションを選択する。実行ルール集合部に格納さ
れているタイプ３とタイプ１のインスタンシェーション
はタイプ２のインスタンシェーションに干渉しないので
、これらのインスタンシェーションとは干渉検出を行わ
ない、しかし、同じタイプ２のインスタンシェーション
と干渉する可能性があるので、実行ルール集合部の全て
のタイプ２のインスタンシェーションが干渉しなければ
、これを実行ルール集合部に格納する。最後に、タイプ
４のインスタンシェーションを選択する。このルールは
全ての夕・イブのインスタンシェーションと干渉する可
能性があるので、実行ルール集合部に格納された全ての
インスタンシェーションが干渉しない場合、これを実行
ルール集合部に格納する。　第４図は干渉検出の必要な
ルールの組合せを示したものである。ｒＯ」はルールタ
イプの比較のみで干渉検出の必要がないもの、「×」は
干渉検出が必要な組合せである。また、「−」は荷記の
タイプ３→１→２の順に並列実行解析を行うときにはお
こらない組合せを示している。しかし、この図かられか
るように、これらタイプ１，２゜３の間では干渉検出が
不要なので、実際には、タイプ１，２．３のルールはど
のような順番で並列実行解析を行ってもかまわない、そ
のあとで、タイプ４の並列実行解析を行う、ｌＩｆ求項
（２）はこれに対応するものである。さらにタイプ１，
２．３のルールについて、実行ルール集合部に格納され
たタイプ４のインスタンシェーションとも干渉検出を行
うようにすれば、タイプ４を含めたいずれのタイプのル
ールから並９列実行解析を行うこともできる。請求項（
３）はこれに対応するものである。

このように、ルールにルールタイプを付加し。

それを比較することにより、干渉する可能性がない２ル
ール（例えばタイプ１−タイプ１）の干渉検出を省略し
、さらに、あるルール類では干渉する可能性があっても
、他のルール類では干渉する可能性がない２ルール（例
えばタイプ１−タイプ３、タイプ１−タイプ２．タイプ
２−タイプ３）についても、干渉検出を省略してこれら
のルールを選択できる。したがって、ルールタイプが上
記１〜４の場合、従来では１６通りのルールタイプの組
合せの干渉検出が必要であったのに対し１木刀式では６
通りの組合せの干渉検出だけでよく。

効率よく並列実行解析を行うことができる。

〔実施例〕

以下、本発明の一実施例について図面により説明する。

第１図は本発明方式によるプロダクション・システム実
行装置の一実施例のブロック図である。

本プロダクション・システム実行装置は、ルール照合部
１０．競合集合部２０、ルール実行部３０゜並列実行解
析機構４０、主記憶５０からなり、並列実行解析機構４
０は、ルールデータ解析部４１、並列実行解析部４２、
実行ルール集合部４３から構成される。

ルールデータ解析部４１では、ユーザの記述したルール
にルールタイプを付加する。主記憶５０には、このルー
ルタイプの付加されたルールが格納される。ルール照合
部１０では初期データをもとに主記憶５０のルールを照
合し、その結果得られたインスタンシェーションを競合
集合部２０に格納する。並列実行解析部４２では、競合
集合部のインスタンシェーションから並列実行可能なイ
ンスタンシェーションを選択し、実行ルール集合部４３
に格納する。競合集合部２０から並列実行可能な全ての
インスタンシェーションを選択し、実行ルール集合部４
３に格納されると、ルール実行部３０では、これらのイ
ンスタンシェーションをすべて並列に実行する。この結
果はルール照合部１０に送られ、再びルール照合を始め
る０以上の認知サイクルを照合するルールがなくなるま
で繰り返す。

本発明方式による並列実行解析の一例を以下に示す０次
の４ルール。

Ａ　：　ｉｆ　ａ、　ｂ　　ｔｈｅｎ　　ｄｅｌｅｔｅ
　ａＢ　：　ｉｆ　ａ、　ｃ　　ｔｈｅｎ　　ｃｒｅａ
ｔｅ　ｄＣ：　ｉｆ　ｎｏｔ　ｄ　ｔｈａｎ　　ｃｒｅ
ａｔｅ　ｅＤ　　：　　ｉｆ　　　ｃ　　　　　ｔｈｅ
ｎ　　　ｍｏｄｉｆｙ　　ｃ　　ｃｌについて並列実行
解析を行う時、これらのルールタイプはそれぞれ、２．
ｌ、３．２となる。各ルールタイプ１，２．３は次のよ
うな記述内容を表わす。

ルールタイプ１：条件要素にｎｏｔ条件要素を含まず、
実行要素に削除と更新を含まない。

ルールタイプ２：条件要素にｎｏｔ条件要素を含まず、
実行要素に削除か更新を含む。

ルールタイプ３：条件要素にｎｏｔ条件要素を含み、実
行要素に削除と更新を含まない。

競合集合部２０には、ルールＡ、Ｂ、Ｃ，Ｄにそれぞれ
ルールタイプ２，１，３．２が付加されて格納されてい
る。並列実行解析部４２では、まずタイプ３のＣを並列
実行可とし１次にタイプ１のＢを干渉検出を行わずに並
列実行可とする０次にタイプ２のＡを干渉検出を行わず
に並列実行可とする。最後にタイプ２のＤについては、
Ａのみと干渉検出を行い、ＡがＤに干渉しないので、Ｄ
も並列実行可とする。

従来方式で、これら４ルールを選択するには６回の干渉
検出が必要であるが、本発明方式ではわずか１回の干渉
検出で済む、また、従来方式では。

干渉検出を行うルール類によっては、タイプ１が先に選
択されるとタイプ３が、タイプ２が先に選択されるとタ
イプ１あるいはタイプ３のルールが選択されないことが
あった。しかし、本発明方式では、並列実行解析を行う
ルール類に関係なく、並列実行可能なこれらのルールを
選択できる。

〔発明の効果〕

以上説明したように、本発明によれば、従来の並列実行
解析と比較して、インスタンシェーションを構成するル
ールに付加されたルールタイプの比較によって、干渉検
出の必要性が判断でき、必要のあるルール間についての
み干渉検出を行うため、並列実行解析の高速化が図れる
。さらに、並列実行解析を行うルールの順番によっては
、従来方式では選択できなかったインスタンシェーショ
ンの組合せも並列実行可能なインスタンシェーションと
して選択できるため、プロダクション・システムを高並
列で高速に実行できる。

【図面の簡単な説明】

第１図は本発明によるプロダクション・システム実行装
置の一実施例のブロック図、第２図はプロダクション・
システムの認知サイクルを説明するための図、第３図は
本発明のルールタイプの比較によるルール干渉の可能性
を示した図、第４図は本発明のルールタイプの比較によ
り並列実行の可能性を示した図である。 １０・・・ルール照合部、　２０・・・競合集合部、３
０・・・ルール実行部、 ４０・・・並列実行解析機構、 ４１・・・ルールデータ解析部、 ４２・・・並列実行解析部、 ４３・・・実行ルール集合部、 ５０・・・主記憶。 第２図

Claims (3)

【特許請求の範囲】
1. （１）複数のルールを並列実行するプロダクシヨン・シ
   ステムにおいて、ルールにルールタイプを付加するルー
   ルデータ解析部と、競合集合中のインスタンシェーショ
   ンからルールタイプを比較して並列実行可能なインスタ
   ンシェーシヨンを選択する並列実行解析部と、該選択し
   たインスタンシェーションを格納する実行ルール集合部
   を設け、該実行ルール集合部に格納されたインスタンシ
   ェーシヨンを並列に実行することを特徴とするプロダク
   シヨン・システムの並列実行方式。
2. （２）ルールデータ解析部では、条件要素にｎｏｔ条件
   要素を含まず、実行要素に削除と変更を含まないルール
   にはルールタイプ１、条件要素にｎｏｔ条件要素を含ま
   ず、実行要素に削除あるいは変更を含むルールにはルー
   ルタイプ２、条件要素にｎｏｔ条件要素を含み、実行要
   素に削除と変更を含まないルールにはルールタイプ３、
   条件要素にｎｏｔ条件要素を含み、実行要素に削除ある
   いは変更を含むルールにはルールタイプ４のルールタイ
   プを付加し、 並列実行解析部では、競合集合中のルールタイプｉ（ｉ
   ＝１〜４）が付加されているルールから構成されるタイ
   プｉのインスタンシェーシヨンのうち、タイプ１のイン
   スタンシェーシヨン、タイプ２のインスタンシェーショ
   ンでかつ実行ルール集合部に格納されたタイプ２のイン
   スタンシェーシヨンと干渉しないインスタンシェーシヨ
   ン、及び、タイプ３のインスタンシェーシヨンでかつ実
   行ルール集合部に格納されたタイプ３のインスタンシェ
   ーシヨンと干渉しないインスタンシェーシヨンを選択し
   て実行ルール集合部に格納し、その後、タイプ４のイン
   スタンシェーシヨンでかつ実行ルール集合部に格納され
   た全てのインスタンシェーションと干渉しないインスタ
   ンシェーションを選択して実行ルール集合部に格納する
   ことを特徴とする請求項（１）記載のプロダクション・
   システムの並列実行方式。
3. （３）ルールデータ解析部では、条件要素にｎｏｔ条件
   要素を含まず、実行要素に削除と変更を含まないルール
   にはルールタイプ１、条件要素にｎｏｔ条件要素を含ま
   ず、実行要素に削除あるいは変更を含むルールにはルー
   ルタイプ２、条件要素にｎｏｔ条件要素を含み、実行要
   素に削除と変更を含まないルールにはルールタイプ３、
   条件要素にｎｏｔ条件要素を含み、実行要素に削除ある
   いは変更を含むルールにはルールタイプ４のルールタイ
   プを付加し、 並列実行解析部では、競合集合中のルールタイプｉ（ｉ
   ＝１〜４）が付加されているルールから構成されるタイ
   プｉのインスタンシェーションのうち、タイプ１のイン
   スタンシェーシヨンでかつ実行ルール集合部に格納され
   たタイプ４のインスタンシェーションと干渉しないイン
   スタンシェーシヨン、タイプ２のインスタンシェーショ
   ンでかつ実行ルール集合部に格納されたタイプ２とタイ
   プ４のインスタンシェーシヨンと干渉しないインスタン
   シェーシヨン、タイプ３のインスタンシェーションでか
   つ実行ルール集合部に格納されたタイプ３とタイプ４の
   インスタンシェーションと干渉しないインスタンシエー
   シヨン、及び、タイプ４のインスタンシェーシヨンでか
   つ実行ルール集合部に格納されたタイプ１、タイプ２、
   タイプ３、タイプ４のインスタンシェーシヨンと干渉し
   ないインスタンシェーションを選択して実行ルール集合
   部に格納することを特徴とする請求項（１）記載のプロ
   ダクシヨン・システムの並列実行方式。