Using multiple searchers to locate a randomly moving target
Santos, Almir Garnier
Dell, Robert F.
MetadataShow full item record
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.
Distinguished Alumni Award Program author. VADM Almir Garnier Santos, Federal Republic of Brazil Navy (Presented 7 Aug 14)
Showing items related by title, author, creator and subject.
Lidbetter, Thomas; Lin, Kyle Y. (2017-10-15);Many practical search problems concern the search for multiple hidden objects or agents, such as earthquake survivors. In such problems, knowing only the list of possible locations, the Searcher needs to find all the ...
Bothwell, Brian P. (Monterey, California. Naval Postgraduate School, 1990-03);Cumulative search-evasion games (CSEGs) involve two players, a searcher and an evader, who move among some finite set of cells. Neither player is aware of the other player's position during any stage of the game. When the ...
Dell, Robert F.; Eagle, James N.; Martins, Gustavo Henrique Alves; Santos, Almir Garnier (1996);The search theory open literature has paid little, if any, attention to the multiple-searcher, moving-target search problem. We develop an optimal branch-and-bound procedure and six heuristics for solving constrained-path ...