JPH05313896A

JPH05313896A - 知識処理システム及び知識表現方法

Info

Publication number: JPH05313896A
Application number: JP4140108A
Authority: JP
Inventors: Takayasu Kasahara; 孝保笠原; Yasuhiro Kobayashi; 康弘小林; Naoyuki Yamada; 直之山田
Original assignee: Hitachi Ltd
Current assignee: Hitachi Ltd
Priority date: 1992-05-01
Filing date: 1992-05-01
Publication date: 1993-11-26

Abstract

(57)【要約】【目的】探索による問題解決構造において、制約条件
の充足順序を自動的に決定することにより、システム開
発に係る負担を軽減することにある。【構成】問題解決の過程を探索木で表現する知識処理
システムにおいて、制約条件入力インターフェース、制
約充足順序決定プログラムと問題解決戦略と対象領域の
知識からなる推論プログラム生成プログラムからなり、
探索木の節点を節点として共有し、デ−タの依存関係を
リンクとするネットワ−クを用いて問題解決に必要な情
報を表現し、ネットワ−クの各節点に、解を得る過程で
充足すべき制約条件を記述し、ネットワ−クの構造にお
ける制約条件の位置に基づいて制約充足の実行順序を決
定して、問題を解決する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、各種解を木構造に展開
し、この木構造を探索することにより、最適解を求める
知識処理システムに係わり、特に、複数の制約条件を全
て充足する解を効率良く求める制約条件の充足順序を自
動的に定める知識処理システム及び知識表現方法に関す
る。

【０００２】

【従来の技術】従来、制約条件に基づいて問題を解く方
法としては、制約指向プログラミングの方法があった。
この方法では、例えば、淵一博監修；知識情報処理シリ
−ズ別巻２「制約論理プログラミング」共立出版ｐｐ３
８−３９に示されるように、宣言的に制約条件を羅列す
るだけで問題を解くプログラムを記述できる。しかし、
この制約指向プログラムの方法では、制約を列挙するだ
けで問題を解くことができるが、複雑なデータの依存関
係を記述することができず、また、詳細な問題解決の方
法を明示的に記述することができない。また、従来、プ
ロダクションシステムを利用して問題解決を行う方法と
しては、フレームのデータ構造の中に手続き的処理を実
行するメソッドと呼ばれる部分に、制約解消のためのプ
ログラムを埋め込んでいた。このプロダクションシステ
ムを利用した場合には、制約充足の実行順序に矛盾がな
いように、また、ルールにより記述した推論制御の方法
と矛盾がないように考える必要がある。また、個々のデ
ータにそのデータに係わる処理を組み込んでプログラム
を作る方法に、オブジェクト指向プログラムの方法があ
り、オブジェクト指向プログラムでは、制約条件は各デ
ータに対して記述される。しかし、このオブジェクト指
向プログラミングの考え方では、制約条件を個々のデー
タに記述するが、制約充足の実行順序については、プロ
グラマ自らが手を動かしてプログラムする煩わしさがあ
る。また、具体的に、ジョブショップスケジューリング
問題を解くシステムの作成について、後述する図５に示
すＪＯＢ（受注情報）の入力に対して、図６に示すジョ
ブショップのスケジュールを出力するシステムを作成す
る場合、従来の知識処理システム構築のための汎用ツー
ルを利用して作成すると、効率的なアルゴリズムやデー
タ構造を草案するのに、計画問題に対する広い知識と労
力を要した。すなわち、図７は、このような問題を解く
ために、よく用いられる手法の一つである資源優先割り
付けのアルゴリズムであり、このようなアルゴリズムに
基づいて、ルールやＣプログラムを記述して問題を解く
ことを示す。図７において、前処理後（ステップ１）、
ＲＥＳＯＵＲＣＥを取り出し（ステップ２）、次に、ス
テップ２において取り出したＲＥＳＯＵＲＣＥに対応し
てＪＯＢを取り出し、（ステップ３）、これに制約デー
タを割り付け（ステップ４）、この割り付けの結果を制
約条件に基づいて判定し（ステップ４）、以上のステッ
プを繰り返し、後処理する（ステップ５）。図８は、こ
のような構成に基づいて、知識処理システムを構築した
場合のフレームやＣプログラムなどからなるシステム構
成を示したものである。この場合、全体として通常１０
００〜３０００ステップのプログラムとなる。このよう
な労力を減らすため、対象とする問題領域に依存した知
識処理システムの作成を支援するためのドメインシェル
と呼ばれる構築ツールが開発されているが、ツールのカ
バーする範囲が狭く、カバーしていない部分と、推論の
詳細な制御についてはシステム利用者が補わなければな
らない。

