Optimal search for moving targets in continuous time and space using consistent approximations
Foraker, Joseph Carl.
Royset, Johannes O.
MetadataShow full item record
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.
Showing items related by title, author, creator and subject.
Karatas, Mumtaz; Craparo, Emily; Akman, Gülşen (Wiley, 2018-09);The problem of determining effective allocation schemes of underwater sensors for surveillance, search, detection, and tracking purposes is a fundamental research area in military operations research. Among the various ...
Royset, Johannes O.; Walton, Claire L.; Gong, Qi; Kaminer, Isaac (IFAC, 2014-08);This paper explores the potential for applying newly available numerical methods in optimal control to solve motion planning problems created by the search for targets with motion uncertainty characterized by constant ...
Chung, Timothy H.; Hollinger, Geoffrey A.; Isler, Volkan (2011-10);This paper surveys recent results in pursuitevasion and autonomous search relevant to applications in mobile robotics. We provide a taxonomy of search problems that highlights the differences resulting from varying ...