Efficient Resource Allocation Schemes for Search.

Abstract

This thesis concerns the problem of efficient resource allocation under constraints. In many applications a finite budget is used and allocating it efficiently can improve performance. In the context of medical imaging the constraint is exposure to ionizing radiation, e.g., computed tomography (CT). In radar and target tracking time spent searching a particular region before pointing the radar to another location or transmitted energy level may be limited. In airport security screening the constraint is screeners' time. This work addresses both static and dynamic resource allocation policies where the question is: How a budget should be allocated to maximize a certain performance criterion.

In addition, many of the above examples correspond to a needle-in-a-haystack scenario. The goal is to find a small number of details, namely `targets', spread out in a far greater domain. The set of `targets' is named a region of interest (ROI). For example, in airport security screening perhaps one in a hundred travelers carry prohibited item and maybe one in several millions is a terrorist or a real threat. Nevertheless, in most aforementioned applications the common resource allocation policy is exhaustive: all possible locations are searched with equal effort allocation to spread sensitivity.

A novel framework to deal with the problem of efficient resource allocation is introduced. The framework consists of a cost function trading the proportion of efforts allocated to the ROI and to its complement. Optimal resource allocation policies minimizing the cost are derived. These policies result in superior estimation and detection performance compared to an exhaustive resource allocation policy. Moreover, minimizing the cost has a strong connection to minimizing both probability of error and the CR bound on estimation mean square error. Furthermore, it is shown that the allocation policies asymptotically converge to the omniscient allocation policy that knows the location of the ROI in advance. Finally, a multi-scale allocation policy suitable for scenarios where targets tend to cluster is introduced. For a sparse scenario exhibiting good contrast between targets and background this method achieves significant performance gain yet tremendously reduces the number of samples required compared to an exhaustive search.