Abstract
Consider a set of n > 2 simple autonomous mobile robots (decentralized, asynchronous, no common coordinate system, no identities, no central coordination, no direct communication, no memory of the past, deterministic) moving freely in the plane and able to sense the positions of the other robots. We study the primitive task of gathering them at a point not fixed in advance (Gathering Problem). In the literature, most contributions are simulation-validated heuristics. The existing algorithmic contributions for such robots are limited to solutions for n ≤ 4 or for restricted sets of initial configurations of the robots. In this paper, we present the first algorithm that solves the Gathering Problem for any initial configuration of the robots.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Anderegg, M. Cieliebak, and G. Prencipe. A Linear Time Algorithm to Identify Equiangular and Biangular Point Configurations. Technical Report TR-03-01, Università di Pisa, 2003.
H. Ando, Y. Oasa, I. Suzuki, and M. Yamashita. A Distributed Memoryless Point Convergence Algorithm for Mobile Robots with Limited Visibility. IEEE Transaction on Robotics and Automation, 15(5):818–828, 1999.
C. Bajaj. The Algebraic Degree of Geometric Optimization Problems. Discrete and Computational Geometry, 3:177–191, 1988.
T. Balch and R. C. Arkin. Behavior-based Formation Control for Multi-robot Teams. IEEE Transaction on Robotics and Automation, 14(6), 1998.
M. Cieliebak and G. Prencipe. Gathering Autonomous Mobile Robots. In SIROCCO 9, pages 57–72, 2002.
E. J. Cockayne and Z. A. Melzak. Euclidean Constructibility in Graph-minimization Problems. Mathematical Magazine, 42:206–208, 1969.
P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots. In ISAAC’ 99, volume 1741 of LNCS, pages 93–102, 1999.
P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of Autonomous Mobile Robots With Limited Visibility. In STACS 2001, volume 2010 of LNCS, pages 247–258, 2001.
D. Jung, G. Cheng, and A. Zelinsky. Experiments in Realising Cooperation between Autonomous Mobile Robots. In ISER, 1997.
Y. Kupitz and H. Martini. Geometric Aspects of the Generalized Fermat-Torricelli Problem. Intuitive Geometry, 6:55–127, 1997.
M. J. Matarić. Designing Emergent Behaviors: From Local Interactions to Collective Intelligence. In From Animals to Animats 2: Int. Conf. on Simulation of Adaptive Behavior, pages 423–441, 1993.
G. Prencipe. CORDA: Distributed Coordination of a Set of Autonomous Mobile Robots. In ERSADS 2001, pages 185–190, 2001.
G. Prencipe. Instantaneous Actions vs. Full Asynchronicity: Controlling and Coordinating a Set of Autonomous Mobile Robots. In ICTCS 2001, pages 185–190, 2001.
I. Suzuki and M. Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. Siam Journal of Computing, 28(4):1347–1363, 1999.
E. Weiszfeld. Sur le Point Pour Lequel la Somme Des Distances de n Points Donnés Est Minimum. Tohoku Mathematical, 43:355–386, 1936.
E. Welzl. Smallest Enclosing Disks (Balls and Ellipsoids). In H. Maurer, editor, New Results and New Trends in Computer Science, LNCS, pages 359–370. Springer, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N. (2003). Solving the Robots Gathering Problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds) Automata, Languages and Programming. ICALP 2003. Lecture Notes in Computer Science, vol 2719. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45061-0_90
Download citation
DOI: https://doi.org/10.1007/3-540-45061-0_90
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-40493-4
Online ISBN: 978-3-540-45061-0
eBook Packages: Springer Book Archive