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.
GECCO 2021 Competition
on the Optimal Camera Placement Problem (OCP)
and the Unicost Set Covering Problem (USCP)
Introduction
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 [7], 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 [4], the OCP is structurally identical to the unicost set covering problem (USCP), which is one of Karp's well-known NP-hard problems [3]. 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 [4], 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.
References:
[1] 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
[2] 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
[3] R. M. Karp. Reducibility among Combinatorial Problems, pages 85–103.
Springer US, Boston, MA, 1972. DOI
[4] 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
[5] 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
[6] 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
[7] 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
History
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).
Organizing committee
Mathieu Brévilliers, Julien Lepagnot, and Lhassane Idoumghar.
Competition description and rules
- Documentation file (~638Kb) PDF
- Problem instance compressed archive (~1Gb, and ~18Gb once decompressed) TAR.XZ
- Example of solution file (~0.1Kb) TXT
As soon as you decide to take part in this competition, please send an email to mathieu.brevilliers@uha.fr 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.
Important dates
| 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 |
Submissions
| 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 technique |
USCP |
| midouLITIO | Université Oran 1, Algeria | cpxRedRowsCols: CPLEX MIP with row dominant elimination technique, and a column elimination strategy |
USCP |
| 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) |
OCP |
Results
| 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 |
- Video of the presentation at the GECCO 2021 competition session WWW
- Slide show presented at the GECCO 2021 competition session (~1.6Mb) PDF
- Spreadsheet file with all results and all score and rank calculations (~36Kb) ODS
Congratulations to the winners!
And our many thanks to the participants! Their work and effort contribute to the success of this competition.
Publications
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.
https://doi.org/10.1145/3449726.3463298
News and updates
- July 16, 2021 : Certificates have been added in section "Results".
- July 12, 2021 : Section "History" has been added.
- July 11, 2021 : Sections "Submissions", "Results" and "Publications" added to the competition website.
- July 5, 2021 : Link to the OCP and USCP benchmark webpage.
- April 1st, 2021 : Section "Competition description and rules" has been updated.
- December 17, 2020 : The competition website is online.