• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings
【24h】

Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings

机译：环中具有局部弱多重性的移动机器人聚集算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The gathering problem of anonymous and oblivious mobile robots is one of fundamental problems in the theoretical mobile robotics. We consider the gathering problem in unoriented and anonymous rings, which requires that all robots gather at a non-predefined node. Since the gathering problem cannot be solved without any additional capability to robots, all the previous works assume some capability of robots, such as accessing the memory on node. In this paper, we focus on the multiplicity capability. This paper presents a deterministic gathering algorithm with local-weak multiplicity, which provides the robot with the information about whether its current node has more than one robot or not. This assumption is strictly weaker than that by previous works. Moreover, we show that our algorithm is asymptotically time-optimal one, that is, the time complexity of our algorithm is O(n), where n is the number of nodes. Interestingly, in spite of assuming the weaker assumption, it achieves significant improvement compared to the previous algorithm, which takes O(kn) time for k robots.
机译：匿名和遗忘的移动机器人的聚集问题是理论上的移动机器人的基本问题之一。我们在无方向性和匿名环中考虑收集问题，这要求所有机械手在一个未预定义的节点处收集。由于没有机器人的任何附加功能都无法解决收集问题，因此所有先前的工作都假定了机器人的某些功能，例如访问节点上的内存。在本文中，我们着重于多重性。本文提出了一种具有局部弱多重性的确定性收集算法，该算法为机器人提供了有关其当前节点是否具有多个机器人的信息。这个假设比以前的工作要严格。此外，我们证明了我们的算法是渐近时间最优的，也就是说，我们算法的时间复杂度是O（n），其中n是节点数。有趣的是，尽管假设的假设较弱，但与以前的算法（k个机器人需要O（kn）时间）相比，它仍取得了显着改进。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号