首页> 外文期刊>Journal of Parallel and Distributed Computing >Gathering of mobile robots with weak multiplicity detection in presence of crash-faults
【24h】

Gathering of mobile robots with weak multiplicity detection in presence of crash-faults

机译:出现碰撞故障时具有弱多重检测的移动机器人的聚集

获取原文
获取原文并翻译 | 示例

摘要

We study the Gathering problem for mobile robots in presence of faults. In classical gathering, robots gather at a point not known a priori in finite time. In this paper, we focus on gathering of all non-faulty robots at a single point in the presence of faulty robots. We propose a wait-free algorithm (i.e., no robot waits for other robot and the algorithm instructs each robot to move in every step, unless it is already at the gathering location), that gathers all non-faulty robots in the semi-synchronous model without any agreement in the coordinate system and with weak multiplicity detection (i.e., a robot can only detect that either there is one or more robots at a location) in the presence of at most n - 1 faulty robots for n = 3. We show that the required capability for gathering robots is minimal in the above model since relaxing it further makes gathering impossible to solve.Also, we introduce a scheduling model as the asynchronous model with instantaneous computation (ASYNC(IC)), which lies in between the asynchronous and the semi-synchronous model. Then we propose another algorithm in the ASYNC(IC) model for gathering all non-faulty robots with weak multiplicity detection and without any agreement on the coordinate system in the presence of at most (left perpendicilar)n/2(right perpendicular) - 2 faulty robots for n = 7. (C) 2018 Elsevier Inc. All rights reserved.
机译:我们研究存在故障的移动机器人的聚集问题。在经典聚会中,机器人会在有限时间内聚集在先验未知的点。在本文中,我们着重于在存在故障机器人的情况下,在同一点收集所有非故障机器人。我们提出了一种免等待算法(即,没有机器人等待其他机器人,并且该算法指示每个机器人在每个步骤中移动,除非它已经在收集位置),该算法将所有非故障机器人收集到半同步机器人中在n≥3的故障机器人最多存在n-1个的情况下,无需在坐标系中达成任何一致的模型,并且具有弱多重检测(即,一个机器人只能检测到某个位置有一个或多个机器人)。我们证明了在上述模型中收集机器人所需的功能是最小的,因为放宽它进一步使收集变得难以解决。此外,我们引入了调度模型作为具有瞬时计算的异步模型(ASYNC(IC)),介于两者之间异步和半同步模型。然后,我们提出了ASYNC(IC)模型中的另一种算法,该算法用于收集所有多重性弱,检测力弱且在最多(左垂直)n / 2(右垂直)-2的坐标系统上没有任何共识的机器人n> = 7的机器人故障。(C)2018 Elsevier Inc.保留所有权利。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号