Multiscale Adaptive Search

We present a continuous-space multiscale adaptive search (MAS) algorithm for single or multiple searchers that finds a stationary target in the presence of uncertainty in sensor diameter. The considered uncertainty simulates the influence of the changing environment and terrain as well as adversarial actions that can occur in practical applications. When available, information about the foliage areas and a priori distribution of the target position is included in the MAS algorithm. By adapting to various uncertainties, MAS algorithm reduces the median search time to find the target with a probability of detection of at least P_D and a probability of false alarm of at most P_FA. We prove that MAS algorithm discovers the target with the desired performance bounds P_D and P_FA. The unique features of the MAS algorithm are realistic second-order dynamics of the mobile sensors that guarantees uniform coverage of the surveyed area and a two-step Neyman-Pearson-based decision-making process. Computer simulations show that MAS algorithm performs significantly better than lawnmower-type search and billiard-type random search. Our tests suggest that the median search time in the MAS algorithm may be inversely proportional to the number of participating searchers. As opposed to lawnmower search, the median search time in the MAS algorithm depends only logarithmically on the magnitude of uncertainty.

I. Introduction

Study of search problems using formalized mathematical models started more than 60 years ago. For a survey, see [1]. During World War II, mathematical theory was applied for the first time to locate German submarine threats in the Atlantic. Since then, the mathematics behind the practical search problems developed into search theory. In the “classical” discrete-space setting (see e.g., [2]–[8]), a target is located somewhere in a region that is partitioned into a finite number of cells. The probability distribution for the target's position (i.e., the probability that the target is in any particular cell) and the detection function of a sensor (i.e., the probability of detection versus effort spent searching a cell, given that the target resides in that cell) are given. The goal is to maximize the probability of detection of the target, assuming that the amount of total effort available for the search is fixed. A major drawback of the above setting is its discrete nature and the assumption of perfectly functioning sensors. Moreover, theoretical solutions given to the discrete space search problem assume that it is possible to move between any two cells and, thus, result in trajectories that could be physically impossible to follow.