A complexity-level analysis of the sensor planning task for object search

Object search is the task of searching for a given 3D object in a given 3D environment by a controllable camera. Sensor planning for object search ref ers 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 i mage of the target to be easily recognized by the available recognition alg orithms. In this paper, we study the task of sensor planning for object sea rch 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 compl exity level and prove that this task is NP-Complete.