【０００３】

【発明が解決しようとする課題】本発明の目的は、上述
した事情に鑑み、直接、プログラムを作成するのではな
く、大まかな探索の方法と制約条件を記述することによ
り、制約条件を順次解消しながら、問題を解く推論プロ
グラムを作成する知識処理システムの構築を支援するこ
と及びそのための知識表現方法を提供することにある。

【０００４】

【課題を解決するための手段】上記目的は、制約条件を
探索木の節点のデータとの依存関係を表現した木構造を
用いて、木構造中の制約条件の記述されている位置に基
づいて、制約充足の実行順序を定めることにより、解決
される。

【０００５】

【作用】知識処理システムを構築するものは、まず、問
題解決の大まかな枠組を決め、それに基づいて探索木の
節点及び各種のデータ構造を定め、探索木の節点を根と
するデータの依存関係を表す木を作成する。推論プログ
ラム生成プログラムは、データの依存関係を表す木のな
かの制約条件の位置関係に基づいて、制約の充足順序を
定め、推論プログラムを作成する。

【０００６】

【実施例】以下、本発明の一実施例を、ジョブショップ
スケジューリング問題を解くシステムの作成を例にと
り、説明する。図１は、本発明の一実施例に係る知識処
理システム構築ツールの要部構成図である。本実施例に
おいては、演算処理装置と記憶装置からなり、問題解決
戦略１−ｂ−２は、あらかじめ与えられているとする。
システム利用者は、ＣＲＴまたはキーボードを用いて、
制約条件入力インターフェース１−ａから推論プログラ
ム生成プログラム１−ｂ中の対象領域の知識１−ｂ−３
に、探索木の節点として何を定義するか、節点の属性値
として何を定義するか、属性値の値域をどの範囲にとる
か、さらに、オブジェクトとオブジェクトの間の包含関
係及びデータ相互の依存関係（制約条件）を入力する
と、推論プログラム生成プログラム１−ｂ中の制約充足
順序決定プログラム１−ｂ−１が、あらかじめ指定した
問題解決戦略１−ｂ−２に基づいて、各制約を解消する
プログラム及び制約の解消順序を決定し、所要の推論プ
ログラム１−ｃを生成する。また、これらの知識及びプ
ログラムは、記憶装置に格納される。この過程を、ジョ
ブショップスケジューリング問題を解く推論プログラム
を生成する場合を例にとって説明する。

