Publication:
Optimal search for moving targets in continuous time and space using consistent approximations

Loading...
Thumbnail Image
Authors
Foraker, Joseph Carl.
Subjects
Search theory
Continuous time-and-space search
Consistent approximations
Generalized optimal control
Adaptive discretization
Polynomial fitting
Rate of convergence
Small boat defense
Force protection
Advisors
Royset, Johannes O.
Date of Issue
2011-09
Date
September 2011
Publisher
Monterey, California. Naval Postgraduate School
Language
Abstract
We show how to formulate many continuous time-and-space search problems as generalized optimal control problems, where multiple searchers look for multiple targets. Speci cally, we formulate problems in which we minimize the probability that all of the searchers fail to detect any of the targets during the planning horizon, and problems in which we maximize the expected number of targets detected. We construct discretization schemes to solve these continuous time-and-space problems, and prove that they are consistent approximations. Consistency ensures that global minimizers, local minimizers, and stationary points of the discretized problems converge to global minimizers, local minimizers, and stationary points, respectively, of the original problems. We also investigate the rate of convergence of algorithms based on discretization schemes as a computing budget tends to in nity. We provide numerical results to show that our discretization schemes are computationally tractable, including examples with three searchers and ten targets. We develop three heuristics for real-time search planning, one based on our discretization schemes, and two based on polynomial tting methods, and compare the three methods to determine which solution technique would be best suited for use onboard unmanned platforms for automatic route generation for search missions.
Type
Description
Series/Report No
Department
Operations Research
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
xvi, 172 p. : col. ill. ; 28 cm.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections