nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Distributed Patrolling with Two-Speed Robots (and an Application to Transportation)

verfasst von : Jurek Czyzowicz, Konstantinos Georgiou, Evangelos Kranakis, Fraser MacQuarrie, Dominik Pajak

Erschienen in: Operations Research and Enterprise Systems

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We initiate the study of patrolling a unit interval with primitive two-speed, autonomous robots, i.e. robots without memory, no communication capabilities and no computation power. Robots have only two moving-states, one for patrolling and one for walking, each associated with a direction and speed. The robots are moving perpetually, and their moving-states and moving directions change only when they collide. Such a dynamic system induces the so-called idleness for patrolling a unit interval, i.e. the smallest time interval within which every point of the domain is patrolled by some robot. Our main technical contribution is an analytic study of the induced dynamic system of robots, which allows us to decide efficiently whether or not the system converges to a stable configuration that is also shown to be optimal.

As a warm-up for our main result, we show how robots can be centrally coordinated, carefully choosing initial locations, so that the induced idleness is optimal. Our main result pertaining to the idleness of primitive robots follows by a technical analysis of their collision locations, which we show, under some conditions, converge to the optimal initial locations for non-distributed robots.

Our result finds an application to a transportation problem concerning Scheduling with Regular Delivery. In this optimization problem, an infinite quantity of a commodity, residing at an endpoint of an interval, needs to be transported to the other endpoint. To that end, we show that the already established patrolling schedules of an interval correspond to optimal strategies that guarantee that the flow of the commodity is the largest possible.

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 Solving Chance-Constrained Games Using Complementarity Problems

Nächstes Kapitel Inventory Routing with Explicit Energy Consumption: A Mass-Flow Formulation and First Experimentation

Agmon, N., Hazon, N., Kaminka, G.A.: The giving tree: constructing trees for efficient offline and online multi-robot coverage. Ann. Math. Artif. Intell. 52(2–4), 143–168 (2008)MathSciNetCrossRefMATH

Agmon, N., Kraus, S., Kaminka, G.A.: Multi-robot perimeter patrol in adversarial settings. In: ICRA, pp. 2339–2345 (2008)

Almeida, A., Ramalho, G., Santana, H., Tedesco, P., Menezes, T., Corruble, V., Chevaleyre, Y.: Recent advances on multi-agent patrolling. In: Bazzan, A.L.C., Labidi, S. (eds.) SBIA 2004. LNCS (LNAI), vol. 3171, pp. 474–483. Springer, Heidelberg (2004). doi:10.1007/978-3-540-28645-5_48 CrossRef

Alpern, S., Morton, A., Papadaki, K.: Optimizing randomized patrols. Operational Research Group, London School of Economics and Political Science (2009)

Alpern, S., Morton, A., Papadaki, K.: Patrolling games. Oper. Res. 59(5), 1246–1257 (2011)MathSciNetCrossRefMATH

Amigoni, F., Basilico, N., Gatti, N., Saporiti, A., Troiani, S.: Moving game theoretical patrolling strategies from theory to practice: an USARSim simulation. In: ICRA, pp. 426–431 (2010)

Angluin, D., Aspnes, J., Diamadi, Z., Fischer, M., Peralta, R.: Computation in networks of passively mobile finite-state sensors. Distrib. Comput. 18(4), 235–253 (2006)CrossRefMATH

Angluin, D., Aspnes, J., Eisenstat, D., Ruppert, E.: The computational power of population protocols. Distrib. Comput. 20(4), 279–304 (2007)CrossRefMATH

Bampas, E., Gąsieniec, L., Hanusse, N., Ilcinkas, D., Klasing, R., Kosowski, A.: Euler tour lock-in problem in the rotor-router model. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 423–435. Springer, Heidelberg (2009). doi:10.1007/978-3-642-04355-0_44 CrossRef

10.

Beauquier, J., Burman, J., Clement, J., Kutten, S.: On utilizing speed in networks of mobile agents. In: Proceeding of the 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 305–314. ACM (2010)

11.

Chalopin, J., Das, S., Gawrychowski, P., Kosowski, A., Labourel, A., Uznański, P.: Limit behavior of the multi-agent rotor-router system. In: Moses, Y. (ed.) DISC 2015. LNCS, vol. 9363, pp. 123–139. Springer, Heidelberg (2015). doi:10.1007/978-3-662-48653-5_9 CrossRef

12.

Chevaleyre, Y.: Theoretical analysis of the multi-agent patrolling problem. In: IAT, pp. 302–308 (2004)

13.

Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Distributed computing by mobile robots: gathering. SIAM J. Comput. 41(4), 829–879 (2012)MathSciNetCrossRefMATH

14.