【０００７】図２は、作成すべきジョブショップスケジ
ュ−リングシステムの仕様を記述したものであり、ＪＯ
Ｂ（受注情報）、ＲＥＳＯＵＲＣＥ（装置）、制約条件
Ａ１、スケジュ−ル結果の例Ａ２を示す。制約条件Ａ１
としては、（１）納期の制約条件、（２）各装置につい
て、生産可能製品及び生産速度の制約条件及び（３）段
取り時間の制約条件等、図示の制約条件がある。また、
システムの入力項目としては、ＪＯＢ（受注情報）に示
すように、受注Ｎｏ．、製品名、生産量、納期、重要度
を各受注に対して入力する。ここで、重要度とは、各受
注について、納期を守ることの重要性を数値で示したも
ので、重要度が１の場合は、制約を必ず満たす場合、重
要度が２の納期の場合は、重要度が１の注文の納期の制
約を全て満足して、まだ余裕がある場合に制約を満足さ
せる。重要度が３の場合は、重要度が１及び２の制約を
全て満足した上に余裕があれば、納期の制約を満足させ
ることを示す。生産可能製品及び生産速度の制約は、例
えば、図３に示すように、ＲＡ，ＲＢ，ＲＣの３種類の
装置があり、ＰＡ，ＰＢ，ＰＣの３種類の製品があった
場合に、各製品を単位時間（分）当り生産できる量（ｔ
ｏｎ）のことである。例えば、装置ＲＡで製品ＰＡを１
分当り１０ｔ生産することができることを示している。
また、段取り時間の制約とは、同じ装置により異なった
製品を続けて生産する場合に、準備に要する時間のこと
である。図４にその例を示す。例えば、製品ＰＡの後に
製品ＰＢを生産する場合には、段取り時間として２０
分、製品ＰＣを生産する場合には、段取り時間として１
０分それぞれ要することを示している。スケジュ−ル結
果の例Ａ２は、以上の入力の結果作成されたスケジュ−
ルを示し、１、２、３、４、５・・は時刻、ＮＯ＿０
１、ＮＯ＿０２、ＮＯ＿０３・・は受注ＮＯ．を表す。
例えば、装置ＲＡは、１の時刻に受注ＮＯ．ＮＯ＿０１
を生産し、２から３の時刻にかけて受注ＮＯ．ＮＯ＿０
４を生産し、３から４の時刻にかけて受注ＮＯ．ＮＯ＿
０９を生産することを示している。装置ＲＢ、ＲＣにつ
いても同様である。

【０００８】図５は、このようなスケジューリングシス
テムにおけるＪＯＢ（受注情報）の入力例である。入力
データは、受注ＮＯ．、製品名、生産高、納期、重要度
であり、注文の数は１７、装置及び製品の種類は、図
３、図４に示したようにそれぞれ３種類ある。ＰＡ１，
ＰＡ２は製品の種類ＰＡの製品であることを示し、同様
に、ＰＢ１，ＰＢ２、ＰＣ１，ＰＣ２は、それぞれ種類
ＰＢ，ＰＣの製品であることを示している。また、生産
量の単位はｔ（ｔｏｎ）である。このような入力に対し
て、出力としては、図６に示すようなジョブショプのス
ケジュールが出力される。すなわち、各受注に対する生
産開始時刻、生産終了時刻（６桁のｄｄｈｈｍｍ表現に
より表している。つまり、上２桁が日付を表し、真中の
２桁が時間を表し、最後の２桁が分を表す。例えば、生
産開始時間が２５１６１２とは、２５日の１６時１２分
であることを意味する。）、使用装置などが出力され
る。

