  We investigate time-optimal Multi-Robot Coverage Path Planning (MCPP) for
both unweighted and weighted terrains, which aims to minimize the coverage
time, defined as the maximum travel time of all robots. Specifically, we focus
on a reduction from MCPP to Min-Max Rooted Tree Cover (MMRTC). For the first
time, we propose a Mixed Integer Programming (MIP) model to optimally solve
MMRTC, resulting in an MCPP solution with a coverage time that is provably at
most four times the optimal. Moreover, we propose two suboptimal yet effective
heuristics that reduce the number of variables in the MIP model, thus improving
its efficiency for large-scale MCPP instances. We show that both heuristics
result in reduced-size MIP models that remain complete (i.e., guaranteed to
find a solution if one exists) for all MMRTC instances. Additionally, we
explore the use of model optimization warm-startup to further improve the
efficiency of both the original MIP model and the reduced-size MIP models. We
validate the effectiveness of our MIP-based MCPP planner through experiments
that compare it with two state-of-the-art MCPP planners on various instances,
demonstrating a reduction in the coverage time by an average of 27.65% and
23.24% over them, respectively.
