JPH0981385A - パタ−ン照合方法および装置 - Google Patents

Abstract

(57)【要約】 【課題】 外界の変化を迅速に取り込むことが可能なエ
キスパートシステムのためのパターン照合方法および装
置を提供すること。 【解決手段】 条件比較が行われていない事実の組み合
わせの内の最新のものから順に、所定組み合わせ数だけ
条件比較を行うパターンマッチ処理行程または手段と、
事実情報が入力されている場合には、現在の状態情報を
保存し、事実情報を取り込んで、取り込んだ事実に関連
する条件比較を優先して実行させるように指示する取り
込み行程または手段を順に繰り返し実行する。従って、
例えば１つの組み合わせについてのパターンマッチ処理
を行うたびに、ほぼ実時間に外界の変化を取り込み、パ
ターン照合に反映させることができる。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明はパターン照合方法
および装置に関し、特に外界の変化を迅速に取り込むこ
とが可能なエキスパートシステムのためのパターン照合
方法および装置に関する。

【０００２】

【従来の技術】エキスパートシステムは専門家の持つ、
系統立てられていない断片的な知識を元に、専門家と同
様な判断、動作を行う必要がある。このため、エキスパ
ートシステムの構築方法の１つとして、専門家の知識を
ルールの形で蓄え、そのルールの実行の組み合わせで専
門家の判断、動作を模擬する方法がある。このルールに
含まれる条件パターンを、与えられている事実と高速に
照合し、合致するルールを抽出して、該ルールによって
指示される処理を実行する装置がプロダクションシステ
ムである。

【０００３】プロダクションシステムにおけるパターン
照合においては、照合すべき事実が多い場合には非常に
処理時間を要する。このために、高速にパターン照合を
行う技術が提案されている。パターン照合の典型的な流
れを図２に示す。図示されているように、従来のプロダ
クションシステムにおいては、パターンマッチ、競合解
消、実行の３段階からなる認識実行サイクルと呼ばれる
処理を繰り返し、事実に合致するルールを順次抽出し、
実行する。このような、パターン照合技術の例としては
ＲＥＴＥ、ＴＲＥＡＴ、ＬＥＡＰＳ等がある。

【０００４】ＲＥＴＥは、ＷＭＥ（ワーキングメモリエ
レメント：ルールと照合する事実のこと）の集合から各
ルールごとに、含まれる定数条件に関する選択を行った
結果の集合であるα記憶、ルール中の条件パターン（Ｃ
Ｅ：コンディショナルエレメント）間の結合条件に基づ
いて、条件結合による選択を行った途中結果であるβ記
憶、および最終的な結果である競合集合、即ち現在発火
（実行）可能なインスタンシエーション（ルールとそれ
に合致する事実の組）の集合の３種類の内部情報を保持
している。これらの内部情報はパターンの結合関係によ
り網状に結合している。ＷＭＥ（事実）が変化した場合
には、内部情報の変化分のみが計算され、更新される。
ＴＲＥＡＴは、ＲＥＴＥで用いられているβ記憶を持た
ず、ＷＭＥの変化が起きた場合には、必要なβ記憶に相
当する情報はα記憶から再計算によって求める。

【０００５】ＬＥＡＰＳは、最良優先探索（ベストファ
ーストサーチ）を用いることにより、競合解消部を必要
としないパターン照合方式の一種である。ＬＥＡＰＳは
競合集合を持たず、インスタンシエーションが検出され
るたびに発火させる。このために、最初に見つかるイン
スタンシエーションが競合解決処理において選択される
べきインスタンシエーションとなるように、探索順序を
制御して最良優先探索を行う。従って、図２の競合解決
部Ｓ４２を持たない。ＬＥＡＰＳにおいては、ＷＭＥに
タイムスタンプ（ｔｓ）と呼ばれる時間順序を判定可能
な情報が付加され、α記憶の内容はそれぞれタイムスタ
ンプ順に並べられる。そして、最も新しいタイムスタン
プを持つインスタンシエーションを探索するようにマッ
チ処理が行われる。一般に競合解決処理においては、最
新のＷＭＥを含むものが選択されるので、最も新しいタ
イムスタンプを持つインスタンシエーションが、競合解
決処理において選択されるべきインスタンシエーション
となる。

