Probabilistic Network Formation through Coverage and Freeze-Tag
We address the problem of propagating a piece of information among robots scattered in an environment. Initially, a single robot has the information. This robot searches for other robots to pass it along. When a robot is discovered, it can participate in the process by searching for other robots. Since our motivation for studying this problem is to form an ad-hoc network, we call it the Network Formation Problem. In this paper, we study the case where the environment is a rectangle and the robots' locations are unknown but chosen uniformly at random. We present an efficient network formation algorithm, Stripes, and show that its expected performance is within a logarithmic factor of the optimal performance. We also compare Stripes with an intuitive network formation algorithm in simulations. The feasibility of Stripes is demonstrated with a proof-of-concept implementation.
- E. Meisner, W. Yang, and V. Isler. Network Formation through Coverage and Freeze-Tag. In Eighth International Workshop on the Algorithmic Foundations of Robotics (WAFR), 2008.
The videos below show an implementation of the algorithm presented in the paper above.
For more recent work on a closely related problem, see: Robotic Routers.
|6||O. Tekdas, Y. Kumar, V. Isler, R. Janardan|
Building a Communication Bridge With Mobile Hubs
IEEE Tran. on Automation Science and Engineering, 9(1): 171--176, 2012.
|5||E. Stump, N. Michael, V. Kumar, V. Isler|
Visibility-Based Deployment of Robot Formations for Communication Maintenance.
In Proc. IEEE Int. Conf. on Robotics and Automation, 2011.
|4||O. Tekdas, W. Yang, V. Isler|
Robotic Routers: Algorithms and Implementation
Int. Journal of Robotics Research, 29(1), 2010.
|3||O. Tekdas, Y. Kumar, V. Isler, R. Janardan|
Building a Communication Bridge with Mobile Hubs
In 5th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 2009.
|2||E. Meisner, W. Yang, V. Isler|
Network Formation through Coverage and Freeze-Tag
In Eighth International Workshop on the Algorithmic Foundations of Robotics, 2008.
|1||O. Tekdas, V. Isler|
In Proc. IEEE Int. Conf. on Robotics and Automation, 2008.