Using multiple searchers in constrained-path, moving-target search problems

✍ Scribed by Robert F. Dell; James N. Eagle; Gustavo Henrique Alves Martins; Almir Garnier Santos

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 915 KB
• Volume: 43
• Category: Article
• ISSN: 0894-069X
• DOI: 10.1002/(sici)1520-6750(199606)43:4<463::aid-nav1>3.0.co;2-5

✦ Synopsis

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 problems with multiple searchers. Our optimal procedure outperforms existing approaches when used with only a single searcher. For more than one searcher, the time needed to guarantee an optimal solution is prohibitive. Our heuristics represent a wide variety of approaches: One solves partial problems optimally, two use paths based on maximizing the expected number of detections, two are genetic algorithm implementations, and one is local search with random restarts. A heuristic based on the expected number of detections obtains solutions within 2% of the best known 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. For threesearcher problems, a genetic algorithm implementation obtains the best-known solution in as little as 20% ofother heuristic solution times.