Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Hand Biometric Verification with Hand Image-Based CAPTCHA Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Optimum Circle Formation by Autonomous Robots

Authors : Subhash Bhagat, Krishnendu Mukhopadhyaya

Published in: Advanced Computing and Systems for Security

Publisher: Springer Singapore

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Automatic Extraction and Identification of Bol from Tabla Signal
next chapter Genre Fraction Detection of a Movie Using Text Mining
Literature
1.
Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Santa Clara, USA (2008). TELOS
2.
Chaudhuri, G.S., Mukhopadhyaya, K.: Leader election and gathering for asynchronous fat robots without common chirality. J. Discrete Algorithms 33, 171–192 (2015)
3.
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)
4.
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)
5.
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)
6.
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)
7.
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)CrossRef
8.
Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2012)CrossRef
9.
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)
10.
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)CrossRef
11.
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)
12.
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)
13.
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)
14.
Sugihara, K., Suzuki, I.: Distributed motion coordination of multiple mobile robots. In: Proceedings of IEEE International Symposium on Intelligent Control, pp. 138–143 (1990)
15.
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)
16.
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)MathSciNetCrossRef
Metadata
Title
Optimum Circle Formation by Autonomous Robots
Authors
Subhash Bhagat
Krishnendu Mukhopadhyaya
Copyright Year
2018
Publisher
Springer Singapore
Book
Advanced Computing and Systems for Security

Print ISBN: 978-981-10-8179-8

Electronic ISBN: 978-981-10-8180-4

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-981-10-8180-4_10

Premium Partner

    Image Credits