Multi-Robot Trajectory Planning with Feasibility Guarantee and Deadlock Resolution An Obstacle-Dense Environment

2025-04-29 1 0 4.07MB 8 页 10玖币

侵权投诉

Multi-Robot Trajectory Planning with Feasibility

Guarantee and Deadlock Resolution: An

Obstacle-Dense Environment

Yuda Chen, Chenghan Wang, Meng Guo and Zhongkui Li, Senior Member, IEEE

Abstract—This article presents a multi-robot trajectory plan-

ning method which not only guarantees optimization feasibility

and but also resolves deadlocks in obstacle-dense environments.

The method is proposed via formulating a recursive optimization

problem, where a novel safe corridor is generated online to

ensure obstacle avoidance in trajectory planning. A dynamic-

priority mechanism is combined with the right-hand rule to

handle potential deadlocks that are much harder to resolve due to

static obstacles. Comparisons with other state-of-the-art results

are conducted to validate the improved safety and success rate.

Additional hardware experiments are carried out with up to eight

nano-quadrotors in various cluttered scenarios.

Index Terms—Trajectory generation, motion planning, multi-

robot system, collision avoidance, deadlock resolution.

I. INTRODUCTION

COLLISION-free trajectory planning plays an essential

role for a swarm of robots navigating in a shared

environment [1]. The robots need to avoid collision with

both other robots and obstacles while moving to their targets.

Various techniques are proposed, among which optimization-

based methods [2], [3] have gained signiﬁcant attentions due

to their ﬂexibility of adding constraints, such as the convex

constraints in [2], [4] and the non-convex constraints in [3].

Nevertheless, the constrained optimization may suffer from the

infeasibility, leading to failed planning. This problem becomes

specially severe in a crowed environment with dense obstacles.

Moreover, without a central coordinator, it often happens

that the robots block each other indeﬁnitely and no further

progresses can be made, which is also known as deadlocks [5].

To address the issue of infeasibility, the work in [6] con-

verts hard constraints into soft ones by adding them to the

objective function. But the safety properties associated with

the constraints such as collision avoidance cannot be ensured

anymore. Our previous work in [7] can provably ensure the

feasibility of underlying optimization, which however cannot

deal with the obstacle collision. To handle obstacles during

motion, one of the most widely-adopted method is safe corri-

dor, e.g., [8] generates a high-quality corridor via semi-deﬁnite

programming, and [9] combines the search-based path plan-

ning and geometry-based corridor construction. Unfortunately,

the hard constraints introduced by the safe corridor may also

lead to infeasible optimizations, as discussed in [10], [11]. In

The authors are with the State Key Laboratory for Turbulence and Complex

Systems, Department of Mechanics and Engineering Science, College of En-

gineering, Peking University, Beijing 100871, China. Corresponding author:

zhongkli@pku.edu.cn.

Fig. 1. Eight nano-quadrotors ﬂy through a cubic framework.

addition, the authors in [12], [13] propose a cubic corridor in

a grid map. Although this method is computationally efﬁcient

to generate safe corridor and can guarantee feasibility, it is

restricted by the cubic shape that may have a lower space

efﬁciency. Furthermore, the method in [14] generates a safe

corridor via supported vector machines, which has a higher

utility rate of freespace, but is centralized and computed

ofﬂine. Another way to construct a safe corridor is the voxel

expansion proposed in [10], [15] on a grid map, which

however is also computed ofﬂine.

As mentioned earlier, another prominent problem in dis-

tributed trajectory planning is deadlock when robots block

each other indeﬁnitely during motion, as also addressed

in [13], [16]. Various heuristic approaches are proposed to

resolve deadlocks, by introducing e.g., the right-hand rule [10],

[17], priority planning [13], and detour points [18]. The com-

mon drawback of these approaches is that the safety of robots

or the effectiveness of deadlock resolution is not ensured

and usually can lead to livelock where deadlocks re-appear

after resolution. Our previous work [7] proposes an adaptive

right-hand rule for deadlock resolution in obstacle-free space.

Unfortunately, it cannot be applied to obstacle-dense environ-

ments because static obstacles are non-cooperative and cannot

be pushed away by the right-hand force.

To address these two issues formally in obstacle-dense en-

vironments, we ﬁrst propose a novel method to construct safe

corridors online which provide feasible space for trajectory

generation. It adopts the path planning method ABIT?[19]

to determine a reference path, based on which the separating

hyperplanes are computed via quadratic programming between

arXiv:2210.04231v2 [cs.RO] 22 Feb 2023

the imminent obstacles and the planned trajectory. Regarding

deadlocks in obstacle-dense environments, a dynamic-priority

mechanism is proposed along with the adaptive right-hand

rule. Invalidation of the right-hand rule would induce a higher

priority thus more egoistic to continue its motion.

The main contributions are summarized as follows.

•The proposed online generation of safe corridor as a

sequence of polytopes has a much higher utilization of

the workspace than the cubic safe corridor proposed

in [12], [13]. It is shown to reduce computational cost

and increase safety margin, compared with [8].

•The proposed dynamic-priority mechanism resolves po-

tential deadlocks whenever the adaptive right-hand rule

[7] is invalidated due to static obstacles.

•Comparisons with several state-of-the-art methods [3],

[6], [13] are made in non-trivial cluttered scenarios.

It is validated that the proposed method has a better

performance in terms of guaranteeing collision avoidance

as well as handling deadlocks.

