Browsing by Subject "Pursuit-evasion games"

Now showing 1 - 2 of 2
  • 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
    Robot Motion Planning for Tracking and Capturing Adversarial, Cooperative and Independent Targets
    (2015-09) Karnad, Nikhil
    The last ten years have seen robots become smaller, lighter and more maneuverable than ever before, paving the way for their use in the service sector, and even in our homes. A key aspect that elevates a network of robots over a bed of sensors is the ability of individual units to autonomously navigate, forming a sensor-actuator network. These added degrees of freedom demand that we revisit existing motion planning and navigation algorithms and extend them to be able to better contribute to the services they are designed to provide. In deploying autonomous robots away from laboratory-controlled settings and in to real-world environments, care must be taken because they share their space with other autonomous agents. For instance, a typical home robot has to account for people as well as their pets. Imparting a fair degree of autonomy to robot navigation tasks thus requires reasoning about the mobility of other entities in the path-planning process. This is not a trivial task because such agents can not often be easily characterized or quantified, e.g. human navigation depends on many factors including the perception of hazards, experience from long-term memory, even whim. In this thesis, we take a deep look at the role of the information available to path-planning algorithms in the context of the mobile target-tracking problem. We start with the problem formulation (Chapter 2), in which robots need to keep track of a single mobile target for as long a duration of time as possible. In the game-theoretic sense, the information available to the target has a different characteristic than the information available to the robots. For example, target behavior varies from adversarial ones in defense applications to cooperative ones in service applications. In the chapters that follow, we present the main contributions of this thesis with this role of information during the path-planning process being the common thread. Traditional surveillance applications assume the worst-case – the target is an adversary actively trying to escape from the robots. We model this strategic interaction with the theory of pursuit-evasion games, wherein a robot pursues a target, which in turn tries to evade it. We study a mathematical variant of the Lion and Man game in the presence of an obstacle, and show that the final outcome of whether the lion can track down the man depends, in closed form, on the initial conditions (Chapter 3). We derive optimal player strategies that work regardless of what the other player does, thus providing the worst-case guarantees that such applications demand. At the opposite end of the spectrum, there exist service applications where the target’s trajectory is known to the robots before they need to move. Our motivating example is mobile telepresence, or virtual presence – an emerging technology that enables people to participate in environments they are not physically present in. Specifically, we present a navigation algorithm for a first-of-its-kind person-following robot with telepresence and monitoring applications (Chapter 4). We require that in the presence of another person, the robot should ensure a safe distance by following that person’s path without losing track. We present a heuristic planning approach that accounts for both non-holonomic constraints and trajectory smoothness. Further, a control-theoretic implementation is provided. Targets that navigate autonomously usually do so with their own intentions. While it is uncertain how they navigate, their behavior may neither be adversarial, nor completely known to the robots in advance. We present a novel data-driven probabilistic mobility model that can be used by path planners to reason about the uncertainties in decisions made by an individual who is navigating in an indoor environment (Chapter 6). We show that it is possible to preserve long temporal histories over an abstracted representation of the environment, which helps predict future mobility of the target better than previous approaches. We present a multi-robot planning algorithm that builds off of this model. Although our algorithm is designed for long-term planning and offline solution, we are able to execute the robot paths in real-time, and demonstrate extended utility with simulations. We discuss the architecture of a complete system implementation for the telepresence application, including both hardware design and software development (Chapter 8). With an increasing aging population in the U.S., it is our belief that such a system would become relevant in the near future, e.g., to assisted living facilities for purposes of healthcare monitoring.