A genetic algorithm applied to planning search paths in complicated environments

We describe a genetic algorithm (GA) for designing efficient search paths, against a moving target, in complicated environments. The immediate application is acoustic search for submarines, but the technique is applicable to more general search problems, including minehunting, search-and-rescue, and non-maritime problems. The problem of optimally allocating idealized search effort against a stationary target was solved in 1946. The moving-target problem was essentially solved in 1980. Both of these solutions assume that search effort is an abstract quantity that may be allocated arbitrarily over the search space, and that the cumulative detection probability is a function of the total amount of effort applied to the target's location. There has been substantial research on branch-and-bound techniques for the discrete-path problem, where the searcher and target move in discrete space and time, the searcher can move at most one cell in any direction at each time step, and search effort is confined to the searcher's current cell. We consider the harder problem where space and time are continuous, the searcher and target must follow physically realizable paths, and detection events are governed by the actual sensor-target geometry and physics-based acoustic models. We present simple examples to illustrate that the GA produces reasonable paths in simple problems, by comparing them with intuitively obvious, (approximately) optimal paths. We also present a more complicated, realistic example in which we compare the GA-generated path with (commonly used) ladder paths (parallel, uniformly spaced sweeps in alternating directions, similar to mowing a lawn). This example indicates that the GA can achieve a significant (46%) improvement in search effectiveness (as measured by cumulative detection probability) over standard search paths.