In this paper, we consider the uniform deployment problem of myopic luminous robots in rings, requiring them to spread uniformly in the ring. Robots are myopic if they have a common limited visibility range and robots are luminous if hey are equipped with a light device that can emit a color from a finite set. The past related research considered uniform deployment for myopic and oblivious robots. Here, robots are oblivious if they have no memory and cannot memorize the history of past actions. In this case, it is shown that quiescent uniform deployment, requiring that robots stop moving after they reached a uniformly deployed configuration but they are allowed to resume moving when observing some configuration changes, is impossible. In this paper, we consider the feasibility of the uniform deployment problem by introducing lights. Let n be the number of nodes and k be the number of robots. First, we show that, even if robots behave fully synchronously and have an infinite number of light colors, they cannot achieve uniform deployment when either of the followings holds: (i) they do not have a common sense of direction, (ii) the visibility range is less than \(\lfloor n/k\rfloor \) , or (iii) the problem requires explicit termination detection. Next, for robots that behave semi-synchronously and have a common sense of direction and visibility range at least \(\lfloor n/k\rfloor \) , we propose an algorithm to solve the quiescent uniform deployment problem, by allowing robots to be luminous and have a constant number of light colors. This is a striking difference compared to the past result for oblivious robots.

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

Uniform Deployment of Myopic Luminous Robots in Rings

  • Masahiro Shibata,
  • Sayaka Kamei,
  • Fukuhito Ooshita,
  • Hirotsugu Kakugawa

摘要

In this paper, we consider the uniform deployment problem of myopic luminous robots in rings, requiring them to spread uniformly in the ring. Robots are myopic if they have a common limited visibility range and robots are luminous if hey are equipped with a light device that can emit a color from a finite set. The past related research considered uniform deployment for myopic and oblivious robots. Here, robots are oblivious if they have no memory and cannot memorize the history of past actions. In this case, it is shown that quiescent uniform deployment, requiring that robots stop moving after they reached a uniformly deployed configuration but they are allowed to resume moving when observing some configuration changes, is impossible. In this paper, we consider the feasibility of the uniform deployment problem by introducing lights. Let n be the number of nodes and k be the number of robots. First, we show that, even if robots behave fully synchronously and have an infinite number of light colors, they cannot achieve uniform deployment when either of the followings holds: (i) they do not have a common sense of direction, (ii) the visibility range is less than \(\lfloor n/k\rfloor \) , or (iii) the problem requires explicit termination detection. Next, for robots that behave semi-synchronously and have a common sense of direction and visibility range at least \(\lfloor n/k\rfloor \) , we propose an algorithm to solve the quiescent uniform deployment problem, by allowing robots to be luminous and have a constant number of light colors. This is a striking difference compared to the past result for oblivious robots.