Achieving connectivity through coalescence in mobile robot networks

ABSTRACT

Coalescence is the problem of isolated mobile robots independently searching for peers with the goal of forming a single connected network. This paper analyzes coalescence time for a worst-case scenario where the robots do not have any knowledge about the environment or positions of other robots and perform independent, memoryless search. Using the random direction mobility model, we show that coalescence time has an exponential distribution which is a function of the number of robots, speed, communication range, and size of the domain. Further, as the number of robots (N) increases, coalescence time decreases as O(1/√N) and Ω(log(N)/N). Simulations validate our analysis and also suggest that the lower bound is tight. This paper is an extension of [1] where we studied a simplified setting with a stationary base station that the robots search for and coalesce to.

REFERENCES

• 1: Sameera Poduri and Gaurav S. Sukhatme, "Latency analysis of coalescence in robot groups," in IEEE International Conference on Robotics and Automation, 2007, pp. 3295--3300.
• 2: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]
• 3: A. Muhammad and M. Egerstedt, "On the structural complexity of multi-agent robot formations," in American Control Conference, 2004, pp. 4957--4962.
• 4: H. Ando, T. Oasa, J. Suzuki, and M. Yamashita, "Distributed memoryless point convergence algorithm for mobile robots with limited visibility," IEEE Transactions on Robotics and Automation, pp. 818--828, Oct. 1999.
• 5: J. Lin, A. S. Morse, and B. D. O. Anderson, "The multi-agent rendezvous problem," in International Conference on Decision and Control, 2003, pp. 1508--1513.
• 6: J. Cortes, S. Martinez, and F. Bullo, "Robust rendezvous for mobile autonomous agents via proximity graphs in d dimensions," IEEE Transactions on Automatic Control, in submission.
• 7: Nicholas Roy , Gregory Dudek, Collaborative Robot Exploration and Rendezvous: Algorithms, Performance Bounds and Observations, Autonomous Robots, v.11 n.2, p.117-136, September 2001 [doi>10.1023/A:1011219024159]
• 8: M. M. Zavlanos and G. J. Pappas, "Controlling connectivity of dynamic graphs," in International Conference on Decision and Control, 2005, pp. 6388--6393.
• 9: D. Spanos and R. M. Murray, "Robust connectivity of networked vehicles," in International Conference on Decision and Control, 2004, pp. 2893--2898.
• 10: M. Porfiri, D. J. Stilwell, E. M. Bollt, and J. D. Skufca, "Random talk: Random walk and synchronizability in a moving neighborhood network," in Physica D (in press).
• 11: Benyuan Liu , Peter Brass , Olivier Dousse , Philippe Nain , Don Towsley, Mobility improves coverage of sensor networks, Proceedings of the 6th ACM international symposium on Mobile ad hoc networking and computing, May 25-27, 2005, Urbana-Champaign, IL, USA [doi>10.1145/1062689.1062728]
• 12: P. Dykiel, "Asymptotic properties of coalescing random walks," Tech. Rep. 2005:15, Uppasala University, Dec 2005.
• 13: David Aldous and James Allen Fill, "Reversible markov chains and random walks on graphs,".
• 14: Christian Bettstetter, Mobility modeling in wireless networks: categorization, smooth movement, and border effects, ACM SIGMOBILE Mobile Computing and Communications Review, v.5 n.3, p.55-66, July 2001 [doi>10.1145/584051.584056]
• 15: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Performance analysis of mobility-assisted routing, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132912]