Gracefully Degrading Gathering in Dynamic Rings
Gracefully Degrading Gathering in Dynamic Rings
复制标题
动态环中优雅的降级聚会
DOI：
10.1007/978-3-030-03232-6_23
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
F. Petit
中科院分区：
文献类型：
--
作者：
Marjorie Bournat;S. Dubois;F. Petit
优雅降级算法 [Biely et al., TCS 2018] 旨在通过使自身适应动态来规避动态系统中的不可能性结果。事实上，这样的算法可以在某些动态下解决给定问题，而且还可以保证在较高动态下解决较弱（但相关）的问题，而在较高动态下原始问题无法解决。潜在的直觉是尽可能解决问题，但如果动态变得（不可预测）更高，则提供某种服务质量。在本文中，我们首次将这种方法应用于机器人网络。我们专注于在动态环的未知位置聚集一队自主机器人的基本问题。在此目标中，我们引入了该问题的一组较弱的变体。受一组与环动力学相关的不可能结果的启发，我们提出了一种优雅降级的收集算法。
Gracefully degrading algorithms [Biely et al., TCS 2018] are designed to circumvent impossibility results in dynamic systems by adapting themselves to the dynamics. Indeed, such an algorithm solves a given problem under some dynamics and, moreover, guarantees that a weaker (but related) problem is solved under a higher dynamics under which the original problem is impossible to solve. The underlying intuition is to solve the problem whenever possible but to provide some kind of quality of service if the dynamics become (unpredictably) higher.In this paper, we apply for the first time this approach to robot networks. We focus on the fundamental problem of gathering a squad of autonomous robots on an unknown location of a dynamic ring. In this goal, we introduce a set of weaker variants of this problem. Motivated by a set of impossibility results related to the dynamics of the ring, we propose a gracefully degrading gathering algorithm.