  The line coverage problem involves finding efficient routes for the coverage
of linear features by one or more resource-constrained robots. Linear features
model environments like road networks, power lines, and oil and gas pipelines.
Two modes of travel are defined for robots: servicing and deadheading. A robot
services a feature if it performs task-specific actions, such as 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, which can be direction-dependent. The environment is modeled as a
graph, and an integer linear program is provided. As the problem is NP-hard, we
design a fast and efficient heuristic algorithm, Merge-Embed-Merge (MEM).
Exploiting the constructive property of the MEM algorithm, algorithms for line
coverage of large graphs with multiple depots are developed. Furthermore,
turning costs and nonholonomic constraints are efficiently incorporated into
the algorithm. The algorithms are benchmarked on road networks and demonstrated
in experiments with aerial robots.
