nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

8. Patrolling and Surveillance Games

verfasst von : Stefan Rass, Stefan Schauer, Sandra König, Quanyan Zhu

Erschienen in: Cyber-Security in Critical Infrastructures

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

Patrolling and surveillance games both deal with a chasing-evading situation of an adversary trying to escape detection by either a mobile defender (patrolling) or a fixed defender (surveillance). Both kinds of games are played on graphs as abstract models of an infrastructure, and we review a variety of closed-form solutions for optimal patrolling in different classes of graph topologies. Applications include patrolling along lines (borders, pipelines, or similar), harbors (tree-structured graphs), and large geographic areas in general (planar graphs and maps). For surveillance and patrolling, we give hints on how to estimate the necessary resources, and how to include imperfectness and uncertainty, related to the detection capabilities, but also the chances of the adversary escaping the view of the patroller or surveillance. In complex terrain, we will discuss the use of simulation and empirical games (over real-valued and stochastic orders).

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 Insurance

Nächstes Kapitel Optimal Inspection Plans

Alonso NZ, Terol PZ (1993) Some games of search on a lattice. Naval Res Logist 40(4):525–541. https://doi.org/10.1002/1520-6750(199306)40:4<525::AID-NAV3220400407>3.0.CO;2-B MathSciNetMATHCrossRef

Alpern S, Asic M (1985) The search value of a network. Networks 15(2):229–238. https://doi.org/10.1002/net.3230150208 MathSciNetMATHCrossRef

Alpern S, Fokkink R (2014) Accumulation games on graphs. Networks 64(1):40–47. https://doi.org/10.1002/net.21555 MathSciNetMATHCrossRef

Alpern S, Fokkink R, Kikuta K (2010) On Ruckle’s conjecture on accumulation games. SIAM J Control Optim 48(8):5073–5083. https://doi.org/10.1137/080741926 MathSciNetMATHCrossRef

Alpern S, Morton A, Papadaki K (2011) Patrolling games. Oper Res 59(5):1246–1257. https://doi.org/10.1287/opre.1110.0983 MathSciNetMATHCrossRef

Alpern S, Lidbetter T, Morton A, Papadaki K (2016) Patrolling a pipeline. In: Zhu Q, Alpcan T, Panaousis E, Tambe M, Casey W (eds) Decision and game theory for security. Lecture notes in computer science. Springer International Publishing, Cham, pp 129–138

Alpern S, Lidbetter T, Papadaki K (2017) Periodic patrols on the line and other networks. ArXiv:1705.10399v1 [math.OC]

Appel K, Haken W (1989) Every planar map is four colorable, vol 98. American Mathematical Society, Providence. https://doi.org/10.1090/conm/098

Basak A, Fang F, Nguyen TH, Kiekintveld C (2016) Combining graph contraction and strategy generation for green security games. In: Zhu Q, Alpcan T, Panaousis E, Tambe M, Casey W (eds) Decision and game theory for security. Lecture notes in computer science. Springer International Publishing, Cham, pp 251–271MATH

10.

Bodor R, Drenner A, Schrater P, Papanikolopoulos N (2007) Optimal camera placement for automated surveillance tasks. J Intell Robot Syst 50(3):257–295. https://doi.org/10.1007/s10846-007-9164-7 CrossRef

11.

Chvátal V (1975) A combinatorial theorem in plane geometry. J Combin Theory Ser B 18:39–41MathSciNetMATHCrossRef

12.

Cormen TH, Leiserson CE, Rivest RL (1994) Introduction to algorithms. MIT Press, CambridgeMATH

13.

Debaque B, Jedidi R, Prevost D (2009) Optimal video camera network deployment to support security monitoring. In: 12th international conference on information fusion, 2009. IEEE, Piscataway, pp 1730–1736

14.

Edmonds J, Johnson EL (1973) Matching, Euler tours and the Chinese postman. Math Program 5(1):88–124. https://doi.org/10.1007/BF01580113 MathSciNetMATHCrossRef

15.

Fisk S (1978) A short proof of Chvátal’s Watchman theorem. J Combin Theory Ser B 24(3):374. https://doi.org/10.1016/0095-8956(78)90059-X MathSciNetMATHCrossRef

16.

Fox CR, Bardolet D, Lieb D (2005) Partition dependence in decision analysis, resource allocation, and consumer choice. In: Zwick R, Rapoport A (eds) Experimental business research. Springer, Dordrecht/Berlin, pp 229–251. https://doi.org/10.1007/0-387-24244-9_10 CrossRef

17.

Garey MR, Johnson DS (1979) Computers and intractability. Freeman, New YorkMATH

18.

Hörster E, Lienhart R (2006) On the optimal placement of multiple visual sensors. In: Aggarwal JK, Cucchiara R, Prati A (eds) Proceedings of the 4th ACM international workshop on video surveillance and sensor networks – VSSN’06, p 111. ACM Press, New York. https://doi.org/10.1145/1178782.1178800

19.

Indu S, Chaudhury S, Mittal N, Bhattacharyya A (2009) Optimal sensor placement for surveillance of large spaces. In: 2009 third ACM/IEEE international conference on distributed smart cameras (ICDSC). IEEE, pp 1–8. https://doi.org/10.1109/ICDSC.2009.5289398

20.

Kikuta K, Ruckle WH (2002) Continuous accumulation games on discrete locations. Naval Res Logist 49(1):60–77. https://doi.org/10.1002/nav.1048 MathSciNetMATHCrossRef

21.

O’Rourke J (1987) Art gallery theorems and algorithms. The international series of monographs on computer science, vol 3. Oxford University Press, New York

22.

Papadaki K, Alpern S, Lidbetter T, Morton A (2016) Patrolling a border. Oper Res 64(6):1256–1269. https://doi.org/10.1287/opre.2016.1511 MathSciNetMATHCrossRef

23.

Pita J, Tambe M, Kiekintveld C, Cullen S, Steigerwald E (2011) GUARDS – innovative application of game theory for national airport security. In: IJCAI 2011, pp 2710–2715 . https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-451

24.

Rass S, Alshawish A, Abid MA, Schauer S, Zhu Q, de Meer H (2017) Physical intrusion games – optimizing surveillance by simulation and game theory. IEEE Access 5:8394–8407. https://doi.org/10.1109/ACCESS.2017.2693425 CrossRef

25.

Rass S, König S, Schauer S (2017) On the cost of game playing: how to control the expenses in mixed strategies. In: Decision and game theory for security. Springer, Cham, Switzerland [S.l.], pp 494–505

Titel: Patrolling and Surveillance Games
verfasst von: Stefan Rass
Stefan Schauer
Sandra König
Quanyan Zhu
Verlag: Springer International Publishing
Buch: Cyber-Security in Critical Infrastructures
Print ISBN: 978-3-030-46907-8

Electronic ISBN: 978-3-030-46908-5

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-46908-5_8

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"

Premium Partner