JPH05342247A

JPH05342247A - 非線形不等式推論方法

Info

Publication number: JPH05342247A
Application number: JP16834892A
Authority: JP
Inventors: Masaru Oki; 優大木; Eiji Ohira; 栄二大平; Hiroshi Shinjo; 広新庄; Masahiro Abe; 正博阿部
Original assignee: Agency of Industrial Science and Technology
Current assignee: National Institute of Advanced Industrial Science and Technology AIST
Priority date: 1992-06-04
Filing date: 1992-06-04
Publication date: 1993-12-24

Abstract

(57)【要約】【構成】ネットワーク制御部１００は、制約式１０２
を読み込み変数を取り出して、制約式と変数をネットワ
ーク部１１４に渡す。制約式と変数のノードを作り、他
の制約式ノードや変数ノードと結合して制約のネットワ
ークを構成する。結果はネットワーク制御部１１０に渡
され推論結果１０８に格納される。このような構成に
て、更新メッセージの中に新しい上限値と下限値以外に
これまで伝播してきた変数ノードにおける更新情報であ
る変数名と上限値あるいは下限値を履歴として記録して
送出し、履歴を調べ、同じ変数ノードに対する上限値と
下限値の更新が一定回数以上行われていることを検知し
たならば、更新メッセージの処理を中断することを特徴
とする。【効果】不等式で表わされた制約を解く問題解決器に
おいて、無限に処理が繰り返されなくて済み、無駄な処
理を防ぐことができる等の効果がある。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、非線形不等式を解く推
論方法にかかわる。特に、区間法と呼ばれるアルゴリズ
ムを使った非線形不等式の解法に適する。

【０００２】

【従来の技術】変数の上限値と下限値を計算して、非線
形連立不等式を解くアルゴリズムとして、区間法がある
（「量に関する不十分な情報に基づく推論」綱谷勝俊、
西田豊明、堂下修司著、知識工学と人工知能研究会、５
２−５、情報処理学会、１９８７，あるいは「COMMONSE
NSE ARITHMETIC REASONING」、Proc. of AAAI-86、pp.
118-124、1986）。区間法は、四則演算に対して図５の
ような規則を適用することにより、変数の上限値と下限
値を計算するアルゴリズムである。図５において、変数
の上限値と下限値を”〔”と”〕”で囲むことによって
表わし、変数Ａと変数Ｂの上限値と下限値をそれぞれ、
〔l1，u1〕と〔l2，u2〕で表わすと、四則演算に関する
上限値と下限値を求めることができる。

【０００３】例えば、Ｘ＝Ｙ＋Ｚという式において、
Ｙ、Ｚの上限値と下限値が、それぞれ、〔−２，３〕と
〔５，６〕とするならば、Ｘの上限値と下限値は、図５
の規則（１）により〔３，９〕となる。

【０００４】線形連立不等式を解くアルゴリズムとして
は、線形計画法で使われているシンプッレクス法などが
あるが、それらのアルゴリズムでは、非線形連立不等式
を解くことはできない。機械や電気、電子部品などにお
ける設計において、数値に関する制約は、一般に線形連
立不等式にならず、非線形連立不等式になる。そのた
め、非線形連立不等式を解くことは、設計において数値
に関する制約を解くために、不可欠な技術である。しか
し、非線形連立不等式を効率良く解くアルゴリズムは知
られていない。その中で、区間法によるアルゴリズム
は、非線形連立不等式を完全には解けないが、非線形連
立不等式を扱うことができるアルゴリズムの一つであ
る。

【０００５】しかし、区間法によるアルゴリズムは論文
等で報告されているが、実現方式は報告されていない。
実際に区間法によるアルゴリズムを使って、非線形連立
不等式を解くシステムを作るといくつか問題が生じる。
その一つは、変数の上限値と下限値を計算する場合、無
限に処理が繰り返されることがあることである。