【０００６】

【発明が解決しようとする課題】前記したような従来の
高速パターン照合方式においては、図２における実行部
Ｓ４３においてのみＷＭＥの変更が可能であり、マッチ
処理部Ｓ４０においては、ＷＭＥの変更ができなかっ
た。ところが、認識実行サイクルの内の大半の処理時間
はマッチ処理Ｓ４０において費やされ、競合解決部Ｓ４
２や実行部Ｓ４３は殆ど処理時間を必要としていない。
そして、マッチ処理Ｓ４０に必要な時間はパターン照合
の対象となっているＷＭＥの量に大きく左右される。従
って、ＷＭＥの量が多い場合には、外界の変化が発生し
てから、その事実がＷＭＥに反映されるまでの時間が長
くかかる恐れがあり、従来のパターン照合技術をそのま
ま応答時間の保証が必要な実時間処理エキスパートシス
テムあるいはプロダクションシステムに適用することが
できないという問題点があった。

【０００７】この発明の目的は、この問題点を解決し、
外界の変化を迅速に取り込むことが可能なエキスパート
システムのためのパターン照合方法および装置を提供す
ることにある。

【０００８】

【課題を解決するための手段】この発明は、条件比較が
行われていない事実の組み合わせの内の最新のものから
順に、所定組み合わせ数だけ条件比較を行うパターンマ
ッチ処理行程または手段と、事実情報が入力されている
か否かを判定し、事実情報が入力されている場合には、
現在の状態情報を保存し、事実情報を取り込んで、取り
込んだ事実に関連する条件比較を優先して実行させるよ
うに指示する取り込み行程または手段を順に繰り返し実
行することを特徴とする。

【０００９】本発明はこのような構成によって、例えば
１つの組み合わせについてのパターンマッチ処理を行う
たびに、外界の変化を取り込む事が可能となる。そし
て、１つの組み合わせについてのパターンマッチ処理は
非常に短時間で処理可能であるので、ほぼ実時間に外界
の変化を取り込み、パターン照合に反映させることがで
きる。

【００１０】

【発明の実施の形態】以下に、図面を参照して本発明を
詳細に説明する。本発明はＬＥＡＰＳ方式のような最良
優先探索を用いるパターン照合方式を基本としており、
以下、パターン照合方式としてＬＥＡＰＳ方式を採用し
た場合の例について説明する。ＬＥＡＰＳ方式において
は、事実にタイムスタンプｔｓを付与して取り込む。図
４は、取り込まれる事実の一例を示す説明図である。図
において、１組の括弧で囲まれた情報が１つの事実であ
り、型と属性の値を持っている。例えば１行目の事実は
型が「円筒形」であり、属性である「＾大きさ」の値が
「５ｃｍ」であり、もう一つの属性である「＾重さ」の
値が２０ｇであるという情報から成っている。「＾」は
属性であることを示す記号である。各事実には取り込ま
れた順にタイムスタンプｔｓ値が付与される。ｔｓ値は
取り込まれた順序さえ識別可能であれば何でもよく、例
えば通し番号でもよいし、実際に取り込まれた時の時刻
情報であってもよい。

【００１１】図５は、ルール表記の一例を示す説明図で
ある。一番外側の括弧によって囲まれた情報が１つのル
ールを表しており、「Ｐ」はルールの始まりであること
を示している。「サンプル」はルール名の例であり、次
行以降の３行のそれぞれがＣＥを表している。条件の１
行目（Ｃ0 ）は、事実の内で型が「立方体」であり、色
は任意の値ｘであり、大きさが５ｃｍであるものを表し
ている。なお「＜ｘ＞」は変数ｘが任意の値を取り得る
が、他の条件における変数ｘとは同じ値であることを表
している。従って、２行目の条件（Ｃ1 ）は、型が
「球」であり、大きさは任意の値ｙであるが、色は条件
Ｃ0 と同じ値ｘであるものを表している。

