Noori, Narges2016-04-142016-04-142016-02https://hdl.handle.net/11299/178937University of Minnesota Ph.D. dissertation. February 2016. Major: Computer Science. Advisor: Volkan Isler. 1 computer file (PDF); xi, 189 pages.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.enAlgorithmEnvironmental monitoringMotion planningProbabilistic searchPursuit-evasion gamesRoboticsThesis or Dissertation