  This paper presents a novel multi-robot coverage path planning (CPP)
algorithm - aka SCoPP - that provides a time-efficient solution, with workload
balanced plans for each robot in a multi-robot system, based on their initial
states. This algorithm accounts for discontinuities (e.g., no-fly zones) in a
specified area of interest, and provides an optimized ordered list of
way-points per robot using a discrete, computationally efficient, nearest
neighbor path planning algorithm. This algorithm involves five main stages,
which include the transformation of the user's input as a set of vertices in
geographical coordinates, discretization, load-balanced partitioning,
auctioning of conflict cells in a discretized space, and a path planning
procedure. To evaluate the effectiveness of the primary algorithm, a
multi-unmanned aerial vehicle (UAV) post-flood assessment application is
considered, and the performance of the algorithm is tested on three test maps
of varying sizes. Additionally, our method is compared with a state-of-the-art
method created by Guasella et al. Further analyses on scalability and
computational time of SCoPP are conducted. The results show that SCoPP is
superior in terms of mission completion time; its computing time is found to be
under 2 mins for a large map covered by a 150-robot team, thereby demonstrating
its computationally scalability.
