The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important requirement of exploration is the {\em termination} condition, i.e., the robots must know that exploration is completed. The problem of live exploration of a dynamic ring using mobile robots was recently introduced in [Di Luna et al., ICDCS 2016]. In it, they proposed multiple algorithms to solve exploration in fully synchronous and semi-synchronous settings with various guarantees when $2$ robots were involved. They also provided guarantees that with certain assumptions, exploration of the ring using two robots was impossible. An important question left open was how the presence of $3$ robots would affect the results. In this paper, we try to settle this question in a fully synchronous setting and also show how to extend our results to a semi-synchronous setting. In particular, we present algorithms for exploration with explicit termination using $3$ robots in conjunction with either (i) unique IDs of the robots and edge crossing detection capability (i.e., two robots moving in opposite directions through an edge in the same round can detect each other), or (ii) access to randomness. The time complexity of our deterministic algorithm is asymptotically optimal. We also provide complementary impossibility results showing that there does not exist any explicit termination algorithm for $2$ robots. The theoretical analysis and comprehensive simulations of our algorithm show the effectiveness and efficiency of the algorithm in dynamic rings. We also present an algorithm to achieve exploration with partial termination using $3$ robots in the semi-synchronous setting.
翻译:图形勘探问题需要一组移动机器人,最初在图表节点上任意放置,以便合作探索图表,使每个节点最终至少由一个机器人访问。 勘探的一个重要要求是 ~ 结束 状态, 即机器人必须知道勘探已经完成 。 使用移动机器人的动态环的现场探索问题最近在 [ Di Luna et al., ICDCS 2016] 中引入 。 其中, 他们提出了多种算法, 以解决在完全同步和半同步环境中进行探索的问题, 当涉及 $ 2 的机器人时提供各种保证 。 他们还提供了以下的保证: 在某些假设下, 利用两个机器人对环的勘探是不可能的。 一个重要的问题在于, 3 $ 机器人的存在会如何影响结果。 在本文中, 我们试图用一个完全同步的设置来解决这个问题, 同时将我们的结果扩展到半同步的设置 。 特别是, 我们用 3$ 的直线的机器人来进行勘探的算法, 与两个移动的 终结性 结束性 。 使用每个机器人和 快速 的精确性 运行 速度 向 展示一个最佳的路径 。