Suppose you have a set of mobile robots that move on a ring or on a line segment at constant speed, bouncing when they run into another robot. The robots have no communication, no sensors, and no control of their motions, but they know when they bounce. The robots also know the perimeter of the ring or the length of the segment, have a clock, and can store the time when they bounce. All the clocks are synchronized. The questions are: Can each robot figure out how many other robots move in the same ring or segment? What are their initial positions and directions? Of course, the problem is an abstraction of a real robotics problem. It ignores friction, errors in the robot motions, and variations in their velocity, and assumes perfectly synchronized clocks, a perfect world, and perfect robots. It is also limited to one-dimensional motions, either along the ring or the segment.
The paper analyzes when the problem is unsolvable and proposes optimal position detection algorithms for all feasible configurations. Feasible configurations in the ring require that not all of the robots move initially in the same direction. For a segment, the initial configurations have to be nonsymmetric. It is not obvious there are any real applications for the algorithms proposed, at least not for real robots, but the problem is interesting. The robots are like moving particles that cannot control their own motion, yet with a clock and memory they can infer information about their environment from their bounces. For readers interested in this line of research, the authors of this paper have additional papers on this and related problems.