Top

Published in:

2020 | OriginalPaper | Chapter

8. Patrolling and Surveillance Games

Authors : Stefan Rass, Stefan Schauer, Sandra König, Quanyan Zhu

Published in: Cyber-Security in Critical Infrastructures

Publisher: Springer International Publishing

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

search-config

AI-assisted search

Off

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).

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 Insurance

next chapter 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

Title: Patrolling and Surveillance Games
Authors: Stefan Rass
Stefan Schauer
Sandra König
Quanyan Zhu
Publisher: Springer International Publishing
Book: Cyber-Security in Critical Infrastructures
Print ISBN: 978-3-030-46907-8

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

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

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner