论文标题
移动机器人的容忍故障分散
Fault-Tolerant Dispersion of Mobile Robots
论文作者
论文摘要
在存在故障的机器人（崩溃失误）的情况下，我们考虑移动机器人分散问题。移动机器人色散由$ n $ node匿名图中的$ k \ leq n $ robots组成。目的是确保不管机器人在节点上的初始放置如何，最终配置最多包括在每个节点上具有一个机器人。在崩溃的装置设置中，最多$ f \ leq k $机器人可能会因任意撞车而失去失败，然后丢失存储在机器人中的所有信息，从而使它们无法交流。在本文中，我们通过考虑两种不同的初始配置来解决崩溃错误设置中的分散问题：i）扎根配置，ii）任意配置。在根本的情况下，所有机器人在开始时都放在一个节点上。任意配置是一种常规配置（又称文献中的任意配置），其中机器人被放置在某个$ l <k $ clusters中，请在整个图形上任意。对于第一种情况，我们在$ O（k^2）$ rounds中存在故障机器人的情况下开发了算法求解散布，该算法比以前的$ o（f \ cdot \ text {min}（m，kΔ）（m，kΔ）$ - 圆形圆形\ cite {ps021}结果改善。对于任意配置，我们在$ o（（（f+l）\ cdot \ text {min}（m，kδ，k^2））中，我们提出了算法求解分散剂，当$ m $和最大$δ$Δ$的最大$δ$时，机器人已知。
We consider the mobile robot dispersion problem in the presence of faulty robots (crash-fault). Mobile robot dispersion consists of $k\leq n$ robots in an $n$-node anonymous graph. The goal is to ensure that regardless of the initial placement of the robots over the nodes, the final configuration consists of having at most one robot at each node. In a crash-fault setting, up to $f \leq k$ robots may fail by crashing arbitrarily and subsequently lose all the information stored at the robots, rendering them unable to communicate. In this paper, we solve the dispersion problem in a crash-fault setting by considering two different initial configurations: i) the rooted configuration, and ii) the arbitrary configuration. In the rooted case, all robots are placed together at a single node at the start. The arbitrary configuration is a general configuration (a.k.a. arbitrary configuration in the literature) where the robots are placed in some $l<k$ clusters arbitrarily across the graph. For the first case, we develop an algorithm solving dispersion in the presence of faulty robots in $O(k^2)$ rounds, which improves over the previous $O(f\cdot\text{min}(m,kΔ))$-round result by \cite{PS021}. For the arbitrary configuration, we present an algorithm solving dispersion in $O((f+l)\cdot\text{min}(m, k Δ, k^2))$ rounds, when the number of edges $m$ and the maximum degree $Δ$ of the graph is known to the robots.
