nach oben

Distributed Computing

Erschienen in:

01.04.2015

Fence patrolling by mobile agents with distinct speeds

verfasst von: Akitoshi Kawamura, Yusuke Kobayashi

Erschienen in: Distributed Computing | Ausgabe 2/2015

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Suppose we want to patrol a fence (line segment) using \(k\) mobile agents with given speeds \(v _1\), ..., \(v _k\) so that every point on the fence is visited by an agent at least once in every unit time period. Czyzowicz et al. conjectured that the maximum length of the fence that can be patrolled is \((v _1 + \cdots + v _k)/2\), which is achieved by the simple strategy where each agent \(i\) moves back and forth in a segment of length \(v _i / 2\). We disprove this conjecture by a counterexample involving \(k = 6\) agents. We also show that the conjecture is true for \(k \le 3\).

Vorheriger Artikel Forming sequences of geometric patterns with oblivious mobile robots

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

Chen, K., Dumitrescu, A., Ghosh, A.: On fence patrolling by mobile agents. In: Proceedings of 25th Canadian Conference on Computational Geometry (CCCG) (2013)

Chevaleyre, Y.: Theoretical analysis of the multi-agent patrolling problem. In: Proceedings of IEEE/WIC/ACM International Conference on Intelligent Agent Technology (IAT), pp. 302–308 (2004)

Collins, A., Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Martin, R., Morales Ponce, O.: Optimal patrolling of fragmented boundaries. In: Proceedings of 25th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 241–250 (2013)

Czyzowicz, J., Gąsieniec, L., Georgiou, K., Kranakis, E., MacQuarrie, F.: The beachcombers’ problem: Walking and searching with mobile robots. In: Proceedings of 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO) (2014)

Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: Proceedings of 19th European Symposium on Algorithms (ESA), LNCS 6942, pp. 701–712 (2011)

Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E., Morales Ponce, O., Pacheco, E.: Position discovery for a system of bouncing robots. In: Proceedings of 26th International Symposium on Distributed Computing (DISC), 2012, LNCS 7611, pp. 341–355

Czyzowicz, J., Kranakis, E., Pajak, D., Taleb, N.: Patrolling by robots equipped with visibility. In: Proceedings of 21st International Colloquium on Structural Information and Communication Complexity (SIROCCO) (2014)

Dumitrescu, A., Ghosh, A., Tóth, C.D.: On fence patrolling by mobile agents. Electron. J. Combin. 21,3–4 (2014)

Elmaliach, Y., Shiloni, A., Kaminka, G.A.: A realistic model of frequency-based multi-robot polyline patrolling. In: Proceedings of 7th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 63–70 (2008)

10.

Kawamura, A., Kobayashi, Y.: Fence patrolling by mobile agents with distinct speeds. In: Proceeings of 23rd International Symposium on Algorithms and Computation (ISAAC), LNCS 7676 pp. 598–608 (2012)

11.

Pasqualetti, F., Franchi, A., Bullo, F.: On optimal cooperative patrolling. In: Proceedings of 49th IEEE Conference on Decision and Control (CDC), pp. 7153–7158 (2010)

12.

Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999)

13.

Yanovski, V., Wagner, I.A., Bruckstein, A.M.: A distributed ant algorithm for efficiently patrolling a network. Algorithmica 37, 165–186 (2003)CrossRefMATHMathSciNet

Titel: Fence patrolling by mobile agents with distinct speeds
verfasst von: Akitoshi Kawamura
Yusuke Kobayashi
Publikationsdatum: 01.04.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Distributed Computing / Ausgabe 2/2015
Print ISSN: 0178-2770
Elektronische ISSN: 1432-0452
DOI: https://doi.org/10.1007/s00446-014-0226-3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2015

Adversarial topology discovery in network virtualization environments: a threat for ISPs?

Forming sequences of geometric patterns with oblivious mobile robots

Soft-error mitigation by means of decoupled transactional memory threads

Deterministic polynomial approach in the plane