【０００６】例えば、以下の式は線形不等式であり、シ
ンプッレクス法などで完全に解くことができ、Ｘ＝１．０−Ｙ（１）Ｙ＝０．２＊Ｘ（２）Ｘ＞０．１（３）ＸとＹはそれぞれ、５／６と１／６になる。しかし、区
間法では、連立不等式を直接解くことができず、上限値
と下限値を求める処理は、例えば、以下のように無限に
繰り返される。

【０００７】Ｙ＜０．９（１）と（３）より（４）Ｙ＞０．０２（２）と（３）より（５）Ｘ＜４．５（２）と（４）より（６）Ｘ＜０．９８（１）と（５）より（７）Ｙ＜０．１９８（２）と（７）より（８）Ｘ＞０．８０２（１）と（５）より（９）Ｙ＞０．１６０４（１）と（５）より（１０）そのため、区間法を実際に使うためには、無限に繰り返
される処理を中断する機構が必要である。

【０００８】さらに、これらの式に、Ｓ＝２．０＊Ｘ（１１）Ｔ＝Ｓ＋１．０（１２）Ｗ＝３．０＊Ｔ＋２．０（１３）のような式が加わったならば、ＳとＴ、Ｗの上限値と下
限値は、Ｘの上限値と下限値に連動して、計算される。
その際、上限値と下限値をどのような順序で計算するか
が問題となる。順序の一つは、深さ優先に対応するもの
で、もう一つは幅優先に対応するものである。深さ優先
は、上限値と下限値を計算する候補が複数ある場合、ど
れか一つを選び、残りは一時保留して、選ばれたものの
処理が終わった後、計算するような計算順序である。上
限値と下限値を計算する候補が複数ある場合は、ある変
数を使っている式が複数ある場合か式の中に上限値と下
限値を計算すべき変数が複数ある場合である。幅優先
は、上限値と下限値を計算する候補が複数ある場合は、
まず、候補のすべてを使って、複数の変数の上限値と下
限値を求め、さらに、求まった上限値と下限値を使っ
て、計算する候補を求め、すべての候補を使って、複数
の変数の上限値と下限値を求める計算順序である。例え
ば、Ｙ＝Ｘ＋Ｚ（１４）Ｓ＝Ｘ＋Ｔ（１５）のような式がある場合、Ｘの上限値と下限値が新しくわ
かった場合、（１４）式ではＹとＺの２つの変数が処理
対象の候補となる。また、さらに、（１５）式も候補と
なりえて、その中のＳとＴの２つの変数が処理対象とな
る。深さ優先では、ＹとＺ、Ｓ、Ｔの中から一つ選び、
その上限値と下限値を計算する。そして、その変数を使
って、処理候補を求め、処理を続ける。最初の候補の残
りの処理は、最初に選ばれた変数に関する処理が終わる
まで保留される。幅優先では、候補のＹとＺ、Ｓ、Ｔの
すべての上限値と下限値を計算し、次にそれらを使って
処理すべき候補を求め、上限値と下限値を求めることを
行う。区間法のアルゴリズムでは、どちらの計算順序が
良いかは、処理すべき式の形により、決められない。た
だし、並列処理には、処理すべき候補が多いほど、有利
なため、幅優先の方が向いている。

【０００９】幅優先順序で計算する場合、一つの変数に
色々な式を使って計算された上限値と下限値が伝播され
る。例えば、（６）式と（７）式の例では、続けてＸの
上限値が更新されている。もし、（６）式の上限値を使
った計算が進んだ場合、（７）式の上限値を使った計算
でより厳しい制約が得られるため、（６）式の上限値を
使った処理は全く無駄になる。無駄な計算を避けるに
は、より厳しい制約（上限値）が求まったならば、前の
制約を使った処理を棄却するほうが望ましい。前の制約
を使った処理を棄却できるならば、計算量は、幅優先順
序の法が深さ優先順序より計算量が少なくなる可能性が
ある。

