Browsing by Author "Noori, Narges"

Now showing 1 - 11 of 11
  • Thumbnail Image
    Item
    A Pursuit-Evasion Toolkit
    (2015-07-24) Noori, Narges; Beveridge, Andrew; Isler, Volkan
    This tutorial contains tools and techniques for designing pursuit and evasion strategies. The material targets a diverse audience including STEM educators as well as robotics researchers interested in applications of pursuit-evasion games. We start with a simple "lion and man" game in a square environment which should be accessible to anyone with a high-school level background on geometry and trigonometry. We then visit various versions of this game with increasing complexity. Rather than surveying specific results for specific environments, the tutorial highlights broadly applicable techniques and strategies. It also includes exercises for STEM educators as well as open problems for robotics researchers.
  • Thumbnail Image
    Item
    Adversarial and Stochastic Search for Mobile Targets in Complex Environments
    (2016-02) Noori, Narges
    A new era of robotics has begun. In this era, robots are coming out of simple, structured environments (such as factory floors) into the real world. They are no longer performing simple, repetitive tasks. Instead, they will soon be operating autonomously in complex environments filled with uncertainties and dynamic interactions. Many applications have already emerged as a result of these potential advances. A few examples are precision agriculture, space exploration, and search-and-rescue operations. Most of the robotics applications involve a ``search'' component. In a search mission, the searcher is looking for a mobile target while the target is avoiding capture intentionally or obliviously. Some examples are environmental monitoring for population control and behavioral study of animal species, and searching for victims of a catastrophic event such as an earthquake. In order to design search strategies with provable performance guarantees, researchers have been focusing on two common motion models. The first one is the adversarial target model in which the target uses best possible strategy to avoid capture. The problem is then mathematically formulated as a pursuit-evasion game where the searcher is called the ``pursuer'' and the target is referred to as the ``evader''. In pursuit-evasion games, when a pursuit strategy exists, it guarantees capture against any possible target strategy and, for this reason, can be seen as the worst-case scenario. Considering the worst-case behavior can be too conservative in many practical situations where the target may not be an adversary. The second approach deals with non-adversarial targets by modeling the target's motion as a stochastic process. In this case, the problem is referred to as one-sided probabilistic search for a mobile target, where the target cannot observe the searcher and does not actively evade detection. In this dissertation, we study both adversarial and probabilistic search problems. In this regard, the dissertation is divided into two main parts. HASH(0x7f7fa33ea740) HASH(0x7f7fa33dadd8) In the first part, we focus on pursuit-evasion games, i.e., when the target is adversarial. We provide capture strategies that guarantee capture in finite time against any possible escape strategy. Our contributions are mainly in two areas whether the players have full knowledge of each other's location or not. First, we show that when the pursuer has line-of-sight vision, i.e., when the pursuer sees the evader only when there are no obstacles in the between them, it can guarantee capture in monotone polygons. Here, the pursuer must first ensure that it ``finds'' the evader when it is invisible by establishing line-of-sight visibility, and then it must guarantee capture by getting close to the evader within its capture distance. In our second set of results, we focus on pursuit-evasion games on the surface of polyhedrons assuming that the pursuers are aware of the location of the evader at all times and their goal is to get within the capture distance of the evader. HASH(0x7f7fa33f6a00) In the second part, we study search strategies for finding a random walking target. We investigate the search problem on linear graphs and also 2-D grids. Our goal here is to design strategies that maximize the detection probability subject to constraints on the time and energy, which is available to the searcher. We then provide field experiments to demonstrate the applicability of our proposed strategies in an environmental monitoring project where the goal is to find invasive common carp in Minnesota lakes using autonomous surface/ground vehicles.
  • 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
    Lion and Man with Visibility in Monotone Polygons
    (2012-02-24) Noori, Narges
    In the original version of the lion and man game, a lion tries to capture a man who is trying to escape in a circular arena. The players have equal speeds. They can observe each other at all times. We study a new variant of the game in which the lion has only line-of-sight visibility. Hence, it can observe the man's position only if the line segment connecting them does not intersect the boundary. We show that despite this limitation the lion can still capture the man in any monotone polygon in finite time.
  • 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
    Navigation Around an Unknown Obstacle for Autonomous Surface Vehicles Using a Forward-Facing Sonar
    (2015-04-16) Plonski, Patrick A.; Vander Hook, Joshua; Peng, Cheng; Noori, Narges; Isler, Volkan
    A robotic boat is moving between two points when it encounters an obstacle of unknown size. The boat must find a short path around the obstacle to resume its original course. How should the boat move when it can only sense the proximity of the obstacle, and does not have prior information about the obstacle’s size? We study this problem for a robotic boat with a forward-facing sonar. We study two versions of the problem. First, we solve a simplified case when the obstacle is a rectangle of known orientation but unknown dimensions. Second, we study a more general case where an arbitrarily shaped obstacle is contained between two known parallel lines. We study the performance of the algorithms analytically using competitive analysis and present results from field experiments. The experimental setup is relevant for harbor patrol or autonomous navigation in shallow water.
  • Thumbnail Image
    Item
    Revised: The Lion and Man Game on Convex Terrains
    (2014-08-27) Noori, Narges
    We study the well-known lion-and-man game in which a lion (the pursuer) tries to capture a man (the evader). The players have equal speed and they can observe each other at all times. In this paper, we study the game on the surface of convex terrains. We show that the lion can capture the man in finite number of steps which is a function of the terrain geometry.
  • 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.
  • Thumbnail Image
    Item
    The Lion and Man Game on Convex Terrains
    (2013-09-13) Noori, Narges
    We study the well-known lion-and-man game in which a lion (the pursuer) tries to capture a man (the evader). The players have equal speeds and they can observe each other at all times. While the game is well-studied in two dimensional domains such as polygons, very little is known about its properties in higher dimensions. In this paper, we study the lion and man game on the surface of convex terrains. We show that the lion can capture the man in a finite number of steps which is a function of the terrain geometry.
  • Thumbnail Image
    Item
    The Lion and Man Game on Polyhedral Surfaces with Boundary
    (2014-02-06) Noori, Narges
    We study the lion-and-man game in which a group of lions (the pursuers) try to capture a man (the evader). The players have equal speed. They can observe each other at all times. While the game is well-studied in two dimensional domains such as polygons, very little is known about its properties in higher dimensions. In this paper, we study the lion and man game when played on the surface of a three-dimensional solid represented as a polyhedron with boundary. We show that three lions with non-zero capture distance $delta$ can capture the man in finite time $O((frac{A}{delta^2} + frac{L}{delta})^2 frac{delta}{2})$ where $A$ is the area of the surface, and $L$ is the total edge length of the surface.