(15) MGTPにおける推論制御と探索問題への適用
研究テーマ、研究代表者:
- (1)研究テーマ
- MGTPにおける推論制御と探索問題への適用
- (2)研究代表者(氏名、所属、役職)
- 井上 克已、神戸大学工学部 助教授
記述項目:
- (1)研究進捗状況
- 本研究では,MGTP における推論の制御と各種の探索方式の整備
を目的とし,その応用としてコスト情報を持つ組合せ問題や最適
化問題などの探索問題を解くために MGTP に改良を加えること
にしている.
現在までに以下の開発作業が終了している.
- Iterative-Deepening 探索を組み込み,動作チェックを行った.
- コスト付き入力節シンタックスの MGTP 節への変換部を作成した.
- (2)現在までの主な成果
- Iterative-Deepening 探索を組み込むことにより,これまで
解を得ることが出来なかった,有限のモデルと無限のモデルを
持つような問題に対し,解(有限のモデル)を得ることが出来
るようになった.
すなわち,MGTP の停止性が向上した.
- コスト付きの問題を MGTP 節へと変換することが可能になった.
- (3)今後の研究概要
- コスト付きの問題を MGTP 節に変換可能になったので,決定問
題・最適化問題を解くために,最良優先探索を組み込んだ推論
エンジンを作成する.
- 変換方式として Non-Horn Magic Set (NHM) 法を組み込み,
ゴール (目標述語)に関係する推論のみに絞ることができるよ
うにする.
- 上記で作成した推論エンジンを他のシステムと比較・評価する.
- (4)今年度目標成果ソフトウェアイメージ
- 本システムは、MGTP (Prolog 版) を拡張したソフトウェアである.
従来の MGTP からの改良点は,以下の (a),(b),(c) に挙げる,推
論制御・探索方式の付加,およびそれに関する入出力インタフェー
スであり,MGTP 自体にもかなりの変更を加える必要がある.
- (a) スタート時のメニュー表示:
- MGTP の推論エンジンが多様になるため,選択可能にするメニュー.
- (b) 入力インタフェース:
- コスト付一階述語ノンホーン節集合で表現された知識ベースを
MGTP で扱われる Prolog プログラムとデータ構造に変換する
コンパイラ.
- (c) 推論実行部:
- 深さ優先探索,DFID 探索,BFID 探索などの探索方式を持ち,
MGTP の前向き推論とケース分割を繰り返し行う.(a) のメニュ
ーで選択可能.
- (d) 出力インタフェース:
- (c) で得られたモデル集合から,最適な解 (最小または最大コ
ストを持つモデルまたはリテラル) を取り出し表示する.
www-admin@icot.or.jp