Please note that up-to-date information are now available on the webpage devoted to the OCP and USCP benchmark used in this competition: it gathers the data, the last version of the documentation, the history of the results obtained so far and the corresponding references.
The use of camera networks is now common to perform various surveillance tasks. These networks can be implemented together with intelligent systems that analyze video footage, for instance, to detect events of interest, or to identify and track objects or persons. According to , whatever the operational needs are, the quality of service depends on the way in which the cameras are deployed in the area to be monitored (in terms of position and orientation angles). Moreover, 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. In this context, the optimal camera placement problem (OCP) is 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?
More specifically, in this competition, the objective will be to determine camera locations and orientations which ensure complete coverage of the area while minimizing the cost of the infrastructure. To this aim, a discrete approach is considered here: 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. A candidate can have several samples within range, and a sample can be seen by several candidates. Now, the OCP comes down to select the smallest subset of candidates which covers all the samples.
According to , the OCP is structurally identical to the unicost set covering problem (USCP), which is one of Karp's well-known NP-hard problems . The USCP 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.
As pointed out in , 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 on both academic [2,1,6] and real-world [5,6] problem instances. These works suggest 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 competition is to encourage innovative research works in this direction, by proposing to solve OCP problem instances stated as USCP.
 M. Brévilliers, J. Lepagnot, L. Idoumghar, M. Rebai, and J. Kritter. Hybrid differential evolution algorithms for the optimal camera placement problem.
Journal of Systems and Information Technology, 20(4):446 – 467, 2018. DOI
 M. Brévilliers, J. Lepagnot, J. Kritter, and L. Idoumghar. Parallel preprocessing for the optimal camera placement problem. International Journal of Modeling and Optimization, 8(1):33 – 40, 2018. DOI
 R. M. Karp. Reducibility among Combinatorial Problems, pages 85–103. Springer US, Boston, MA, 1972. DOI
 J. Kritter, M. Brévilliers, J. Lepagnot, and L. Idoumghar. On the optimal placement of cameras for surveillance and the underlying set cover problem. Applied Soft Computing, 74:133 – 153, 2019. DOI
 J. Kritter, M. Brévilliers, J. Lepagnot, and L. Idoumghar. On the real-world applicability of state-of-the-art algorithms for the optimal camera placement problem. In 2019 6th International Conference on Control, Decision and Information Technologies (CoDIT), pages 1103–1108, April 2019. DOI
 Weibo Lin, Fuda Ma, Zhouxing Su, Qingyun Zhang, Chumin Li, and Zhipeng Lü. Weighting-based parallel local search for optimal camera placement and unicost set covering. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, GECCO'20, pages 3–4, New York, NY, USA, 2020. Association for Computing Machinery. DOI
 J. Liu, S. Sridharan, and C. Fookes. Recent advances in camera planning for large area surveillance: A comprehensive review. ACM Comput. Surv., 49(1):6:1–6:37, May 2016. DOI
This is the 2nd edition of the OCP and USCP competition. The 1st edition was held in 2020 and was also hosted by the GECCO international conference (GECCO 2020 Competition on the OCP and the USCP).
As soon as you decide to take part in this competition, please send an email to email@example.com to declare your intention to compete. Early registration is strongly encouraged, so that the organizing committee is aware of all entrant teams, and can then keep them informed of any update regarding the organization of the competition (e.g. deadline extension).
We offer to the participants the opportunity to publish their algorithm descriptions as GECCO Companion abstracts (2-page contributions). In this regard, please pay attention to the submission deadline (see next section just below).
It is also worth noting that taking part in this competition does not require a GECCO registration, unless a submitted GECCO Companion abstract is accepted for publication.
|April 12, 2021||Submission deadline for the GECCO Companion abstracts and the corresponding solution files|
|April 26, 2021||Notification of acceptance for GECCO Companion abstracts|
|May 3, 2021||Deadline to submit the camera-ready GECCO Companion abstracts|
|June 4, 2021||End of the competition, i.e. final submission deadline|
|July 10-14, 2021||GECCO 2021 Conference, and announcement of the competition results|
|Team||Affiliation||Algorithm||Type of solver|
|lastMinute||Jozef Stefan Institute, Slovenia||Branch-And-Bound USCP Parallel solver (BAB_USCPP)||USCP|
|midouLITIO||Université Oran 1, Algeria||cpxPure: CPLEX MIP||USCP|
|midouLITIO||Université Oran 1, Algeria||cpxRedRows: CPLEX MIP with row dominant elimination
|midouLITIO||Université Oran 1, Algeria||cpxRedRowsCols: CPLEX MIP with row dominant elimination
technique, and a column elimination strategy
|SmartOCP||Huazhong University of Science and Technology, China
Université de Picardie Jules Verne, France
|Weighting-based Variable Neighborhood Search
with the use of the geometric information (WVNS-g)
|Rank||Team||Algorithm||Type of solver||Certificate|
|1||SmartOCP||WVNS-g||OCP||PDF - PNG|
|2||midouLITIO||cpxPure||USCP||PDF - PNG|
|3||midouLITIO||cpxRedRows||USCP||PDF - PNG|
|3||midouLITIO||cpxRedRowsCols||USCP||PDF - PNG|
|5||lastMinute||BAB_USCPP||USCP||PDF - PNG|
Congratulations to the winners!
And our many thanks to the participants! Their work and effort contribute to the success of this competition.
Radescek J. and Depolli M. (2021),
Exact and Approximate USCP With Branch and Bound,
In Genetic and Evolutionary Computation Conference Companion (GECCO'21 Companion), July 10–14, 2021, Lille, France,
ACM, New York, NY, USA, 2 pages.