【０００９】以下、このような図５の入力例に対して、
図６のようなジョブショプのスケジュールが出力される
システムを作成するにあたって、本発明による問題を解
く推論プログラムを作成する手順を説明する。図９は、
図１のインターフェースプログラムとこの例における入
力の過程を示す。ただし、本実施例では、図１の推論プ
ログラム生成プログラム中の問題解決プログラムの表示
と、この例における入力の過程を示す。ここで、本実施
例では、図１の推論プログラム生成プログラム１ーｂ中
の問題解決戦略１ーｂー２として、最良探索が指定して
あるとする。インターフェースプログラムは、まず、探
索ノードの名称、状態オブジェクトの名称、制約名称、
属性の名称、値域を指定する。この場合は、探索ノード
の名称として計画案が、状態オブジェクトの名称として
時間帯が、制約名称として、納期と段取り時間が、属性
名称として実施作業が、属性の値域として「ｓｅｔｏｆ
注文」が定義してある。これは、注文というオブジェ
クトのインスタンスの集合が属性値であることを示して
いる。次に、注文、段取り時間など未定義のオブジェク
トを順次、入力していく。例えば、「注文」オブジェク
トに対する属性名称としては注文番号、値域としてはＳ
ＴＲＩＮＧが指定される。このＳＴＲＩＮＧというオブ
ジェクト名称は、Ｃ言語の文字列型に対応する予約オブ
ジェクト名称で、これ以上再定義はしない。予約オブジ
ェクト名称としては、このほか、整数、実数、集合型
（ｓｅｔｏｆ）がある。集合型は、特別の意味のある
予約語で、例えば、ｓｅｔｏｆ整数とすれば、整数
の集合からなる文字列型となる。このように、問題を網
羅して記述していくと、図１０に示したような図に対応
する対象知識が生成される。最後に、各オブジェクトに
対して定義した制約条件を順次記述していく。例えば、
生産可能装置に対しては、時間帯ｏｆ実施作業ｏ
ｆ使用装置ｏｆ生産可能製品ｉｎｃｌｕｄｅ
実施作業ｏｆ製品という形で制約を定義する。これ
は、実施作業の製品が同じ実施作業の使用装置の生産可
能製品を含むことを意味する。ここで、図１０におい
て、楕円印はオブジェクト、二重楕円印は予め定義され
ている項目、四角印は属性、ペーパー表示印は制約を表
わす。”探索ノードオブジェクト”については、「名
称」（計画案）、”状態オブジェクト”については、
「名称」（時間帯）、「開始時刻」、「終了時刻」、
「実施作業」（ｓｅｔｏｆ）がそれぞれ属性であり、
「納期の制約」、「段取り時間の制約」がそれぞれ制約
条件である。以下同様に、オブジェクト”装置”につい
ては、「装置のタイプ」、「使用時間帯」、「装置
名」、「生産能力」、”装置のタイプ”については、
「タイプ名称」、「可能製品」、「段取り時間」、”注
文”については、「注文番号」、「開始時刻」、「終了
時刻」、「人員」、「先行作業」、「製品名」、「生産
量」、「使用装置」、「生産可能装置の制約」、”段取
り時間”については”「名称」、「前作業」、「後作
業」、”製品”については、「名称」、”時刻”につい
ては、「日付」、「時間」、「分」、「時間表現の制
約」がそれぞれ属性と制約条件である。矢印は、例え
ば、”状態オブジェクト”の「開始時刻」、「終了時
刻」と”注文”の「開始時刻」、「終了時刻」の属性に
対し、”時刻”の属性値の値域「日付」、「時間」、
「分」と制約条件「時間表現の制約」が関連することを
示す。また、点線は、インスタンスの関係を表す。

【００１０】このような入力を用いて、推論プログラム
を自動生成する概略手順を図１１に示す。まず、第１０
ステップでは、入力に従い、図１０に相当する対象知識
を内部表現に変換する。次に、第２０ステップでは、入
力された制約条件を変換した内部表現に基づいて生成
し、第３０ステップでは、制約を充足するためのプログ
ラムの実行順序を図１０の対象知識の知識構造に基づい
て決定し、推論プログラムの中に埋め込み、推論プログ
ラムを完成する。第１０ステップにおける処理の詳細を
図１２に示す。この第１０ステップは、図９における入
力を図１３から図１５に示した内部表現に変換する手続
きである。図１３から図１５は、内部表現を示したもの
である。これらの内部表現は、基本的に属性値をもった
オブジェクトのデータ構造とオブジェクト同志の依存関
係及び推論処理の過程でデータの実現値を保存するテー
ブルからなる。図１２の最初の第１０１ステップの処理
では、データの依存関係を解析して、オブジェクト同志
の依存関係を表現する図１５のデータを作成する。これ
は、入力されたデータの属性値の依存関係に基づいて決
定する。次に、第１０２ステップでは、図１７の変数管
理表のテーブル（後述する）に、このデータを書き出
す。第１０３ステップにおいて、全てのオブジェクトを
処理したとき、第１０４ステップ、第１０５ステップに
おいて、次の新しいオブジェクトについて同様の処理を
施す。

