Advertisement
Published in:
2010 | OriginalPaper | Chapter
Probabilistic Network Formation through Coverage and Freeze-Tag
Authors : Eric Meisner, Wei Yang, Volkan Isler
Published in: Algorithmic Foundation of Robotics VIII
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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.