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:
Optimal Embedding of Locally Twisted Cubes into Grids Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Optimum Gathering of Asynchronous Robots

Authors : Subhash Bhagat, Krishnendu Mukhopadhyaya

Published in: Algorithms and Discrete Applied Mathematics

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

This paper considers the problem of gathering a set of asynchronous robots on the two dimensional plane under the additional requirement that the maximum distance traversed by the robots should be minimized. One of the implications of this optimization criteria is the energy efficiency for the robots. The results of this paper are two folds. First, it is proved that multiplicity detection capability is not sufficient to solve the constrained gathering problem for a set of oblivious robots even when the robots are fully synchronous. The problem is then studied for the robots having O(1) bits persistent memory and a distributed algorithm is proposed for the problem in this model for a set of \(n\ge 5\) robots. The proposed algorithm uses only two bits of persistent memory.

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 Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function
next chapter Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime
Literature
1.
Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: Proceedings of ACM Symposium on Principles of Distributed Computing (PODC), pp. 250–259 (2013)
2.
Bhagat, S., Chaudhuri, S.G., Mukhopadhyaya, K.: Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discret. Algorithms 36, 50–62 (2016)MathSciNetCrossRefMATH
3.
Bramas, Q., Tixeuil, S.: Wait-free gathering without chirality. In: Scheideler, C. (ed.) Structural Information and Communication Complexity. LNCS, vol. 9439, pp. 313–327. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-25258-2_​22 CrossRef
4.
Chaudhuri, S.G., Mukhopadhyaya, K.: Leader election and gathering for asynchronous fat robots without common chirality. J. Discret. Algorithms 33, 171–192 (2015)MathSciNetCrossRefMATH
5.
Cicerone, S., Di Stefano, G., Navarra, A.: Minmax-distance gathering on given meeting points. In: Paschos, V.T., Widmayer, P. (eds.) CIAC 2015. LNCS, vol. 9079, pp. 127–139. Springer, Heidelberg (2015). doi:10.​1007/​978-3-319-18173-8_​9 CrossRef
6.
Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)MathSciNetCrossRefMATH
7.
8.
Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: The power of lights: synchronizing asynchronous robots using visible bits. In: Proceedings of IEEE 32nd International Conference on Distributed Computing Systems (ICDCS), pp. 506–515 (2012)
9.
Défago, X., Gradinariu, M., Messika, S., Raipin-Parvédy, P.: Fault-tolerant and self-stabilizing mobile robots gathering. In: Dolev, S. (ed.) DISC 2006. LNCS, vol. 4167, pp. 46–60. Springer, Heidelberg (2006). doi:10.​1007/​11864219_​4 CrossRef
10.
Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by oblivious mobile robots. In: Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers (2012)
11.
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1–3), 147–168 (2005)MathSciNetCrossRefMATH
12.
Flocchini, P., Santoro, N., Viglietta, G., Yamashita, M.: Rendezvous of two robots with constant memory. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 189–200. Springer, Heidelberg (2013). doi:10.​1007/​978-3-319-03578-9_​16 CrossRef
13.
Peleg, D.: Distributed coordination algorithms for mobile robot swarms: new directions and challenges. In: Pal, A., Kshemkalyani, A.D., Kumar, R., Gupta, A. (eds.) IWDC 2005. LNCS, vol. 3741, pp. 1–12. Springer, Heidelberg (2005). doi:10.​1007/​11603771_​1 CrossRef
14.
Prencipe, G.: Instantaneous actions vs. full asynchronicity: controlling and coordinating a Sset of autonomous mobile robots. In: Restivo, A., Della Rocca, S.R., Roversi, L. (eds.) ICTCS 2001. LNCS, vol. 2202, pp. 154–171. Springer, Heidelberg (2001). doi:10.​1007/​3-540-45446-2_​10 CrossRef
15.
16.
Suzuki, I., Yamashita, M.: Formation and agreement problems for anonymous mobile robots. In: Proceedings of 31st Annual Conference on Communication, Control and Computing, pp. 93–102 (1993)
17.
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)MathSciNetCrossRefMATH
18.
Viglietta, G.: Rendezvous of two robots with visible bits. In: Flocchini, P., Gao, J., Kranakis, E., Meyer auf der Heide, F. (eds.) ALGOSENSORS 2013. LNCS, vol. 8243, pp. 291–306. Springer, Heidelberg (2014). doi:10.​1007/​978-3-642-45346-5_​21 CrossRef
Metadata
Title
Optimum Gathering of Asynchronous Robots
Authors
Subhash Bhagat
Krishnendu Mukhopadhyaya
Copyright Year
2017
Book
Algorithms and Discrete Applied Mathematics

Print ISBN: 978-3-319-53006-2

Electronic ISBN: 978-3-319-53007-9

Copyright Year: 2017

DOI
https://doi.org/10.1007/978-3-319-53007-9_4

Premium Partner

    Image Credits