Searching for a One-Dimensional Random Walker: Deterministic Strategies with a Time Budget When Crossing is Allowed

Abstract

We present deterministic strategies for capturing a target taking a discrete random walk on a line segment. The searcher has a limited time budget. Its goal is to maximize the probability of capturing the target within the budget. A challenging aspect of our model is that the target can cross the searcher without being captured when they take the same edge at the same time in opposite directions. We present a POMDP approach for finding the optimal search strategy, as well as an efficient approximate solution to the POMDP. The strategies found by this approach reveal structural properties of the efficient search strategies which we exploit to solve the problem efficiently without the POMPD.