A Point Set Connection Problem for Autonomous Mobile Robots in a Grid

keywords: Asynchronous algorithm, autonomous mobile robot, distributed algorithm, connected network, oblivious algorithm, grid
Consider an orthogonal grid of streets and avenues in a Manhattan-like city populated by stationary sensor modules at some intersections and mobile robots that can serve as relays of information that the modules exchange, where both module-module and module-robot communication is limited to a straight line of sight within the grid. The robots are oblivious and move asynchronously. We present a distributed algorithm that, given the sensor locations as input, moves the robots to suitable locations in the grid so that a connected network of all modules is established. The number of robots that the algorithm uses is worst case optimal.
mathematics subject classification 2000: 68W15, 68M14, 68R01
reference: Vol. 31, 2012, No. 2, pp. 349–369