期待値に基づく探索タスクの分配とその制御

概要

論文の詳細を見る
本稿では、得られる解の品質と実行時間が確率分布で与えられている探索問題を、複数のエージェントを用いて解決するための手法について述べる。まず、探索問題に対する制限時間までに達成可能な解を期待値に基づいて解析し、複数のエージェントに対する有効なスケジュールを作成する。そして、このスケジュールに従って、エージェントにタスクを分配し、各エージェントは、独立に探索を行う.期待値から大きく外れた結果を得たエージェントは、適宜リスケジュール要求を発することで、全体解の質を保つことに務める。本稿では、スケジュール及びタスク分配のためのアルゴリズムと作成されたタスクスケジュールに対するシミュレーション実験について報告する。実験から、リスケジューリングの効果が、問題の難しさ(探索の制限時間の厳しさ)に依存して変化し、中程度の難しさの問題で効果がピークを迎えた後、再び効果が低下することが明らかとなり、リスケジューリングにかかるコストと効果のトレードオフが示された。
社団法人情報処理学会の論文
1996-09-04