
2
detail. In Section V, the planner is employed for different
formation constraints by a case study in object transportation.
The simulations and results are given in Section VI. Section
VII concludes the paper and outlines the future work.
II. RELATED WORK
In many studies of multi-robot motion planning, formation
constraints among robots are not the key point. For each
robot, it regards other robots as dynamic obstacles and collab-
oration is not considered [6]–[8]. However, as tasks become
more complex, the collaboration between multiple robots is
inevitable, especially with formation constraints.
Generally, approaches in the previous works on motion
planning of MMRS under formation constraints can be divided
into two categories. The first category is individually planning
each robot while satisfying formation constraints and avoiding
obstacles. Under the combination of the two behaviors, the
system can hold desired formations [9]. Based on the leader-
follower and potential-based methods, desired formations with
obstacle avoidance were achieved in [10]–[12]. By combining
the virtual structure and obstacle avoidance methods, [13]
introduced an approach for multiple robots to maintain forma-
tions. Similarly, the combination can be found in [14]. Besides,
learning-based methods are also employed for the problems.
Formations could be adjusted independently by each robot to
pass through obstacle areas based on reinforcement learning
[15], [16]. In [17], the task space, including formation con-
straints and obstacle avoidance, was decomposed into different
convex regions through a global planner. Then, configurations
were planned through a local planner. In the above research,
the systems can all maintain desired formations tightly and
move to the goal in environments without obstacles. However,
when it comes to obstacle avoidance, some uncontrollable
deformation of system formations will appear more or less,
which is not acceptable for some cooperative tasks.
The second category considers the multi-robot system as
a whole 2D area, which is planned to be strictly separated
from obstacles. A system outlined rectangle approach was
proposed in [18], regarding the multi-robot system as a virtual
rectangle to avoid obstacles. Then, the problem was simplified
to the motion planning of a single robot. The idea can
also be found in [19], [20]. In [21] and [22], a constrained
optimization method was presented for motion planning of
multiple robots. The robots could always form the desired
formations in the largest convex obstacle-free region computed
in the neighborhood of the system. A region-based framework
for multi-robot systems was introduced in [23]. Based on
virtual structure, robots moved and formed formations inside a
changeable circular region always separated from obstacles. In
[24], formation control and change were achieved by caging
behaviors. The whole system was planned by the rapidly-
exploring random tree for obstacle avoidance. Sometimes, the
multi-robot systems have to be considered as a whole due to
special tasks, as in [25]–[28]. However, for the above research,
it is over-constrained since robots can actually be separated.
At least, the system could have crossed obstacles instead of
merely bypassing obstacles as a whole. Therefore, the system
loses part of its obstacle avoidance ability.
It is noted that current research did not explicitly consider
the formation constraints. Thus, the deformation of systems
during motion cannot be limited to a certain range of tasks.
The conflict between forming formations and avoiding obsta-
cles has not been fully handled. In some situations where rigid
or less flexible connections among the robots are required,
these methods are unsuitable. 2D region-based methods are
safe for obstacle avoidance. However, it is only suitable for
a few obstacles environment. Therefore, it is worth finding
a method for multi-robot motion planning in obstacle-rich
environments, at the same time keeping formation constraints.
In multi-robot motion planning studies, graph theory is a
powerful tool [29]–[31]. In [7], based on a graph and spanning
tree representation, a multi-phase approach was described.
Through the relationship between multi-robot planning prob-
lems and multi-flow problems, integer linear programming
models were proposed to compute optimal paths for multiple
robots on connected graphs [32]. Their models were further
extended in [33] in connection with different minimization ob-
jectives in path planning. The optimal solution or approximate
optimal solution could be quickly calculated on the connected
graphs. In [34], goal allocation and motion planning were
achieved on roadmaps for non-holonomic robots.
In the above studies with graph theory, the robots are more
likely to be planned individually, where the confliction be-
tween waypoints is the only connection among multiple robots
[35]–[38]. However, formation constraints are not considered.
Therefore, in order to solve the problem through graph the-
ory, the mapping between configuration space and workspace
needs to be studied [39]. Moreover, the configuration space of
MMRS should be further investigated, especially in the case
of integrated obstacle avoidance and formation constraints.
III. PROBLEM FORMULATION
In this work, we consider multi-mobile robot motion plan-
ning under both obstacle-rich environments and formation
constraints. The mobile robots are assumed to be holonomic,
and they move on a 2D plane. The typical task is to transport
an object from the initial position to goal position.
Some important notations are listed in Table I for conve-
nience. In a workplace W ⊂ R3, the position of the ith mobile
robot is denoted as ri∈R2, i = 1, . . . , n, and nis used to
denote the number of mobile robots. The plane where robots
are located is denoted by P ⊂ R2. The center of multi-robot
systems is denoted as p= [x, y] :=
n
P
i=1
ri
n∈R2, which is used
to describe the absolute location of systems in the workplace.
Formation s∈ S formed by robots is defined as follows.
s:= d∗
ij i, j = 1, . . . , n i 6=j
d∗
ij =kri−rjk2
(1)
where sis the desired formation shape of multi-robot systems,
which consists of relative positions between robots. Since p
is not changed by the rotation of the same formation shape,
multiple positions of robots may exist. As shown in Fig. 1,
it can be seen that the two formation shapes are the same,
but riis different from each other. Therefore, θ∈Ris used
to denote the shape angle and distinguish positions of robots.