分散制約最適化問題の解法Max-Sumにおける評価関数の緩和手法 ○川東 勇輝† 松井 俊浩† 松尾 啓志† † 名古屋工業大学

2 背景 分散制約最適化問題(DCOP) マルチエージェントシステムにおける 分散協調問題解決を表す基礎的な表現 DCOPの解法 厳密解法 必ず最適解が得られるが,計算コストが高い 非厳密解法 最適解が得られるとは限らないが,計算コストは低い 比較的軽量な非厳密解法であるMax-Sum*1とその拡張であるMS-Stable*1に注目する *1 Farinelli, A., et al: Decentralised coordination of low-power embedded devices using the Max-Sum Algorithm,2008

3 分散制約最適化問題 分散制約最適化問題 マルチエージェントの協調問題を表す基本的な枠組み エージェントは状態を表す変数を保持 変数xi,xjに関する二項制約に対応する評価関数fi,j により変数値の割り当ての評価値が得られる xj xi Ai Aj f i,j すべての評価関数の値の合計を最大化する事が目的 制約網

4 Max-Sumアルゴリズムでの問題表現 評価関数と制約 変数値と値域 x2 x1 x3 U1 U2 U3 x1 x2 x3 A1 A2 A3 関数ノード 変数ノード 変数値と値域 評価関数と制約 A1 A2 A3 factorグラフ Max-Sumは確率伝搬に基づく解法 factorグラフを用いて準最適解を求める 制約網 ・関数ノードから変数ノードへの メッセージ(評価値)送受信 ・変数ノードから関数ノードへの メッセージ(評価値)送受信

5 Max-Sumの評価関数Uims 　　自エージェントと隣接エージェントとの制約を使用 長所:少ない計算コスト 短所:サイクルを多く含む制約網の場合 解の精度が低下 拡張されたMax-Sumの評価関数Uimss(MS-Stable) 隣接エージェント間の制約も使用 長所:サイクルを多く含む制約網でも 解の精度は良好 短所:計算コストが大幅に増加 従来手法 Ak Ai Al Aj Ak Ai Al Aj 自Aと制約があるA 使用しない 使用する 制約網 使用する 使用しない Max-Sumでは解の精度が足らず、MS-Stableでは計算コストが高い

6 提案手法 解の精度を維持しつつ,計算量を抑える手法を提案 k-GMSS(k-Group MS-Stable) アルゴリズムの実行前に評価関数を変更 隣接エージェントをk個でグループ化 部分的にMS-Stableを適用 Z-MSS(Z-MS-Stable) 周辺関数Z(x)の値を指標 アルゴリズムの実行中に評価関数を切り替え

7 k-GMSS 隣接エージェントを最大k個でグループ化を行い グループ部に部分的にMS-Stableを適用する手法 グループ間の制約を緩和 グループ化を行う個数kを増減する事で緩和する制約数を増減 Ak Ai Al Aj 最大2個でグループ化 Ak Ai Al Aj Group2 評価関数に用いる制約数を調整することで 解の精度と計算量を調整する Max-Sum 2-GMSS 3-GMSS 最大3個でグループ化 制約網 部分的な MS-Stable

Ai Ai 8 Z-MSS 周辺関数Zが均衡する時、評価関数を切り替える 周辺関数Z:そのエージェントが各変数値を取った時の利得 Max-Sumは常に周辺関数Zの値が最大となる変数値を取る Ai Z(x) x= A B C 均衡 1.周辺関数の値の均衡 　 を検知する 2.δサイクルの間 　評価関数をMS-Stable 　に切り替える Z(x) x= A B C Max-Sum MS-Stable 均衡解消 制約網 制約を詳細に用いる評価関数に切り替える事により均衡が解消し 変数値が安定するため、準最適解に速やかに到達する 解法の途中で

9 実験諸元 問題設定 3色の頂点彩色問題 頂点数10,12,15,18,20 制約数は頂点数*3　(過制約) 比較手法 従来手法 Max-Sum,MS-Stable 提案手法 k-GMSS,Z-MSS 評価 50インスタンスの違反数と計算量の平均 違反数:両端が同じ色となった制約の数 計算量:評価関数の計算に必要となった変数値の組み合わせ数

10 k-GMSSの平均違反数と計算量 ・2-GMSSは違反数・計算量ともにMax Sum,MS-Stableの中間となり 計算量を抑えつつ、ある程度の解の精度が得られた

11 Z-MSSの平均違反数と計算量 ・全ての頂点数でZ-MSSはMS-Stableとほぼ同じ違反数となった ・計算量はMS-Stableの約1/10に削減できた

12 まとめと今後の課題 まとめ k-GMSS 隣接Aをk個でグループ化し、部分的にMS-Stableを適用する手法 Z-MSS 周辺関数Zの均衡を検出し、実行中に評価関数を切り替える手法 今後の課題 他のクラスの問題における提案手法の適用 提案手法のより詳細な解析 解の精度を維持しつつ、計算量を削減できた