【００１０】しかし、無駄な処理を棄却するだけでは、
問題がある。（５）式と（１０）式の例を見ると、（１
０）式の下限値は（５）式の下限値より厳しくなってい
るため、（１０）式の下限値がわかった時点で、（５）
式の下限値に関する処理を棄却する。ところが、（１
０）式の下限値が求まったのは、（５）式の下限値に関
する処理を行ったためである。もし、（５）式の下限値
に関する処理をすべて棄却すると、（１０）式の下限値
の処理まで棄却されてしまうことになる。そのため、よ
り厳しい制約が求められた時に前の制約の処理を棄却す
る場合、より厳しい制約が自分自身の処理結果が起因し
た制約に基づいている場合は、前の処理を単純に棄却す
ることはできない。

【００１１】また、次のような式のような場合、Ｚ＝Ｙ＋１．０（１６）Ｙ＝Ｒ＊Ｚ（１７）Ｒ＞２．０（１８）Ｒ＜３．０（１９）Ｚ＞０．１（２０）Ｙの下限の変化は、以下のようになる。

【００１２】Ｙ＞０．２（２１）Ｙ＞２．４（２２）Ｙ＞６．８（２３）Ｙ＞１５．６（２４）Ｙ＞３３．２（２５）（２１）式から（２５）式へのＹの下限の変化は、２．
２倍、４．４倍、８．８倍、１７．６倍と増えており、
Ｙの下限が発散していることがわかる。これは、（１
６）式から（２０）式が正帰還を表わしてためであり、
その結果、（２１）式から（２５）式のように下限が発
散する。

【００１３】従来の連立不等式を解くアルゴリズム（例
えば、線形計画法等で使われているシンプレックス法）
は、正帰還を扱うことができず、実際の挙動とは別な解
を出す。例えば、（１６）式から（２０）式の代わり
に、Ｒが２．０となった以下のような式の場合、Ｚ＝Ｙ＋１．０（２６）Ｙ＝２．０＊Ｚ（２７）Ｚ＝−１．０、Ｙ＝−２．０となる。また、（２６）式
と（２７）式に（２０）式が加わった場合は、解が存在
しない状態になってしまう。このように、従来の連立不
等式を解くアルゴリズムでは、正帰還を含むような電子
回路などの連立不等式を扱うことはできない。

【００１４】

【発明が解決しようとする課題】不等式による制約式と
変数をノードとして表わし、それらをネットワークでつ
なぎ、制約式のノード（制約式ノード）では、変数の上
限値か下限値が伝播されたならば、制約式を使ってその
制約式に含まれる別の変数の上限値と下限値を求め、よ
り厳しい上限値あるいは下限値が求まったならば、それ
をその制約式に含まれる変数のノード（変数ノード）に
更新メッセージとして伝播し、変数ノードでは、伝播さ
れた変数の上限値と下限値がこれまでより厳しい制約で
あるならば、他の制約式ノードにその変数の上限値と下
限値を伝播することによって、制約式全体のより厳しい
制約を求める問題解決器において、ある変数の上限値あ
るいは下限値を決めたことが、その変数自身の上限値あ
るいは下限値にも影響するような場合、その変数への上
限値あるいは下限値の更新が無限に繰り返されることが
あり、処理が終了しないことが起こりえる。そのような
場合、下限値あるいは上限値が一定の範囲で収束したこ
とを検知し処理が無限に繰り返されることを回避する。

【００１５】また、変数の上限値あるいは下限値のより
厳しい上限値あるいは下限値が求まった状況において、
その変数に対する以前の上限値あるいは下限値を元にし
て進められている他のノードでの処理があるならば、そ
れらの処理の結果は、後の更新された上限値と下限値を
使った処理によって更新されてしまうため、無駄な処理
となる。より効率的な処理を行うためには、この無駄な
処理を減らす必要がある。

【００１６】また、制約式が正帰還を表わす式を含む場
合は、ある変数の上限値あるいは下限値が発散してしま
い、解が求まらない状況になるが、正帰還が起きている
ことを検知する必要がある。

【００１７】

