Active target detection with navigation costs: A randomized benchmark

Detecting the presence of a target within a field, is a long-standing problem of interest in a variety of applications from environmental to military. A framework is considered in which a single autonomous underwater vehicle (AUV), physically samples a decaying separable field generated by the target, to determine the target location. The overarching metric of interest is the three fold trade-off between the sampling and computational complexity of target detection, the cost of navigation for the AUV subject to a low detection error probability. The non-triviality of this problem stems from the emphasis on detection error probability rather than field reconstruction error and the inclusion of navigational cost as a performance metric of interest. In the absence of these two aspects, standard low-rank matrix completion theory is order-optimal in terms of sample complexity for field reconstruction. An active (adaptive) sampling and reconstruction strategy for target detection is proposed which takes the form of a partial low-rank matrix completion algorithm that simultaneously improves over standard low-rank matrix completion from random measurements on all three metrics, viz. sampling, computational and navigational complexities, subject to meeting a detection error probability. As a consequence of the strong concentration properties of the Euclidean Traveling Salesperson Problem (TSP), it turns out (somewhat surprisingly) that random spatial sampling strategy is simultaneous orderoptimal for sampling and navigational complexities w.r.t. size of the search space for uniform prior on the target location with localized target signatures.