Weighting-based Variable Neighborhood Search for Optimal Camera Placement

Authors

  • Zhouxing Su School of Computer Science and Technology, Huazhong University of Science and Technology
  • Qingyun Zhang School of Computer Science and Technology, Huazhong University of Science and Technology
  • Zhipeng Lü School of Computer Science and Technology, Huazhong University of Science and Technology
  • Chu-Min Li MIS, University of Picardie Jules Verne
  • Weibo Lin Huawei Cloud Alkaid Lab, Huawei Technologies Co., Ltd.
  • Fuda Ma Huawei Cloud Alkaid Lab, Huawei Technologies Co., Ltd.

DOI:

https://doi.org/10.1609/aaai.v35i14.17471

Keywords:

Local Search, Heuristic Search, Applications, Deterministic Planning

Abstract

The optimal camera placement problem (OCP) aims to accomplish surveillance tasks with the minimum number of cameras, which is one of the topics in the GECCO 2020 Competition and can be modeled as the unicost set covering problem (USCP). This paper presents a weighting-based variable neighborhood search (WVNS) algorithm for solving OCP. First, it simplifies the problem instances with four reduction rules based on dominance and independence. Then, WVNS converts the simplified OCP into a series of decision unicost set covering subproblems and tackles them with a fast local search procedure featured by a swap-based neighborhood structure. WVNS employs an efficient incremental evaluation technique and further boosts the neighborhood evaluation by exploiting the dominance and independence features among neighborhood moves. Computational experiments on the 69 benchmark instances introduced in the GECCO 2020 Competition on OCP and USCP show that WVNS is extremely competitive comparing to the state-of-the-art methods. It outperforms or matches several best performing competitors on all instances in both the OCP and USCP tracks of the competition, and its advantage on 15 large-scale instances are over 10%. In addition, WVNS improves the previous best known results for 12 classical benchmark instances in the literature.

Downloads

Published

2021-05-18

How to Cite

Su, Z., Zhang, Q., Lü, Z., Li, C.-M., Lin, W., & Ma, F. (2021). Weighting-based Variable Neighborhood Search for Optimal Camera Placement. Proceedings of the AAAI Conference on Artificial Intelligence, 35(14), 12400-12408. https://doi.org/10.1609/aaai.v35i14.17471

Issue

Section

AAAI Technical Track on Search and Optimization