【課題を解決するための手段】本発明は、その変数自身
の上限値あるいは下限値にも影響するような場合に処理
が終了しない事態ことを解決するために、更新メッセー
ジの中に新しい上限値と下限値以外にこれまで伝播して
きた変数ノードにおける更新情報である変数名と上限値
あるいは下限値を記録し、また、同じ変数に対するより
厳しい上限値と下限値の更新が起きたならば、棄却フラ
グを棄却に設定することにより前の上限値と下限値を使
って別の変数の上限値と下限値を求める処理を棄却する
ために、更新メッセージにメッセージの無効である棄却
を意味する棄却フラグを持ち、棄却フラグが棄却になっ
ている場合は更新メッセージを無視し、同じ変数に対す
る上限値と下限値の更新が繰り返し起きて、かつ上限値
か下限値が発散している場合に、上限値と下限値が発散
していることを発散を検知して処理を中断し、発散が起
きていることを報告するものである。

【００１８】

【作用】更新メッセージの中の変数名と上限値あるいは
下限値からなる履歴から、同じ変数ノードに対する上限
値と下限値の更新が一定範囲に収束していれば、正常終
了とし、一定回数以上繰り替えされるているならば、収
束しないとして処理を中断することにより、更新が無限
回繰り返されることを回避する。また、更新メッセージ
にメッセージの無効である棄却を意味する棄却フラグが
棄却に設定されていたならば、処理を無視するようにし
ておき、同じ変数に対するより厳しい上限値と下限値の
更新が起きた場合に更新メッセージにメッセージの無効
である棄却を意味する棄却フラグを棄却に設定すること
により、前の上限値と下限値を使って別の変数の上限値
と下限値を求める処理を棄却し、無意味な処理を減らし
高速化する。また、更新メッセージの履歴を調べること
により、同じ変数の上限値か下限値が発散していること
を調べ、発散しているならば、発散が起きていることを
報告し処理を終了する。この報告により、正帰還による
発散が起きていることを知ることができる。

【００１９】

【実施例】図２は、推論制御装置の構成図である。装置
全体の構成と動作の概要を説明する。

【００２０】装置は、制御装置（CPU）２００と主メモ
リ２０６、磁気ディスク２０８、CRT２０２、キーボー
ド２０４からなる。図１のネットワーク制御部１００や
ネットワーク部１１４、制約式１０２は、磁気ディスク
装置２０８に格納されている。キーボード２０４は、プ
ログラムの指示のために使用する。ＣＲＴ２０２は結果
の表示などに使用する。

【００２１】必要に応じて、ネットワーク制御部１００
やネットワーク部１１４のプログラムや、制約式１０２
の内容が主メモリ２０６にローデングされる。この操作
は、キーボード２０４から行なわれる。また、ネットワ
ーク制御部１００やネットワーク部１１４を主記憶２０
６に呼び込むための指令や実行開始指令の指定もキーボ
ード２０４から行なわれる。推論経過や結果などは、Ｃ
ＲＴ２０２に表示される。

【００２２】以下、本発明を具体的に説明する。

【００２３】まず、本発明の一実施例の概要について説
明する。図１は、全体のプログラムおよびデータ構成に
ついて示したものである。ネットワーク制御部１００
は、制約式１０２を読み込み、１０４を介して制約式１
０２に含まれている変数を取り出し、制約式と変数を１
１０を介してネットワーク部１１４に渡す。ネットワー
ク部１１４は、制約式と変数のノードを作り、他の制約
式ノードや変数ノードと結合し、制約のネットワークを
構成する。結果はネットワーク部１１４から１１２を介
してネットワーク制御部１００に渡される。そして、１
０６を介して推論結果１０８に格納される。

