Exact, Approximate, and Metaheuristic Techniques for Discrete Search Problems

Abstract

This work analyzes three search problems. The first study is the Path-Constrained Trail-Based Moving Target Problem (PCTBMT), a new variant of the moving target problem where the objective is to detect a target that leaves a trail of detectable material, such as the scent trails, that can be detected by sensors like roving canine search teams. The problem accounts for the trail's decay over time, the target's movement across the pre-defined area and assumes no false negative detection errors. We only consider methods that do not require a commercial solver for this chapter and we apply the standard branch-and-bound method from the moving-target problem to our trail-based variant. We systematize the design of longest-path bounds from the literature within a common framework. We formulated another bound, which we call SCENPROD. Additionally, we introduce and demonstrate the versatility of an Ant Colony Optimization (ACO) algorithm for heuristically solving the PCTBMT problem, devising a reward function tailored towards search problems. To show the value of the ACO algorithm, we present several computational examples and examine the performance metrics of the exact methods we adapted to the problem as well as compare against a myopic heuristic search strategy. We provide results for ACO's performance in simplistic search spaces and for a large-scale case designed to represent Auburn University. The intended practical application of the model is in security and law-enforcement operations with canines, where optimal search strategies are essential for resource-limited scenarios.

The second problem is resource-constrained sequential discrete search for a stationary target. The problem formulation that is put forward generalizes the traditional version of the discrete sequential search by allowing for dependence between the search areas; that is, the probability of detection when searching an area given the target is in the area (the glimpse probability) depends on which areas have been searched previously. The search effort is also discrete, meaning we cannot arbitrarily divide the search effort. The direct application of this appears when search areas overlap with one another. We call this problem the window search as it is reminiscent of viewing the same area through different windows giving a different view of the same region. We show how to compute the probability of detection with overlapping search areas and analyze the increase in complexity due to the overlap. We explore the relationship between the optimal allocation and what we refer to as the $\textbf{z}$-dominant search sequence, a property that is a resource-constrained version of uniformly optimal search sequences. Two exhaustive algorithms, a branch-and-bound algorithm, and a two-stage algorithm that utilizes a combination of the nonlinear integer programming solver and the exhaustive algorithms are described. All but the two stage method solve for the optimal allocation and in doing so simultaneously solve for the $\textbf{z}$-dominant search sequence. We show three use-cases and analyze the performance of the three algorithms.

The final problem is an extension of the stationary window search. By adding a graph structure onto the set of windows, we formulate and model the Path Constrained Window Search. In this Chapter, we consider linearization methods that utilize commercial mixed integer linear programming solvers. We describe four methods for solving the linearized version, three are adapted from the moving target literature and the fourth is a standard piecewise linear approximation of a convex objective using SOS2 constraints. Two of the three methods from the literature are exact under the assumption that the glimpse rate can be quantized into integer segments, and thus are approximations if this is not the case. We analyze the error in the objective induced by the approximations, and we give procedures for limiting it. Finally, we consider a complicating constraint that can arise in a search context, which is a region cover constraint. This added constraint requires every possible search region to be searched at least once, and we show that the methods proposed here appear to handle the added constraint quite well.