Weighting-based Variable Neighborhood Search for Optimal Camera Placement

Zhouxing Su, Qingyun Zhang, Zhipeng Lü, Chu-Min Li, Weibo Lin, Fuda MaAAAI 2021 · DOI

Abstract

This paper introduces a highly efficient algorithm for the Optimal Camera Placement (OCP) problem, presented at AAAI 2021. By treating OCP as a specialized version of the Unicost Set Covering Problem (USCP), the authors developed a weighting-based variable neighborhood search (WVNS) that dominated the GECCO 2020 competition, outperforming existing solvers on massive, real-world datasets. The approach combines geometric tiling for initial solutions with a novel neighborhood pruning technique based on move independence, achieving state-of-the-art results on large-scale benchmarks.

Introduction

The goal of OCP is to cover every "sample point" in a target area using the minimum number of cameras. Mathematically, this is a Unicost Set Covering Problem (USCP): you have a universal set (the area to watch) and various subsets (the field of view of each potential camera position). You want the smallest collection of subsets whose union equals the universal set.

While USCP is a classic NP-hard problem, OCP adds a layer of complexity: real-world instances are massive, often involving millions of potential camera positions and sample points. Standard exact solvers often struggle with the scale, and general-purpose heuristics frequently miss the underlying geometric structure of the problem.

Methodology: Weighting-based Variable Neighborhood Search (WVNS)

The authors propose a multi-stage approach called WVNS to tackle these challenges:

1. Problem Reduction and Initial Tiling

Before searching, the algorithm applies four reduction rules (Row/Column Dominance, Unit Clause, and Connected Components) to eliminate redundant cameras or points. For instances with geometric data, they use a "tiling" method. Since many surveillance areas are regular grids, the algorithm looks for repeating camera patterns (tiles) to quickly build a high-quality starting solution.

The tiling heuristic identifies repeating geometric patterns to build a high-quality initial solution.

The algorithm tries to solve a series of decision subproblems: "Can we cover everything with exactly $k$ cameras?" It uses a weighting technique where uncovered points gain penalty weights over time, forcing the search to prioritize hard-to-cover areas and escape local optima.

3. Neighborhood Reduction and Independence

Evaluating every possible "swap" is computationally expensive. The authors' core innovation is proving that many moves are independent—if two cameras cover completely different areas, the benefit of swapping one doesn't affect the other. They use this to prune the neighborhood and combine the "best pick" and "best drop" moves in linear time, focusing on the $N^3$ neighborhood (sets within three hops in a bipartite graph) of uncovered elements.

Experimental Results

The algorithm was evaluated on the GECCO 2020 Competition dataset, which includes 32 academic instances (AC), 37 real-world instances (RW) featuring up to 4 million sets, and 12 classical benchmarks.

WVNS demonstrated significant performance gains:

  • Competition Dominance: WVNS outperformed or matched all top competitors in both the OCP and USCP tracks of the GECCO 2020 competition.
  • Efficiency: The variable neighborhood strategy allowed the solver to overtake naive implementations within just 20 seconds of execution, as seen in the rapid convergence of the gap metrics.
  • Significant Gains: On 15 large-scale instances, WVNS showed an advantage of over 10% compared to the previous state-of-the-art (DEsim).
  • New Records: The authors improved the best-known results for 12 classical benchmark instances studied for years.
Performance curves (Gap vs. Time) for real-world instances RW13, RW25, and RW31, showing the rapid convergence of WVNS variants.

Conclusion and Future Work

WVNS succeeds by exploiting both the geometric symmetry of camera placement through tiling and the locality of camera influence through independent neighborhood moves. While the tiling method is powerful for initial solution generation, the local search phase remains purely combinatorial. Future work aims to integrate geometric properties directly into the local search moves and test if independence-based neighborhood reduction can generalize to other combinatorial problems like Maximum Clique or Vertex Cover.

Summary updated

BibTeX
@inproceedings{su2021weighting,
  author = {Zhouxing Su and Qingyun Zhang and Zhipeng Lü and Chu-Min Li and Weibo Lin and Fuda Ma},
  title = {{Weighting-based Variable Neighborhood Search for Optimal Camera Placement}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i14.17471},
}
Figure