Title: Game-theoretic methods for locating camera towers and scheduling surveillance

Authors: Javier Salmeron; R. Kevin Wood

Addresses: Operations Research Department, Naval Postgraduate School, Monterey, CA, 93943, USA ' Operations Research Department, Naval Postgraduate School, Monterey, CA, 93943, USA

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.

Keywords: camera tower; surveillance; column generation; integer programming; randomised algorithm.

DOI: 10.1504/IJSPM.2017.085539

International Journal of Simulation and Process Modelling, 2017 Vol.12 No.3/4, pp.264 - 273

Received: 31 Mar 2016
Accepted: 12 Oct 2016
Published online: 30 Jul 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article