Fully Dynamic Line Maintenance by a Simple Robot

In this paper, we consider a hybrid system composed of a line of nano-sized passive elements incapable of movement (called tiles), which can be manipulated by an active mobile entity (called robot). The line maintenance problem requires the robot to operate so that, whenever a tile becomes faulty, it is removed from the line and all the non-faulty tiles are rearranged into a line, always maintaining connectivity in the overall structure. We propose a solution algorithm that works under the worst possible dynamic failure conditions: any tile can stop functioning at any time. Our algorithm requires the robot to have only minimal computational capabilities, that of a deterministic finite automaton.