Optimal Search for Moving Targets

The problem of how to search for a moving target arises every day. Search problems arise in military, rescue, law enforcement, and border patrol operations. In military operations, the searchers may be aircraft looking for suspected individuals or downed pilots in an area of interest. The U. S. Navy has a long history of planning searches for adversarial submarines. Park rangers may search for lost hikers. Almost every day someone is lost in a wilderness or rural area, and volunteer search and rescue groups plan and execute searches to find them – Koester (2008). In a damaged or burning building, fire fighters and ground robots may search for trapped individuals. Law enforcement officers may act as searchers when looking for criminals. Near national borders, the searchers may be border patrols seeking illegal immigrants. The searchers may also be Coast Guard cutters and helicopters scanning the ocean for smugglers.

Many algorithms for computing optimal search plans for a moving target rely on being able to compute optimal plans for a stationary target. This chapter provides an overview of the standard models and results for optimal search for a stationary target. It discusses search sensors and some basic notions of detection modeling, including lateral range curves, sweep widths, and detection functions. It defines the search space and the prior distribution on target location in discrete and continuous space. It develops methods for finding search plans that maximize the probability of detecting the target by a fixed time and explores related optimal search problems such as minimizing the mean time to find the target. It presents algorithms that may be used to compute optimal plans in most cases. Optimal search for a stationary target is covered more extensively in Stone (2007).

This chapter develops methods for finding optimal search plans for a target that is moving in discrete space and time. In the case where the detection function is exponential, optimal moving target plans can be obtained by computing a sequence of optimal stationary target plans. The algorithm developed to find these plans is a special case of the more general Forward-And-Backward (FAB) algorithm which is also presented in this chapter.

In some practical situations, a searcher might have difficulties with implementing an optimal search plan of the form stipulated in the previous chapters. The plan might call for an instantaneous shift of search effort from one time period to the next. If the searcher requires a significant amount of time to carry out this shift, a relatively fast moving target would “get ahead” of the searcher. This situation is especially prevalent in robotic searches of buildings, where transit from room to room accounts for the majority of time expenditure, and searches using low-speed unmanned aerial systems, where the ratio of searcher speed to target speed is low. In this chapter, we describe methods for computing optimal search plans while accounting for real-world constraints on the agility of the searcher. In fact, we consider multiple searchers, each providing a discrete search effort, as well as multiple targets. The chapter starts, however, with the simpler situation of a single searcher looking for a single target. We formulate the optimal search problem as that of finding the optimal searcher path and describe a branch-and-bound algorithm for its solution. We proceed by generalizing the formulation to account for a searcher that operates at different “altitudes” with a more complex sensor. We also describe algorithmic enhancements that both handle the more general situation and provide computational speed-ups. The chapter then addresses the situation with multiple searchers, first of identical types and second of different types and also with multiple targets. These generalizations are most easily handled within a mathematical programming framework, which facilitates the consideration of a multitude of constraints including those related to airspace deconflication and also allows the leverage of well-developed optimization solvers for the determination of optimal searcher plans. The chapter ends with a description of some algorithms behind these solvers, with an emphasis on cutting-plane methods. Throughout the chapter we remain in the context of discrete time and space search.

In Chap. 3, we found optimal search allocations for problems that take place in discrete space and time. For the most part, algorithms for computing these allocations are limited to exponential detection functions.

So far in this book we have essentially assumed that the target is either indifferent to the outcome or unable to influence it. Any uncertainty about target location has been in accord with a stochastic model of some kind that the searcher understands. If there is uncertainty about initial location, as in Chap. 2, then a probability distribution for that location has been given. If there is also uncertainty about subsequent movement, as in later chapters, then a probability law for that motion has also been given. But the target of search might have an opinion about whether being found is actually a desirable outcome, and might also be able to influence it. In this chapter we will consider the target to be sentient, making his choices about location and movement to either discourage detection (Sect. 7.1) or encourage it (Sect. 7.2). The searcher will know the target’s capabilities, but not his habits or intentions, so probability laws for the target’s location and movement will be missing.