Using Multiple Searchers to Locate a Randomly Moving Target
Abstract
The need to search effectively for objects presents itself in many civilian and military applications. This thesis develops and tests six heuristics and an optimal branch and bound procedure to solve the heretofore uninvestigated problem of searching for a Markovian moving target using multiple searchers. For more than one searcher, the time needed to guarantee an optimal solution for the problems considered is prohibitive. The heuristics represent a wide variety of approaches and consist of two based on the expected number of detections, two genetic algorithm implementations, one based on solving partial problems optimally, and local search. A heuristic based on the expected number of detections obtains solutions within two percent of the best known solution for each one, two, and three searcher test problem considered. For one and two searcher problems, the same heuristic's solution time is less than that of other heuristics considered. A Genetic Algorithm implementation performs acceptably for one and two searcher problems and highlights its ability, effectively solving three searcher problems in as little as 20% of, other heuristic run- times.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 23, 1993
- Accession Number
- ADA275602
Entities
People
- Almir G. Santos
Organizations
- Naval Postgraduate School