Browsing by Subject "Probabilistic search"

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
    Learning in Human and Robot Search: Subgoal, Submodularity, and Sparsity
    (2016-08) Tseng, Kuo-Shih
    Search is an essential technology for various robotic applications and it is also central to human daily activities. Searching for targets efficiently consists of NP-hard problems, but young children can search for targets very efficiently . How humans search for targets efficiently is still a mystery. Hence, two central questions are as follows: First, how do humans search for targets efficiently ? Second, how can robots learn to search like humans? The central goal of this dissertation is to explore these two questions, analyzing and modeling human search behavior and then applying the findings to robot search. This thesis is organized in three parts--human search analysis, problem reformulation, and learning in robot search. In the first part, the goal is to analyze and model human search behavior. In the experiments, human subjects remotely control a mobile robot to search for a target through teleoperation. Their search data are collected for further analysis. A novel framework consisting structure learning and K-means clustering is proposed to model and analyze humans search behavior. The analysis of the experimental data demonstrates that (1) humans are able to solve the complex search task by breaking it up into smaller tasks (so called subgoal hypothesis); and (2) humans consider both coverage and motion cost while searching. In the second part, the goal is to derive an objective function considering coverage and motion cost. The objective of search is to maximize the probability of target detection while covering most of the environment in minimum time. The robot needs to consider three objectives: (1) maximal coverage; (2) maximal probability of detection; and (3) minimum-time trajectory planning. However, all these objectives are NP-hard. Since two of these objective functions are submodular, the search problem can be reformulated as maximizing the cumulative probability of detection (PD) with motion cost. The proof shows that greedy algorithms give near-optimal subgoals with high probability. In the last part, the approach is to learn to search through sequential perception and actions. Since the PD function and cost-to-go (CTG) function depend on the environment, the robot needs to learn both the PD function and CTG function. To make the learning process of the PD function tractable, a technique based on Spatial Fourier Sparse Set (SFSS) is proposed that takes advantage of the structure in the relationship between the robot's spatial conguration and its environmental sensing. Q-learning is proposed to learn the CTG function. The learned PD and CTG functions can then be used to generate subgoals for search tasks. Based on compressed sensing theory, the proposed SFSS is able to learn a submodular function with m samples, where m <= O(klog(b)), b is the Fourier basis number and k is the number of nonzero Fourier coecients. The proposed algorithms generate near-optimal subgoals for both human and robot search experiments. Human experiments showed that the human search performance is improved with the assistance of subgoals. Robot experiments demonstrated that the robot can search for the target faster than any existing approaches. To the best of our knowledge, this is the first work that theorems and experiments prove that humans cannot outperform robots since the objective functions of search problems are submodular.