Self-stabilizing robot formations over unreliable networks

ABSTRACT

We describe how a set of mobile robots can arrange themselves on any specified curve on the plane in the presence of dynamic changes both in the underlying ad hoc network and in the set of participating robots. Our strategy is for the mobile robots to implement a self-stabilizing virtual layer consisting of mobile client nodes, stationary Virtual Nodes (VNs), and local broadcast communication. The VNs are associated with predetermined regions in the plane and coordinate among themselves to distribute the client nodes relatively uniformly among the VNs' regions. Each VN directs its local client nodes to align themselves on the local portion of the target curve. The resulting motion coordination protocol is self-stabilizing, in that each robot can begin the execution in any arbitrary state and at any arbitrary location in the plane. In addition, self-stabilization ensures that the robots can adapt to changes in the desired target formation.

REFERENCES

• 1: Ando, H., Oasa, Y., Suzuki, I., and Yamashita, M. 1999. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robotics Autom. 15, 5, 818--828.
• 2: Blondel, V., Hendrickx, J., Olshevsky, A., and Tsitsiklis, J. 2005. Convergence in multi-agent coordination consensus and flocking. In Proceedings of the Joint 44th IEEE Conference on Decision and Control and European Control Conference. 2996--3000.
• 3: Brown, M. D. 2007. Air traffic control using virtual stationary automata. M.S. thesis, Massachusetts Institute of Technology.
• 4: K. Mani Chandy , Sayan Mitra , Concetta Pilotto, Convergence Verification: From Shared Memory to Partially Synchronous Systems, Proceedings of the 6th international conference on Formal Modeling and Analysis of Timed Systems, September 15-17, 2008, Saint Malo, France [doi>10.1007/978-3-540-85778-5_16]
• 5: Gregory Chockler , Seth Gilbert , Nancy Lynch, Virtual infrastructure for collision-prone wireless networks, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, August 18-21, 2008, Toronto, Canada [doi>10.1145/1400751.1400783]
• 6: Clavaski, S., Chaves, M., Day, R., Nag, P., Williams, A., and Zhang, W. 2003. Vehicle networks: Achieving regular formation. In Proceedings of the American Control Conference.
• 7: Cortes, J., Martinez, S., Karatas, T., and Bullo, F. 2004. Coverage control for mobile sensing networks. IEEE Trans. Robotics Autom. 20, 2, 243--255.
• 8: Xavier Défago , Akihiko Konagaya, Circle formation for oblivious anonymous mobile robots with no common sense of orientation, Proceedings of the second ACM international workshop on Principles of mobile computing, October 30-31, 2002, Toulouse, France [doi>10.1145/584490.584509]
• 9: Xavier Défago , Samia Souissi, Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity, Theoretical Computer Science, v.396 n.1-3, p.97-112, May, 2008 [doi>10.1016/j.tcs.2008.01.050]
• 10: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 11: Shlomi Dolev , Limor Lahiani , Seth Gilbert , Nancy Lynch , Tina Nolte, Brief announcement: virtual stationary automata for mobile networks, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073876]
• 12: Dolev, S., Gilbert, S., Lahiani, L., Lynch, N. A., and Nolte, T. A. 2005b. Virtual stationary automata for mobile networks. Tech. rep. MIT-LCS-TR-979.
• 13: Dolev, S., Gilbert, S., Lynch, N., Shvartsman, A., and Welch, J. 2003. Geoquorums: Implementing atomic memory in ad hoc networks. In Distributed Algorithms, F. E. Fich, Ed. Lecture Notes in Computer Science, vol. 2848. 306--320.
• 14: Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Elad Schiller , Alex A. Shvartsman , Jennifer Welch, Brief announcement: virtual mobile nodes for mobile ad hoc networks, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011845]
• 15: Shlomi Dolev , Seth Gilbert , Nancy A. Lynch , Alexander A. Shvartsman , Jennifer L. Welch, GeoQuorums: implementing atomic memory in mobile ad hoc networks, Distributed Computing, v.18 n.2, p.125-155, December 2005 [doi>10.1007/s00446-005-0140-9]
• 16: Asaf Efrima , David Peleg, Distributed Models and Algorithms for Mobile Robot Systems, Proceedings of the 33rd conference on Current Trends in Theory and Practice of Computer Science, January 20-26, 2007, Harrachov, Czech Republic [doi>10.1007/978-3-540-69507-3_5]
• 17: Fax, J. and Murray, R. 2004. Information flow and cooperative control of vehicle formations. IEEE Trans. Autom. Control 49, 1465--1476.
• 18: Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 2001. Pattern formation by autonomous robots without chirality. In Proceedings of the Colloquium on Structural Information and Communication Complexity (SIROCCO). 147--162.
• 19: Gazi, V. and Passino, K. M. 2003. Stability analysis of swarms. IEEE Trans. Autom. Control 48, 4, 692--697.
• 20: David Kiyoshi Goldenberg , Jie Lin , A. Stephen Morse , Brad E. Rosen , Y. Richard Yang, Towards mobility as a network control primitive, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989481]
• 21: Herman, T. 1996. Self-stabilization bibliography: Access guide. Theoretical Comput. Sci.
• 22: Jadbabaie, A., Lin, J., and Morse, A. S. 2003. Coordination of groups of mobile autonomous agents using nearest neighbor rules. IEEE Trans. Autom. Control 48, 6, 988--1001.
• 23: Dilsun K. Kaynar , Nancy Lynch , Roberto Segala , Frits Vaandrager, The Theory of Timed I/O Automata (Synthesis Lectures in Computer Science), Morgan & Claypool Publishers, 2006
• 24: Lin, J., Morse, A., and Anderson., B. 2003. Multi-agent rendezvous problem. In Proceedings of the 42nd IEEE Conference on Decision and Control.
• 25: Lynch, N., Mitra, S., and Nolte, T. 2005. Motion coordination using virtual nodes. In Proceedings of the 44th IEEE Conference on Decision and Control (CDC'05).
• 26: Martinez, S., Cortes, J., and Bullo, F. 2005. On robust rendezvous for mobile autonomous agents. In Proceedings of the IFAC World Congress.
• 27: Nolte, T. and Lynch, N. A. 2007a. Self-stabilization and virtual node layer emulations. In Proceedings of the International Symposium on Self-Stablizing Systems (SSS). 394--408.
• 28: Tina Nolte , Nancy Lynch, A Virtual Node-Based Tracking Algorithm for Mobile Networks, Proceedings of the 27th International Conference on Distributed Computing Systems, p.1, June 25-27, 2007 [doi>10.1109/ICDCS.2007.82]
• 29: Nolte, T. A. 2008. Virtual stationary timed automata for mobile networks. Ph.D. thesis, Massachusetts Institute of Technology, Cambridge.
• 30: Olfati-Saber, R., Fax, J., and Murray, R. 2007. Consensus and cooperation in networked multi-agent systems. Proc. IEEE 95, 1, 215--233.
• 31: Prencipe, G. 2000. Achievable patterns by an even number of autonomous mobile robots. Tech. rep. TR-00-11. 17.
• 32: Prencipe, G. 2001. Corda: Distributed coordination of a set of autonomous mobile robots. In Proceedings of the European Research Seminar on Advances in Distributed Systems (ERSADS). 185--190.
• 33: Ichiro Suzuki , Masafumi Yamashita, Distributed Anonymous Mobile Robots: Formation of Geometric Patterns, SIAM Journal on Computing, v.28 n.4, p.1347-1363, Aug. 1999 [doi>10.1137/S009753979628292X]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Interactive and reactive computation

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Distributed systems

General Terms:
Algorithms, Reliability

Keywords:
Formal methods, cooperative mobile robotics, distributed algorithms, pattern formation, replicated state machines, self-stabilization