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.
Publié le : 2012-07-18
Classification:  Asynchronous algorithm; autonomous mobile robot; distributed algorithm; connected network; oblivious algorithm; grid
@article{cai944,
     author = {Adrian Kosowski; Department of Algorithms and Systen Modeling and Ichiro Suzuki; Department of Electronic Engineering and Computer Science and Pawe\l\ \'Zyli\'nski; Institute of Informatics},
     title = {A Point Set Connection Problem for Autonomous Mobile Robots in a Grid},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai944}
}
Adrian Kosowski; Department of Algorithms and Systen Modeling; Ichiro Suzuki; Department of Electronic Engineering and Computer Science; Paweł Źyliński; Institute of Informatics. A Point Set Connection Problem for Autonomous Mobile Robots in a Grid. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai944/