The use of camera networks is now common to perform various surveillance tasks. Due to the prohibitive cost of setting or modifying such a camera network, it is required to provide a priori a configuration that minimizes the number of cameras in addition to meeting the operational needs. The optimal camera placement problem (OCP) is thus of critical importance, and can be generically formulated as follows. Given various constraints, usually related to coverage or image quality, and an objective to optimise (typically, the cost), how can the set of positions and orientations which best (optimally) meets the requirements be determined?
The objective considered here is to determine camera locations and orientations which ensure complete coverage of the area while minimizing the cost of the infrastructure. To this aim, the surveillance area is reduced to a set of three-dimensional sample points to be covered, and camera configurations are sampled into so-called candidates each with a given set of position and orientation coordinates.
Now, the OCP comes down to select the smallest subset of candidates which covers all the samples.
The OCP is structurally identical to the unicost set covering problem (USCP), which is one of Karp's well-known NP-hard problems, and which can be stated as follows: given a set of elements I (rows) to be covered, and a collection of sets J (columns) such that the union of all sets in J is I, find the smallest subset C of J such that C covers I.
Many papers dealing with the OCP use this relationship implicitly, but few works done on the USCP have been applied or adapted to the OCP, and vice versa. In very recent years however, approaches from the USCP literature have been successfully applied in the OCP context: it suggests that bridges can be built between these two bodies of literature to improve the results obtained so far on both USCP and OCP problems.
The main goal of this benchmark testbed is to encourage innovative research works in this direction, by proposing to solve OCP problem instances stated as USCP.
This benchmark testbed gathers 69 OCP problem instances:
Actually, a subset of the academic problems listed in this benchmark was first introduced in [1], and the method used to generate all real-world instances of this benchmark is presented in [2]. For these reasons, any publication related to this benchmark testbed should refer to it by citing the articles [1, 2] and by adding a link to the benchmark website [3]:
[1] Brévilliers M., Lepagnot J., Idoumghar L., Rebai M. and Kritter J. (2018),
Hybrid Differential Evolution Algorithms for the Optimal Camera Placement Problem,
Journal of Systems and Information Technology, Special issue on Optimisation Solutions in Systems, Vol.20 No.4, pp.446-467, Emerald.
https://doi.org/10.1108/JSIT-09-2017-0081
[2] Kritter J., Brévilliers M., Lepagnot J. and Idoumghar L. (2019),
On the Real-World Applicability of State-of-the-Art Algorithms for the Optimal Camera Placement Problem,
6th International Conference on Control, Decision and Information Technologies (IEEE CoDIT’19), Paris, France.
https://doi.org/10.1109/CoDIT.2019.8820295
[3] http://www.mage.fst.uha.fr/brevilliers/ocp-uscp-benchmark/
The whole benchmark testbed has been introduced for the GECCO 2020 Competition on the OCP and the USCP. A second edition of this competition has been hosted by GECCO 2021. For more information, please refer to the websites devoted to these competitions:
Documentation and data files are available for download in the section just below. History of the results obtained so far is also provided.
Please, feel free to contact the authors to update these files, whether it is to fix an error or to add new results.
Mathieu Brévilliers*,
Julien Kritter,
Julien Lepagnot,
and Lhassane Idoumghar,
Université de Haute-Alsace, IRIMAS UR 7499, F-68100 Mulhouse, France.
*Coresponding author: mathieu.brevilliers@uha.fr.
This work was funded as part of the French-German OPMoPS project, by the French Agence Nationale de la Recherche (under grant number ANR-16-SEBM-0004) and the German Bundesministerium für Bildung und Forschung.