Skip to main content
main-content

Über dieses Buch

This book begins with a review of basic results in optimal search for a stationary target. It then develops the theory of optimal search for a moving target, providing algorithms for computing optimal plans and examples of their use. Next it develops methods for computing optimal search plans involving multiple targets and multiple searchers with realistic operational constraints on search movement. These results assume that the target does not react to the search. In the final chapter there is a brief overview of mostly military problems where the target tries to avoid being found as well as rescue or rendezvous problems where the target and the searcher cooperate.

Larry Stone wrote his definitive book Theory of Optimal Search in 1975, dealing almost exclusively with the stationary target search problem. Since then the theory has advanced to encompass search for targets that move even as the search proceeds, and computers have developed sufficient capability to employ the improved theory. In this book, Stone joins Royset and Washburn to document and explain this expanded theory of search. The problem of how to search for moving targets arises every day in military, rescue, law enforcement, and border patrol operations.

Inhaltsverzeichnis

Frontmatter

Chapter 1. Introduction

Abstract
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.
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Chapter 2. Search for a Stationary Target

Abstract
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).
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Chapter 3. Search for a Moving Target in Discrete Space and Time

Abstract
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.
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Chapter 4. Path-Constrained Search in Discrete Time and Space

Abstract
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.
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Chapter 5. Search for Moving Targets in Continuous Space

Abstract
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.
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Chapter 6. Constrained Search in Continuous Time and Space

Abstract
As we recall from Chap. 4, search applications might require the consideration of constraints on the agility of the searcher. For example, in the development of real-time controllers for autonomous systems it becomes essential to account for their often limited speed, turn radii, and other performance characteristics. When such systems need to be controlled on a very fine time scale, it becomes natural to formulate these problems in continuous time. Consequently, we are faced with the problem of optimal search in continuous time and space subject to constraints. This chapter provides an introduction to the subject through the formulation of several search situations as uncertain optimal control problems. Although there are computational challenges associated with the solution of uncertain optimal control problems, they are not unsurmountable. In fact, we include a section with examples that illustrate today’s capabilities and demonstrate that practically useful solutions can be obtained in tens of minutes by standard optimization solvers. We also provide an introduction to the theory supporting such problems.
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Chapter 7. Search Games

Abstract
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.
Lawrence D. Stone, Johannes O. Royset, Alan R. Washburn

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise