Search Path Optimization for UAVs Using Stochastic Sampling with Abstract Pattern Descriptors
Vitaly Ablavsky, Daniel W. Stouch, Magnús S. Snorrason · AIAA Guidance, Navigation, and Control Conference and Exhibit · 2003
The problem of generating the optimal search path for an unmanned aerial vehicle to locate a potentially moving target is of importance in many civilian and military applications. Search-and-rescue in open sea or in sparsely-populated areas and search missions for previously-spotted enemy targets are just a few examples. Few algorithms exist for solving this problem, and our solution is novel in that it combines the optimal allocation of search effort with the actual computation of trajectories that a searcher must (and physically can) follow. Our approach exploits the target’s spatial mobility constraints to derive accurate regions of interest, and then utilizes the geometric properties of a region of interest to decompose the overall search problem into a set of simpler search problems. Our approach involves applying computational geometry methods to partition the complex search region into minimallyoverlapping compact sub-regions. This enables closed-form computation of a flight trajectory for each sub-region, such that path length is min imized while full coverage is guaranteed and constraints of the airframe and sensor are met. The novelty of our solution described in this paper lies in how we optimize the global sequencing of individual trajectories into a complete near-optimal search path that covers the whole complex search region. We use the concept of abstract pattern descriptors to simplify the representation of each search pattern. A stochastic Metropolis sampling approach with Markov random fields is then used in conjunction with a simulated annealing algorithm to derive the near optimal global search path for each isochronal contour.