【００１１】図１３は、オブジェクトとオブジェクトの
間の継承関係と属性値の間の参照関係に対応する内部表
現である。この内部表現は線型リストを用いて実現され
ている。Ｎｏｄｅというオブジェクトが先頭にあり、オ
ブジェクト名称、属性名称、オブジェクトのタイプ、属
性値の値域、依存関係のタイプ、依存関係のあるオブジ
ェクトへのポインタ、次の変数へのポインタ及び値テー
ブルへのポインタの８つのデータ項目からなる。属性名
称は、オブジェクトが含む属性の名称であり、特別な場
合として、インスタンスオブジェクトの場合がある。イ
ンスタンスオブジェクトは、基のオブジェクトの各属性
値に具体的な値を設定したものである。オブジェクトの
タイプとは、一般のオブジェクトの場合は、オブジェク
トと記述し、あらかじめシステムで定義した整数、実
数、文字列の３種類の予約オブジェクトに対しては、そ
れぞれの名前を記述する。値域は値域のタイプが整数や
文字列、実数である場合には、等号及び不等号で表現
し、あるオブジェクトのインスタンスである場合には、
値としてとり得るインスタンスの集合を列挙法により表
現する。例えば、｛ｉｎｓｔａｎｃｅ＿１，ｉｎｓｔａ
ｎｃｅ＿２，．．，ｉｎｓｔａｎｃｅ＿ｎ｝のように表
現する。ここで、ｉｎｓｔａｎｃｅ＿１，ｉｎｓｔａｎ
ｃｅ＿２，．．，ｉｎｓｔａｎｃｅ＿ｎは、インスタン
スオブジェクトとする。依存関係のタイプとしては、以
下の２種類がある。１）属性値の値域がそのオブジェク
トのインスタンスの集合となる場合（この時、属性値の
依存；ｖａｌと記述する。）。２）属性があるオブジェ
クトの集合となる場合（この時、属性の依存；ａｔｔｒ
と記述する。）。例えば、ノードの属性が時間帯となっ
ており、属性の依存関係がある場合に、時間帯のオブジ
ェクトのインスタンスオブジェクトがＴ１、Ｔ２、Ｔ３
とする。この時、Ｔ１，Ｔ２，Ｔ３がノード属性であ
り、Ｔ１，Ｔ２，Ｔ３の属性に値を決定することがノー
ド属性を決定することを意味する。図１４は、変数値が
探索の過程でどのように変っていったかを記録するため
の表であり、これを変数管理表と呼んでいる。変数管理
表は、変数名と値定義リストへのポインタの組みからな
っている。値定義リストは、値とその値を設定した時の
ノード名称及び値を決定した制約名称、次の値へのポイ
ンタ及び制約が成立したかどうかのチェックフラグから
なる。探索の過程で、数多くのノードが生成され、変数
の値が多く変更されると、新たに変数が定義される度に
新たな値定義リストのセルが生成され、直前に生成され
たセルからリストの先頭にポイントされていく。図１５
は、制約条件の表であり、制約条件の名前と、それが定
義されているオブジェクトの名称の組からなる。システ
ムには、図１６に示すように、図１３の参照関係の内部
表現のうち、オブジェクト先頭のＮｏｄｅに関する線形
リストと、図１４の変数名と値定義ポインタからなる表
を持っている。初期の参照関係のデ−タの中身は、属性
名称、タイプ、値域、依存関係のタイプは、値未設定と
いう値が入っており、依存するオブジェクトへのポイン
タ、次の変数へのポインタ、値テ−ブルへのポインタは
ＮＵＬＬが入っている。また、図１４の表は、中身には
何も書き込まれていない。Ｎｏｄｅについての図９の上
段の入力があると、図１７のオブジェクト名称表に新し
いオブジェクト名称「時間帯」が登録されるとともに、図
１６の参照関係のデ−タの中身は、図１８のノ−ドオブ
ジェクトの場合には、属性名称は図９において入力した
状態オブジェクト名称「時間帯」がとられ、タイプはオブ
ジェクトとなり、値域は値未設定のままであり、依存関
係のタイプは、状態オブジェクトに対しては、「ａｔｔ
ｒ」となる。一方、内部表現において、この状態値に対
する変数名称は、自動的に設定され、図１４のテ−ブル
に対して登録され、このテ−ブルの位置に値テ−ブルへ
のポインタがなされる。たとえば、内部表現における変
数名称は、設定された順にｘ１，ｘ２，．．．，ｘｎと
して設定される。したがって、ここでは、状態属性の値
は、ｘ１として定義される。図１２は、このようなオブ
ジェクトとその変数名を取り込んで、変数管理表と内部
表現リストを作成する処理手順を示したものである。処
理は、Ｎｏｄｅオブジェクトからはじめられ、まず、状
態オブジェクト名称を読み込み、図１６に示す参照関係
の内部表現リストの参照関係を書き込み、図１６の下側
に示した変数テーブルに変数名を書き込む。この処理を
状態オブジェクトと関係のあるすべてのオブジェクトに
対して順次行なう。また、もうひとつの属性名称、「実
施作業」に対して、Ｎｏｄｅの名称のついた参照関係の
内部表現のリストが生成され、このリスト要素の先頭に
対して、初期に生成した線形リスト要素の次の変数への
ポインタからポイントする。あらたに生成したリスト要
素は、属性名称「実施作業」、タイプ「オブジェクト」、値
域「ｓｅｔｏｆ注文」、依存関係のタイプ「ｖａ
ｌ」が設定される。それとともに、新たなオブジェクト
「注文」が生成され、図１８の表に書き加えられる。ま
た、この属性に対する内部表現の変数名称がｘ２と設定
され、図１４の表に書き込まれる。この表の位置に対し
て、線形リスト要素の値テ−ブルへのポインタからポイ
ントされる。図１８は、これまでの過程で生成される内
部表現をまとめたものである。

