Abstract
This paper considers a constrained version of the circle formation problem for a set of asynchronous, autonomous robots on the Euclidean plane. The circle formation problem asks a set of autonomous, mobile robots, initially having distinct locations, to place themselves, within finite time, at distinct locations on the circumference of a circle (not defined a priori), without colliding with each other. The constrained circle formation problem demands that in addition the maximum distance moved by any robot to solve the problem should be minimized. A basic objective of the optimization constrain is that it implies energy savings of the robots. This paper presents results in two parts. First, it is shown that the constrained circle formation problem is not solvable for oblivious asynchronous robots under ASYNC model even if the robots have rigid movements. Then the problem is studied for robots which have O(1) bits of persistent memory. The initial robot configurations, for which the problem is not solvable in this model, are characterized. For other configurations, a distributed algorithm is presented to solve the problem for asynchronous robots. Only one bit of persistent memory is needed in the proposed algorithm.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Santa Clara, USA (2008). TELOS
Chaudhuri, G.S., Mukhopadhyaya, K.: Leader election and gathering for asynchronous fat robots without common chirality. J. Discrete Algorithms 33, 171–192 (2015)
Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: The power of lights: synchronizing asynchronous robots using visible bits. In: IEEE 32nd International Conference on Distributed Computing Systems (ICDCS), pp. 506–515 (2012)
Défago, X., Gradinariu, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Proceeding of 20th International Symposium on Distributed Computing, pp. 46–60 (2006)
Défago, X., Konagaya, A.: Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In: Proceedings of the Second ACM International Workshop on Principles of Mobile Computing, POMC 2002, pp. 97–104. ACM, New York, USA (2002)
Di Luna, G.A., Flocchini, P., Chaudhuri, S.G., Santoro, N., Viglietta, G.: Robots with lights: overcoming obstructed visibility without colliding. In: Proceeding of 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2014), pp. 150–164 (2014)
Dutta, A., Chaudhuri, S.G., Datta, S., Mukhopadhyaya, K.: Circle formation by asynchronous fat robots with limited visibility. In: Proceedings of International Conference on Distributed Computing and Internet Technology (ICDCIT), pp. 83–93 (2012)
Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2012)
Flocchini, P., Prencipe, G., Santoro, N., Viglietta, G.: Distributed computing by mobile robots: solving the uniform circle formation problem. In: The 18th International Conference on Principles of Distributed Systems (OPODIS 2014), pp. 217–232 (2014)
Flocchini, P., Santoro, N., Viglietta, G., Yamashita, M.: Rendezvous of two robots with constant memory. In: Proceeding of International Colloquium on Structural Information and Communication, Complexity, pp. 189–200 (2013)
Mamino, M., Viglietta, G.: Square formation by asynchronous oblivious robots. In: Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), pp. 1–6 (2016)
Peleg, D.: Distributed coordination algorithms for mobile robot swarms: new directions and challenges. In: Distributed Computing—IWDC 2005. Lecture Notes in Computer Science, vol. 3741, pp. 1–12. Springer, Berlin (2005)
Prencipe, G.: Instantaneous actions versus full asynchronicity: controlling and coordinating a set of autonomous mobile robots. In: Proceeding of 7th Italian Conference on Theoretical Computer Science, pp. 154–171 (2001)
Sugihara, K., Suzuki, I.: Distributed motion coordination of multiple mobile robots. In: Proceedings of IEEE International Symposium on Intelligent Control, pp. 138–143 (1990)
Suzuki, I., Yamashita, M.: Formation and agreement problems for anonymous mobile robots. In: Proceeding of 31st Annual Conference on Communication, Control and Computing, pp. 93–102 (1993)
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Singapore Pte Ltd.
About this chapter
Cite this chapter
Bhagat, S., Mukhopadhyaya, K. (2018). Optimum Circle Formation by Autonomous Robots. In: Chaki, R., Cortesi, A., Saeed, K., Chaki, N. (eds) Advanced Computing and Systems for Security. Advances in Intelligent Systems and Computing, vol 666. Springer, Singapore. https://doi.org/10.1007/978-981-10-8180-4_10
Download citation
DOI: https://doi.org/10.1007/978-981-10-8180-4_10
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-10-8179-8
Online ISBN: 978-981-10-8180-4
eBook Packages: EngineeringEngineering (R0)