(7) KL1 による PROGOL の並列化に関する研究

［中間報告］

１）研究進捗状況

KL1によるPROGOLの並列化の検討を進めてきた。そのために、まず、現在 のPROGOLのアルゴリズムを詳細に検討し、その全貌を明らかにした。そして、 MGTPを用いたボトムアップ計算による新たなアルゴリズムを検討し、その見通 しを得た。すなわち、Prolog的なトップダウン計算に基づく従来のアルゴリズ ムに対して、帰納推論により適していると思われる方式の検討を行なった。従 来、PROGOLでは、最特殊仮説の生成を、モード宣言によって定義される可能な 述語を列挙して調べる方法をとっていたが、ここでは、それをMGTPによる帰結 発見問題と定義して、ボトムアップ計算による解法を得た。元々のMGTPには計 算の制限が無いが、ここでの計算は、与えられた有限ステップ内で計算される 帰結のみを求める必要があったので、そのような拡張を行なった。また、最適 な仮説を求めるための探索アルゴリズムについては、元々のPROGOL同様、A*ア ルゴリズムを採用しているが、そこで用いられるコストの推定を行なう新たな、 より精度の良い関数を導入した。KL1プログラミングについては、予定通り１ ２月中に終了させるよう、現在作業を進めている。

２）現在までの主な成果

PROGOLの並列化のために、既存のPROGOLシステムのアルゴリズムを解明し、 一部をPrologにより記述した。

PROGOLにおける最特殊仮説の生成を、MGTPによる帰結発見問題と定義して、ボ トムアップ計算による解法を得た。とくに、PROGOLのモード宣言自身をMGTPの 入力節として定義し、モードによってガイドされた帰結発見アルゴリズムを考 案した。また、計算の制限については、従来のresolution stepに基づく容易 性に対して、それを並列計算に拡張する概念を導入した。

最適な仮説を求めるための探索アルゴリズムについては、A*アルゴリズムで用 いられるコストの推定を行なう新たな、より精度の良い関数を導入した。その ためのMGTPを利用した計算アルゴリズムも、同時に開発した。

３）今後の研究概要

今年度中の今後の研究開発は、現在進めているKL1によるプログラミング の完了、および、そのデバッグを予定している。来年度は、実際に並列コンピュー タ上での動作実験を行ない、高並列度の達成を目指す。さらに、本実験システ ムを利用した、応用実験を行なう。