【００１２】図１１の第２０ステップにおいて、制約条
件を内部表現に変換する。これは、図９の制約名称に対
して、第１０ステップにおける内部表現との対応づけを
するとともに、図１５の制約表に制約条件を記述する操
作である。例えば、図９の例においては、まず、図１５
の表に、オブジェクト名称「製品」、制約名称「生産可
能装置」が登録される。一方、「時間帯ｏｆ実施作
業ｏｆ使用装置ｏｆ生産可能製品ｉｎｃｌｕｄ
ｅ実施作業ｏｆ製品」は、図１９に対応する制約
判定プログラムを出力する。ここで、例えば、時間帯、
実施作業は、時間帯というオブジェクト、実施作業とい
うオブジェクトを指す。このような変換は、図２０の変
換ル-ルを入力した制約式に適用することにより実現す
る。

【００１３】図１１の第３０ステップにおいて、対応す
るオブジェクトのインスタンスの属性値それぞれの制約
を充足するように設定する。この時、各オブジェクトの
依存関係に基づいて、依存関係グラフを作成し、制約の
実行順序を決定する。この依存関係グラフは、ステップ
１０、ステップ２０の過程で分析した各オブジェクトの
依存関係に基づいて作成する。図２１は、グラフの部分
的な形と実行順序の対応を示したものである。図２１の
第１番目のタイプのパターンは、単純な参照関係がある
場合で、下位のオブジェクトは、上位のオブジェクトの
制約を必ず満足する必要がある。また、制約の充足の実
行順序としては、上位のオブジェクトの属性値を決定し
た後に、下位のオブジェクトの属性値を満たすべき全て
の制約を充足するように決定する。図２１の第２番目の
パターンは、参照関係がループをなしている場合であ
り、全てのオブジェクトがループをなしている全てのオ
ブジェクトが持っている制約条件を制約として持つ。ま
た、制約条件の充足順序としては、理論的にはどの順番
でも制約充足を実行することができるが、実際のシステ
ムでは、制約テーブルにポインタでつながれている順に
制約を解消する。第３番目のパターンは、オブジェクト
の参照関係が２重のループになっている場合で、この場
合も、ループの中のオブジェクトは、ループ内のオブジ
ェクトが持っている全ての制約条件を満足する。また、
制約条件を充足する順序は、ループのどちらか一方を先
頭にし、同一のループを一回りした後、別のループのオ
ブジェクトにいき、順次制約を充足していく。ところ
で、制約条件に重要度が定義してあり、制約緩和が可能
な場合には、このような一般的な制約充足順序は用い
ず、制約条件の重要度が高い順に、オブジェクトの属性
値を決定していく。そして、重要度が１以外のオブジェ
クトに対しては、制約条件が守られない場合には、制約
条件にできるだけ近い値を当てはめていく。制約条件に
できるだけ近い値とは、例えば、ある整数型の属性に対
する制約条件を満足する集合が、｛３，４，５，７｝の
時、６が最も制約条件の充足する集合に近く、次が２と
８である。このように、制約条件の充足順序が決定する
と、後は、あらかじめ入力されている探索戦略に基づ
き、ノードの属性値から順に制約条件を当てはめて、問
題を解く推論プログラムのアルゴリズムを厳密に定める
ことができる。つまり、制約の実行順序とステップ３０
で定まった制約処理の実行順序に基づいて、処理を実行
する。

