経験的知識を利用した適応型問題解決に関する研究

点击翻译按钮获取中文摘要

事例形式で知識を獲得・再利用する適応型問題解決パラダイムを提案した.悪定義な現実問題として日本語点字翻訳問題を,悪構造な現実問題として室内レイアウト変更計画問題を,それぞれ対象問題とし,提案するパラダイムを適用した.ここで,室内レイアウト変更計画問題とは,変更前後の機器配置レイアウト,変更作業者数,作業時間の上限が与えられたときに,各機器の移動経路の集合からなるプラン,および,機器移動作業への作業者および作業時間の割当てからなるスケジュールを求める問題である.本年度は,室内レイアウト変更計画問題において,事例知識を再利用する方式の開発・評価を行った.本問題は,プランニングとスケジューリングの双方を同時に行わなければならない複雑な問題である.このため,本問題を制約充足問題として定式化することによって,汎用的な解探索ソルバを用いてプランとスケジュールを同時作成できるようにした.また,対象とする問題インスタンスに最も類似した過去の事例から,ヒューリスティクスを選択的に作成することにより,探索の効率化を実現した.実験により,事例を用いることによって,事例検索・適合のオーバーヘッドを加味しても,40問題のうち31問題において,探索性能を改善できることを確認した.現段階では,過去の事例を対象問題インスタンスに適合させる処理において,再利用していないパラメータが多く存在する.これらのパラメータについても再利用することにより,さらなる探索性能の改善を図ることができると考える.