【００１２】矢印以降には、３つの条件Ｃ0 、Ｃ1 、Ｃ
2 の全てを満たす事実ＷＭＥの組み合わせが存在した場
合に実行すべき処理Ｅが記載されている。この例の場合
は、変数ｚの値をプリントアウトするという処理である
が、事実ＷＭＥの追加、修正、削除を伴う処理であって
もよい。

【００１３】図６（ａ）は、図４の事実を取り込んだ後
の、本発明におけるパターンマッチ処理の開始時におけ
るα記憶およびスタック（ＬＩＦＯバッファ）の内容の
例を示す説明図である。α記憶およびスタックの内容は
事実が取り込まれるか、あるいは追加されるたびに更新
される。α記憶は、前述したように、ＷＭＥの集合から
各ルールごとに、含まれる定数条件に関する選択を行っ
た結果、即ち各条件単独に合致する事実の集合であり、
各条件毎に存在する。また、α記憶にＷＭＥが登録され
るたびに、スタックには、エントリ（ｔｓ値のセット）
がプッシュされる。プッシュされる各ｔｓ値の値は、登
録したα記憶に対応する位置のｔｓ値は登録したＷＭＥ
に対応する最新のｔｓ値であり、その他の位置のｔｓ値
は該事実のｔｓ値から１（あるいは単位時間）を減算し
た値である。

【００１４】例えば、ｔｓ＝１の事実を取り込んだ場合
には、該事実がルール内の各条件に合致するか否かを判
定し、条件Ｃ2 と合致することが判明する。すると、条
件Ｃ2 に対応するα記憶に、タイムスタンプ値１および
ＷＭＥの変数値５ｃｍおよび２０ｇを登録する。また、
スタックには、Ｃ2 に対応するｔｓ値が１であり、他の
ｔｓ値が０であるようなエントリをプッシュする。

【００１５】以下同様に、タイムスタンプ２および３の
事実は条件Ｃ1 に合致するので、Ｃ1 に対応するα記憶
に登録され、スタックにはそれぞれ（１、２、１）、
（２、３、２）のエントリがプッシュされる。また、タ
イムスタンプ５および６の事実は条件Ｃ0 に合致するの
で、Ｃ0 に対応するα記憶に登録され、スタックにはそ
れぞれ（５、４、４）、（６、５、５）のエントリがプ
ッシュされる。従って、図４に示すような事実が順に取
り込まれた場合には、α記憶の内容は最終的に図６
（ａ）のような内容となる。

【００１６】図１は、本発明のパターンマッチ処理を示
すフローチャートである。この処理は、α記憶およびス
タックの状態が例えば図６（ａ）のような内容であるこ
とを前提に開始される。なお、図１において、点線で囲
んだ処理は図２のマッチ処理に相当する部分である。ス
テップＳ１においては、スタックからシードＷＭＥの情
報、即ち最上位にプッシュされているエントリである
（６、５、５）が取り出される。このエントリの中の最
も新しいｔｓ値（ＤＴ：ドミナントタイムスタンプ）６
に対応するＷＭＥがシードＷＭＥである。ステップＳ２
においては、スタックが空であり、何も取り出せなかっ
たか否かが判定され、空であればパターンマッチ処理を
終了する。

【００１７】ステップＳ３においては、シードＷＭＥを
起点として、α記憶における１組のＷＭＥの組み合わせ
についてマッチ処理を行う。図６（ｂ）は、スタックか
ら（６、５、５）のセットが取り出され、各α記憶のポ
インタＰ0 、Ｐ1 、Ｐ2 にセットされた状態を示してい
る。但し、Ｐ1 、Ｐ2 にセットされたｔｓ値は前述した
ように、機械的に算出された値であり、該値のＷＭＥが
存在しない場合には、各α記憶中の最も新しい（大き
い）ｔｓ値のＷＭＥを指すようにポインタが修正され
る。

