Local Algorithms for Autonomous Robot Systems

  • Reuven Cohen
  • David Peleg
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 4056)


This paper studies local algorithms for autonomous robot systems, namely, algorithms that use only information of the positions of a bounded number of their nearest neighbors. The paper focuses on the spreading problem. It defines measures for the quality of spreading, presents a local algorithm for the one-dimensional spreading problem, prove its convergence to the equally spaced configuration and discusses its convergence rate in the synchronous and semi-synchronous settings. It then presents a local algorithm achieving the exact equally spaced configuration in finite time in the synchronous setting, and proves it is time optimal for local algorithms. Finally, the paper also proposes an algorithm for the two-dimensional case and presents simulation results of its effectiveness.


Mobile Robot Discrete Fourier Transform Local Algorithm Voronoi Cell Global Coordinate System 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.


Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.


  1. 1.
    Akansu, A.N., Haddad, R.A.: Multiresolution Signal Decomposition. Academic Press, San Diego (1992)zbMATHGoogle Scholar
  2. 2.
    Ando, H., Suzuki, I., Yamashita, M.: Formation and agreement problems for synchronous mobile robots with limited visibility. In: Proc. IEEE Symp. of Intelligent Control, pp. 453–460 (August 1995)Google Scholar
  3. 3.
    Balch, T., Arkin, R.: Behavior-based formation control for multi-robot teams. IEEE Trans. on Robotics and Automation 14 (December 1998)Google Scholar
  4. 4.
    Beni, G., Hackwood, S.: Coherent swarm motion under distributed control. In: Proc. DARS 1992, pp. 39–52 (1992)Google Scholar
  5. 5.
    Cao, Y.U., Fukunaga, A.S., Kahng, A.B.: Cooperative mobile robotics: Antecedents and directions. Autonomous Robots 4(1), 7–23 (1997)CrossRefGoogle Scholar
  6. 6.
    Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Proc. 30th Int. Colloq. on Automata, Languages and Programming, pp. 1181–1196 (2003)Google Scholar
  7. 7.
    Defago, X., Konagaya, A.: Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In: Proc. 2nd ACM Workshop on Principles of Mobile Computing, pp. 97–104. ACM Press, New York (2002)CrossRefGoogle Scholar
  8. 8.
    Dijkstra, E.W.: Selected Writings on Computing: A Personal Perspective, pp. 34–35. Springer, New York (1982)zbMATHGoogle Scholar
  9. 9.
    Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In: Proc. 10th Int. Symp. on Algorithms and Computation, pp. 93–102 (1999)Google Scholar
  10. 10.
    Gordon, N., Wagner, I.A., Bruckstein, A.M.: Gathering multiple robotic a(ge)nts with limited sensing capabilities. In: Proc. 4th Int. Workshop on Ant Colony Optimization and Swarm Intelligence, pp. 142–153 (September 2004)Google Scholar
  11. 11.
    Jung, D., Cheng, G., Zelinsky, A.: Experiments in realising cooperation between autonomous mobile robots. In: Proc. Int. Symp. on Experimental Robotics (1997)Google Scholar
  12. 12.
    Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete euclidean graph. Discrete computational Geometry 7, 13–28 (1992)zbMATHCrossRefMathSciNetGoogle Scholar
  13. 13.
    Mataric, M.J.: Interaction and Intelligent Behavior. PhD thesis, MIT (1994)Google Scholar
  14. 14.
    Parker, L.E.: Designing control laws for cooperative agent teams. In: Proc. IEEE Conf. on Robotics and Automation, pp. 582–587 (1993)Google Scholar
  15. 15.
    Parker, L.E.: On the design of behavior-based multi-robot teams. J. of Advanced Robotics 10 (1996)Google Scholar
  16. 16.
    Parker, L.E., Touzet, C., Fernandez, F.: Techniques for learning in multi-robot teams. In: Balch, T., Parker, L.E. (eds.) Robot Teams: From Diversity to Polymorphism. A.K. Peters (2001)Google Scholar
  17. 17.
    Prencipe, G.: CORDA: Distributed coordination of a set of atonomous mobile robots. In: Proc. 4th European Research Seminar on Advances in Distributed Systems, pp. 185–190 (May 2001)Google Scholar
  18. 18.
    Prencipe, G.: Distributed Coordination of a Set of Atonomous Mobile Robots. PhD thesis, Universita Degli Studi Di Pisa (2002)Google Scholar
  19. 19.
    Sugihara, K., Suzuki, I.: Distributed algorithms for formation of geometric patterns with many mobile robots. J. of Robotic Systems 13(3), 127–139 (1996)zbMATHCrossRefGoogle Scholar
  20. 20.
    Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. on Computing 28, 1347–1363 (1999)zbMATHCrossRefMathSciNetGoogle Scholar
  21. 21.
    Wagner, I.A., Bruckstein, A.M.: From ants to a(ge)nts. Annals of Mathematics and Artificial Intelligence 31, 1–5 (1996), special issue on ant-roboticsGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2006

Authors and Affiliations

  • Reuven Cohen
    • 1
  • David Peleg
    • 2
  1. 1.Dept. of Electrical and Computer Eng.Boston UniversityBostonUSA
  2. 2.Dept. of Computer ScienceWeizmann InstituteRehovotIsrael

Personalised recommendations