Karnad, Nikhil2015-11-092015-11-092015-09https://hdl.handle.net/11299/175532University of Minnesota Ph.D. dissertation. September 2015. Major: Computer Science. Advisor: Volkan Isler. 1 computer file (PDF); xii, 147 pages.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.enAutonomous navigationMobile telepresenceMotion planningMulti-robot target trackingPursuit-evasion gamesRobotic sensor networksThesis or Dissertation