【００１４】このアルゴリズムの基本的な構成を図２２
に示す。まず、探索ノードの初期値を設定する。その初
期値に対して与えられた制約を満たす各オブジェクトの
属性値を設定し、全ての制約を処理して、新しいノード
と新しいノードの属性値を設定する。もし、探索の終了
条件が満たされれば、そこで探索を終了し、そうでなけ
れば、引き続き新たな設定値に対応するオブジェクトの
属性値を定めていく。また、与えられた制約条件より、
制約を充足するプログラムは、列挙法などの組合せアル
ゴリズムに値域やデータの依存関係のデータを付加して
データを作成する。図２３は、個々の制約充足のプログ
ラム生成のアルゴリズムを示したものであり、３通りの
場合に分けられる。まず、各オブジェクトの属性値の値
域が整数又は文字列の場合は、評価値が最大で、既存の
解と同じ組合せにならない解を探す。また、属性値の値
域が整数又はオブジェクトの集合の場合は、任意の数の
組合せ生成アルゴリズムを用いて、制約を満たす属性値
の組合せで求めて、解とする。また、属性値の値域がオ
ブジェクトの場合は、属性値として、そのオブジェクト
のインスタンスオブジェクトのうち、制約を満たすもの
を探して解とする。このように、個々のプログラム部品
が生成されると、後は、パラメータをプログラムに追加
する方法や、骨組みのプログラムの所々の部分に適当な
プログラム部品を当てはめることにより、全体のプログ
ラムを生成することができる。図２４は、図２２の基本
的なプログラム構造に、情報を付加して全体のソースプ
ログラムを作成するアルゴリズムを示したものである。
まず、探索ノードの初期値を設定し、ノードと関係する
制約充足プログラムを呼び出し、関係するオブジェクト
の属性値を定める。次に、属性値が定まったオブジェク
トと制約条件と関係するオブジェクトの属性値を順次定
めていく。最終的にすべての依存関係のあるオブジェク
トの属性値が定まったところで処理が終了する。図２５
は、こうして完成したジョブショップスケジューリング
システムの完成図である。入出力インターフェースから
ユーザは、図５のような計画データを入力する。推論プ
ログラムは、おおまかな推論をする最良探索プログラム
であり、最良な計画案になるような解の候補を順次生成
していき、制約を充足する解を探すものである。詳細な
推論制御は、図中の４つの制約充足プログラムで実行さ
れ、結果として、図６のような制約を充足し、かつ、も
っとも良い計画が出力される。

