Optimal search for a moving target - A geometric approach

The problem of optimal (or near-optimal) exhaustive search for a moving target is of importance in many civilian and military applications. Search-andrescue in open sea or in sparsely-populated areas and search missions for previously-spotted enemy targets are just a few examples. Yet, few known algorithms exist for solving this problem and none of them combine the optimal allocation of search effort with the actual computation of trajectories that a searcher must (and physically can) follow. We propose a divide-andconquer geometric approach for constructing optimal search paths for arbitrarily-shaped regions of interest. The technique is both generalizable to multiple search agents and extensible in that additional real-life search requirements (maneuverability constraints, additional information about the sensor, etc.) can be incorporated into the existing framework. Another novelty of our approach is the ability to optimally deal with a search platform which, due to design constraints, can only perform detection while moving along straight-line sweeps.