Dispersion of Mobile Robots in the Global Communication Model
Dispersion of Mobile Robots in the Global Communication Model
复制标题
移动机器人在全球通信模式中的分散
DOI：
10.1145/3369740.3369775
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Gokarna Sharma
中科院分区：
文献类型：
--
作者：
A. Kshemkalyani;A. R. Molla;Gokarna Sharma
图上的分散问题要求初始任意放置在n节点匿名图的节点上的k≤n个机器人自主重新定位，以达到每个机器人在图的不同节点上的配置。由于该问题与其他基本机器人协调问题（如自动驾驶电动汽车（机器人）的探索、分散、负载平衡以及向充电站（节点）的迁移）之间的关系，因此引起了人们的极大兴趣。在本文中，我们考虑全局通信模型中的离散性，其中机器人可以与图中的任何其他机器人通信（但图对机器人来说是未知的）。我们提供了三种新的确定性算法，两种用于任意图，一种用于任意树，在同步设置中，所有机器人在每个时间步执行其动作。对于任意图，我们的第一个算法基于DFS遍历，并使用Θ（log（max（k， Δ）））位在每个机器人上保证O（min（m, kΔ））步运行时间，其中m是边的数量，Δ是图的最大度。任意图的第二种算法基于BFS遍历，并保证在每个机器人上使用O（max（D, k）Δ（D + Δ））位运行O（max(D， Δ log k)）步，其中D是图的直径。任意树的算法也是基于BFS旅行，并保证在每个机器人上使用O（max(D， Δ log k)）位来运行O（D max(D, k)）步。与本地通信模型中建立的现有结果相比，我们的结果有了显著的改进，在本地通信模型中，机器人只能与同一节点上的其他机器人通信。
The dispersion problem on graphs asks k ≤ n robots placed initially arbitrarily on the nodes of an n-node anonymous graph to reposition autonomously to reach a configuration in which each robot is on a distinct node of the graph. This problem is of significant interest due to its relationship to other fundamental robot coordination problems, such as exploration, scattering, load balancing, and relocation of self-driven electric cars (robots) to recharge stations (nodes). In this paper, we consider dispersion in the global communication model where a robot can communicate with any other robot in the graph (but the graph is unknown to robots). We provide three novel deterministic algorithms, two for arbitrary graphs and one for arbitrary trees, in a synchronous setting where all robots perform their actions in every time step. For arbitrary graphs, our first algorithm is based on a DFS traversal and guarantees O(min(m, kΔ)) steps runtime using Θ(log(max(k, Δ))) bits at each robot, where m is the number of edges and Δ is the maximum degree of the graph. The second algorithm for arbitrary graphs is based on a BFS traversal and guarantees O(max(D, k)Δ(D + Δ)) steps runtime using O(max(D, Δ log k)) bits at each robot, where D is the diameter of the graph. The algorithm for arbitrary trees is also based on a BFS travesal and guarantees O(D max(D, k)) steps runtime using O(max(D, Δ log k)) bits at each robot. Our results are significant improvements compared to the existing results established in the local communication model where a robot can communication only with other robots present at the same node.