MSTC
∗
:Multi-robot Coverage Path Planning under Physical Constraints
Jingtao Tang, Chun Sun and Xinyu Zhang
Abstract— For large-scale tasks, coverage path planning
(CPP) can benefit greatly from multiple robots. In this paper,
we present an efficient algorithm MSTC
∗
for multi-robot
coverage path planning (mCPP) based on spiral spanning
tree coverage (Spiral-STC). Our algorithm incorporates strict
physical constraints like terrain traversability and material load
capacity. We compare our algorithm against the state-of-the-
art in mCPP for regular grid maps and real field terrains in
simulation environments. The experimental results show that
our method significantly outperforms existing spiral-STC based
mCPP methods. Our algorithm can find a set of well-balanced
workload distributions for all robots and therefore, achieve the
overall minimum time to complete the coverage.
I. INTRODUCTION
Coverage path planning (CPP) is the problem of deter-
mining a set of paths that cover the area of interest while
avoiding obstacles[1]. Coverage path planning has many
indoor and outdoor robotic applications, such as vacuum
cleaning robots[2], autonomous underwater vehicles[3], un-
manned aerial vehicles[4], demining robots[5], automated
harvesters[6], planetary exploration[7], search and rescue
operations[8], lawn mowers[9], massive afforestation[10].
Coverage path planning has been received a lot of
attention in robotics and there are a considerable re-
search work addressing this problem[1]. This includes cel-
lular decomposition[11], [12], [13], gird map[14], spanning
tree coverage[15], neural network-based coverage[16], [17],
graph-based coverage[18], optimal coverage[19], [20], cover-
age under uncertainty[21], [22]. Most these approaches were
designed mainly for a single robot.
For large-scale tasks, coverage path planning can benefit
greatly from multi-robot systems. First, a multi-robot system
clearly completes the task fast due to workload distribution.
Second, multiple robots can collaborate with each other
to accomplish complex tasks efficiently. Third, multi-robots
improve robustness in case of failure of some robots. Though
there are many advantages using multiple robots, the research
in multi-robot coverage path planning is relatively limited
since some extra factors (e.g., data sharing, complex path
generation, task division/allocation, physical constraints, etc.)
need to be taken into account. Many approaches extended
single-robot algorithms to handle multi-robot systems using
workload division/distribution[23].
Despite the exciting potential applications, designing a
scalable and practical multi-robot coverage path planning
The authors are with Shanghai Key Laboratory of Trustworthy Comput-
ing, Engineering Research Center of Software/Hardware Co-design Technol-
ogy and Application (MoE) and School of Software Engineering, East China
Normal University, Shanghai. Xinyu Zhang is the corresponding author. E-
mail: {xyzhang}@sei.ecnu.edu.cn.
(mCPP) algorithm under strict physical constraints remains
a challenging problem. Our research was developed from
an ambitious program for tree planting robots to restore
vast degraded lands. These terrains may exhibit complex
surface and topology. The robots have limited energy and
workload/material capacity (e.g., 100 tree saplings per load
for planting robots and 500kg water per load for watering
robots). Coverage path planning with physical constraints
is a relatively new topic and energy constraints were often
considered in limited research literatures[24], [25], [26], [27].
Main Results: We propose a novel method namely
MSTC
∗
(Multi-robot Spanning Tree Coverage Star), to solve
the mCPP problem under physical constraints of traversabil-
ity and limited workload/material capacity. We treat mCPP
as the problem of partitioning a topological loop and assign
each partition to one robot. To find a set of well-balanced par-
titions, we start with a set of na
¨
ıve partitions and iteratively
generate balanced partitions for all robots by minimizing the
maximum weights. Our balanced-MSTC
∗
uses the strategy
of balanced cut to search the most unbalanced two partitions
(with the maximum and minimum weights, respectively).
This strategy is a greedy algorithm and is able to gradually
approximate the optimal partitions. Our algorithm can find a
set of well-balanced workload distributions for all robots and
therefore, achieve the overall optimal time to complete the
coverage. We compare our algorithm against other spiral-
STC based mCPP methods on regular grid maps and real
field terrains in simulation environments. The results show
that our MSTC
∗
algorithm outperforms the state-of-the-
art, like classic MSTC (MSTC-NB)[28], MSTC with back-
tracking (MSTC-BO)[28] and Multi-robot Forest Coverage
(MFC)[29].
II. RELATED WORK
Coverage path planning is well studied for a single robot
and we refer readers to [14], [1], [23] for extensive survey.
Here, we briefly review the literature relevant to our work.
Our method is inspired by spiral spanning tree coverage
(Spiral-STC) [15] for a single robot and multi-robot spanning
tree coverage (MSTC) [28] for unweighted graph. The latter
improved the efficiency and robustness by introducing redun-
dancy and backtracking optimization using multiple robots.
Agmon et al. constructed a spanning tree by minimizing the
time to complete the coverage [30], [31]. Zheng et.al. pro-
posed multi-robot forest coverage (MFC) to solve the mCPP
problem using multiple minimal spanning trees to cover
the terrain generated by min-max tree cover algorithm [32].
The algorithm works for both unweighted terrains [29] and
weighted terrains [33], [34]. Most algorithms assumed that
arXiv:2108.04632v1 [cs.RO] 10 Aug 2021
资源评论
