Deterministic Dispersion of Mobile Robots in Dynamic Rings
Deterministic Dispersion of Mobile Robots in Dynamic Rings
复制标题
动态环中移动机器人的确定性色散
DOI：
10.1145/3154273.3154294
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Sridhar
中科院分区：
文献类型：
--
作者：
Ankush Agarwalla;John E. Augustine;W. Moses;Sankar K. Madhav;A. Sridhar
在本工作中，我们研究了移动机器人在动态环上的分散问题。N结点图上n个机器人的分散问题，由Augustine和Mosse Jr.[2]，需要机器人相互协调，并达到每个节点上恰好有一个机器人的配置。这个问题在现实世界中有应用，每当我们想要最小化n个代理共享位于不同地点的n个资源的总成本时，约束条件是一个代理转移到不同资源的成本相对要比多个代理共享同一资源的成本小得多(例如，智能电动汽车共享充电站)。该问题的研究也为图上的散布、移动机器人的探索、图上的负载均衡等研究提供了间接的帮助。我们解决了在基础图中存在两种类型的动态时的离散问题：(I)顶点置换和(Ii)1-区间连通。我们引入了顶点置换动态的概念，这意味着对于给定的一组节点，在每一轮中，对手确保保持环状结构，但节点之间的连接可能会改变。我们使用了Di，露娜等人的1-区间连通性的思想。[11]，其中对于给定的环，在每一轮中，对手至多选择一条边来移除。我们假设机器人具有完全可见性，当机器人具有手性时，我们给出了渐近时间最优算法，以实现在两种动态情况下的分散。当机器人不具有手性时，我们给出了在一定约束下实现分散的渐近时间最优算法。最后，我们给出了当机器人不可见时分散的不可能结果。
In this work, we study the problem of dispersion of mobile robots on dynamic rings. The problem of dispersion of n robots on an n node graph, introduced by Augustine and Moses Jr. [2], requires robots to coordinate with each other and reach a configuration where exactly one robot is present on each node. This problem has real world applications and applies whenever we want to minimize the total cost of n agents sharing n resources, located at various places, subject to the constraint that cost of an agent moving to a different resource is comparatively much smaller than cost of multiple agents sharing a resource (e.g. smart electric cars sharing recharge stations). Study of this problem also provides indirect benefits to the studies of scattering on graphs, exploration by mobile robots, and load balancing on graphs. We solve the problem of dispersion in presence of two types of dynamism in the underlying graph: (i) vertex permutation and (ii) 1-interval connectivity. We introduce the notion of vertex permutation dynamism and have it mean that for a given set of nodes, in every round, the adversary ensures a ring structure is maintained, but the connections between the nodes may change. We use the idea of 1-interval connectivity from Di Luna et al. [11], where for a given ring, in each round, the adversary chooses at most one edge to remove. We assume robots have full visibility and present asymptotically time optimal algorithms to achieve dispersion in the presence of both types of dynamism when robots have chirality. When robots do not have chirality, we present asymptotically time optimal algorithms to achieve dispersion subject to certain constraints. Finally, we provide impossibility results for dispersion when robots have no visibility.