TY - GEN
T1 - Searching for a one-dimensional random walker
T2 - 2013 26th IEEE/RSJ International Conference on Intelligent Robots and Systems: New Horizon, IROS 2013
AU - Noori, Narges
AU - Renzaglia, Alessandro
AU - Isler, Volkan
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84893760623&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84893760623&partnerID=8YFLogxK
U2 - 10.1109/IROS.2013.6697050
DO - 10.1109/IROS.2013.6697050
M3 - Conference contribution
AN - SCOPUS:84893760623
SN - 9781467363587
T3 - IEEE International Conference on Intelligent Robots and Systems
SP - 4811
EP - 4816
BT - IROS 2013
Y2 - 3 November 2013 through 8 November 2013
ER -