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:
Leader Election in Rings with Bounded Multiplicity (Short Paper) Read chapter Read first chapter

2016 | OriginalPaper | Chapter

Flocking with Oblivious Robots

Authors : Davide Canepa, Xavier Defago, Taisuke Izumi, Maria Potop-Butucaru

Published in: Stabilization, Safety, and Security of Distributed Systems

Publisher: Springer International Publishing

Log in

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

search-config
loading …

Abstract

We propose a new self-stabilizing flocking algorithm for oblivious robot networks, and prove its correctness. With this algorithm, a flock head emerges from a uniform flock of robots, and the algorithm allows those robots to follow the head, whatever its direction on the plane. Robots are oblivious in that they do not recall the result of their previous computations and do not share a common coordinate system.
The novelty of our approach consists in identifying the sufficient conditions to set on the flock pattern placement and the velocity of the flock-head (rotation, translation or speed), such that the flock head and the flock pattern are both preserved while the flock moves (following the head). Additionally, our system is both self-healing and self-stabilizing. In case the head leaves (e.g., disappears or is damaged) the flock agrees on a new head and follows its trajectory. Also, robots keep no record of their previous computations and we make no assumption on their initial position. The step complexity of our solution is O(n).

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 Probabilistic Asynchronous Arbitrary Pattern Formation (Short Paper)
next chapter Making Local Algorithms Wait-Free: The Case of Ring Coloring
Footnotes
1
The curent work is supported by the ANR project R-DISCOVER that brings together roboticians and computer scientiests.
 
2
A round is a fragment of execution where each robot in the system executes its actions.
 
Literature
1.
Ben-Shahar, O., Dolev, S., Dolgin, A., Michael, S.: Direction election in flocking swarms. Ad Hoc Netw. 12, 250–258 (2014)CrossRef
2.
Canepa, D., Défago, X., Izumi, T., Potop-Butucaru, M.: Emergent velocity agreement in robot networks. CoRR, abs/1105.4082 (2011)
3.
Canepa, D., Potop-Butucaru, M.G.: Stabilizing flocking via leader election in robot networks. In: Masuzawa, T., Tixeuil, S. (eds.) SSS 2007. LNCS, vol. 4838, pp. 52–66. Springer, Heidelberg (2007). doi:10.​1007/​978-3-540-76627-8_​7 CrossRef
4.
Chazelle, B.: The convergence of bird flocking. J. ACM 61(4), 21:1–21:35 (2014)
5.
6.
Dieudonné, Y., Petit, F., Villain, V.: Leader election problem versus pattern formation problem. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 267–281. Springer, Heidelberg (2010)
7.
Dolev, S.: Self-stabilization. MIT Press (2000)
8.
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Pattern formation by anonymous robots without chirality. In: Proceedings of the SIROCCO, pp. 147–162 (2001)
9.
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407(1–3), 412–447 (2008)MathSciNetCrossRefMATH
10.
Gervasi, V., Prencipe, G.: Flocking by a set of autonomous mobile robots. Technical report TR-01-24, Universitat di Pisa (2001)
11.
Gervasi, V., Prencipe, G.: Coordination without communication: the case of the flocking problem. Discrete Appl. Math. 144(3), 324–344 (2004)MathSciNetCrossRefMATH
12.
Gu, D., Wang, Z.: Leader-follower flocking: algorithms and experiments. IEEE Trans. Control Syst. Technol. 17(5), 1211–1219 (2009)CrossRef
13.
Huang, A.Q.J., Farritor, S.M., Goddard, S.: Localization, follow-the-leader control of a heterogeneous group of mobile robots. IEEE ASME Trans. Mechatron. 11, 205–215 (2006)
14.
La, H.M., Sheng, W.: Flocking control of a mobile sensor network to track and observe a moving target. In: Proceedings of the ICRA, pp. 3129–3134, May 2009
15.
La, H.M., Sheng, W.: Flocking control of multiple agents in noisy environments. In: Proceedings of the ICRA, pp. 4964–4969, May 2010
16.
Lee, G., Chong, N.-Y.: Adaptive flocking of robot swarms: algorithms and properties IEICE Trans. 91-B(9), 2848–2855 (2008)
17.
Lindhe, M.: A flocking and obstacle avoidance algorithm for mobile robots. Ph.D. thesis, KTH Stockholm (2004)
18.
19.
Renaud, P., Cervera, E., Martiner, P.: Towards a reliable vision-based mobile robot formation control. IEEE/ASME Trans. Mechatron. 4, 3176–3181 (2004)
20.
Souissi, S., Izumi, T., Wada, K.: Oracle-based flocking of mobile robots in crash-recovery model. In: Guerraoui, R., Petit, F. (eds.) SSS 2009. LNCS, vol. 5873, pp. 683–697. Springer, Heidelberg (2009). doi:10.​1007/​978-3-642-05118-0_​47 CrossRef
21.
Suzuki, I., Yamashita, M.: A theory of distributed anonymous mobile robots formation and agreement problems. Technical report, Wisconsin Univ. Milwaukee Dept. of Electrical Engineering and Computer Science 6 (1994)
22.
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots–formation and agreement problems. In: Proceedings of the 3rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 1996), Siena, Italy, June 1996
23.
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999)MathSciNetCrossRefMATH
24.
Wang, Z., Gu, D.: A local sensor based leader-follower flocking system. In: Proceedings of the ICRA, pp. 3790–3795, May 2008
25.
Yang, Y., Souissi, S., Défago, X., Takizawa, M.: Fault-tolerant flocking for a group of autonomous mobile robots. J. Syst. Softw. 84(1), 29–36 (2011)
Metadata
Title
Flocking with Oblivious Robots
Authors
Davide Canepa
Xavier Defago
Taisuke Izumi
Maria Potop-Butucaru
Copyright Year
2016
Book
Stabilization, Safety, and Security of Distributed Systems

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

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

Copyright Year: 2016

DOI
https://doi.org/10.1007/978-3-319-49259-9_8

Premium Partner

    Image Credits