分散制約最適化問題の解法Max-Sumにおける評価関数の動的な変更手法

IR IPSJ Web Site

Bibliographic Information

Other Title
  • ブンサン セイヤク サイテキ カ モンダイ ノ カイホウ Max-Sum ニ オケル ヒョウカ カンスウ ノ ドウテキ ナ ヘンコウ シュホウ
  • Dynamically Changing Utility-functions in Max-Sum Algorithm

Search this article

Abstract

分散制約最適化問題（DCOP）はマルチエージェントシステムにおける分散協調問題解決の基礎的な表現として研究されている．本研究では，近年提案されたDCOPの解法であるMax-Sumアルゴリズムに注目する．Max-Sumは，問題を表現するfactorグラフに含まれるサイクルの数が少なければ比較的精度が高い解を得る傾向があるが，より多くのサイクルを含み，辺の密度が高い部分がある場合には解の精度が低下する．その解の精度の低下は，制約網において隣接する変数間の制約も含める評価関数MS-Stableにより改善されるが，各エージェントが評価する部分問題の規模は拡大する．そこで，解の精度と計算量のトレードオフを利用するために，解法の実行中に2つの評価関数を適応的に切り替える手法Z-MSSを提案する．Z-MSSでは各エージェントの利得の推定値に基づいて，評価関数を動的に変更する．利得の推定値により，詳細な評価が必要な部分に対してMS-Stableが割り当てられるため，計算量の増加を抑えつつ，比較的高い解の精度を得ることが期待される．また，Z-MSSはパラメータによって，ある程度は解の精度と計算量を調整でき，その適切な設定値は問題の種類やグラフの構造に依存する．頂点彩色問題および重み付きの二項制約からなる問題において，Z-MSSおよびそのパラメータの効果を実験により評価する．

Distributed Constraint Optimization Problems (DCOPs) have been studied as a fundamental model of multi-agents cooperation. We address the Max-Sum algorithm that has been proposed as a solution method for DCOPs. The Max-Sum algorithm generates relatively better approximate solutions when it is applied to less cyclic factor graphs. However, in the case that the graph contains many cycles and dense parts, the quality of the solution decreases. The solution quality can be improved by using extended utility function MS-Stable that additionally evaluates constraints among neighborhood nodes. On the other hand, the MS-Stable increases the size of the local problem that is computed in each agent. To employ this trade off, we propose Z-MSS that suitably switches the both types of utility-functions while the solution method is running. In Z-MSS, each agent switches utility functions based on the estimation values of its utilities. As a result, MS-Stable is applied to the parts of the problem that need detailed evaluation. The effects of Z-MSS and its parameters are experimentally evaluated applying it to graph coloring problems and weighted binary constraint problems.

Journal

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top