限られた通信下での複数ロボットによる複数目標追跡の分散割り当て
Distributed Assignment with Limited Communication for Multi-Robot Multi-Target Tracking
通信が制限された環境で複数ロボットが複数移動目標を追跡するため、限られた通信ラウンドで解を得る2つの分散アルゴリズム（貪欲法と局所法）を提案し、理論保証と実験評価を示した論文。
著者: Yoonchang Sung, Ashish Kumar Budhiraja, Ryan K. Williams, Pratap Tokekar
分類: cs.RO
原文アブストラクト
We study the problem of tracking multiple moving targets using a team of mobile robots. Each robot has a set of motion primitives to choose from in order to collectively maximize the number of targets tracked or the total quality of tracking. Our focus is on scenarios where communication is limited and the robots have limited time to share information with their neighbors. As a result, we seek distributed algorithms that can find solutions in bounded amount of time. We present two algorithms: (1) a greedy algorithm that is guaranteed finds a $2$-approximation to the optimal (centralized) solution albeit requiring $|R|$ communication rounds in the worst-case, where $|R|$ denotes the number of robots; and (2) a local algorithm that finds a $\mathcal{O}\left((1+\epsilon)(1+1/h)\right)$-approximation algorithm in $\mathcal{O}(h\log 1/\epsilon)$ communication rounds. Here, $h$ and $\epsilon$ are parameters that allow the user to trade-off the solution quality with communication time. In addition to theoretical results, we present empirical evaluation including comparisons with centralized optimal solutions.
