資源割当問題向き協調問題解決手法

概要

論文の詳細を見る
ネットワークなどの限られた資源を複数の経路設定などの要求に割り当てる資源割当問題は,一般にNP完全問題となるため,規模の大きな問題に対しては実用的な時間で最適解を求めることは因難である.そこで,必ずしも最適解が得られなくても,実用上問題のない近似解を妥当な時間で求めることができる発見的手法が提案されている.しかし,より問題の規境が大きく,さらに要求が動的に変化するような状況では,発見的手法と言えども近似解の導出は因難になる.このような場合,問題を分割して複数のエージェントに分配し,エージェント間の協調により近似解を求める協調問題解決手法が提案されている.特に,地域性を前提として問題を分割する地域分散手法が一般的であるが,必ずしも都合良く分割できるとは限らない.そこで,我々は地域性のない場合を想定して,要求(タスク)という側面から問題を分割し,分配された要求を受け持つエージェント間の協調により,動的に変化する要求にも対応できるような協調問題解決手法(タスク分散手法)を検討している.本稿では,タスク分散手法を提案するとともに,処理時間と解の質について発見的手法と比較/評価を行う.
1993-03-01