Abstract
Consider a community of simple autonomous robots freely moving in the plane. The robots are decentralized, asynchronous, deterministic without the common coordination system, identities, direct communication, memory of the past, but with the ability to sense the positions of the other robots. This paper presents a distributed algorithm for the convergence problem with limited visibility in 1-bounded asynchrony. The presented algorithm also solves the convergence problem with unlimited visibility in full asynchrony without the need for the multiplicity detection.
Supported in part by VEGA 1/0671/11.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
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.
References
Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the gathering problem. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 1181–1196. Springer, Heidelberg (2003)
Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34(6), 1516–1528 (2005)
Cohen, R., Peleg, D.: Local algorithms for autonomous robot systems. In: Flocchini, P., Gąsieniec, L. (eds.) SIROCCO 2006. LNCS, vol. 4056, pp. 29–43. Springer, Heidelberg (2006)
Dieudonne, Y., Petit, F.: Swing words to make circle formation quiescent. In: Prencipe, G., Zaks, S. (eds.) SIROCCO 2007. LNCS, vol. 4474, pp. 166–179. Springer, Heidelberg (2007)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous mobile robots with limited visibility. In: Ferreira, A., Reichel, H. (eds.) STACS 2001. LNCS, vol. 2010, pp. 247–258. Springer, Heidelberg (2001)
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407, 412–447 (2008)
Katreniak, B., Katreniaková, J.: On the inability of gathering by asynchronous mobile robots with initial movements. In: ECAI 2006, pp. 255–259. IOS Press, Amsterdam (2006)
Katreniak, B.: Biangular circle formation by asynchronous mobile robots. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 185–199. Springer, Heidelberg (2005)
Katreniak, B.: Convergence with Limited Visibility by Asynchronous Mobile Robots (2011), http://www.archive.org/details/Sirocco2011Katreniak
Prencipe, G.: On the feasibility of gathering by autonomous mobile robots. In: Pelc, A., Raynal, M. (eds.) SIROCCO 2005. LNCS, vol. 3499, pp. 246–261. Springer, Heidelberg (2005)
Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Transactions on Robotics and Automation 28(4), 1347–1363 (1999)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing 28(4), 1347–1363 (1999)
Yang, Y., Souissi, S., Défago, X., Takizawa, M.: Fault-tolerant flocking of mobile robots with whole formation rotation. In: The IEEE 23rd International Conference on Advanced Information Networking and Applications, AINA 2009, Bradford, United Kingdom, pp. 830–837. IEEE Computer Society, Los Alamitos (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Katreniak, B. (2011). Convergence with Limited Visibility by Asynchronous Mobile Robots. In: Kosowski, A., Yamashita, M. (eds) Structural Information and Communication Complexity. SIROCCO 2011. Lecture Notes in Computer Science, vol 6796. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22212-2_12
Download citation
DOI: https://doi.org/10.1007/978-3-642-22212-2_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22211-5
Online ISBN: 978-3-642-22212-2
eBook Packages: Computer ScienceComputer Science (R0)