Browsing by Author "Renzaglia, Alessandro"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Constrained Probabilistic Search for a One-Dimensional Random Walker
    (2015-12-21) Noori, Narges; Renzaglia, Alessandro; Vander Hook, Joshua; Isler, Volkan
    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.
  • Thumbnail Image
    Item
    Long-Term Search Through Energy Efficiency and Harvesting
    (2013-01-09) Noori, Narges; Plonski, Patrick A.; Renzaglia, Alessandro; Tokekar, Pratap; VanderHook, Joshua
    We study a search problem motivated by our ongoing work on finding radio-tagged invasive fish with an Autonomous Surface Vehicle (ASV). We focus on settings where the fish tend to move along the boundary of a lake. This setting allows us to formulate the problem as a one-dimensional search problem in which the searcher chooses between station keeping and moving so as to maximize the probability of finding the target in a given amount of time without violating its energy-budget. We model the movement of the target as a random-walk and present a closed-form solution for this search problem. Next, we investigate how long-term autonomy can be enabled by energy harvesting. In this case, the search strategy should incorporate the amount of solar energy available at a particular location and particular time. We show how this quantity can be predicted by estimating the geometry of the tree line along the shore. We then obtain the optimal strategy which maximizes the probability of finding the target by formulating the problem as finding the optimal strategy for a Markov Decision Process. Data collected from field experiments validate our approach.
  • Thumbnail Image
    Item
    Searching for a One-Dimensional Random Walker: Deterministic Strategies with a Time Budget When Crossing is Allowed
    (2013-03-20) Noori, Narges; Renzaglia, Alessandro
    We present deterministic strategies for capturing a target taking a discrete random walk on a 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 POMDP approach for finding the optimal search strategy, as well as 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 the POMPD.
  • Thumbnail Image
    Item
    Searching for a One-Dimensional Random Walker: Randomized Strategy with Energy Budget
    (2013-03-20) Renzaglia, Alessandro; Noori, Narges
    In this paper we study the the problem of designing search strategies to find a target whose motion is described by a random walk along a one-dimensional bounded environment. The sensing model and the characteristic of the environment require the searcher and the target to be on the same site at the same time to guarantee capture. The objective is to optimize the searcher's motion, given by a sequence of actions (move right, left or remain stationary), so that the probability of capturing the target is maximized. Each action is associated with an energy cost. The searcher strategy is constrained by a total energy budget. We propose a class of randomized strategies for which we provide an analytical expression for the capture probability as a function of a single parameter. We then use this expression to find the best strategy within this class. In addition to theoretical results, the algorithms are analyzed in simulation and compared with other intuitive solutions.