Circle formation for oblivious anonymous mobile robots with no common sense of orientation

ABSTRACT

This paper proposes a distributed algorithm by which a collection of mobile robots roaming on a plane move to form a circle. The algorithm operates under the premises that robots (1) are unable to recall past actions and observations (i.e., oblivious), (2) cannot be distinguished from each others (i.e., anonymous), (3) share no common sense of direction, and (4) are unable to communicate in any other ways than by observing each others position.

REFERENCES

• 1: H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. on Robotics and Automation, 15(5):818--828, Oct. 1999.
• 2: Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
• 3: I. Chatzigiannakis, S. Nikoletseas, and P. Spirakis. On the average and worst-case efficiency of some new distributed communication and control algorithms for ad-hoc mobile networks. In Proc. 1st ACM Int'l Workshop on Principles of Mobile Computing (POMC'01), pages 1--19, Newport, RI, USA, Aug. 2001.
• 4: Diane Crawford, Technical correspondence, Communications of the ACM, v.38 n.2, p.115-120, Feb. 1995 [doi>10.1145/204826.1037835]
• 5: X. Défago. Distributed computing on the move: From mobile computing to cooperative robotics and nanorobotics (a position paper). In Proc. 1st ACM Int'l Workshop on Principles of Mobile Computing (POMC'01), pages 49--55, Newport, RI, USA, Aug. 2001.
• 6: M. B. Dias and A. Stentz. A free market architecture for distributed control of a multirobot system. In Proc. 6th Int'l Conf. on Intelligent Autonomous Systems (IAS-6), pages 115--122, Venice, Italy, July 2000.
• 7: Shlomi Dolev, Self-stabilization, MIT Press, Cambridge, MA, 2000
• 8: Paola Flocchini , Giuseppe Prencipe , Nicola Santoro , Peter Widmayer, Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots, Proceedings of the 10th International Symposium on Algorithms and Computation, p.93-102, December 16-18, 1999
• 9: Paola Flocchini , Giuseppe Prencipe , Nicola Santoro , Peter Widmayer, Gathering of Asynchronous Oblivious Robots with Limited Visibility, Proceedings of the 18th Annual Symposium on Theoretical Aspects of Computer Science, p.247-258, February 15-17, 2001
• 10: and G Vincenzo Gervasi, Flocking by a Set of Autonomous Mobile Robots, University of Pisa, 2001
• 11: M. J. B. Krieger, J.-B. Billeter, and L. Keller. Ant-like task allocation and recruitment in cooperative robots. Nature, 406(6799):992--995, Aug. 2000.
• 12: Sven Skyum, A simple algorithm for computing the smallest enclosing circle, Information Processing Letters, v.37 n.3, p.121-125, Feb. 18, 1991 [doi>10.1016/0020-0190(91)90030-L]
• 13: K. Sugihara and I. Suzuki. Distributed algorithms for formation of geometric patterns with many mobile robots. Journal on Robotics Systems, 3(13):127--139, Mar. 1996.
• 14: Ichiro Suzuki , Masafumi Yamashita, Agreement on a Common X - Y Coordinate System by a Group of Mobile Robots, Intelligent Robots: Sensing, Modeling and Planning [Dagstuhl Workshop, September 1-6, 1996], p.305-321, September 01-06, 1996
• 15: 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]
• 16: Y. Uny Cao , Alex S. Fukunaga , Andrew Kahng, Cooperative Mobile Robotics: Antecedents and Directions, Autonomous Robots, v.4 n.1, p.7-27, March 1997 [doi>10.1023/A:1008855018923]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency; Interactive and reactive computation

  J. Computer Applications
  J.7 COMPUTERS IN OTHER SYSTEMS

General Terms:
Algorithms, Theory

Keywords:
anonymous computations, circle formation, computational geometry, cooperative mobile robotics, distributed algorithms, geometric pattern formation, oblivious computations, self-stabilization