【００１５】

【発明の効果】以上説明したように、本発明によれば、
設計や計画などのシステムを作成する時間を大幅に短縮
することができる。また、作成したシステムについて、
後からプログラムの微妙な変更を加えることが容易とな
る。

【図面の簡単な説明】

【図１】本発明のシステム構成図

【図２】例題の説明図

【図３】

【図４】例題の制約条件の例

【図５】例題の入力の例

【図６】例題の出力の例

【図７】例題の解法

【図８】例題のシステム構成

【図９】インターフェースプログラムの表示例

【図１０】例題における対象知識の例図

【図１１】推論プログラムを生成する手順を示した図

【図１２】図１１の第１０ステップの詳細な手順を示し
た図

【図１３】対象知識の内部表現を示した図

【図１４】対象知識の内部表現を示した図

【図１５】対象知識の内部表現を示した図

【図１６】対象知識の内部表現を示した図

【図１７】対象知識の内部表現を示した図

【図１８】対象知識の内部表現を示した図

【図１９】制約判定プログラムを出力する論理式を示し
た図

【図２０】変換ル-ルを入力した制約式を示した図

【図２１】制約充足の順序を決定するルールを示した図

【図２２】制約充足と探索に基づくプログラムの基本的
な構成図

【図２３】個々の制約充足プログラムの生成アルゴリズ
ムの例図

【図２４】個々の制約充足プログラムを集めて全体の探
索プログラムを生成するアルゴリズム

【図２５】本方式により作成したジョブショップスケジ
ュ−リングシステムの構成図

【符号の説明】

１−ａ制約条件入力インターフェース１−ｂ推論プログラム生成プログラム１−ｂ−１制約充足順序決定プログラム１−ｂ−２問題解決戦略１−ｂ−３対象領域の知識１−ｃ推論プログラム

Claims

【特許請求の範囲】

【請求項１】問題解決の過程を探索木で表現する知識
処理システムにおいて、探索木の節点を節点として共有
し、デ−タの依存関係をリンクとするネットワ−クを用
いて問題解決に必要な情報を表現し、ネットワ−クの各
節点に、解を得る過程で充足すべき制約条件を記述し、
ネットワ−クの構造における制約条件の位置に基づいて
制約充足の実行順序を決定し、問題を解決することを特
徴とする知識処理システム。
【請求項２】問題解決の過程を探索木で表現する知識
処理システムにおいて、探索木の節点を節点として共有
し、デ−タの依存関係をリンクとするネットワ−クを用
いて問題解決に必要な情報を表現し、ネットワ−クの各
節点に、解を得る過程で充足すべき制約条件を記述し、
ネットワ−クの構造において根に近い節点に記述された
制約の充足を根から遠い節点に記述された制約の充足よ
りも優先的に実行して、問題を解決することを特徴とす
る知識処理システム。
【請求項３】問題解決のための推論を実行するプログ
ラムを格納する推論制御装置、問題解決に必要な知識を
探索木の節点との依存関係に基づいて格納する記憶装
置、問題解決に必要な知識を入力し、問題解決の結果を
表示する入出力装置からなる知識処理システムにおい
て、問題解決の過程で充足すべき制約条件を探索木の節
点との依存関係に基づいて定義することにより、制約の
充足順序を自動的に決定する推論処理機能を推論制御装
置の推論プログラムに有することを特徴とする知識処理
システム。
【請求項４】問題解決の過程を探索木で表現する知識
処理システムにおいて、探索木の節点を節点として共有
し、デ−タの依存関係をリンクとするネットワ−クを用
いて問題解決に必要な情報を表現し、ネットワ−クの各
節点に、解を得る過程で充足すべき制約条件を記述し、
ネットワ−クの構造における制約条件の位置に基づいて
制約充足の実行順序を記述することを特徴とする知識表
現方法。