Search-based Planning for Sensor-based Coverage

Abstract

Robots are excellent candidates for the dull, dirty, and dangerous jobs we do not want humans to perform. Today, these include inspection of large areas or structures, post-disaster assessment, and surveillance. Assessing the aftermath of the recent Fern Hollow bridge collapse in Pittsburgh is one such example. Many such real-world inspection or surveillance tasks can be cast as robot coverage problems. Coverage path planning (CPP) is the problem of determining a collision-free path for a robot that observes all reachable points of interest in an environment. A variant of this problem is persistent coverage, wherein coverage levels decay over time and the robot must ensure to persistently observe all points of interest over time. Further, systems performing such tasks can be extended to have actively controllable sensors or multiple robots. This thesis proposes novel motion planning methods for robots performing such tasks. Planning via graph search on state lattices has the advantages of resolution completeness and bounded suboptimality, and this is the overarching approach to motion planning we use in this thesis. We first look at a system of multiple unmanned aerial vehicles (UAVs) with fixed, downward-facing cameras persistently covering a large environment. This requires stitching together solutions to subproblems such as goal assignment, multi-agent planning, and handling kinematic and dynamic constraints of the robots. We demonstrate the effectiveness of our method on real-world field tests. Next, we look at the case of having an actively controllable onboard sensor and zoom into the problem of a single UAV actively sensing its environment while navigating towards a goal. We develop two novel search-based planners for simultaneous robot and sensor trajectory generation. The first decouples robot and sensor planning to compute solutions quickly, and the second (optionally) iteratively refines this solution in the joint robot and sensor search space. We then look at the standard CPP problem, where most popular approaches are decomposition based and require extensive pre-processing of the environment. These methods come with strong properties of completeness and optimality with respect to the corresponding objective. Decomposition-free methods are few, simpler, but heuristic or random and offer weak performance guarantees. We bridge this methodological gap with a novel, decomposition-free coverage path planner that provides completeness guarantees with minimal environment processing. Our planner leverages precomputed coverage behaviors and automatically determines where to execute them online. And finally, we tackle an important limitation of this planner: that it exhaustively evaluates all coverage behaviors online, which is prohibitively expensive with large numbers of behaviors or higher-fidelity sensor models such as ray casting. We propose a method that uses supervised learning to predict how useful a behavior will be in a given local environment, and use this to reduce the online computational burden on the planner.