【００１８】ステップＳ４においては、外界変化フラグ
がオンであるか否かが判定され、結果が肯定の場合には
ステップＳ１５に移行するが、否定の場合にはステップ
Ｓ５に移行する。ステップＳ５においては、インスタン
シエーション、即ちルールとそれに合致する事実の組が
有ったか否かが判定され、結果が肯定の場合にはステッ
プＳ７に移行するが、否定の場合にはステップＳ６に移
行する。

【００１９】ステップＳ６においては、現在のシードＷ
ＭＥに関するマッチ処理が終了したか否かが判定され、
結果が否定の場合には、シードＷＭＥ以外のα記憶のポ
インタを所定の規則に従って１つ変え、ステップＳ３に
戻ってマッチ処理を繰り返す。図６（ｃ）は、図６
（ｂ）の状態におけるマッチ処理の結果、ｔｓ値６と３
のＷＭＥの色の値が一致していないので、インスタンシ
エーションは存在せず、ポインタＰ1 が１つ古い（小さ
い）ｔｓ値に移動した状態を示している。このようにし
て、入れ子ループ処理によって、シードＷＭＥに対応す
るポインタＰ0 以外のポインタ値の可能な組み合わせが
全てチェックされる。

【００２０】ステップＳ６の判定結果が肯定の場合、即
ち、シードＷＭＥに対応するポインタＰ0 以外のポイン
タ値の可能な組み合わせのチェックが全て完了した場合
にはステップＳ１に戻り、スタックから次のシードＷＭ
Ｅ（エントリ）を取り出してマッチ処理を繰り返す。図
６（ｄ）は、ｔｓ値６のシードＷＭＥについてのマッチ
処理が終了したので、ステップＳ１に戻って、スタック
からシードＷＭＥ情報として（５、４、４）というエン
トリを取り出し、α記憶のポインタにセットした状態を
示している。

【００２１】ステップＳ４において、外界変化フラグが
オンであった場合にはステップＳ１５に移行する。ステ
ップＳ１５においては、マッチ処理の途中結果である、
現在の各α記憶のポインタの指しているｔｓ値のセット
をスタックに保存（プッシュ）する。図７は、外界変化
時におけるα記憶およびスタックの内容の変化を示す説
明図である。図７（ｃ）は、図６（ｃ）と同じ状態であ
り、この時に外界変化として、後述する割り込み処理に
よって、「大きさ＝１０ｃｍ、重さ＝５０ｇの円筒形」
という事実にｔｓ値７が付与されて取り込まれたものと
する。図７（ｅ）は、図７（ｃ）におけるα記憶の各ポ
インタの指しているｔｓ値セット（６、２、１）がスタ
ックにプッシュされた状態を示している。

【００２２】図１に戻って、ステップＳ１６において
は、新たに入力バッファに取り込まれた事実情報がＷＭ
Ｅに追加される。ステップＳ１７においては新たに追加
された事実に基づき、α記憶が更新される。ステップＳ
１８においては、ステップＳ１７においてα記憶にＷＭ
Ｅの追加があった場合には、該ＷＭＥに対応するエント
リをスタックにプッシュする。図７（ｆ）は新たな事実
が各条件と比較された結果、条件Ｃ2 に合致するので、
Ｃ2 に対応するα記憶にｔｓ値７の事実が登録され、か
つスタックには対応するエントリ（６、６、７）がプッ
シュされた状態を示している。

