We study a fundamental cooperative message-delivery problem on the plane. Assume $n$ robots which can move in any direction, are placed arbitrarily on the plane. Robots each have their own maximum speed and can communicate with each other face-to-face (i.e., when they are at the same location at the same time). There are also two designated points on the plane, $S$ (the source) and $D$ (the destination). The robots are required to transmit the message from the source to the destination as quickly as possible by face-to-face message passing. We consider both the offline setting where all information (the locations and maximum speeds of the robots) are known in advance and the online setting where each robot knows only its own position and speed along with the positions of $S$ and $D$. In the offline case, we discover an important connection between the problem for two-robot systems and the well-known Apollonius circle which we employ to design an optimal algorithm. We also propose a $\sqrt 2$ approximation algorithm for systems with any number of robots. In the online setting, we provide an algorithm with competitive ratio $\frac 17 \left( 5+ 4 \sqrt{2} \right)$ for two-robot systems and show that the same algorithm has a competitive ratio less than $2$ for systems with any number of robots. We also show these results are tight for the given algorithm. Finally, we give two lower bounds (employing different arguments) on the competitive ratio of any online algorithm, one of $1.0391$ and the other of $1.0405$.
翻译:我们研究的是飞机上的基本合作信息传递问题。 代表着能向任何方向移动的美元机器人, 被任意放置在飞机上。 机器人各自拥有自己的最大速度, 并且可以彼此面对面地交流( 即当他们在同一地点同时在同一地点时) 。 飞机上还有两个指定点, 即 $S( 源) 和 $D( 目的地) 。 机器人需要通过面对面传递信息, 尽快将信息从源头传送到目的地。 我们既考虑所有信息( 机器人的位置和最高比率) 的离线设置, 也考虑着每个机器人只知道自己的位置和速度的在线设置 。 在离线情况下, 我们发现两个机器人系统的问题和我们用来设计最佳算法的知名阿波纽圆之间存在重要联系 。 我们还提议用一个$2美元的近似值算法, 与一个机器人的网络数相比, 两个机器人的更低值 。 在在线设置中, 我们提供一种具有竞争力的 RON2 和 4 的算法 。