Volume 55, Number 4, July-August 2021
Decision and Optimization in Service, Control and Engineering (CoDIT2019-DOSCE)
|Page(s)||2069 - 2091|
|Published online||08 July 2021|
On the computational cost of the set cover approach for the optimal camera placement problem and possible set-cover-inspired trade-offs for surveillance infrastructure design
IRIMAS, Université de Haute-Alsace, 12 Rue des Frères Lumière, 68 093 Mulhouse, France
* Corresponding author: firstname.lastname@example.org
Accepted: 17 June 2021
The 𝒩𝒫-hard minimum set cover problem (SCP) is a very typical model to use when attempting to formalise optimal camera placement (OCP) applications. In a generic form, the OCP problem relates to the positioning of individual cameras such that the overall network is able to cover a given area while meeting a set of application-specific requirements (image quality, redundancy, ...) and optimising an objective, typically minimum cost or maximum coverage. In this paper, we focus on an application called global or persistent surveillance: camera networks which ensure full coverage of a given area. As preliminary work, an instance generation pipeline is proposed to create OCP instances from real-world data and solve them using existing literature. The computational cost of both the instance generation process and the solving algorithms however highlights a need for more efficient methods for decision makers to use in real-world settings. In this paper, we therefore propose to review the suitability of the approach, and more specifically to question two key elements: the impact of sampling frequencies and the importance of rigid full-coverage constraints. The results allow us to quickly provide decision makers with an overview of available solutions and trade-offs.
Mathematics Subject Classification: 90-05 / 90-06 / 90-08 / 90C27 / 90-10
Key words: Combinatorial optimization / optimal camera placement / set cover problem
© The authors. Published by EDP Sciences, ROADEF, SMAI 2021
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (https://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.