We consider the stronger version of the gathering problem for n autonomous mobile robots that evolve in a line graph: if there is no crash, the robots must gather as usual, and if there is a single crash location, the remaining correct robots have to gather at this location. The robots have very weak capabilities: their vision is limited and depends on the initial maximum distance between the robots, they are unaware of n, and they either retain no memory of the past, or retain a fixed number of states. In this context, we clarify the problem solvability according to visibility range and memory. If the initial number of occupied nodes is odd, we show that (i) an oblivious (that retains no past memory) algorithm can solve the problem if the visibility radius is one more hop than the trivial lower bound, and that bound is tight, and (ii) robots with one bit of persistent memory can solve the problem with optimal visibility radius, which is also tight with respect to the persistent memory. In the more relaxed setting where the initial number of occupied nodes may be even (but in that case, the distance between the border robots must be even), our one-bit memory algorithm remains valid (and optimal), while we present an oblivious algorithm for the same setting that uses two more hops than our lower bound.

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

A Visibility vs. Memory Trade-Off for Stand-Up Indulgent Gathering on Lines

  • Quentin Bramas,
  • Hirotsugu Kakugawa,
  • Sayaka Kamei,
  • Anissa Lamani,
  • Fukuhito Ooshita,
  • Masahiro Shibata,
  • Sébastien Tixeuil

摘要

We consider the stronger version of the gathering problem for n autonomous mobile robots that evolve in a line graph: if there is no crash, the robots must gather as usual, and if there is a single crash location, the remaining correct robots have to gather at this location. The robots have very weak capabilities: their vision is limited and depends on the initial maximum distance between the robots, they are unaware of n, and they either retain no memory of the past, or retain a fixed number of states. In this context, we clarify the problem solvability according to visibility range and memory. If the initial number of occupied nodes is odd, we show that (i) an oblivious (that retains no past memory) algorithm can solve the problem if the visibility radius is one more hop than the trivial lower bound, and that bound is tight, and (ii) robots with one bit of persistent memory can solve the problem with optimal visibility radius, which is also tight with respect to the persistent memory. In the more relaxed setting where the initial number of occupied nodes may be even (but in that case, the distance between the border robots must be even), our one-bit memory algorithm remains valid (and optimal), while we present an oblivious algorithm for the same setting that uses two more hops than our lower bound.