Abstract

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.

Keywords

MSC

68W15, 68M14, 68R01

Cite this article

@article{cai-18110-2011-1,
  author  = {Adrian Kosowski and Ichiro Suzuki and Paweł Zylinski},
  title   = {A Point Set Connection Problem for Autonomous Mobile Robots in a Grid},
  journal = {Computing and Informatics},
  volume  = {30},
  number  = {1},
  pages   = {137--153},
  year    = {2011},
  issn    = {1335-9150},
  url     = {https://cai.type.sk/content/2011/1/a-point-set-connection-problem-for-autonomous-mobile-robots-in-a-grid/}
}
Download .bib