直線上の複数ロボットによる対称ランデブー探索
Multi-robot Symmetric Rendezvous Search on the Line
直線上に任意配置された3台以上のロボットが、互いの位置を知らないまま同じ探索戦略で最短時間に集合するためのランダム化アルゴリズムを提案し、移動距離の競合比が定数であることを示した。
著者: Deniz Ozsoyeller, Pratap Tokekar
分類: cs.RO, cs.DM
原文アブストラクト
We study the Symmetric Rendezvous Search Problem for a multi-robot system. There are $n>2$ robots arbitrarily located on a line. Their goal is to meet somewhere on the line as quickly as possible. The robots do not know the initial location of any of the other robots or their own positions on the line. The symmetric version of the problem requires the robots to execute the same search strategy to achieve rendezvous. Therefore, we solve the problem in an online fashion with a randomized strategy. In this paper, we present a symmetric rendezvous algorithm which achieves a constant competitive ratio for the total distance traveled by the robots. We validate our theoretical results through simulations.
