Game-theoretic methods for locating camera towers and scheduling surveillance. (2017)

• Record Type: Journal Article
• Authors: Salmeron, Javier; Wood, R. Kevin
• Is Part Of: International journal of simulation and process modelling. Volume 12:Number 3/4(2017)
• Page Start: 264
• Page End: 273
• Publication Date: 2017
• Subjects: camera tower -- surveillance -- column generation -- integer programming -- randomised algorithm; Management -- Computer simulation -- Periodicals; Mathematical models -- Periodicals; Operations research -- Periodicals; Simulation methods -- Periodicals; 003.05
• Languages: English
• ISSNs: 1740-2123

Abstract

We develop techniques to optimise the locations and surveillance scheduling of tower-mounted camera systems used by a military force in an urban setting. Using a game-theoretic foundation, we seek to minimise expected damage from attacks or other adversarial events (e.g., emplacements of improvised explosive devices). Assuming that at most one camera may surveil a single point of interest (POI) at any time, a mixed-integer program uses an additive-probability model to optimise the placement of towers, while allocating 'aggregate, normalised surveillance time' between cameras and POIs. Linear-programming-based column generation then creates a probability distribution for camera-to-POI assignments to define implementable schedules. We prove that such schedules must exist, making the additive probability model exact. Computational examples on realistically sized problems produce high-quality solutions quickly, with quality suffering only when the number of cameras available nears the number of POIs to be surveilled. We show that an alternative game-theoretic model may produce better solutions when such a situation arises.