Probabilistic network Formation through coverage and freeze-tag

Eric Meisner, Wei Yang, Volkan Isler

Research output: Contribution to journalArticlepeer-review

2 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)265-273
Number of pages9
JournalIntelligent Service Robotics
Issue number4
StatePublished - Oct 1 2009


  • Distributed artificial intelligence
  • Formation
  • Generation
  • Multiagent systems
  • Plan execution

Fingerprint Dive into the research topics of 'Probabilistic network Formation through coverage and freeze-tag'. Together they form a unique fingerprint.

Cite this