Files
Abstract
Recent technological advances have facilitated the use of mobile robots for a wide range of coverage applications such as inspection and mapping of infrastructure, precision agriculture, and disaster management. With the proliferation of these tasks comes an increasing need for autonomous systems to efficiently gather data for analyzing the state of the environment. The dissertation answers the following fundamental question: How should resource-constrained robots traverse the environment to collect data from all the relevant features? These features of interest can be represented as points, lines or curves, and areas. This dissertation unifies simultaneous coverage of all three types of features into a novel generalized coverage framework, develops algorithms for efficient coverage using multiple mobile robots, and validates them in experiments.The dissertation first comprehensively studies the line coverage problem, i.e., coverage of one-dimensional features with multiple resource-constrained robots. We model the environment as a graph and formalize line coverage as an optimization problem using integer linear programs (ILP). The problem is NP-hard, and therefore we design approximation algorithms with provable guarantees and heuristic algorithms for large graphs, validating them extensively in simulations and experiments. Extensions to the formulation and algorithms address large-scale environments and nonholonomic robots that cannot make point turns. These formulations of the line coverage problem lay the foundation for generalized coverage. Next, we show that we can transform the area coverage problem into a line coverage problem using computational geometry techniques and then generate routes using line coverage algorithms. Existing methods have significant inefficiencies due to their use of monotone polygons. Using the line coverage transformation allows polygons with obstacles that are not monotone while minimizing the number of turns for the robots. The transformation enables algorithmic advances in line coverage to be directly applied to area coverage. Finally, we formulate the generalized coverage problem and solve it by transforming both point and area features into line features in a unified framework. The algorithms demonstrate significantly improved performance over state-of-the-art solutions while additionally incorporating battery life constraints, nonholonomic robots, and multiple home locations for large-scale environments. We evaluate the performance of the algorithms on several real-world datasets in simulations and experiments. The algorithms are very fast and generate high-quality solutions for robotics applications.