Minimum algorithm sizes for self-stabilizing gathering and related problems of autonomous mobile robots
share
We investigate a swarm of autonomous mobile robots in the Euclidean plane. A robot has a function called target function to determine the destination point from the robots' positions. All robots in the swarm conventionally take the same target function, but there is apparent limitation in problem-solving ability. We allow the robots to take different target functions. The number of different target functions necessary and sufficient to solve a problem Π is called the minimum algorithm size (MAS) for Π. We establish the MASs for solving the gathering and related problems from any initial configuration, i.e., in a self-stabilizing manner. We show, for example, for 1 ≤ c ≤ n, there is a problem Π_c such that the MAS for the Π_c is c, where n is the size of swarm. The MAS for the gathering problem is 2, and the MAS for the fault tolerant gathering problem is 3, when 1 ≤ f (< n) robots may crash, but the MAS for the problem of gathering all robot (including faulty ones) at a point is not solvable (even if all robots have distinct target functions), as long as a robot may crash.
READ FULL TEXT