Optimal Search for Moving Targets in Continuous Time and Space using Consistent Approximations

摘要

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.