【００２３】ステップＳ１９においては、外界変化フラ
グがリセットされ、ステップＳ１に戻って、スタックか
らシードＷＭＥ（エントリ）を取り出してマッチ処理が
再開される。図７（ｇ）は、スタックからエントリ
（６、６、７）が取り出され、マッチ処理が再開された
状態を示している。このように、新たに追加されたＷＭ
Ｅは最初にシードＷＭＥとしてマッチ処理されることに
なる。また、追加前のマッチ処理の途中結果であるエン
トリ（６、２、１）は、スタック内に保存されており、
該セットが取り出された場合には、前回のマッチ処理の
続きが実行される。

【００２４】ステップＳ５においてインスタンシエーシ
ョンがあった場合にはステップＳ７に移行する。ステッ
プＳ７においては、ステップＳ１５と同様に途中結果で
あるｔｓ値セットをスタックに保存する。ステップＳ８
においては、発火したインスタンシエーションのルール
に指示されている処理を実行する。例えば、図６（ｄ）
のｔｓ値（５、３、１）の組み合わせは図５のルールに
合致するので、実行処理Ｅが実行され、「円筒形の重さ
＝２０ｇ」という文がプリントアウトされる。

【００２５】ステップＳ９においては、実行処理の結
果、ＷＭＥの更新（追加、修正、削除）があったか否か
が判定され、結果が肯定の場合にはステップＳ１２、１
３、１４のＷＭＥ更新処理が実行される。なお、ＷＭＥ
の追加の場合には、ステップＳ１２、１３、１４におい
ては、それぞれステップＳ１６、１７、１８と同じ処理
が実行され、ＷＭＥの削除の場合には、ＷＭＥ記憶、α
記憶、スタックから該当するＷＭＥおよびｔｓ値セット
が削除される。また、修正の場合には削除および追加が
実行される。

【００２６】ステップＳ１０においては、外界変化フラ
グがオンであるか否かが判定され、結果が肯定の場合に
はステップＳ１６に移行するが、否定の場合にはステッ
プＳ１１に移行する。ステップＳ１１においては、実行
処理の結果、停止が指示されたか否かが判定され、結果
が肯定の場合にはパターンマッチ処理を終了するが、否
定の場合にはステップＳ１に戻って、マッチ処理を繰り
返す。

【００２７】図３は、外界変化による割り込み処理を示
すフローチャートである。この処理は、新たな事実情報
がオンラインにより、あるいはキーボード等から入力さ
れた場合に発生する割り込みによって起動される。ステ
ップＳ３０においては、受信され、あるいは入力された
事実（外界変化）情報を入力バッファ内に格納する。ス
テップＳ３１においては、外界変化フラグをオンにセッ
トする。以上のような処理によって、従来、図２のマッ
チ処理部Ｓ４０においては、ＷＭＥの変更ができなかっ
たものが、本発明においては、図２のマッチ処理部Ｓ４
０に対応する、図１において点線で囲んだマッチ処理ブ
ロック内において、外界の変化を迅速に取り込み、パタ
ーンマッチ処理に反映させることが可能となる。

【００２８】以上、実施例を開示したが、更に以下に述
べるような変形例も考えられる。実施例においては、外
界の変化を割り込み処理およびフラグを使用して検知す
る方式を開示したが、本発明はこれに限らず、ポーリン
グ等任意の方式で外界の変化を取り込み可能である。ま
た、マッチ処理１回ごとに外界変化をチェックする例を
開示したが、システムに要求される応答時間等の条件に
基づき、所定のマッチ処理回数ごとに外界の変化をチェ
ックするようにしてもよい。

【００２９】実施例においては、ＬＥＡＰＳ方式のパタ
ーンマッチ処理に本発明を適用した例を開示したが、最
良優先探索を用いるパターンマッチ処理であれば、任意
のパターン照合方式に本発明を適用可能である。本発明
は、例えばプラント制御、通信網の管理、トラフィック
制御等の実時間処理が必要な任意のエキスパートシステ
ムに適用することができる。

【００３０】

