Skip to main content

2018 | OriginalPaper | Buchkapitel

Optimum Circle Formation by Autonomous Robots

verfasst von : Subhash Bhagat, Krishnendu Mukhopadhyaya

Erschienen in: Advanced Computing and Systems for Security

Verlag: Springer Singapore

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

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!

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!

Literatur
1.
Zurück zum Zitat Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Santa Clara, USA (2008). TELOS Berg, M., Cheong, O., Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Santa Clara, USA (2008). TELOS
2.
Zurück zum Zitat Chaudhuri, G.S., Mukhopadhyaya, K.: Leader election and gathering for asynchronous fat robots without common chirality. J. Discrete Algorithms 33, 171–192 (2015) Chaudhuri, G.S., Mukhopadhyaya, K.: Leader election and gathering for asynchronous fat robots without common chirality. J. Discrete Algorithms 33, 171–192 (2015)
3.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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., 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2012)CrossRef Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2012)CrossRef
9.
Zurück zum Zitat 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., 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.
Zurück zum Zitat 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 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat 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) 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.
Zurück zum Zitat Sugihara, K., Suzuki, I.: Distributed motion coordination of multiple mobile robots. In: Proceedings of IEEE International Symposium on Intelligent Control, pp. 138–143 (1990) 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.
Zurück zum Zitat 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.: Formation and agreement problems for anonymous mobile robots. In: Proceeding of 31st Annual Conference on Communication, Control and Computing, pp. 93–102 (1993)
16.
Zurück zum Zitat Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)MathSciNetCrossRef Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)MathSciNetCrossRef
Metadaten
Titel
Optimum Circle Formation by Autonomous Robots
verfasst von
Subhash Bhagat
Krishnendu Mukhopadhyaya
Copyright-Jahr
2018
Verlag
Springer Singapore
DOI
https://doi.org/10.1007/978-981-10-8180-4_10