Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction to Swarm Search Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Swarm Search of Expanding Regions in Grids: Upper Bounds

verfasst von : Yaniv Altshuler, Alex Pentland, Alfred M. Bruckstein

Erschienen in: Swarms and Network Intelligence in Search

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this chapter we examine the dynamic generalization of the Cooperative Cleaners problem presented in Altshuler et al., Swarm intelligent systems (2006), [10] and in the previous chapters of this book, involving a swarm of collaborative drones that are required to search a dynamically expanding region on the \( \mathbf{Z}^{2}\) grid (whose “pixels” that were visited by the drones can become “un-searched” after a certain period of time). The goal of the swarm’s members is to “clean” the spreading contamination in as little time as possible. In this work we present a collaborative swarm search algorithm, as well as several upper bounds on the completion time it takes a swarm of k drones, of various velocities.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Swarm Search of Expanding Regions in Grids: Lower Bounds
Nächstes Kapitel The Search Complexity of Collaborative Swarms in Expanding Grid Regions
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
This is a simple consequence of the “rotation index” Theorem (see e.g. [21] p. 396): If \(\alpha : [0,1] \rightarrow R^{2}\) is a plane, regular, simple, closed curve, then \(\int _{0}^{1}k(s)ds = 2 \pi \), where k(s) is the curvature of \(\alpha (s)\) and the curve is traversed in the positive direction.
 
2
The existence of a non-critical point is guaranteed since \(\partial F_{t}\) is a connected graph and thus has a spanning tree, in which at least two tiles has a degree of 1, which makes them non-critical tiles.
 
3
The integral was produced using MATLAB [38].
 