【００２４】ネットワーク部で作成されるネットワーク
の例を図３に示す。３０６や３１２など四角で示された
ノードは制約式のノードを示す。３０２や３２０などの
丸で示されたノードは変数のノードを示す。図３では、ｃ＞１０ｘ＝ｃ＋ｄｘ＝ｙ＋ｚｚ＝＜０ｘ＝ｓ＊ｔｓ＝１の制約式がネットワーク部に与えられたところである。
ｃ＞１０（３０６）の制約式が与えられているため、ｃ
の変数ノード（３０２）では、３００で表わされている
ように、ｃの下限値が１０であることがわかる。３３４
でｚの上限値が０とわかっているのも制約式３４０があ
るからである。ノード間の矢印はノード間のデータ転送
の道筋であるストリームを表わしている。３１０のよう
な双方向のストリームはノード間で双方向にデータが転
送することができることを示している。また、３４６の
ような片方向のストリームは矢印で示された片方向しか
データが転送されないことを示す。ストリームが片方向
になる場合は、以下のような場合である。

【００２５】（ルール１）制約式に一つしか変数が含ま
れていない場合は、制約式のノードからその変数ノード
への片方向のストリームとなる。

【００２６】（ルール２）変数ノードにおいて、値が確
定した場合は、変数ノードから制約式のノードへの片方
向のストリームとなる。

【００２７】（ルール３）制約式ノードにおいて、値が
確定していない変数が一つになった（その一つの変数を
除いて変数ノードからの片方向ストリームになった状
況）ならば、その変数ノードへのストリームは、制約式
ノードから変数ノードへの片方向のストリームとなる。

【００２８】（ルール４）（ルール１）から（ルール
３）を繰り返すことにより、（ルール３）の規則を適用
することができる場合。

【００２９】図３の制約式のネットワークに新たに、ｔ＝１の制約式が追加されたならば、ネットワークは図４のよ
うになる。制約式ノード４８０が作成され、その中に変
数が一つしかないため、先の（ルール１）を使い、制約
式ノード４８０から変数ノード４５６へのストリーム４
８２は片方向ストリームになる。さらに、制約式４８０
によってｔの値が確定するため、ｔの変数ノード４５６
からのストリーム４５４は（ルール２）より片方向スト
リームになる。制約式ノード４４２では、３変数の内、
ｓとｔの２変数の値が確定しているため、ｘの変数ノー
ド４２０へのストリーム４２４は片方向ストリームとな
る。さらに、ｘ＝ｓ＊ｔの制約式に対して、ｓとｔの値
が確定しているためｘの値が求まり、ｘの変数ノードの
値は４８４のようになる。ｘを求める際、ｓとｔが上限
値と下限値の区間しかわからない状況では、図５に示す
ような区間法の規則を適用する必要がある。区間法の規
則を適用する場合は、一般に値が確定しないので、スト
リームは双方向のままになる。ネットワーク制御部で
は、制約式が追加されたならば、制約式ノードを作り、
制約式に既に変数ノードとして存在している変数が含ま
れていれば、制約式ノードとネットワークを張る。その
とき双方向になるか片方向になるかは、（ルール１）か
ら（ルール４）によって決められる。

【００３０】ネットワーク制御部で制約式から変数を取
り出す処理は数式処理で行われている処理と同様であ
り、ネットワーク部での制約式ノードと変数ノードを作
りストリームを張る処理は、グラフで使われている手法
と同様である。

【００３１】次に、制約式ノードと変数ノードの処理に
ついて説明する。図６は制約式ノードの処理を示したも
のである。制約式ノードは、変数ノードから更新メッセ
ージを受け取る。更新メッセージのなかには、（１）棄却フラグ０ならば、有効な更新メッセージである。

【００３２】１ならば、無効なメッセージである。

【００３３】（２）変数名および変数の上限値と下限値更新メッセージを送出した変数ノードとその変数の上限
値と下限値が格納されている。

【００３４】（３）履歴更新メッセージが伝播された履歴が格納されている。

