• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots
【24h】

Optimal Deterministic Ring Exploration with Oblivious Asynchronous Robots

机译：渐进式异步机器人的最优确定性环探索

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

摘要

We consider the problem of exploring an anonymous unori-ented ring of size n by k identical, oblivious, asynchronous mobile robots, that are unable to communicate, yet have the ability to sense their environment and take decisions based on their local view. Previous works in this weak scenario prove that k must not divide n for a deterministic solution to exist. Also, it is known that the minimum number of robots (either deterministic or probabilistic) to explore a ring of size n is 4. An upper bound of 17 robots holds in the deterministic case while 4 probabilistic robots are sufficient. In this paper, we close the complexity gap in the deterministic setting, by proving that no deterministic exploration is feasible with less than five robots, and that five robots are sufficient for any n that is coprime with five. Our protocol completes exploration in O(n) robot moves, which is also optimal.
机译：我们考虑了一个问题，即探索一个未知的无序环，大小为n×k，它们是相同的，遗忘的，异步的移动机器人，它们无法通信，但是能够感知其环境并根据其本地视图做出决定。在这种较弱的情况下，以前的工作证明，对于确定性解的存在，k不能除以n。同样，已知探索大小为n的环的最小数量的机器人（确定性或概率性机器人）为4。在确定性情况下，17个机器人的上限保持不变，而4个概率性机器人就足够了。在本文中，我们通过证明少于五个机器人没有确定性探索是可行的，并且对于任何与五个互质的n，五个机器人就足够了，从而弥合了确定性设置中的复杂性差距。我们的协议完成了对O（n）机器人运动的探索，这也是最佳的。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号