Game-theoretic methods for locating camera towers and scheduling surveillance

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.