...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Algorithmica >Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots
【24h】

Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots

机译：无需通信即可进行计算：异步遗忘机器人进行环探索

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

摘要

We consider the problem of exploring an anonymous unoriented ring by a team of k identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible. We first show that, when k and n are not co-prime, the problem is not solvable in general, e.g., if k divides n there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that n and k are co-prime, for k ≥ 17, by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number ρ(n) of robots that can explore a ring of size n. As a consequence of our positive result we show that ρ(n) is O(logn). We additionally prove that Q, (log n) robots are necessary for infinitely many n.
机译：我们考虑由k个可以观察环境但无法通信的相同的，遗忘的异步移动机器人团队探索匿名的无方向环的问题。当机器人在其中操作的空间宇宙是二维平面时，这种较弱的情况是标准的，但是（除一个例外）之前尚未对网络进行过研究。我们的结果表明，尽管机器人的这些薄弱功能使问题变得更加困难，但仍然可以由一小组机器人进行环形勘探。我们首先表明，当k和n不是互质时，这个问题通常无法解决，例如，如果k将n除以n，则存在机器人无法进行初始放置的位置。然后，通过给出一个从任意初始配置开始总是终止的探索算法，证明对于k≥17的n和k是互质的，这个问题总是可以解决的。最后，我们考虑可以探索大小为n的环的机器人的最小数量ρ（n）。作为我们积极结果的结果，我们证明ρ（n）为O（logn）。我们还证明了Q（log n）个机器人对于无限多的n是必需的。

著录项

  • 来源
    《Algorithmica》 |2013年第3期|562-583|共22页
  • 作者

    Paola Flocchini; David Ilcinkas; Andrzej Pelc; Nicola Santoro;

  • 作者单位

    School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Ontario K1N 6N5, Canada;

    LaBRI, CNRS & Universite de Bordeaux, 351 cours de la Liberation, 33405 Talence cedex, France;

    Departement d'informatique, Universite du Quebec en Outaouais, Gatineau, Quebec J8X 3X7, Canada;

    School of Computer Science, Carleton University, Ottawa, Ontario, K1S 5B6, Canada;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    mobile robots; asynchronous; oblivious; exploration; ring;

    机译：移动机器人;异步;遗忘勘探;环;

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号