Fault-tolerant gathering algorithms for autonomous mobile robots
Fault-tolerant gathering algorithms for autonomous mobile robots
复制标题
自主移动机器人的容错采集算法
DOI：
10.1137/050645221
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Noam Agmon;D. Peleg
研究了N个自主移动的机器人聚集问题的容错算法。由每个机器人独立执行的收集算法必须确保所有机器人在有限时间内聚集在一个点。首先观察到，大多数现有算法在允许崩溃故障的设置中不能正确操作。随后，对一个碰撞故障的机器人在三个或更多的机器人系统的容错算法。然后，它表明，在异步环境中，它是不可能执行一个成功的收集在3机器人系统与一个拜占庭失败。最后，在完全同步系统中，给出了N ≥ 3个机器人且至多有一个故障机器人的集结算法，并在N-机器人系统中给出了一个更一般的至多有f个故障机器人的集结算法，其中N ≥ 3f +1.
This paper studies fault tolerant algorithms for the problem of gathering N autonomous mobile robots. A gathering algorithm, executed independently by each robot, must ensure that all robots are gathered at one point within finite time. It is first observed that most existing algorithms fail to operate correctly in a setting allowing crash failures. Subsequently, an algorithm tolerant against one crash-faulty robot in a system of three or more robots is presented. It is then shown that in an asynchronous environment it is impossible to perform a successful gathering in a 3-robot system with one Byzantine failure. Finally, in a fully synchronous system, an algorithm is provided for gathering N ≥ 3 robots with at most a single faulty robot, and a more general gathering algorithm is given in an N-robot system with up to f faults, where N ≥ 3 f +1.