分散制約最適化問題の非同期分散探索における上下界の導出と学習を用いた効率改善手法

松井　俊浩  松尾　啓志  岩田　彰  

誌名
電子情報通信学会論文誌 D   Vol.J88-D1   No.8   pp.1235-1246
発行日: 2005/08/01
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 論文
専門分野: 分散協調とエージェント
キーワード: 
分散制約最適化問題,  分散制約充足問題,  マルチエージェント,  分枝限定法,  

本文: PDF(483KB)>>
論文を購入



あらまし: 
分散制約最適化問題（DCOP）は非同期分散環境における問題解決を扱うものとして，マルチエージェント分野で重要な位置付けにある．本論文では，DCOPの解法として最近提案された分枝限定法に基づく非同期分散探索手法に対し，基本的な効率改善手法を提案する．従来手法は深さ優先探索木に配置されたノード（エージェント）によるコスト計算を基礎として非同期分散探索を実現しているが，バックトラック処理に効率化の余地がある．また非同期性により同一解を再探索する機会が多い．提案手法はバックトラックにおけるオーバヘッドの削減のために，上下界に関連する解の導出及び上位ノードへの下界通知のショートカットを導入する．また，再探索の削減のために，探索済みの上下界情報の学習を導入する．計算機実験により提案手法の有効性を評価する．