JPH0635703A - 仮説推論処理方法 - Google Patents

Abstract

(57)【要約】 【目的】 仮説推論処理を行う装置に関し、コンシュー
マ機構のメモリ所要量と、コンシューマ待ち行列操作の
処理時間を共に減少できる仮説推論処理方法を目的とす
る。 【構成】 システムに再評価用スタック72を設け、コン
シューマ70の待ち行列71を、単方向リンクのみで形成し
（処理73）、該再評価を要するコンシューマを検出した
場合には、当該コンシューマ70の待ち行列71上の接続を
保持したまま、該コンシューマを再評価用スタック72に
登録し（処理74）、該注目環境ごとの該コンシューマ評
価処理（処理75）では、待ち行列71の該リンクに従って
すべてのコンシューマ70の該評価を行った後、再評価用
スタック72に登録されたすべてのコンシューマ70を順次
再評価スタック72から取り出して評価し、該起動可能コ
ンシューマには、起動したことを示す所定の状態表示を
行うように構成する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、スケジューリング、プ
ランニング等を、必ずしも真であるか否か判定できてい
ない仮説のデータに基づいて問題解決を行うための、仮
説推論処理をコンシューマ機構を用いて実行する装置に
おいて、コンシューマの管理を改善した仮説推論処理方
法に関する。

【０００２】

【従来の技術】いくつかの仮説を同時に選択して解を探
索する処理を行う一手法として、公知のＡＴＭＳ(assum
ption-based truth maintenance system) がある。

【０００３】仮説推論では、いくつかの仮説の論理積集
合を環境と呼び、１又は複数の環境の論理和について、
その環境が真のとき成り立つデータを前提として、ある
知識を適用して結果を推論するのであるが、その場合に
ＡＴＭＳでは、各特定の推論動作が、その前提データす
べてが、そのとき注目している環境において成立すると
きに初めて実行されるように制御するために、コンシュ
ーマ機構を用いる。

【０００４】即ち、与えられた知識について、前提デー
タに対してコンシューマと呼ぶデータ構造を作成してお
き、現在の注目環境（別途適当な戦略で設定される真と
仮定された仮説の集合）に対して前提データがすべて成
立するコンシューマを検索し、それを起動可能コンシュ
ーマとして取り出して推論処理を行う。

【０００５】図２はＡＴＭＳによる仮説推論装置の構成
例を示すブロック図であり、問題解決部１と無矛盾性管
理部２とからなる。問題解決部１において、制御部３は
注目環境を決定し、起動待ちの各コンシューマについ
て、すべての前提データが注目環境で成立しているか評
価し、起動可能コンシューマを検出するごとに推論部４
に渡す。

【０００６】推論部４は、起動可能コンシューマについ
て、コンシューマに設定されているポインタで指定され
る知識を、知識管理部５に保持する知識から取り出して
推論を実行する。

【０００７】その推論によって、新しいデータが推論さ
れれば、無矛盾性管理部２のノード管理部６に通知し、
ノード管理部６が新しいデータのためのノード（後述す
るデータのためのデータ構造）を生成し、コンシューマ
管理部７が知識管理部５に保持する知識を参照すること
により、そのデータを前提とする知識について、新しい
コンシューマを生成する。

【０００８】推論により、新しい正当化（後述するよう
にして関係付けられる、データ間の前提／帰結の関係）
が判明したときは、ラベル更新部８を起動してラベル更
新処理を行い正当化を伝播する。又、推論によって矛盾
が判明した場合には、矛盾管理部９を起動して、正当化
の調整と呼ぶ処理を行うが、詳細は省略する。

【０００９】ここで、正当化の伝播とは、後述のよう
に、その正当化で確定した、データが成立する環境を、
該当ノードの情報に追加し、そのデータを前提とするデ
ータがある場合に、それらのデータのノードにも新たな
正当化を波及させるラベル更新部８の処理である。

