  Line coverage is to cover linear infrastructure modeled as 1D segments by
robots, which received attention in recent years. With the increasing
urbanization, the area of the city and the density of infrastructure continues
to increase, which brings two issues: (1) Due to the energy constraint, it is
hard for the homogeneous robot team to cover the large-scale linear
infrastructure starting from one depot; (2) In the large urban scene, the
imbalance of robots' path greatly extends the time cost of the multi-robot
system, which is more serious than that in smaller-size scenes. To address
these issues, we propose a heterogeneous multi-robot approach consisting of
several teams, each of which contains one transportation robot (TRob) and
several coverage robots (CRobs). Firstly, a balanced graph partitioning (BGP)
algorithm is proposed to divide the road network into several similar-size
sub-graphs, and then the TRob delivers a group of CRobs to the subgraph region
quickly. Secondly, a balanced ulusoy partitioning (BUP) algorithm is proposed
to extract similar-length tours for each CRob from the sub-graph. Abundant
experiments are conducted on seven road networks ranging in scales that are
collected in this paper. Our method achieves robot utilization of 90% and the
best maximal tour length at the cost of a small increase in total tour length,
which further minimizes the time cost of the whole system. The source code and
the road networks are available at
https://github.com/suhangsong/BLC-LargeScale.
