マルチエージェント系最適化における局所計算の理論
On Local Computation for Optimization in Multi-Agent Systems
各エージェントの決定変数が少数の隣接エージェントとしか結合しない局所構造に着目し、局所近傍情報だけで全体解の一部を計算できる度合いを定量化する理論を構築。問題の局所性と目標精度に応じた部分問題を各エージェントが解く簡潔なアルゴリズムを提案した。
著者: Robin Brown, Federico Rossi, Kiril Solovey, Michael T. Wolf, Marco Pavone
分類: cs.MA, cs.RO, cs.SY, eess.SY
原文アブストラクト
A number of prototypical optimization problems in multi-agent systems (e.g., task allocation and network load-sharing) exhibit a highly local structure: that is, each agent's decision variables are only directly coupled to few other agent's variables through the objective function or the constraints. Nevertheless, existing algorithms for distributed optimization generally do not exploit the locality structure of the problem, requiring all agents to compute or exchange the full set of decision variables. In this paper, we develop a rigorous notion of "locality" that quantifies the degree to which agents can compute their portion of the global solution based solely on information in their local neighborhood. This notion provides a theoretical basis for a rather simple algorithm in which agents individually solve a truncated sub-problem of the global problem, where the size of the sub-problem used depends on the locality of the problem, and the desired accuracy. Numerical results show that the proposed theoretical bounds are remarkably tight for well-conditioned problems.
