In this paper, we introduce cameras view-frame placement problem (denoted by CFP) in the presence an adversary whose objective is to minimize the maximum coverage by p cameras in response to input provided by n autonomous agents in a remote location. We allow uncertainty in the success of attacks, incomplete information of the probability distribution associated with the uncertain data, and varying levels of risk-appetite of the adversary. We present an exact cutting planes based algorithm to solve this problem along with conditions under which it is finitely convergent. Since this approach solves deterministic CFP in each iteration, we also present improved exact method for CFP with p=1, approximation algorithm and heuristics for Multi-CFP with p>1, and Multi-CFP with fixed tilt of the cameras. To evaluate the effectiveness and performance of the proposed approaches, we conduct computational experiments using randomly generated instances and simulation experiments where these approaches are utilized to find a hidden object in a remote location.
Note to Practitioners: This paper is motivated from application of cameras view-frame placement problem for military surveillance and reconnaissance in the presence of an adversary. We formulate this problem as a game played between an attacker and the camera-system user that captures uncertainty in the success of attacks and risk-appetite of the players. Its optimal solution, obtained using the proposed solution approaches, provides insight to both decision-makers/players. Especially, the camera-system user can identify the set of agents that are susceptible to attacks by a reasonable (risk-averse) attacker, and hence, can plan to have backup agents as well. Likewise, the proposed algebraic modeling framework and solution approaches are also applicable for planning interdiction actions to minimize the information acquisition by an evader/enemy.
View Algorithms for Cameras View-Frame Placement Problems in the Presence of an Adversary and Distributional Ambiguity