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

2025-04-28 0 0 4.1MB 12 页 10玖币

侵权投诉

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-speciﬁed formations, making

feasible motions decrease signiﬁcantly. 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 conﬁguration space of multi-mobile robot

systems is ﬁrst built, where valid conﬁgurations can be acquired

to satisfy both formation constraints and collision avoidance.

Then, an undirected graph is generated by verifying connectivity

between valid conﬁgurations. The breadth-ﬁrst 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 ﬂexibility.

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 Artiﬁcial 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 ﬂexibility 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 ﬂexible as possible. Conﬂicts 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-speciﬁed

formation constraints. Moreover, if it is possible, what is the

optimal path for the robots to fulﬁll 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 conﬁguration space of MMRS is

ﬁrst built, where valid conﬁgurations are acquired according to

formation constraints and obstacle avoidance. An undirected

connected graph with boundary densiﬁcation is then generated

by verifying the connectivity between valid conﬁgurations.

Vertices and edges on the graph represent valid conﬁgura-

tions and the connectivity between conﬁgurations, respectively.

Finally, the breadth-ﬁrst 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 conﬁguration 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 densiﬁcation 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 deﬁne

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

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 ﬁrst 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, conﬁgurations

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 simpliﬁed

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 conﬂict between forming formations and avoiding obsta-

cles has not been fully handled. In some situations where rigid

or less ﬂexible 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 ﬁnding

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-ﬂow 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 conﬂiction 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 conﬁguration space and workspace

needs to be studied [39]. Moreover, the conﬁguration 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] :=

i=1

n∈R2, which is used

to describe the absolute location of systems in the workplace.

Formation s∈ S formed by robots is deﬁned 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.

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 conﬁguration space of a system.

cConﬁgurations of a system, c={x, y, θ, S}.

csConﬁgurations 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 conﬁgurations, Cf ree ⊂ C.

f ree A set of valid conﬁgurations in the same formation shape.

∂Cs

f ree The boundary of Cs

f ree .

N(cs, ξ)Neighborhood conﬁgurations of cs.

Ω(cs,p)Valid angles of the same formation Swith the same p.

To sum up, the conﬁguration cof multi-mobile robot systems

can be described as c={p, θ, S}, and the whole conﬁguration

space is denoted as C. Once cis given, the position of each

robot in the workspace can be determined as follows.

{r1, . . . , rn}=S−1(p, θ)(2)

where S−1indicates positions of robots are calculated by the

relative position relationship within the formation shape.

Now, let oi⊂R2, 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 conﬁgurations Cfree is deﬁned 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 conﬁgurations 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, conﬁgurations of systems will be planned

ﬁrst, after which paths of robots can be quickly computed.

It can be found that conﬁgurations of a system consist of

absolute information {x, y, θ}and relative information S.

Therefore, planning conﬁgurations of a system is divided into

two parts. The ﬁrst 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

r6r1

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 conﬁgurations can

be switched to each other through all available conﬁgurations

in Cfree, they are deﬁned as connected. Therefore, the ﬁrst

issue to be studied is the connectivity between conﬁgurations

after discretizing the workspace.

First, given a formation shape s, the conﬁguration space

of the same formation is denoted as cs={x, y, θ}. The set

of valid conﬁgurations of this formation is deﬁned 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

conﬁgurations before planning.

Theorem 1.For any cs∈ Cs

free,csis connected in

a neighborhood area N(cs, ξ) := {˜

cs}, conﬁgurations in

neighborhood area are deﬁned as follows.



(˜x−x)2+ (˜y−y2

2< ξ

abs(˜

θ−θ)< ξ, ξ > 0(5)

Proof :∀cs={x, y, θ}∈Cs

free, from the deﬁnition (3), all

robots are separated from obstacles although their distances

may be very small. In this case, a speciﬁc obstacle-free space

Tican be found for the ith robot, which satisﬁes

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 conﬁgurations. Therefore, csis connected

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

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

展开>> 收起<<

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

共12页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

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

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: