Searching for a one-dimensional random walker: Deterministic strategies with a time budget when crossing is allowed

Narges Noori, Alessandro Renzaglia, Volkan Isler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

We present deterministic strategies for capturing a target performing a discrete random walk on a discretized 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 Partially Observable Markov Decision Process (POMDP) approach for finding the optimal search strategy. We also present 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 running the POMDP.

Original languageEnglish (US)
Title of host publicationIROS 2013
Subtitle of host publicationNew Horizon, Conference Digest - 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems
Pages4811-4816
Number of pages6
DOIs
StatePublished - 2013
Event2013 26th IEEE/RSJ International Conference on Intelligent Robots and Systems: New Horizon, IROS 2013 - Tokyo, Japan
Duration: Nov 3 2013Nov 8 2013

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
ISSN (Print)2153-0858
ISSN (Electronic)2153-0866

Other

Other2013 26th IEEE/RSJ International Conference on Intelligent Robots and Systems: New Horizon, IROS 2013
CountryJapan
CityTokyo
Period11/3/1311/8/13

Fingerprint Dive into the research topics of 'Searching for a one-dimensional random walker: Deterministic strategies with a time budget when crossing is allowed'. Together they form a unique fingerprint.

Cite this