Searching for a One-Dimensional Random Walker: Deterministic Strategies with a Time Budget When Crossing is Allowed
2013-03-20
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Searching for a One-Dimensional Random Walker: Deterministic Strategies with a Time Budget When Crossing is Allowed
Authors
Published Date
2013-03-20
Publisher
Type
Report
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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Noori, Narges; Renzaglia, Alessandro. (2013). Searching for a One-Dimensional Random Walker: Deterministic Strategies with a Time Budget When Crossing is Allowed. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215912.
Content distributed via the University Digital Conservancy may be subject to additional license and use restrictions applied by the depositor. By using these files, users agree to the Terms of Use. Materials in the UDC may contain content that is disturbing and/or harmful. For more information, please see our statement on harmful content in digital repositories.