【００１０】図４(a）は、データ等を格納するデータ構
造である前記ノードの構成を説明する図であって、ノー
ドはデータ項、ラベル項、正当化項、帰結項からなり、
データ項にデータが格納され、ラベル項にはデータ項の
データが成立する環境の論理和が格納される。

【００１１】正当化項と帰結項とは、他のノードとの前
提／帰結関係を指示する項であるが、ノード間の前提／
帰結関係は次に述べる正当化のデータ構造（以下に単に
正当化という）を介して指示するので、正当化項には、
このデータが導かれた前提となった他のデータのノード
を指示するために、各正当化を指示するポインタが格納
され、帰結項には、このデータを前提として導かれた他
のデータのノードを指示するために、各正当化を指示す
るポインタが格納される。

【００１２】図４(b）は、正当化のデータ構造であっ
て、前提項と帰結項からなり、前提項には前提となった
ノード（即ち前記の帰結項で、この正当化を指示してい
るノード）すべてのアドレスが格納され、帰結項には前
提項で指示するノード集合からの帰結データを表すノー
ド（即ち前記の正当化項で、この正当化を指示している
ノード）のアドレスが格納される。

【００１３】図５は以上のデータ構造によって推論結果
が表現されている例を示す図であって、ノードは、先
ず網かけ部分が無い状態では、環境「Ａ＆Ｂ」（仮説Ａ
と仮説Ｂの論理積）の下でデータ「Ｘ＝１」が成立する
ことを表し、ノードは環境「Ｃ」でデータ「Ｙ＝２」
が成立することを表し、ノードは環境「Ｄ」でデータ
「Ｘ＝２」が成立することを表し、ノードは環境
「Ｅ」でデータ「Ｙ＝１」が成立することを表す。

【００１４】これらのノード〜に対して、知識「Ｚ
＝Ｘ＋Ｙ」に基づく推論のために、コンシューマが後述
のように生成され、前記のようにしてそのコンシューマ
が起動可能になって推論部４による推論が行われると、
正当化、正当化、ノードが作られる。

【００１５】正当化は、ノードとノードとを前提
として、ノードが表しているデータ「Ｚ＝３」が導か
れることを表し、正当化は、ノードとノードとを
前提として、同じくノードのデータ「Ｚ＝３」が導か
れることを表す。

【００１６】従ってノードのラベル項には、前記ラベ
ル更新部８によるラベル更新処理によって、正当化に
対応する環境「Ａ＆Ｂ＆Ｃ」と、正当化に対応する環
境「Ｄ＆Ｅ」とが、データ「Ｚ＝３」が成立する環境と
して表現される。

【００１７】このような関係がある場合に、既存のノー
ドで表すデータが別の推論によっても再び導かれると、
ラベル更新処理によって、そのノードの正当化項とラベ
ル項がそれに従って拡張するように更新すると共に、更
に正当化のポインタを使って関連するノードのラベル項
へ更新を伝播する。

【００１８】例えば図５が前記説明のように表現されて
いる場合に、推論部４によってノードのデータ「Ｘ＝
１」が、環境「Ｆ」の下でデータ「Ｗ＝１」の成立を示
すノードと知識「Ｘ＋Ｗ＝２」から導かれると、正当
化が生成されて、ラベル更新部８によってノードの
ラベル項に環境「Ｆ」が追加され、更に正当化がノード
まで伝播されてラベル項に環境「Ｃ＆Ｆ」が追加され
る。

【００１９】以上の処理は前記のように、コンシューマ
管理部７が生成するコンシューマから、制御部３が検索
する起動可能コンシューマに基づいて、推論部４、ラベ
ル更新部８等によって実行される。

【００２０】図６(a)はコンシューマのデータ構造を示
す図であって、各コンシューマは前提項と知識項を有
し、コンシューマ間に双方向リンクを設けて待ち行列を
構成し管理するためにnext項とprev項を持つ。前提項は
推論の前提となるノードを直接又は間接に指示するポイ
ンタを保持し、知識項は推論に使用する知識を指定する
ために、知識管理部５に保持する知識のアドレスを保持
する。

【００２１】図６(b)は、(a)に示したコンシューマによ
って前提のノードを指示する一例であり、前記の図５に
よって説明したノードに知識「Ｘ＋Ｗ＝２」を適用す
るためのコンシューマとノードとの接続構造である。

【００２２】このコンシューマは、注目環境が環境Ｆ
を論理的に包含することを制御部３で判定されたとき、
起動可能コンシューマとなり、推論部４の推論が起動さ
れて図５に示す正当化が作られて、コンシューマは
削除される。

【００２３】又、図６(c）は、前記図５のノードとノ
ードを前提として、知識「Ｚ＝Ｘ＋Ｙ」を適用するた
めのコンシューマの接続構造である。このように複数の
ノードを前提とする場合には、図示のように一時的にテ
ンポラリノードを設けて、コンシューマはそれを前提
ノードとして指示する。

【００２４】テンポラリノードには、前提ノードがすべ
て成立する環境（この例の場合、環境「Ａ＆Ｂ＆Ｃ」）
を示し、正当化を介してノードと接続する。この場
合、注目環境がテンポラリノードに示す環境を論理的に
包含するときにコンシューマは起動可能とされ、推論
の結果新しいデータ「Ｚ＝３」が導かれる結果、ノード
が生成されて、図５に示すような接続構造ができて、
コンシューマは削除される。

【００２５】以上のように制御部３の主要な機能は、予
め与えられている戦略に基づいて注目環境を逐次決定
し、注目環境を決定するごとに、待ち行列の全コンシュ
ーマを順次調べて、その注目環境によって起動可能か判
断し、起動可能のコンシューマを推論部４に渡すことで
ある。

【００２６】このように、制御部３は注目環境ごとに、
すべてのコンシューマについて起動可能か否かを１回は
評価し、起動可能と判断したコンシューマは待ち行列か
ら削除して推論処理に渡される。

【００２７】しかし、起動できないと判断されたコンシ
ューマについては、その後に起動可能とした他のコンシ
ューマの推論の結果によって行われるラベル更新処理に
よる正当化の伝播によって、前提ノードの環境が追加さ
れることにより、同じ注目環境で「起動可能」に変化す
る可能性がある。

【００２８】従って、ラベル更新処理で環境を変化させ
たとき、そのノードが前提となっているコンシューマが
あった場合には、そのコンシューマについて、既に評価
が行われていたとしても、必ず再評価をする必要があ
り、そのために、そのコンシューマがその時点で必ず未
処理のコンシューマ群に入るように、待ち行列上の順位
を変えることとし、そのコンシューマを待ち行列の末尾
に移動する。

【００２９】前記のようにコンシューマの待ち行列のリ
ンクを双方向にしているのは、このように再評価のため
に、待ち行列の途中のコンシューマを行列の末尾につな
ぎ変える処理を、行列の先頭から走査して当該コンシュ
ーマの前位のコンシューマを探索しないでもできるよう
にするためである。

【００３０】図７はコンシューマの待ち行列の構造を示
す図であり、待ち行列は先頭にダミーのコンシューマを
ヘッダとして置き、行列上の各コンシューマはnext項で
次位のコンシューマを指示し、prev項で前位のコンシュ
ーマを指示し、新しいノードは順次行列の末尾に追加さ
れるものとし、先頭のヘッダのprev項及び末尾コンシュ
ーマのnext項の値は所定の無効表示値 (以下においてNU
LLという）にする。

【００３１】又、行列の操作のためのポインタとして、
先頭のヘッダを指示するhead、現処理対象のコンシュー
マを指示するcurrent、currentの指示するコンシューマ
の直前位のコンシューマを指示するprev、及び末尾コン
シューマを指示するtailを設ける。

【００３２】図８〜図10は、コンシューマの行列を操作
する処理を必要とする、制御部３、ラベル更新部８及び
コンシューマ管理部７の処理の流れである。以後の処理
の流れの説明において、「aa.bb.cc」のような表現は、
aaで指示されるブロックのbb項で指示されるブロックの
cc項の内容を表すものとする。

【００３３】図８は制御部３の処理の流れであって、先
ず処理ステップ10で所定の条件で結論を得ていないこと
を識別した場合に１つの注目環境についての処理に入
り、処理ステップ11で所与の条件により注目環境を決定
し、処理ステップ12で待ち行列のポインタheadの内容を
ポインタprevに設定して各コンシューマについての処理
を開始する。

【００３４】処理ステップ13でポインタcurrent にpre
v.next(即ちprevで指示するコンシューマのnext項の内
容)を設定し、処理ステップ14でcurrentがNULLか識別
し、それがNULLなら行列の末尾まで処理を終わったの
で、現注目環境についての処理は終了する。

【００３５】currentがNULLでなければ、処理ステップ1
5でcurrentの指示するコンシューマが起動可能か、即ち
そのコンシューマの指示するすべての前提ノードを成立
させる環境が現注目環境に含まれるかを判定し、含まれ
なければこのコンシューマは起動できないので、処理ス
テップ16でポインタprevにcurrentの値を設定して処理
ステップ13に戻り、次のコンシューマの処理に移る。

【００３６】処理ステップ15で起動可能と判定すれば、
処理ステップ17でcurrent.nextをprev.next に設定し、
処理ステップ18でポインタprevの値をcurrent.next.pre
v に設定して、current の前位と次位のコンシューマが
直接リンクされるようにすることにより、そのコンシュ
ーマを待ち行列から削除した後、処理ステップ19で、cu
rrent の指示するコンシューマを渡して推論部４を起動
する。

【００３７】そこで、推論部４が推論を実行し、その結
果により前記のようにノード管理部６、ラベル更新部８
又は矛盾管理部個が起動され、必要な場合にはコンシュ
ーマ管理部７が動作した後、制御部３へ制御が戻される
ので、制御部３は処理ステップ13で引き続いて次のコン
シューマの処理を始める。

【００３８】図９はラベル更新部８の処理の流れであっ
て、ラベル更新部８は推論部４から更新すべき正当化Ｊ
を指定して起動されると、処理ステップ20で変数nodeに
正当化Ｊの帰結項の値を設定し、処理ステップ21でnode
で指示するノードのラベル項に、正当化Ｊの前提項で指
示する全ノードの環境の論理積を追加するように更新す
る処理をする。

【００３９】処理ステップ22で、その更新処理の結果ラ
ベル項の内容が変化したか識別し、変化の無い場合には
処理を終わるが、変化がある場合には正当化を伝播する
ための処理に入り、処理ステップ23で識別してnode.帰
結(nodeで指示するノードの帰結項)で指示する要素(正
当化又はコンシューマである) をすべて処理するまで、
以下の処理を繰り返す。

【００４０】即ち、処理ステップ24で node.帰結の指示
する未処理要素から一要素のアドレスを変数Ｃに設定
し、処理ステップ25でＣの指示する要素がコンシューマ
か否か識別し、コンシューマでない場合は正当化である
ので、処理ステップ26に進んでその正当化を再び正当化
Ｊとして本ラベル更新処理を再帰的に実行する。

【００４１】コンシューマである場合には、前記の理由
によりそのコンシューマの再評価が必要になるので、そ
のコンシューマを行列の末尾に移動させるために、先ず
処理ステップ27、28で行列から外し、処理ステップ29〜
32で末尾につなぐ。

【００４２】即ち処理ステップ27でC.nextをC.prev.nex
t へ設定し、次に処理ステップ28でC.prevをC.next.pre
v に設定して、Ｃで指示するコンシューマの前位と次位
のコンシューマが直接リンクするように変更することに
よって、Ｃを行列の現位置から除く。

【００４３】次に、処理ステップ29でＣを行列のポイン
タtailで指示するtail.next へ設定し、処理ステップ30
でtailの値をC.prevに設定し、処理ステップ31でC.next
の値をNULLにし、最後にtailをＣの値にすることによ
り、Ｃのコンシューマを行列の末尾にする。以上により
node.帰結の指示する未処理要素の１個ごとの処理を終
わる。

【００４４】図10はコンシューマ管理部７の処理の流れ
であり、ノード管理部６が新しいノードｎを渡してコン
シューマ管理部７を起動すると、知識管理部５が保持す
る知識を調べてｎが前提となる知識が得られるごとに処
理ステップ41以降の処理を行ってコンシューマを生成
し、処理ステップ40で識別して全知識を調べるまでこの
処理を繰り返す。

【００４５】ノードｎのデータを前提とする知識がある
と、処理ステップ41でそのアドレスを変数Ｋとし、処理
ステップ42でＫの知識の前提となるノードが１個か複数
かで処理を分ける。

【００４６】前提が１個の場合には、前記図６(b）によ
って説明したような構造にすればよいので、処理ステッ
プ43で新しいコンシューマＣを作って、待ち行列の末尾
に追加し、処理ステップ44でC.知識に知識のアドレスＫ
を設定し、処理ステップ45でC.前提にｎを設定してコン
シューマから前提ノードを指示させ、処理ステップ46で
n.帰結にＣを追加して、前提ノードからコンシューマを
指示するリンクを作って、その知識についての処理を終
わる。

【００４７】知識の前提が複数ある場合には、更に複数
の前提ノードからなる前提の組が複数組ある場合がある
ので、処理ステップ47で識別して、そのようなすべての
前提の組について、処理ステップ48以降の処理を繰り返
して、それらの組ごとにコンシューマを生成する。

【００４８】即ち処理ステップ48でＫの前提をなすノー
ドの１組を検索すると、処理ステップ49で正当化Ｊを生
成して、その前提項で前提ノードを指示し、各前提ノー
ドの帰結項から正当化Ｊを指示するリンクを作る。

【００４９】処理ステップ50で前記図６(c) で説明した
テンポラリノードＴを作り、処理ステップ51で前提ノー
ドの環境の論理積をテンポラリノードに設定し、処理ス
テップ52で正当化Ｊの帰結項にＴを設定し、処理ステッ
プ53でテンポラリノードの正当化項にＪを設定する。

【００５０】処理ステップ54で新しいコンシューマＣを
作って、待ち行列の末尾に追加し、処理ステップ55でC.
知識に知識のアドレスＫを設定し、処理ステップ56でC.
前提にテンポラリノードのアドレスＴを設定してコンシ
ューマとテンポラリノードをリンクし、処理ステップ57
でT.帰結にＣを設定して、その前提の組についての処理
を終わる。

【００５１】

【発明が解決しようとする課題】前記のようにコンシュ
ーマは双方向リンクで待ち行列を作る構造になるので、
各コンシューマに管理の目的のみのために２個のポイン
タを必要とし、比較的大きなメモリを必要とすると共
に、行列の操作において双方向リンクを操作するための
処理時間も多くなる。

【００５２】本発明は、コンシューマ機構のメモリ所要
量と、コンシューマ待ち行列操作の処理時間を共に減少
できる仮説推論処理方法を目的とする。

【００５３】

【課題を解決するための手段】図１は、本発明の構成を
示すブロック図である。図は仮説推論処理方法の構成で
あって、本発明を適用するシステムは、所与の仮説の論
理積で表す環境について、該環境の論理和の下に成立す
るデータを示すノードを設け、該データを前提として所
与の知識によって結論となるデータを推論する場合に、
該知識と前提データ群との組合せごとにコンシューマ70
を設け、コンシューマ70から当該知識と当該前提データ
の該ノードを指示し、コンシューマ70を待ち行列71に接
続し、所定の注目環境ごとに、待ち行列71の先頭から各
コンシューマ70の前提ノードの環境を順次評価し、当該
注目環境によって、すべての該ノードの該環境が成立し
ているコンシューマ70を起動可能コンシューマとし、当
該起動可能コンシューマについて、所定の推論処理を行
い、待ち行列71から削除し、該推論処理の結果で該環境
の論理和の内容が更新された該ノードを該前提とするコ
ンシューマ70がある場合には、当該コンシューマを当該
注目環境について再評価するシステムである。

【００５４】第１の発明では、このシステムに再評価用
スタック72を設け、コンシューマ70の待ち行列71を、単
方向リンクのみで形成し（処理73）、該再評価を要する
コンシューマを検出した場合には、当該コンシューマ70
の待ち行列71上の接続を保持したまま、該コンシューマ
を再評価用スタック72に登録する（処理74）。

【００５５】該注目環境ごとの該コンシューマ評価処理
（処理75）では、待ち行列71の該リンクに従ってすべて
のコンシューマ70の該評価を行った後、再評価用スタッ
ク72に登録されたすべてのコンシューマ70を順次再評価
スタック72から取り出して評価し、該起動可能コンシュ
ーマには、起動可能としたことを示す所定の状態表示を
行う。

【００５６】第２の発明では、第１の発明の各コンシュ
ーマ70に、２値を表示するフラグを設けて、前記注目環
境ごとのコンシューマ評価処理75の開始時に、すべての
該コンシューマの該フラグが同一の一方の値を初期値と
して保持するようにし、該評価処理を行ったコンシュー
マ70の該フラグを他方の値に更新する。

【００５７】前記再評価用スタック72にコンシューマ70
を登録する（処理74）場合には、当該コンシューマの該
フラグが他方の値に更新されている場合のみ該登録を実
行し、且つ当該フラグを該初期値に再設定する。

【００５８】

【作用】本発明の仮説推論処理方法により、コンシュー
マの待ち行列を単方向リンクとするので、従来の各コン
シューマから１個のポインタが不要になるので、その領
域を省くか、又は他の情報の領域に転用することによっ
て、システムの所要メモリ量を減少できる。

【００５９】行列を単方向リンクにした結果、再評価コ
ンシューマを従来のように行列の末尾に移動する方法を
採ると、当該コンシューマを行列から一旦外すために、
行列の先頭から走査して、そのコンシューマの前位コン
シューマを検索することが必要になり、処理時間を大幅
に増加する。

【００６０】そこで本発明では、再評価用スタックを設
けて、再評価するコンシューマは、行列上の移動を行う
ことなく、再評価用スタックにそのコンシューマのアド
レスを登録し、コンシューマの評価では、行列を末尾ま
で処理した後、再評価用スタックに登録されているコン
シューマの再評価を行うようにする。

【００６１】このようにすることにより、従来行ってい
たような、再評価するコンシューマの行列上の移動を双
方向のポインタを操作して行う処理が、本発明では単に
そのコンシューマのアドレスをスタックする処理に変わ
るので、処理時間を減少することができる。

【００６２】なお、以上の再評価用スタックへの登録に
よると、再評価を要すると判定した時点で、これから最
初の評価が行われる順位にあるコンシューマもスタック
され、そのようになったコンシューマは不必要に２回処
理対象となる。

【００６３】それでも、起動可能となったことを示す表
示を参照することによって、再評価対象としないことを
識別できるので論理的な不都合は生じ無い。しかし、第
２の発明によるフラグをコンシューマに設けることがで
きる場合には、そのフラグによって再評価用スタックへ
の登録要否を識別して、必要なもののみ登録するように
すれば更に効率よく処理することができる。

【００６４】

【実施例】図３(a)は本発明のコンシューマのデータ構
造例を示す図であり、図６(a)で説明した従来のコンシ
ューマのprev項が無くなっている。

【００６５】図３(d)は(a)のコンシューマによって構成
する待ち行列の例であり、単方向リンクで構成する。行
列の操作のためのポインタ等は従来と同様として、ポイ
ンタhead、current、prev、及びtailを設ける。

【００６６】又、本発明により、コンシューマの待ち行
列と組み合わせて再評価用スタックを設け、後述のよう
にして再評価を要するコンシューマのアドレスをこのス
タックに登録する。

【００６７】図３(b) は第２の発明におけるコンシュー
マの例であって、知識項の１ビットをフラグに使用し、
後述のようにして再評価用スタックへの登録要否を識別
するのに使用する。待ち行列は前記(d)と同様になる。

【００６８】なお、このデータ構造を採るためには、知
識を格納する領域のアドレス境界を工夫する等によっ
て、知識を指示するアドレスを格納する場合のビット長
を１ビット短縮できるようにする必要がある。

【００６９】又、図３(c)は、(a)のように減少したポイ
ンタの部分を、前記テンポラリノードのラベル項に使用
する例であって、このようなコンシューマの構造にする
ことにより、テンポラリノードを設ける必要が無くな
り、例えば前記図６(c) に示した構造を、図６(d)に示
すように縮小することができる。

【００７０】従って、テンポラリノードを設けるコンシ
ューマが多くなるシステムの場合には、このようにラベ
ル項を持つ構造のコンシューマを使用することによっ
て、所要メモリ量を更に減少することができる。

【００７１】この場合には、正当化が指示しているデ
ータ構造がコンシューマを表現しているのか（即ち推論
がまだ行われていないのか）、或いは正当化が指示し
ているデータ構造が推論結果のノードを表現しているの
か、を識別できることが必要であるが、その識別は例え
ば次のようにして比較的簡単にできる。

【００７２】それは、例えば知識を格納するメモリ領域
を特定の領域として、アドレス値で他の領域と簡単に区
別できるように領域を管理しておき、コンシューマかノ
ードかの判別を要する場合には、データ構造の第４項の
アドレス値が知識の領域を指示しているか否か識別する
ようにする。

【００７３】このデータ構造の第４項が知識項として、
知識へのアドレスを格納していればコンシューマであ
り、帰結項として帰結となる他の正当化を指示するポイ
ンタを格納していればノードであるから、以上によって
データ構造がコンシューマかノードかを識別することが
できる。

【００７４】図11は第１の発明における制御部３の処理
の流れ図であって、前記従来の図８に対応する処理であ
り、処理ステップ100〜103は従来の処理ステップ10〜13
と同じである。

【００７５】処理ステップ104 で従来と同様に行列の末
尾まで処理したか識別するが、末尾まで処理を終わった
場合には、本発明により後述のように再評価用スタック
の処理をする。

【００７６】処理ステップ104で末尾まで処理してない
と判定したときは、処理ステップ105でcurrent.前提がN
ULLか識別し、NULLであれば処理ステップ106 でcurren
t.nextをprev.next に設定することによって、現処理中
のコンシューマを行列から削除する。

【００７７】この「current.前提＝NULL」は本発明によ
って必要となったコンシューマの処理状態の表示であっ
て、第１の発明の場合には、行列を走査して評価するコ
ンシューマが、既に再評価用スタックに登録されている
場合があるので、起動可能として推論したコンシューマ
は識別できるようにして、再評価スタックから取り出し
た場合に捨てるようにしなければならないので、例えば
推論処理したコンシューマは、既に不要な前提項の値を
NULLにすることによって、その表示とする。

【００７８】又、第１及び第２の発明ともに、再評価ス
タックに登録されたコンシューマを、スタックから取り
出して評価した結果が起動可能となっても、待ち行列か
ら削除するためには、行列を先頭から走査して、削除す
るコンシューマの位置を識別することが必要になる。

【００７９】それを避けるために、再評価スタックから
取り出して推論処理をしたものについて、前記と同じよ
うに「current.前提＝NULL」にして、評価処理のための
待ち行列走査のついでに、前記のように処理ステップ10
5、106の処理によって行列から削除する。

【００８０】処理ステップ105でcurrent.前提がNULLで
なければ処理ステップ107でコンシューマが起動可能か
評価し、起動可能でなければ処理ステップ108 で、ポイ
ンタprevにcurrentの値を設定して処理ステップ103に戻
り、次のコンシューマの処理に移る。この部分は従来と
同様である。

【００８１】処理ステップ107で起動可能と判定すれ
ば、処理ステップ109でcurrent.nextをprev.next に設
定して、そのコンシューマを待ち行列から削除する。こ
のように従来は処理ステップ17、18の２ステップの処理
を要したリンクの操作が本発明では１ステップで終わ
る。

【００８２】その後従来と同様に、処理ステップ110
で、currentの指示するコンシューマを渡して推論部４
を起動するが、推論処理の後、制御部３へ制御が戻され
ると、処理ステップ111 でcurrent.前提をNULLとして、
前記のとおり起動済みの表示とした後、処理ステップ10
3へ戻る。

【００８３】処理ステップ104で、「current＝NULL」の
場合には、処理ステップ112 で識別して、再評価用スタ
ックが空になるまで、スタックに登録されているコンシ
ューマを順次以下のように処理する。

【００８４】処理ステップ113 で、再評価用スタックに
登録されているコンシューマのアドレスを１個取り出し
てポインタcurrent に設定して、そのコンシューマの処
理を開始し、処理ステップ114 でcurrent.前提がNULLか
識別する。

【００８５】NULLであれば、前記のとおり既に行列上で
起動可能となって処理されたコンシューマであるので、
そのまま処理をおわって処理ステップ112 に戻り、NULL
でなければ処理ステップ115 でそのコンシューマが起動
可能か評価する。

【００８６】起動可能でなければ、処理ステップ112 へ
もどり、起動可能であれば処理ステップ116、117によ
り、前記処理ステップ110、111と同様に推論部の処理、
及び起動済みの表示の設定をして、処理ステップ112に
戻る。

【００８７】図12は第１の発明のラベル更新部８の処理
の流れであって、前記従来の図９に対応する処理であ
り、処理ステップ120〜126の処理は、図９の処理ステッ
プ20〜26と同様である。

【００８８】処理ステップ125 で、従来の処理ステップ
25と同様にＣの指示する要素がコンシューマか否か識別
し、コンシューマである場合には再評価が必要なコンシ
ューマとして再評価されるようにする。

【００８９】しかし、その処理は本発明により、従来の
ような行列内の移動ではなく、処理ステップ127 によっ
て、コンシューマのアドレスであるＣの内容を再評価用
スタックに登録することで完了する。即ち従来は処理ス
テップ27〜32の６ステップによる行列のリンク操作を行
っていたのが、スタックへの登録の１ステップに短縮さ
れる。

【００９０】第１の発明の場合のコンシューマ管理部７
の動作は、図10によって説明した従来の処理の流れと同
様である、但し処理ステップ43及び処理ステップ54にお
ける新しいコンシューマを作って行列の末尾に追加する
場合に、本発明では単方向リンクのみを処理すればよい
ようになる。

【００９１】次に第２の発明の場合の処理例を説明す
る。第２の発明で前記のように設けるフラグの使い方と
しては、例えば制御部３のコンシューマ評価処理の最初
に、全コンシューマのフラグを例えば初期値「０」に設
定し、評価済みを「１」で表すようにしてもよい。

【００９２】しかし、このようにして評価処理を進める
と、行列から再評価用スタックまで一連の処理を完了し
たときには、すべてのコンシューマのフラグが「１」に
なっている。

【００９３】そこで、初期値を固定値「０」にしない
で、「０」を初期値として一連の処理を完了すると、次
の回の処理では「１」を初期値として、評価済みを
「０」で表すというように、交互にフラグの値の解釈を
交換することにすれば、処理の最初に初期設定を行う必
要が無くなる。

【００９４】図13〜図15は、第２の発明を後者の方法に
よって処理する場合の、各部の処理の流れである。図13
は制御部３の処理の流れであって、変数FLAGを設けて、
例えばシステムの運転開始時にFLAGを１に初期設定して
おくものとする。このようにして制御部３は処理ステッ
プ100〜110を前記図11と同様に処理する。

【００９５】但し、処理ステップ101aでこの回の処理に
おけるFLAGの値を、現に保持されている前回の値の反転
値に更新する処理が入る。この結果、FLAGの値は、現在
の全コンシューマのフラグと同じ値になる筈である。

【００９６】又処理ステップ107 でコンシューマが起動
可能か評価し、起動可能でない場合に次のコンシューマ
を処理するために処理ステップ108でポインタcurrentの
値をポインタprevに設定する処理は前記と同様である
が、次に現に処理したコンシューマに評価済みの表示を
するために、処理ステップ108aでcurrent.フラグを反転
した後、処理ステップ103に戻る。

【００９７】起動可能の場合には前記と同様に処理ステ
ップ109、処理ステップ110で推論処理を実行するが、第
２の発明により後述のように、未評価のコンシューマが
再評価用スタックに登録されることは無くなるので、前
記の処理ステップ111 の処理は不要になる。

【００９８】処理ステップ104 で、待ち行列の末尾まで
処理したと識別した場合には、再評価用スタックの処理
に入り、処理ステップ112、113でスタックに登録されて
いるコンシューマのアドレスを１個取り出すと、直ちに
処理ステップ115 でそのコンシューマが起動可能か識別
する。

【００９９】即ち、第２の発明では後述のようにして、
待ち行列上で未評価のコンシューマが再評価用スタック
に登録されることは無いので、第１の発明の場合の処理
ステップ114 のように、スタックから取り出したコンシ
ューマが、既に起動可能として処理済みではないかチェ
ックする必要は無い。

【０１００】処理ステップ115で起動可能と評価すれ
ば、前記と同様に処理ステップ116、処理ステップ117
の処理をする。又、起動可能で無い場合には、処理ステ
ップ115aでcurrent.フラグを反転して、評価済みにして
おく。

【０１０１】図14は第２の発明におけるラベル更新部８
の処理の流れであり、処理ステップ120から126までの処
理、及び処理ステップ127 は、前記第１の発明の図12の
処理と同様である。

【０１０２】処理ステップ125 でノードの帰結項で指示
する要素がコンシューマであると識別した場合に、第２
の発明では処理ステップ125aで、そのコンシューマのフ
ラグC.フラグがFLAGに保持する値と同一か識別し、FLAG
と異なれば評価済みであるので、その場合のみ処理ステ
ップ125bでC.フラグを反転して、未評価の表示に戻し、
処理ステップ127で再評価用スタックに登録する。

【０１０３】図15は第２の発明のコンシューマ管理部７
の処理の流れであり、処理ステップ140〜157は前記図10
により説明した従来の処理の処理ステップ40〜57と同様
である。

【０１０４】第２の発明により、新しく生成したコンシ
ューマのフラグを設定する必要があるので、処理ステッ
プ145a及び処理ステップ156aが挿入され、フラグをその
時の変数FLAGの値に設定する。

【０１０５】

【発明の効果】以上の説明から明らかなように本発明に
よれば、仮説推論処理を行う装置において、コンシュー
マ機構のメモリ所要量と、コンシューマの待ち行列操作
の処理時間を共に減少して、システムの処理効率を改善
するという著しい工業的効果がある。

【図面の簡単な説明】

【図１】 本発明の構成を示すブロック図

【図２】 仮説推論装置の構成例ブロック図

【図３】 本発明のコンシューマのデータ構造を示す図

【図４】 ノード及び正当化のデータ構造を説明する図

【図５】 推論結果の表現例を示す図

【図６】 コンシューマのデータ構造を説明する図

【図７】 従来のコンシューマの待ち行列の構造を示す
図

【図８】 従来の制御部の処理の流れ図

【図９】 従来のラベル更新部の処理の流れ図

【図１０】 従来のコンシューマ管理部の処理の流れ図

【図１１】 第１の発明の制御部の処理の流れ図

【図１２】 第１の発明のラベル更新部の処理の流れ図

【図１３】 第２の発明の制御部の処理の流れ図

【図１４】 第２の発明のラベル更新部の処理の流れ図

【図１５】 第２の発明のコンシューマ管理部の処理の
流れ図

【符号の説明】

１ 問題解決部 ２ 無矛盾性管理部 ３ 制御部 ４ 推論部 ５ 知識管理部 ６ ノード管理部 ７ コンシューマ管理部 ８ ラベル更新部 ９ 矛盾管理部 10〜32、40〜57、100〜117、120〜126、140〜157 処理
ステップ 70 コンシューマ 71 待ち行列 72 再評価用スタック 73〜75 処理

Claims (2)

【特許請求の範囲】
1. 【請求項１】 所与の仮説の論理積で表す環境につい
   て、該環境の論理和の下に成立するデータを示すノード
   を設け、該データを前提として所与の知識によって結論
   となるデータを推論する場合に、 該知識と前提データ群との組合せごとにコンシューマ(7
   0)を設け、該コンシューマから当該知識と当該前提デー
   タの該ノードを指示し、 該コンシューマを待ち行列(71)に接続し、所定の注目環
   境ごとに、該待ち行列の先頭から各該コンシューマの前
   提ノードの環境を順次評価し、当該注目環境によって、
   すべての該ノードの該環境が成立している該コンシュー
   マを起動可能コンシューマとし、当該起動可能コンシュ
   ーマについて、所定の推論処理を行い、該待ち行列から
   削除し、 該推論処理の結果で該環境の論理和の内容が更新された
   該ノードを該前提とする該コンシューマがある場合に
   は、当該コンシューマを当該注目環境について再評価す
   るシステムにおいて、 再評価用スタック(72)を設け、 該コンシューマの待ち行列(71)を、単方向リンクのみで
   形成し(73)、 該再評価を要するコンシューマ(70)を検出した場合に
   は、当該コンシューマの該待ち行列上の接続を保持した
   まま、該コンシューマのアドレスを該再評価用スタック
   (72)に登録し(74)、 該注目環境ごとの該コンシューマ評価処理(75)では、該
   待ち行列(71)の該リンクに従ってすべての該コンシュー
   マの該評価を行った後、該再評価用スタックに登録され
   たすべての該コンシューマを順次該再評価スタック(72)
   から取り出して評価し、 該起動可能コンシューマには、起動したことを示す所定
   の状態表示を行うように構成されていることを特徴とす
   る仮説推論処理方法。
2. 【請求項２】 各前記コンシューマ(70)に、２値を表示
   するフラグを設けて、前記注目環境ごとのコンシューマ
   評価処理の開始時に、すべての該コンシューマの該フラ
   グが同一の一方の値を初期値として保持するようにし、 該評価処理を行った該コンシューマの該フラグを他方の
   値に更新し、 前記再評価用スタック(72)に該コンシューマを登録する
   場合には、当該コンシューマの該フラグが他方の値に更
   新されている場合のみ該登録を実行し、且つ当該フラグ
   を該初期値に再設定する、請求項１記載の仮説推論処理
   方法。