A Complexity-Level Analysis of the Sensor Planning Task for Object Search

Object search is the task of searching for a given 3 D object in a given 3 D environment by a controllable camera. Sensor planning for object search refers to the task of how to select the sensing parameters of the camera so as to bring the target into the field of view of the camera and to make the image of the target to be easily recognized by the available recognition algorithms. In this paper, we study the task of sensor planning for object search from the theoretical point of view. We formulate the task and point out many of its important properties. We then analyze this task from the complexity level and prove that this task is NP-Complete.