•Extensive hardware experiments are conducted to val-

idate the real-time performance, including eight nano-

quadrotors navigating in obstacle-dense 3D scenarios, as

shown in Fig. 1.

II. PROBLEM STATEMENT AND PRELIMINARIES

Consider a team of Nrobots that navigate to their respective

destinations within a common 2D or 3D workspace that are

cluttered with static obstacles. During the navigation, a robot

cannot collide with either other robots or obstacles. Each robot

can determine its own control input and exchange information

with other robots via communication.

A. Robot Dynamics

Let h > 0denote the sampling time. The dynamic model

of the robot i∈ N ={1,· · · , N}is given by

k(t) = Axi

k−1(t) + Bui

k−1(t),(1)

where k∈ K ,{1,· · · , K}is the step within the planning

horizon K > 0;pi

k(t), vi

k(t), ui

k(t)are the planned position,

velocity, and control input at time t+kh, respectively;

k(t)=[pi

k(t), vi

k(t)] is the planned state at time t+kh

with xi

0(t) = xi(t); the double-integrator dynamics are given

by A=IdhId

0dId,B=h2

2Id

hIdwith the dimension

d= 2,3. The planned trajectory of robot iat the time t > 0

is deﬁned as Pi(t) = pi

1(t), pi

2(t),· · · , pi

K(t). Additionally,

the velocity and input constraints are given as

kΘaui

k−1(t)k2≤amax, k ∈ K,

kΘvvi

kk2≤vmax, k ∈ K,(2)

where Θv,Θaare given positive-deﬁnite matrices, and

vmax, amax denote the maximum velocity and acceleration,

respectively.

Once the planned trajectory is computed, a lower feedback

controller is followed to drive robot iwithin the time interval

[t, t +h], such that xi(t+h) = xi

1(t)holds when robot i

re-plans at time t+h. Furthermore, at each time step t,

robot isends its predetermined trajectory Pi(t)to other

robot j6=i, which is constructed directly from the planned

trajectory Pi(t−h)derived at t−h. More speciﬁcally, Pi(t) =

pi

1(t), pi

2(t),· · · , pi

K(t), where pi

k(t) = pi

k+1(t−h),

∀k∈˜

K,{1,2,· · · , K −1}and pi

K(t),pi

K(t−h). For the

sake of simplicity, the time index tis omitted in the sequel,

whenever ambiguity is not caused.

B. Collision Avoidance

1) Inter-Robot Collision Avoidance: The safety area around

each robot i∈ N is represented by a ball as Ri=

x+pi| kxk2≤ra, where ra>0is a given safety radius.

To avoid inter-robot collisions, any pair of robots should

satisfy kpi−pjk2≥2ra. This constraint can be converted

equivalently to linear constraints via the modiﬁed buffered

Voronoi cells with warning band (MBVC-WB) proposed in

our previous work [7] as follows:

aij

Tpi

k≥bij

k,∀j6=i, ∀k∈˜

K,(3a)

aij

Tpi

K≥bij

K+wij ,∀j6=i. (3b)

where aij

k=pi

k−pj

kpi

k−pj

kk2

,bij

k=aij

Tpi

k+pj

2+rmin

2,rmin =

p4ra2+h2v2

max denotes the extended minimum distance, and

wij ∈[0, ]is an additional variable as the warning band with

the maximum width  > 0.

2) Obstacle Avoidance: Let O ⊂ Rddenote the set of

obstacles’ occupied space. Similar to [11], the obstacles are

assumed to be convex-shaped. Thus, the constraint of obstacle

avoidance requires that the safety area of each robot does not

intersect with any obstacle, i.e., Ri∩O =∅,∀i∈ N . Namely,

a planned trajectory Pis collision-free, if

Conv(pi

k, pi

k+1)∩˜

O=∅,∀k∈˜

K,(4)

holds, where ˜

Ois the set of occupied space

after inﬂating obstacles by raand Conv(P),

{Pn

i=1 θipi|pi∈P, θi≥0,Piθi= 1, i = 1,2,· · · , n}

is the convex hull formed by points in the set P.

C. Problem Statement

Assuming that all robots are collision-free initially at

time t0, our goal is to design a distributed trajectory planning

algorithm that drives each robot to its target pi

target,∀i∈ N ,

while respecting the constraints speciﬁed in (1)-(4).

III. TRAJECTORY PLANNING METHOD

The overall trajectory planning algorithm will be described

in this section, which consists of the construction of safe

corridor, the deadlock resolution scheme, the trajectory op-

timization algorithm and the proof of feasibility guarantee.

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

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

10 玖币 0人已下载

立即下载

摘要：

Multi-RobotTrajectoryPlanningwithFeasibilityGuaranteeandDeadlockResolution:AnObstacle-DenseEnvironmentYudaChen,ChenghanWang,MengGuoandZhongkuiLi,SeniorMember,IEEEAbstractThisarticlepresentsamulti-robottrajectoryplan-ningmethodwhichnotonlyguaranteesoptimizationfeasibilityandbutalsoresolvesdeadlocksi...

展开>> 收起<<

Multi-Robot Trajectory Planning with Feasibility Guarantee and Deadlock Resolution An Obstacle-Dense Environment.pdf

共8页,预览2页

还剩页未读，继续阅读

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

Multi-Robot Trajectory Planning with Feasibility Guarantee and Deadlock Resolution An Obstacle-Dense Environment

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: