...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Robotics, IEEE Transactions on >Multirobot Tree and Graph Exploration
【24h】

Multirobot Tree and Graph Exploration

机译：多机器人树和图探索

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

摘要

In this paper, we present an algorithm for the exploration of an unknown graph by multiple robots, which is never worse than depth-first search with a single robot. On trees, we prove that the algorithm is optimal for two robots. For $k$ robots, the algorithm has an optimal dependence on the size of the tree but not on its radius. We believe that the algorithm performs well on any tree, and this is substantiated by simulations. For trees with $e$ edges and radius $r$, the exploration time is less than ${2e}/{k}+(1+{(k}/{r)})^{k-1}({2}/{k!})r^{k-1} =({2e}/{k}) + O((k+r)^{k-1})$ (for $r>k$, $le ({2e}/{k}) + 2r^{k-1}$), thereby improving a recent method with time $O(({e}/{log k)} + r)$ , and almost reaching the lower bound ${rm max} (({2e}/{k}), 2r)$. The model underlying undirected-graph exploration is a set of rooms connected by opaque passages; thus, the algorithm is appropriate for scenarios like indoor navigation or cave exploration. In this framework, communication can be realized by bookkeeping devices being dropped by the robots at explored vertices, the states of which are read and changed by further visiting robots. Simulations have been performed in both tree and graph explorations to corroborate the mathematical results.
机译：在本文中，我们提出了一种利用多个机器人探索未知图形的算法，该算法永远不会比使用单个机器人进行深度优先搜索更糟糕。在树上，我们证明该算法对于两个机器人而言是最优的。对于$ k $机器人，该算法对树的大小具有最佳依赖关系，而对树的半径则没有依赖关系。我们相信该算法在任何树上都能表现良好，并且通过仿真证明了这一点。对于具有$ e $边和半径$ r $的树，探索时间小于$ {2e} / {k} +（1 + {（k} / {r）}）^ {k-1}（{2 } / {k！}）r ^ {k-1} =（{2e} / {k}）+ O（（k + r）^ {k-1}）$（$ r> k $，$ le （{2e} / {k}）+ 2r ^ {k-1} $），从而改进了时间为$ O（（{{e} / {log k）} + r）$的最近方法，并且几乎达到了绑定$ {rm max}（（{{2e} / {k}），2r）$。无向图探索的基础模型是一组由不透明通道连接的房间。因此，该算法适用于室内导航或洞穴探险等场景。在此框架中，可以通过将机器人放到探究的顶点处的簿记设备来实现通信，通过进一步访问的机器人读取并更改其状态。在树和图探索中都进行了模拟，以证实数学结果。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号