【００３５】が含まれている。まず、更新メッセージの
中の棄却フラグが１になっているか調べる（６０２）。
もし、棄却フラグが１であるならば、処理を正常終了と
して終了する（６２８）。これにより、棄却フラグが１
である更新メッセージは無視され、制約式を使った上限
値と下限値の計算は行われない。更新フラグが１でない
ならば、制約式ノードの制約式に含まれている変数の数
が、一つかどうか調べる（６０４）。そうであれば、更
新メッセージの中にある変数の上限値と下限値を使っ
て、制約式が満足するか調べる（６２０）。制約式が満
足するか調べるためには図５の区間法の規則を使用す
る。矛盾を調べて（６２２）、矛盾がが検知されたなら
ば、処理結果を矛盾として返す（６２４）。制約式の中
に一つ以上の変数が含まれているならば、更新メッセー
ジが伝えられた変数以外の変数を制約式取り出し（６０
６）、その変数の上限値と下限値を図５の規則を使い求
め（６０８）、矛盾が検知されたかどうか調べる（６１
０）。矛盾が検知されたならば、処理結果を矛盾として
返す（６２４）。矛盾が検知されなければ、計算された
変数の上限値あるいは下限値が、記録されているその変
数の上限値あるいは下限値に比べて厳しくなっているか
どうか調べる（６１２）。厳しくなっていなければ、他
の変数について上限値と下限値を計算する（６１６）。
厳しくなっていれば、その変数に対応する変数ノード
に、（１）棄却フラグ受け取った更新メッセージの棄却フラグ。

【００３６】（２）変数名と制約式で計算された上限値
と下限値（３）履歴送られてきた更新メッセージの履歴の先頭に制約式の識
別子を付ける。

【００３７】を含む更新メッセージを送出する（６１
４）。履歴の形式は、制約式の識別子、（変数名、上限
値、下限値）、がリスト形式で繰り返されたものであ
る。制約式の識別子は、制約式に付けられた名前であ
る。上限値あるいは下限値が更新されなければ、数値で
ない記号になる。すべての変数について（６０８）から
（６１４）までの処理を行っているか調べ（６１６）、
そうであれば、処理を終了する。そうでなければ、制約
式に含まれている別の変数を選び（６１８）、その変数
の上限値と下限値を計算する。

【００３８】次に、図７を使って、変数ノードの処理に
ついて説明する。制約式ノードから更新メッセージが送
られると、その中にある棄却フラグを調べる（７０
２）。更新メッセージの形式は制約式ノードへの更新メ
ッセージとおなじである。棄却フラグが１であれば、上
限値あるいは下限値の更新を行わず、処理を終了する。
そうでなければ、更新メッセージで伝えられた上限値あ
るいは下限値が、最新の上限値あるいは下限値に比べて
厳しくなっているか調べる（７０４）。厳しくなってい
なければ、処理結果を正常終了として（７１８）、処理
を終了する。厳しくなっていれば、更新メッセージの履
歴を取り出し（７０６）、履歴の中に自分自身の要素が
あるか調べる（７０８）。なければ、処理８００を行
う。あれば、自分自身が設定した上限値と下限値を調べ
て、上限値あるいは下限値が発散しているか調べる（７
１０）。発散を調べるためには、履歴の中に少なくとも
自分変数に関する要素が２つ入っており、新しく伝えら
れた上限値あるいは下限値の３組を使って調べる必要が
ある。最初と２つめの要素の変化と２つめの要素と計算
された上限値あるいは下限値の変化を比較し、後者の変
化が前者の変化よりも大きい場合は発散していると見な
す。この時、２つの変化の間に使われた制約式ノードが
同じである必要がある。発散していれば、処理結果に正
帰還が起きていることとその変数名とその方向を設定す
る（７２２）。発散していなければ、履歴の中に自分自
身の要素が一定回数以上あるか調べる（７１２）。一定
回数以上履歴の中になければ、処理９００を行う。あれ
ば、処理結果を収束しないとして処理を終了する（７１
４）。

