  Line coverage is the task of servicing a given set of one-dimensional
features in an environment. It is important for the inspection of linear
infrastructure such as road networks, power lines, and oil and gas pipelines.
This paper addresses the single robot line coverage problem for aerial and
ground robots by modeling it as an optimization problem on a graph. The problem
belongs to the broad class of arc routing problems and is closely related to
the rural postman problem (RPP) on asymmetric graphs. The paper presents an
integer linear programming formulation with proofs of correctness. Using the
minimum cost flow problem, we develop approximation algorithms with guarantees
on the solution quality. These guarantees also improve the existing results for
the asymmetric RPP. The main algorithm partitions the problem into three cases
based on the structure of the required graph, i.e., the graph induced by the
features that require servicing. We evaluate our algorithms on road networks
from the 50 most populous cities in the world, consisting of up to 730 road
segments. The algorithms, augmented with improvement heuristics, run within 3s
and generate solutions that are within 10% of the optimum. We experimentally
demonstrate our algorithms with commercial UAVs.
