Optimal Multi-Sensor based Multi Target Detection by Moving Sensors to the Maximal Clique in a Covering Graph

Ganesh Kumar, K Madhava Krishna

Different methodologies have been employed to solve the multi-sensor multi-target detection prob-lem in a variety of scenarios. In this paper, we de-vise a time-step optimal algorithm for this problem when all but a few parameters of the sensor/target system are unknown. Using the concept of cover-ing graph, we find an optimum solution for a single sensor, which is extended to multiple sensors by a tagging operation. Both covering graph and tagging are novel concepts, developed in the context of the detection problem for the first time, and bring a mathematical elegance to its solution. Furthermore, an implementation of the resulting algorithm is found to perform better than other notable ap-proaches. The strong theoretical foundation, com-bined with the practical efficacy of the algorithm, makes it a very attractive solution to the problem.