【００３９】次に、図８を用いて、処理８００の説明を
行う。更新メッセージの上限値あるいは下限値が現在の
上限値あるいは下限値にくらべて、厳しくなっていて、
かつ履歴の中に自分の要素がない場合は、今まで送出し
て更新メッセージの棄却フラグをすべて１にする（８０
２）。そして、送出された更新メッセージから棄却フラ
グを取り出し、記録する（８０４）。そして、（１）新しい棄却フラグ０にする。

【００４０】（２）変数名と計算された上限値と下限値（３）追加された履歴送られてきた更新メッセージの履歴の先頭に自分の変数
名と上限値と下限値を追加する。

【００４１】を含む更新メッセージを送出し（８０
６）、新しい棄却フラグも記録しておく。そして、送ら
れてきた更新メッセージに格納されていた棄却フラグが
１になったならば、新しい棄却フラグも１になるように
図１０で示すようなプロセスを同時に起動する（８０
８）。そのプロセスは、送られてきた更新メッセージの
中にある棄却フラグが１になったならば、送出する更新
メッセージの中にある新しい棄却フラグを１にする（１
００２）。これは、（８００）から（８１２）の処理と
は別のプロセス（あるいはタスク）で実行されるもので
ある。これは、棄却フラグの伝播の方向を送られてきた
更新メッセージから送出する更新メッセージの方向に制
限するために行うものである。もし、単純に、送られて
きた更新メッセージの棄却フラグを送出する更新メッセ
ージの棄却フラグにすると、棄却フラグの伝播の方向が
双方向となり、送出した更新メッセージの処理でその棄
却フラグが棄却されると、送られてきた更新メッセージ
の棄却フラグも棄却されることになる。そうすると、す
べての更新メッセージの棄却フラグが棄却になり、すべ
ての処理が中断されてしまう。一方、（１００２）の処
理は、マルチタスクの制御下で行われるため、古い棄却
フラグが１になったらただちに、新しい棄却フラグを１
にすることはできない。また、この場合はそのようにす
る必要がない。棄却フラグによる処理の中断は、無駄な
処理を省くためのものであり、中断が遅れても処理結果
には影響がない。

【００４２】次に、受け取った更新メッセージの履歴の
中に、自分の要素が含まれるが、一定回数以上ない場合
の処理である処理９００の説明を行う。まず、履歴を調
べ、上限値あるいは下限値が一定範囲に収束しているか
調べる（９０１）。収束しているならば、処理結果を正
常終了とする（９１０）。収束していなければ、今まで
送出して更新メッセージの棄却フラグをすべて１にする
（９０２）。これは、既に送出した更新メッセージの処
理を棄却するためである。これにより、受け取った更新
メッセージの中の棄却フラグも図１０の処理によって１
になる。そして、新しい棄却フラグと計算された上限値
と下限値、追加された履歴を持つ更新メッセージを変数
を使用している制約式ノードに送出する（６０４）。こ
の場合、送られてきた制約式ノードと制約式へ転送する
ストリームがないものには送らない。そして、最初に自
分が更新メッセージを送った原因である受け取った更新
メッセージの棄却フラグを取り出す（９０６）。その棄
却フラグと送出した更新メッセージの中の新しい棄却フ
ラグを図１０の処理を行うプロセスを生成することによ
り連動させる。更新メッセージが変数ノードから送出さ
れる度に、受け取った棄却フラグと送出した棄却フラグ
が図１０のプロセスによってつながれる。ある変数ノー
ドで棄却フラグが１になると図１０の（１００２）の処
理が起動され、つぎつぎに、棄却フラグが１になる。

【００４３】

【発明の効果】本発明によれば、変数の上限値と下限値
を伝播することによって、不等式で表わせられた制約を
解く問題解決器において、同じ変数ノードに対する上限
値と下限値の更新が一定回数以上繰り替えされたなら
ば、処理を中断するため、無限に処理が繰り返されなく
て済み、同じ変数に対するより厳しい上限値と下限値の
更新が起きたならば、前の上限値と下限値を使って別の
変数の上限値と下限値を求める処理を棄却することによ
り、無駄な処理を防ぎ、同じ変数に対する上限値と下限
値の更新が繰り返し起きて、かつ上限値か下限値が発散
して起こることを検知したならば、発散が起こっている
ことを報告することにより正帰還を検知することができ
る。

