平成9年度 委託研究ソフトウェアの中間報告

(15) MGTPにおける推論制御と探索問題への適用

研究代表者: 井上 克已 助教授
神戸大学工学部


研究テーマ、研究代表者:
(1)研究テーマ
MGTPにおける推論制御と探索問題への適用

(2)研究代表者(氏名、所属、役職)
井上 克已、神戸大学工学部 助教授

記述項目:
(1)研究進捗状況

本研究では,MGTP における推論の制御と各種の探索方式の整備 を目的とし,その応用としてコスト情報を持つ組合せ問題や最適 化問題などの探索問題を解くために MGTP に改良を加えること にしている.
現在までに以下の開発作業が終了している.

  1. Iterative-Deepening 探索を組み込み,動作チェックを行った.
  2. コスト付き入力節シンタックスの MGTP 節への変換部を作成した.

(2)現在までの主な成果

  1. Iterative-Deepening 探索を組み込むことにより,これまで 解を得ることが出来なかった,有限のモデルと無限のモデルを 持つような問題に対し,解(有限のモデル)を得ることが出来 るようになった. すなわち,MGTP の停止性が向上した.
  2. コスト付きの問題を MGTP 節へと変換することが可能になった.

(3)今後の研究概要

  1. コスト付きの問題を MGTP 節に変換可能になったので,決定問 題・最適化問題を解くために,最良優先探索を組み込んだ推論 エンジンを作成する.
  2. 変換方式として Non-Horn Magic Set (NHM) 法を組み込み, ゴール (目標述語)に関係する推論のみに絞ることができるよ うにする.
  3. 上記で作成した推論エンジンを他のシステムと比較・評価する.

(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