Between Dec 19, 2024 and Jan 2, 2025, datasets can be submitted to DRUM but will not be processed until after the break. Staff will not be available to answer email during this period, and will not be able to provide DOIs until after Jan 2. If you are in need of a DOI during this period, consider Dryad or OpenICPSR. Submission responses to the UDC may also be delayed during this time.
 

Constrained Probabilistic Search for a One-Dimensional Random Walker

Loading...
Thumbnail Image

View/Download File

Persistent link to this item

Statistics
View Statistics

Journal 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

Technical Report; 15-021

Funding information

Isbn identifier

Doi identifier

Previously Published Citation

Other identifiers

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.