Using multiple searchers to locate a randomly moving target
Loading...
Authors
Santos, Almir Garnier
Subjects
Advisors
Dell, Robert F.
Date of Issue
1993-09
Date
September 1993
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Distinguished Alumni Award Program author. VADM Almir Garnier Santos, Federal Republic of Brazil Navy (Presented 7 Aug 14)
Series/Report No
Department
Operations Research
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
45 p.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.