Line Coverage with Multiple Robots: Algorithms and Experiments

The line coverage problem is to find efficient routes for coverage of linear features by one or more resource-constrained robots. Linear features model environments such as road networks, power lines, and oil and gas pipelines. We define two modes of travel for robots: servicing and deadheading. A robot services a feature if it performs task-specific actions, e.g., taking images, as it traverses the feature; otherwise, it is deadheading. Traversing the environment incurs costs (e.g., travel time) and demands on resources (e.g., battery life). Servicing and deadheading can have different cost and demand functions, and we further permit them to be direction dependent. We model the environment as a graph and provide an integer linear program. As the problem is NP-hard, we develop a fast and efficient heuristic algorithm, Merge-Embed-Merge (MEM). By exploiting the constructive property of the MEM algorithm, we develop algorithms for line coverage of large graphs with multiple depots. Furthermore, we efficiently incorporate turning costs and nonholonomic constraints into the algorithm. We benchmark the algorithms on road networks and demonstrate them in experiments using aerial robots.