View source

== 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. [http://www.cs.umn.edu/~isler/pub/wafr08.pdf 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.

{{#ev:youtube|YbAF7gQL4_I}}

{{#ev:youtube|OvRSxsiiDh0}}