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


  • Adrian Kosowski Department of Algorithms and Systen Modeling
  • Ichiro Suzuki Department of Electronic Engineering and Computer Science
  • Paweł Źyliński Institute of Informatics


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.


Download data is not yet available.




How to Cite

Kosowski, A., Suzuki, I., & Źyliński, P. (2012). A Point Set Connection Problem for Autonomous Mobile Robots in a Grid. COMPUTING AND INFORMATICS, 31(2), 349–369. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/944