1 A Novel Graph-based Motion Planner of Multi-Mobile Robot Systems with Formation and

2025-04-28 0 0 4.1MB 12 页 10玖币
侵权投诉
1
A Novel Graph-based Motion Planner of
Multi-Mobile Robot Systems with Formation and
Obstacle Constraints
Wenhang Liu, Jiawei Hu, Heng Zhang, Michael Yu Wang, Fellow, IEEE/ASME, and
Zhenhua Xiong, Member, IEEE
Abstract—Multi-mobile robot systems show great advantages
over one single robot in many applications. However, the robots
are required to form desired task-specified formations, making
feasible motions decrease significantly. Thus, it is challenging to
determine whether the robots can pass through an obstructed en-
vironment under formation constraints, especially in an obstacle-
rich environment. Furthermore, is there an optimal path for
the robots? To deal with the two problems, a novel graph-
based motion planner is proposed in this paper. A mapping
between workspace and configuration space of multi-mobile robot
systems is first built, where valid configurations can be acquired
to satisfy both formation constraints and collision avoidance.
Then, an undirected graph is generated by verifying connectivity
between valid configurations. The breadth-first search method is
employed to answer the question of whether there is a feasible
path on the graph. Finally, an optimal path will be planned
on the updated graph, considering the cost of path length and
formation preference. Simulation results show that the planner
can be applied to get optimal motions of robots under formation
constraints in obstacle-rich environments. Additionally, different
constraints are considered.
Index Terms—Multi-mobile robot systems, motion planning,
formation constraints, obstacle-rich environment.
I. INTRODUCTION
IN recent years, multi-mobile robot systems (MMRS) have
attracted increasing attention from robotics researchers.
Compared with a single robot, the robots can cooperate with
each other to achieve better system robustness and flexibility.
Through collaboration among robots, complex tasks can be
accomplished, such as search and rescue [1], [2], exploring
[3], assembling [4] and transporting [5]. Moreover, MMRS can
replace the bigger single robot in scenarios with a restricted
and cramped environment, where there is not enough space.
In many applications of MMRS mentioned above, the robots
are usually required to form desired formations to achieve
cooperation, such as the object will connect the robots to form
a whole system during cooperative transporting. Accordingly,
This work was supported in part by the National Natural Science Foundation
of China (U1813224), Ministry of Education China Mobile Research Fund
Project (MCM20180703) and MoE Key Lab of Artificial Intelligence, AI
Institute, Shanghai Jiao Tong University, China. (Corresponding author:
Zhenhua Xiong.)
Wenhang Liu, Jiawei Hu, Heng Zhang, and Zhenhua Xiong are with
the School of Mechanical Engineering, Shanghai Jiao Tong University,
Shanghai, China (e-mail: liuwenhang@sjtu.edu.cn; hu jiawei@sjtu.edu.cn;
zhanghengme sjtu@sjtu.edu.cn; mexiong@sjtu.edu.cn).
Michael Yu Wang is with the Department of Mechanical and
Aerospace Engineering, Monash University, Victoria 3800, Australia (e-mail:
Michael.Y.Wang@monash.edu).
the flexibility of each robot will be decreased since it has
to satisfy formation constraints. In the meanwhile, the robots
also need to avoid obstacles when working, which requires
them to be as flexible as possible. Conflicts will arise if
simultaneously considering formation constraints and obstacle
avoidance when planning motions of robots, especially in
a dense environment with multiple obstacles. Therefore, it
is a challenging problem to determine whether MMRS can
pass through an obstructed environment under task-specified
formation constraints. Moreover, if it is possible, what is the
optimal path for the robots to fulfill the task? Thus, we focus
on multi-mobile robot motion planning problems under for-
mation constraints in obstacle-rich environments in this paper.
A novel graph-based motion planner is proposed. A mapping
between the workspace and configuration space of MMRS is
first built, where valid configurations are acquired according to
formation constraints and obstacle avoidance. An undirected
connected graph with boundary densification is then generated
by verifying the connectivity between valid configurations.
Vertices and edges on the graph represent valid configura-
tions and the connectivity between configurations, respectively.
Finally, the breadth-first search algorithm is adopted on the
graph to quickly determine whether there is a feasible path,
and the optimal path and motions of robots are computed
considering path length and formation preference. Cooperative
object transportation is used as a typical example. Simulation
results in different obstacle-rich environments demonstrate the
effectiveness and generality of the proposed planner. Besides,
the planner can be extended if there are additional constraints
brought by the tasks.
The main contributions of this paper are threefold. First, a
novel mapping between workspace and configuration space of
multi-mobile robot systems satisfying formation constraints is
proposed. Theoretical proofs show that the problems can be
solved on the undirected connected graph generated by map-
ping. Second, a boundary densification method is proposed
on the connected graph to facilitate planning and improve the
success rate for obstacle-rich environments. Third, the planner
can quickly determine whether it is feasible for MMRS to
pass an obstacle-rich environment under formation constraints.
Then, the optimal motions of the robots can be planned.
The rest of this paper is organized as follows. In Section
II, some related work is discussed. In Section III, we define
the basic concepts of multi-robot motion planning problems.
In Section IV, the proposed motion planner is explained in
arXiv:2210.03340v1 [cs.RO] 7 Oct 2022
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 riR2, 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
nR2, 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 =krirjk2
(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.
3
TABLE I
DEFINITION OF SOME IMPORTANT NOTATIONS
riThe position of ith mobile robot.
pThe center of multi-mobile robot systems.
PThe plane where mobile robots are located.
SFormation constraints of multi-robot systems.
θThe angle of formations.
CWhole configuration space of a system.
cConfigurations of a system, c={x, y, θ, S}.
csConfigurations of a system in the same formation shape,
cs={x, y, θ}.
oiThe position of ith obstacle.
W(oi)Space occupied by obstacle oi.
W(ri)Space occupied by robot ri.
Cf ree A set of valid configurations, Cf ree ⊂ C.
Cs
f ree A set of valid configurations in the same formation shape.
Cs
f ree The boundary of Cs
f ree .
N(cs, ξ)Neighborhood configurations of cs.
(cs,p)Valid angles of the same formation Swith the same p.
To sum up, the configuration cof multi-mobile robot systems
can be described as c={p, θ, S}, and the whole configuration
space is denoted as C. Once cis given, the position of each
robot in the workspace can be determined as follows.
{r1, . . . , rn}=S1(p, θ)(2)
where S1indicates positions of robots are calculated by the
relative position relationship within the formation shape.
Now, let oiR2, i = 1, . . . , m denotes the position of the
ith obstacle, and mis the number of obstacles. W(oi)R3
is used to denoted the workspace occupied by the ith obstacle.
Similarly, W(ri)is the workspace occupied by the ith robot.
The set of valid configurations Cfree is defined as follows.
Cfree := {c| R ∩ O =}
where R=W(ri)∪ · · · ∪ W(rn)(3)
O=W(oi)∪ · · · ∪ W(om)
In other words, c∈ Cfree indicates that the desired formation
exists, satisfying that all robots are not in contact with obsta-
cles. Planning configurations in Cfree ensures safety during
movement. If we directly plan the motion of each robot with
formation constraints and obstacle avoidance, it will suffer
from the curse of dimensionality. Generally, it is as high as
R2n. To avoid this, configurations of systems will be planned
first, after which paths of robots can be quickly computed.
It can be found that configurations of a system consist of
absolute information {x, y, θ}and relative information S.
Therefore, planning configurations of a system is divided into
two parts. The first part is to plan S, which is more dependent
on formation constraints and will be further discussed. Sis
strongly related to applications and tasks. The second part is
to plan {x, y, θ}for driving the system on P, which is more
concerned in this section.
(a) Shape with θ1(b) Shape with θ2
p
p
r6r1
r2
r3
r4
r5
r2
r3
r4
r5
r6
r1
x-axis
θ1θ2
x-axis
Fig. 1. The same formation shape with different angles. pis the same in (a)
and (b), while positions of robots are different.
For a multi-mobile system, the planning problem considered
in this paper can be formulated as follows.
Input :O,S
Output :{c1,...,ck}
Subject to
ci∈ Cfree,ckis the goal
ciand ci+1 are connected
(4)
Since it is extremely hard to obtain a real continuous space
of Cfree in the graph, we will solve the problem (4) by translat-
ing it using the discretization method. If two configurations can
be switched to each other through all available configurations
in Cfree, they are defined as connected. Therefore, the first
issue to be studied is the connectivity between configurations
after discretizing the workspace.
First, given a formation shape s, the configuration space
of the same formation is denoted as cs={x, y, θ}. The set
of valid configurations of this formation is defined as Cs
free.
As shown in Fig. 2, cs
1and cs
2are connected because the
system can move from cs
1to cs
2while keeping the formation
continuously unchanged. However, cs
2and cs
3are not con-
nected although they are both in Cs
free. They can switch to
each other only if ignoring the formation constraint. Hence,
it is necessary to study the connectivity between different
configurations before planning.
Theorem 1.For any cs∈ Cs
free,csis connected in
a neighborhood area N(cs, ξ) := {˜
cs}, configurations in
neighborhood area are defined as follows.
(˜xx)2+ (˜yy2
2< ξ
abs(˜
θθ)< ξ, ξ > 0(5)
Proof :cs={x, y, θ}∈Cs
free, from the definition (3), all
robots are separated from obstacles although their distances
may be very small. In this case, a specific obstacle-free space
Tican be found for the ith robot, which satisfies
W(ri)⊂ Ti,Ti∩ O =(6)
Tiis a bounded open set. Since (6) is available for each
robot, the whole formation can move or rotate freely in any
direction if W(˜ri)still stays in Tiafter movement, which will
generate new valid configurations. Therefore, csis connected
摘要:

1ANovelGraph-basedMotionPlannerofMulti-MobileRobotSystemswithFormationandObstacleConstraintsWenhangLiu,JiaweiHu,HengZhang,MichaelYuWang,Fellow,IEEE/ASME,andZhenhuaXiong,Member,IEEEAbstract—Multi-mobilerobotsystemsshowgreatadvantagesoveronesinglerobotinmanyapplications.However,therobotsarerequiredtof...

展开>> 收起<<
1 A Novel Graph-based Motion Planner of Multi-Mobile Robot Systems with Formation and.pdf

共12页,预览3页

还剩页未读, 继续阅读

声明:本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知玖贝云文库,我们立即给予删除!
分类:图书资源 价格:10玖币 属性:12 页 大小:4.1MB 格式:PDF 时间:2025-04-28

开通VIP享超值会员特权

  • 多端同步记录
  • 高速下载文档
  • 免费文档工具
  • 分享文档赚钱
  • 每日登录抽奖
  • 优质衍生服务
/ 12
客服
关注