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

Authors

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

Keywords:

Asynchronous algorithm, autonomous mobile robot, distributed algorithm, connected network, oblivious algorithm, grid

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.

Downloads

Download data is not yet available.

Downloads

Published

2012-07-18

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