TY - JOUR
T1 - Constrained Probabilistic Search for a One-Dimensional Random Walker
AU - Noori, Narges
AU - Renzaglia, Alessandro
AU - Hook, Joshua Vander
AU - Isler, Volkan
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/4
Y1 - 2016/4
N2 - This paper addresses a fundamental search problem in which a searcher subject to time and energy constraints tries to find a mobile target. The target's motion is modeled as a random walk on a discrete set of points on a line segment. At each time step, the target chooses one of the adjacent nodes at random and moves there. We study two detection models. In the no-crossing model, the searcher detects the target if it is on the same node or if it takes the same edge at the same time. In the crossing model, detection happens only if the target lands on the same node at the same time. For the no-crossing model, where move and stay actions may have different costs, we present an optimal search strategy under energy and time constraints. For the crossing model, we formulate the problem of designing an optimal strategy as a partially observable Markov decision process (POMDP) and solve it using methods that reduce the state-space representation of the belief. The POMDP solution reveals structural properties of the optimal solution. We use this structure to design an efficient strategy and analytically study its performance. Finally, we present preliminary experimental results to demonstrate the applicability of our model to our tracking system, which is used for finding radio-tagged invasive fish.
AB - This paper addresses a fundamental search problem in which a searcher subject to time and energy constraints tries to find a mobile target. The target's motion is modeled as a random walk on a discrete set of points on a line segment. At each time step, the target chooses one of the adjacent nodes at random and moves there. We study two detection models. In the no-crossing model, the searcher detects the target if it is on the same node or if it takes the same edge at the same time. In the crossing model, detection happens only if the target lands on the same node at the same time. For the no-crossing model, where move and stay actions may have different costs, we present an optimal search strategy under energy and time constraints. For the crossing model, we formulate the problem of designing an optimal strategy as a partially observable Markov decision process (POMDP) and solve it using methods that reduce the state-space representation of the belief. The POMDP solution reveals structural properties of the optimal solution. We use this structure to design an efficient strategy and analytically study its performance. Finally, we present preliminary experimental results to demonstrate the applicability of our model to our tracking system, which is used for finding radio-tagged invasive fish.
KW - Networked robots
KW - sensor networks
KW - surveillance systems
UR - http://www.scopus.com/inward/record.url?scp=84961344078&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84961344078&partnerID=8YFLogxK
U2 - 10.1109/TRO.2015.2513751
DO - 10.1109/TRO.2015.2513751
M3 - Article
AN - SCOPUS:84961344078
SN - 1552-3098
VL - 32
SP - 261
EP - 274
JO - IEEE Transactions on Robotics
JF - IEEE Transactions on Robotics
IS - 2
M1 - 7393596
ER -