Literatur
1.
M. Abramowitz, I.A. Stegun, Handbook of Mathematical Functions, Applied Mathematics Series (National Bureau of Standards, 1964), p. 55
2.
M. Ahmadi, P. Stone, A multi-robot system for continuous area sweeping tasks, in IEEE International Conference on Robotics and Automation, 2006 (ICRA 2006) (2006)
3.
S. Alpern, S. Gal, The Theory of Search Games and Rendezvous (Kluwer Academic Publishers, Boston, 2003)MATH
4.
Y. Altshuler, Multi Agents Robotics in Dynamic Environments. Ph.D. thesis, Israeli Institute of Technology, May 2010
5.
Y. Altshuler, A.M. Bruckstein, The complexity of grid coverage by swarm robotics, in ANTS 2010 (LNCS, 2010), pp. 536–543
6.
Y. Altshuler, A.M. Bruckstein, Static and expanding grid coverage with ant robots: complexity results. Theoret. Comput. Sci. 412(35), 4661–4674 (2011)MathSciNetCrossRefMATH
7.
Y. Altshuler, A.M. Bruckstein, I.A. Wagner, Swarm robotics for a dynamic cleaning problem, in IEEE Swarm Intelligence Symposium (2005), pp. 209–216
8.
Y. Altshuler, V. Yanovski, I.A. Wagner, A.M. Bruckstein, The cooperative hunters - efficient cooperative search for smart targets using uav swarms, in Second International Conference on Informatics in Control, Automation and Robotics (ICINCO), the First International Workshop on Multi-Agent Robotic Systems (MARS) (2005), pp. 165–170
9.
Y. Altshuler, I.A. Wagner, A.M. Bruckstein, Shape factor‘s effect on a dynamic cleaners swarm, in Third International Conference on Informatics in Control, Automation and Robotics (ICINCO), the Second International Workshop on Multi-Agent Robotic Systems (MARS) (2006), pp. 13–21
10.
Y. Altshuler, V. Yanovsky, I. Wagner, A. Bruckstein, Swarm intelligencesearchers, cleaners and hunters. Swarm Intelligent Systems (2006), pp. 93–132
11.
Y. Altshuler, V. Yanovsky, A.M. Bruckstein, I.A. Wagner, Efficient cooperative search of smart targets using uav swarms. ROBOTICA 26, 551–557 (2008)CrossRef
12.
Y. Altshuler, I.A. Wagner, A.M. Bruckstein, On swarm optimality in dynamic and symmetric environments. Economics 7, 11 (2008)
13.
Y. Altshuler, I.A. Wagner, A.M. Bruckstein, Collaborative exploration in grid domains, in Sixth International Conference on Informatics in Control, Automation and Robotics (ICINCO) (2009)
14.
Y. Altshuler, I.A. Wagner, V. Yanovski, A.M. Bruckstein, Multi-agent cooperative cleaning of expanding domains. Int. J. Robot. Res. 30, 1037–1071 (2010)CrossRef
15.
Y. Altshuler, S. Dolev, Y. Elovici, N. Aharony, Ttled random walks for collaborative monitoring, in NetSciCom, Second International Workshop on Network Science for Communication Networks. San Diego, CA, USA, 3 (2010)
16.
Y. Altshuler, A. Pentland, S. Bekhor, Y. Shiftan, A. Bruckstein, Optimal dynamic coverage infrastructure for large-scale fleets of reconnaissance uavs (2016), arXiv:​1611.​05735
17.
18.
R. Bejar, B. Krishnamachari, C. Gomes, B. Selman, Distributed constraint satisfaction in a wireless sensor tracking system, in Proceedings of the IJCAI-01 Workshop on Distributed Constraint Reasoning (2001)
19.
M. Bender, S. Michel, P. Triantafillou, G. Weikum, C. Zimmer, Minerva: collaborative p2p search, in Proceedings of the 31st international conference on Very large data bases (2005), pp. 1263–1266
20.
D.W. Casbeer, D.B. Kingston, R.W. Beard, T.W. McLain, Cooperative forest fire surveillance using a team of small unmanned air vehicles. Int. J. Syst. Sci. 37(6), 351–360 (2006)CrossRefMATH
21.
M.P. Do-Carmo, Differential Geometry of Curves and Surfaces (Prentice-Hall, New-Jersey, 1976)MATH
22.
Y. Gabriely, E. Rimon, Competitive on-line coverage of grid environments by a mobile robot. Comput. Geom. 24, 197–224 (2003)MathSciNetCrossRefMATH
23.
S. Hedberg, Robots cleaning up hazardous waste, in AI Expert (1995), pp. 20–24
24.
M. Held, On the computational geometry of pocket machining, in Lecture Notes in Computer Science (1991)
25.
26.
R. Janakiraman, M. Waldvogel, Q. Zhang, Indra: a peer-to-peer approach to network intrusion detection and prevention, in Proceedings of IEEE WETICE (2003)
27.
W. Kerr, D. Spears, Robotic simulation of gases for a surveillance task, in Intelligent Robots and Systems (IROS 2005) (2005), pp. 2905–2910
28.
29.
D. Latimer, S. Srinivasa, V. Lee-Shue, S. Sonne, H. Choset, A. Hurst, Toward sensor based coverage with robot teams, in Proceedings of the 2002 IEEE International Conference on Robotics and Automation (2002)
30.
T.W. Min, H.K. Yin, A decentralized approach for cooperative sweeping by multiple mobile robots, in IEEE/RSJ International Conference on Intelligent Robots and Systems (1998), pp. 380–385
31.
W. Neubauer, Locomotion with articulated legs in pipes or ducts. Robot. Auton. Syst. 11, 163–169 (1993)CrossRef
32.
K. Passino, M. Polycarpou, D. Jacques, M. Pachter, Y. Liu, Y. Yang, M. Flint, M. Baum, Cooperative Control for Autonomous Air Vehicles, chapter Cooperative Control and Optimization (Kluwer Academic, Boston, 2002)
33.
M. Polycarpou, Y. Yang, K. Passino, A cooperative search framework for distributed agents, in IEEE International Symposium on Intelligent Control (2001)
34.
E. Regev, Y. Altshuler, A.M. Bruckstein, The cooperative cleaners problem in stochastic dynamic environments (2012), arXiv:​1201.​6322
35.
I. Rekleitis, V. Lee-Shuey, A. Peng Newz, H. Choset, Limited communication, multi-robot team based coverage, in IEEE International Conference on Robotics and Automation (2004)
36.
Y. Shoham, M. Tennenholtz, On social laws for artificial agent societies: off line design. AI J. 73(1–2), 231–252 (1995)
37.
L.D. Stone, Theory of Optimal Search (Academic Press, New York, 1975)MATH
38.
The MathWorks Inc. Matlab — the language of technical computing, ver. 6.5 (2002)
39.
I.A. Wagner, Y. Altshuler, V. Yanovski, A.M. Bruckstein, Cooperative cleaners: a study in ant robotics. Int. J. Robot. Res. (IJRR) 27(1), 127–151 (2008)CrossRef
Metadaten
Titel
Swarm Search of Expanding Regions in Grids: Upper Bounds
verfasst von
Yaniv Altshuler
Alex Pentland
Alfred M. Bruckstein
Copyright-Jahr
2018
Buch
Swarms and Network Intelligence in Search

Print ISBN: 978-3-319-63602-3

Electronic ISBN: 978-3-319-63604-7

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-63604-7_4