Abstract
In this paper we aim at an understanding of the fundamental algorithmic limitations on what a set of autonomous mobile robots can or cannot achieve. We study a hard task for a set of weak robots. The task is for the robots in the plane to form any arbitrary pattern that is given in advance. The robots are weak in several aspects. They are anonymous; they cannot explicitly communicate with each other, but only observe the positions of the others; they cannot remember the past; they operate in a very strong form of asynchronicity. We show that the tasks that such a system of robots can perform depend strongly on their common knowledge about their environment, i.e., the readings of their environment sensors.
This work has been performed while the first and third authors have been visiting ETH Zürich and while the second and fourth authors have been visiting Carleton University. We also gratefully acknowledge the partial support of the Swiss Natio- nal Science Foundation, the Natural Science and Engineering Research Council of Canada and the Fonds pour la Formation de Chercheurs et l’Aide à la Recherche du Québec.
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
T. Balch and R. C. Arkin. Motor Schema-based Formation Control for Multiagent Robot Teams. ICMAS, pages 10–16, 1995.
E. H. Durfee. Blissful Ignorance: Knowing Just Enough to Coordinate Well. IC-MAS, pages 406–413, 1995.
P. Flocchini, G. Prencipe, N. Santoro, E. Welzl, and P. Widmayer. Point Formation for Oblivious Robots. manuscript, in preparation, 1999.
P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Hard Tasks for Weak Robots. Technical Report TR-99-07, School of Comp. Sc. Carleton Univ., 1999.
M. J. Mataric. Designing Emergent Behaviors: From Local Interactions to Collective Intelligence. From Animals to Animats 2, pages 423–441, 1993.
L. E. Parker. Adaptive Action Selection for Cooperative Agent Teams. Proc. Second Int’l. Conf. on Simulation of Adaptive Behavior, pages 442–450, 1992.
I. Suzuki and M. Yamashita. Formation and Agreement Problems for Anonymous Mobile Robots. Proceedings of the 31st Annual Conference on Communication, Control and Computing, University of Illinois, Urbana, IL, pages 93–102, 1993.
I. Suzuki and M. Yamashita. Distributed Anonymous Mobile Robots-Formation and Agreement Problems. Proc. Third Colloq. on Struc. Information and Communication Complexity (SIROCCO), pages 313–330, 1996.
I. Suzuki and M. Yamashita. Distributed Anonymous Mobile Robots: Formation of Geometric Patterns. Siam J. Comput., 28(4):1347–1363, 1999.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P. (1999). Hard Tasks for Weak Robots: The Role of Common Knowledge in Pattern Formation by Autonomous Mobile Robots. In: Algorithms and Computation. ISAAC 1999. Lecture Notes in Computer Science, vol 1741. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46632-0_10
Download citation
DOI: https://doi.org/10.1007/3-540-46632-0_10
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66916-6
Online ISBN: 978-3-540-46632-1
eBook Packages: Springer Book Archive