【発明の効果】以上述べたように、この発明によれば、
条件比較が行われていない事実の組み合わせの内の最新
のものから順に、所定組み合わせ数だけ条件比較を行う
パターンマッチ処理行程または手段と、事実情報が入力
されている場合には、現在の状態情報を保存し、事実情
報を取り込んで、取り込んだ事実に関連する条件比較を
優先して実行させるように指示する取り込み行程または
手段を順に繰り返し実行するので、例えば１つの組み合
わせについてのパターンマッチ処理を行うたびに、外界
の変化を取り込む事が可能となる。そして、１つの組み
合わせについてのパターンマッチ処理は非常に短時間で
処理可能であるので、ほぼ実時間に外界の変化を取り込
み、パターン照合に反映させることができるという効果
がある。

【図面の簡単な説明】

【図１】本発明のパターンマッチ処理を示すフローチャ
ートである。

【図２】従来のパターンマッチ処理を示すフローチャー
トである。

【図３】外界変化による割り込み処理を示すフローチャ
ートである。

【図４】取り込まれる事実の一例を示す説明図である。

【図５】ルール表記の一例を示す説明図である。

【図６】マッチ処理時のα記憶およびスタックの内容の
変化を示す説明図である。

【図７】ＷＭＥ追加時のα記憶およびスタックの内容の
変化を示す説明図である。

【符号の説明】

Ｃ0 、Ｃ1 、Ｃ2 …条件、Ｅ…実行内容、Ｐ0 、Ｐ1 、
Ｐ2 …ポインタ、ＷＭＥ…事実

Claims (4)

【特許請求の範囲】
1. 【請求項１】 条件比較が行われていない事実の組み合
   わせの内の最新のものから順に、所定組み合わせ数だけ
   条件比較を行うパターンマッチ処理行程と、 事実情報が入力されているか否かを判定し、事実情報が
   入力されている場合には、 パターンマッチ処理行程の現在の状態情報を保存する行
   程と、 取り込み順序に関する情報を付加して事実情報を取り込
   む行程と、 パターンマッチ処理行程において、取り込んだ事実に関
   連する条件比較を優先して実行させるように指示する行
   程とを任意の順序で実行する取り込み行程とを順に繰り
   返し実行することを特徴とするパターン照合方法。
2. 【請求項２】 最良優先探索を用いるパターン照合方法
   におけるパターン照合処理に、請求項１に記載の各行程
   を採用したことを特徴とするパターン照合方法。
3. 【請求項３】 条件比較が行われていない事実の組み合
   わせの内の最新のものから順に、所定組み合わせ数だけ
   条件比較を行うパターンマッチ処理手段と、 パターンマッチ処理行程の現在の状態情報を保存する保
   存手段と、 取り込み順序に関する情報を付加して事実情報を取り込
   む取り込み手段と、 パターンマッチ処理手段において、取り込んだ事実に関
   連する条件比較を優先して実行させるように指示する指
   示手段と、 事実情報が入力されているか否かを判定し、事実情報が
   入力されている場合には、保存手段、取り込み手段、指
   示手段を起動する判定手段と、 パターンマッチ処理手段と判定手段とを順に繰り返し実
   行させる実行制御手段と含むことを特徴とするパターン
   照合装置。
4. 【請求項４】 更に、割り込み処理によって事実情報を
   入力すると共に、事実情報が入力されたことを示すフラ
   グ手段をオンに設定する入力手段を有し、 保存手段は、前記フラグがオンである場合には、現在の
   状態情報である、α記憶のポインタ情報をスタック手段
   に保存し、 取り込み手段は、入力された事実情報を取り込むと共に
   α記憶に反映させ、 指示手段は、入力された事実情報に対応するα記憶のポ
   インタ情報をスタック手段に保存し、 パターンマッチ処理手段は、事実が取り込まれた場合に
   は、スタック手段からポインタ情報を取り出して、該情
   報に基づきパターンマッチ処理を再開することを特徴と
   する、最良優先探索を用いるパターン照合方式を採用し
   た請求項３に記載のパターン照合装置。