Collins, A., Czyzowicz, J., Gasieniec, L., Kosowski, A., Kranakis, E., Krizanc, D., Martin, R., Morales Ponce, O.: Optimal patrolling of fragmented boundaries. In: SPAA (2013)

15.

Czyzowicz, J., Gąsieniec, L., Kosowski, A., Kranakis, E.: Boundary patrolling by mobile agents with distinct maximal speeds. In: Demetrescu, C., Halldórsson, M.M. (eds.) ESA 2011. LNCS, vol. 6942, pp. 701–712. Springer, Heidelberg (2011). doi:10.1007/978-3-642-23719-5_59 CrossRef

16.

Czyzowicz, J., Kranakis, E., Pacheco, E.: Localization for a system of colliding robots. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013. LNCS, vol. 7966, pp. 508–519. Springer, Heidelberg (2013). doi:10.1007/978-3-642-39212-2_45

17.

Dereniowski, D., Kosowski, A., Pajak, D., Uznanski, P.: Bounds on the cover time of parallel rotor walks. In: STACS 2014, pp. 263–275 (2014)

18.

Dijkstra, E.W.: Selected Writings on Computing: A Personal Perspective. Springer, New York (1982)CrossRefMATH

19.

Dumitrescu, A., Ghosh, A., Csaba, D.T.: On fence patrolling by mobile agents. CoRR, abs/1401.6070 (2014)

20.

Elmaliach, Y., Agmon, N., Kaminka, G.A.: Multi-robot area patrol under frequency constraints. Ann. Math. Artif. Intell. 57(3–4), 293–320 (2009)MathSciNetCrossRefMATH

21.

Elmaliach, Y., Shiloni, A., Kaminka, G.A.: A realistic model of frequency-based multi-robot polyline patrolling. In: AAMAS, vol. 1, pp. 63–70 (2008)

22.

Elor, Y., Bruckstein, A.M.: Autonomous multi-agent cycle based patrolling. In: Dorigo, M., Birattari, M., Caro, G.A., Doursat, R., Engelbrecht, A.P., Floreano, D., Gambardella, L.M., Groß, R., Şahin, E., Sayama, H., Stützle, T. (eds.) ANTS 2010. LNCS, vol. 6234, pp. 119–130. Springer, Heidelberg (2010). doi:10.1007/978-3-642-15461-4_11 CrossRef

23.

Gabriely, Y., Rimon, E.: Spanning-tree based coverage of continuous areas by a mobile robot. In: ICRA, pp. 1927–1933 (2001)

24.

Hare, J., Gupta, S., Wilson, J.: Decentralized smart sensor scheduling for multiple target tracking for border surveillance. In: ICRA, pp. 3265–3270. IEEE (2015)

25.

Hazon, N., Kaminka, G.A.: On redundancy, efficiency, and robustness in coverage for multiple robots. Robotics Auton. Syst. 56(12), 1102–1114 (2008)CrossRef

26.

Kawamura, A., Kobayashi, Y.: Fence patrolling by mobile agents with distinct speeds. In: Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 598–608. Springer, Heidelberg (2012). doi:10.1007/978-3-642-35261-4_62 CrossRef

27.

Kosowski, A., Pająk, D.: Does adding more agents make a difference? A case study of cover time for the rotor-router. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8573, pp. 544–555. Springer, Heidelberg (2014). doi:10.1007/978-3-662-43951-7_46

28.

Machado, A., Ramalho, G., Zucker, J.-D., Drogoul, A.: Multi-agent patrolling: an empirical analysis of alternative architectures. In: Simão Sichman, J., Bousquet, F., Davidsson, P. (eds.) MABS 2002. LNCS (LNAI), vol. 2581, pp. 155–170. Springer, Heidelberg (2003). doi:10.1007/3-540-36483-8_11 CrossRef

29.

Marden, M.: The Geometry of the Zeros of a Polynomial in a Complex Variable. Mathematical Surveys, vol. 3. AMS (1949)

30.

Marino, A., Parker, L.E., Antonelli, G., Caccavale, F.: Behavioral control for multi-robot perimeter patrol: a finite state automata approach. In: ICRA, pp. 831–836 (2009)

31.

Pasqualetti, F., Franchi, A., Bullo, F.: On optimal cooperative patrolling. In: CDC, pp. 7153–7158 (2010)

32.

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

Titel: Distributed Patrolling with Two-Speed Robots (and an Application to Transportation)
verfasst von: Jurek Czyzowicz
Konstantinos Georgiou
Evangelos Kranakis
Fraser MacQuarrie
Dominik Pajak
Verlag: Springer International Publishing
Buch: Operations Research and Enterprise Systems
Print ISBN: 978-3-319-53981-2

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

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-53982-9_5

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"