【図面の簡単な説明】

【図１】本発明の一実施例に係る全体プログラムおよび
データ構成を示す図である。

【図２】推論制御装置の構成図である。

【図３】ネットワーク部で作成されるネットワークの例
を示す図である。

【図４】図３のネットワークに新たな制約式が追加され
たネットワークを示す図である。

【図５】区間法の規則を示す図である。

【図６】制約式ノードの処理を示す図である。

【図７】変数ノードの処理を示す図である。

【図８】メッセージの中に自分自身の要素がない場合の
処理を示す図である。

【図９】受け取った更新メッセージの履歴の中に自分の
要素が含まれるが、一定回数以上ない場合の処理を示す
図である。

【図１０】送られてきた棄却フラグが１になったなら
ば、送出した棄却フラグを１にする処理を示す図であ
る。

【符号の説明】

１００…ネットワーク制御部、１０２…制約式、１０８
…推論結果、１１４…ネットワーク部。

───────────────────────────────────────────────────── フロントページの続き (72)発明者阿部正博東京都国分寺市東恋ケ窪１丁目280番地株式会社日立製作所中央研究所内

Claims

【特許請求の範囲】

【請求項１】不等式による制約式と変数をノードとして
表わし、それらをネットワークでつなぎ、制約式のノー
ドである制約式ノードでは、変数の上限値か下限値が伝
播されたならば、制約式を使ってその制約式に含まれる
別の変数の上限値と下限値を求め、より厳しい上限値あ
るいは下限値が求まったならば、それをその制約式に含
まれる変数のノードである変数ノードに更新メッセージ
として伝播し、その変数ノードでは、伝播された変数の
上限値と下限値がこれまでより厳しい制約であるなら
ば、他の制約式ノードにその変数の上限値と下限値を伝
播することによって、制約式全体のより厳しい制約を求
める問題解決器において、更新メッセージの中に新し
い上限値と下限値以外にこれまで伝播してきた変数ノー
ドにおける更新情報である変数名と上限値あるいは下限
値を履歴として記録して送出し、履歴を調べ、同じ変数ノードに対する上限値と下限値の
更新が一定回数以上行われていることを検知したなら
ば、更新メッセージの処理を中断する、ことを特徴とする非線形不等式推論方法。
【請求項２】請求項１において、更新メッセージの中に
そのメッセージの処理をする必要があるかないかを示す
棄却フラグを保持し、同じ変数に対するより厳しい上限値と下限値の更新が起
きていることを検知したならば、その更新メッセージの
棄却フラグに棄却を設定し、棄却フラグが棄却に設定されている更新メッセージを受
け取ったならばそのメッセージを無視し、更新メッセージを受け取り処理した後、他のノードに更
新メッセージを送出する時に、将来、受け取った更新メ
ッセージの中の棄却フラグが棄却に設定されたならば、
送出した更新メッセージの棄却フラグを棄却に設定する
処理を起動する、ことを特徴とする非線形不等式推論方法。
【請求項３】請求項２において、同じ変数に対するより
厳しい上限値と下限値の更新メッセージの中の履歴にそ
の変数自身が行った更新が含まれていることを検知した
ならば、その更新メッセージの履歴の中でその変数ノー
ドに最初に伝えられた更新メッセージの棄却フラグが棄
却に設定されると、送出した更新メッセージの棄却フラ
グを棄却に設定する処理を起動する、ことを特徴とする非線形不等式推論方法。
【請求項４】請求項１において、更新メッセージの履歴
を調べることにより、同じ変数に対する上限値と下限値
の更新が繰り返し起きており、かつその上限値か下限値
が発散していることを検知し、発散を検知したならば、発散が起こっていることを報告
する、ことを特徴とする非線形不等式推論方法。