A Visibility vs. Memory Trade-Off for Stand-Up Indulgent Gathering on Lines
摘要
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.