In the problem of dispersion, a set of mobile robots, starting from one or multiple source nodes in a network, must relocate themselves in such a way that there is at most one robot present at any node of the graph. Most of the prior works on dispersion assume local communication between robots: any two robots, while located on the same node, can communicate by exchanging messages of arbitrary size. A recent paper by Gorain et al. [4] has shown that this kind of local communication is not necessary to achieve dispersion. They have shown that dispersion can be achieved using very limited local knowledge, where a robot can sense the following local information at any node: A) Is the robot alone at a node in a round? B) Do the number of robots at a node in the current round have increased compared to the previous round? and C) Do the number of robots at a node in the current round have decreased compared to the previous round? The authors have proposed an algorithm using which a set of co-located robots with access to the above local information achieved dispersion. In this paper, we show the existence of an algorithm for dispersion in a weaker model than that is considered in [4]. Specifically, we show that the knowledge of (A) and (C) are enough to achieve dispersion. Moreover, our algorithm works even if the robots do not wake up at the same time.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Collaborative Dispersion of Silent Robots with Different Wake-Up Time

  • Barun Gorain,
  • Subhrangsu Mandal,
  • Yash Sharma

摘要

In the problem of dispersion, a set of mobile robots, starting from one or multiple source nodes in a network, must relocate themselves in such a way that there is at most one robot present at any node of the graph. Most of the prior works on dispersion assume local communication between robots: any two robots, while located on the same node, can communicate by exchanging messages of arbitrary size. A recent paper by Gorain et al. [4] has shown that this kind of local communication is not necessary to achieve dispersion. They have shown that dispersion can be achieved using very limited local knowledge, where a robot can sense the following local information at any node: A) Is the robot alone at a node in a round? B) Do the number of robots at a node in the current round have increased compared to the previous round? and C) Do the number of robots at a node in the current round have decreased compared to the previous round? The authors have proposed an algorithm using which a set of co-located robots with access to the above local information achieved dispersion. In this paper, we show the existence of an algorithm for dispersion in a weaker model than that is considered in [4]. Specifically, we show that the knowledge of (A) and (C) are enough to achieve dispersion. Moreover, our algorithm works even if the robots do not wake up at the same time.