Constrained Probabilistic Search for a One-Dimensional Random Walker
Loading...
View/Download File
Persistent link to this item
Statistics
View StatisticsJournal Title
Journal ISSN
Volume Title
Title
Constrained Probabilistic Search for a One-Dimensional Random Walker
Published Date
2015-12-21
Publisher
Type
Report
Abstract
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 the line: 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
they are on the same node or if they take the same edge at the same
time. In the crossing model, detection happens only if they land 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 which 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.
Keywords
Description
Related to
Replaces
License
Series/Report Number
Funding information
Isbn identifier
Doi identifier
Previously Published Citation
Suggested citation
Noori, Narges; Renzaglia, Alessandro; Vander Hook, Joshua; Isler, Volkan. (2015). Constrained Probabilistic Search for a One-Dimensional Random Walker. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/215986.
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.