Using Prize-Collection Concepts to Solve Time-Limited Search Problems: A Military and Security Case Study

We establish a framework that links time-limited search problems with prize-collection problems. The searcher’s objective is to travel a path with a particular origin and destination so that the probability of finding the entity within the available time budget is maximized. As the searcher traverses the network, they learn more about their surroundings. Hence, the a priori probabilities need to be updated so that the searcher can choose the next moves using real-time data. Other variants of the base search problem are also studied, including searching for two immobile entities with (in)dependent locations and searching for an unknown number of entities. Our theoretical analysis demonstrates that learning does not occur in the base search problem. Thus, it is the same as the prize-collection problem and can be solved to optimality. Conversely, after mapping the other extensions to the prize-collection problem, finding the optimal solution is not guaranteed due to the presence of learning. Computational experiments as well as a military and security case study are presented at the end, the latter taking practical considerations, including uncertainties in traveling times and collaboration between multiple searchers into account.