第38卷第4期
计算机仿真2021年4月文章编号：1006-9348(2021)04 - 0281 -05
陈曦，王熙，李宁
(河北工业大学人工智能与数据科学学院，天津300130)
摘要：针对广义速度障碍（Generalized Velocity ObstadeS，GV O)算法解决动态环境避障问题时计算量过大、动作过于保守等
问题，提出了速度障碍法（Velocity Obstacles, V0)与G V0组成的分级避障控制生成策略，使用V0判断所选控制生成的速度 矢量是否存在碰撞危险，如果存在碰撞危险则进一步使用G V0对该控制进行判断，否则认为该控制为安全控制。通过建立
碰撞时间评价函数和目标适应度评价函数选取最优控制。当可达控制集中所有控制都不可行时，通过可达控制集外的一组 密目式安全网控制来启发当前控制的生成。仿真结果表明，所提算法有效的避免了G V0算法中不必要的计算，在不同场景中至少缩短算
法运行时间15. 91%，改善了G V0算法无解时避障，得到了更合理的轨迹。
关键词：机器人；动态避障；速度障碍；评价函数；控制集
中图分类号:TP242 文献标识码：B
Mobile Robot Obstacle Avoidance Algorithm
Based on Hierarchical Velocity Obstacle
CHEN Xi，WANG Xi，L I Ning
(S chool of A rtificial In tellig en c e,H ebei U niversity of T echnology,T ianjin 300130,C h in a)
A B S T R A C T：A im ing at th e problem that the G eneralized V elocity O bstacles (G V O)algorithm h as too m uch com pu
tation and too conservative action w hen solving the problem of dynam ic environm ent obstacle av o
id an ce,a hierarchical obstacle avoidance control generation strategy com posed of V elocity O bstacles (V O)and GVO is prop o sed.F irs tly, VO was used to determ ine w hether there is a collision risk in the velocity vector generated by the selected control.If there was a collision risk,G V O would be used to judge th e co n tro l,o th erw ise,it was considered to be a safety control.
T he collision tim e evaluation function and the target fitness evaluation function were established to select the optim al control.W hen all the controls available w ere not fe a sib le,an other group of outside control would be used to inspire the generate of cu rren t control.T he sim ulation results show that the proposed algorithm can effectively avoid u n n ecessary calculations in the GVO algorithm and shorten the algorithm running tim e by at least15. 91%in different sc e n e s,a n d the obstacle avoidance of GVO is im proved by this new system.E sp e c ia lly,obstacle -avoidance is improved w hen GVO algorithm has no so lu tio n,a n d a m ore reasonable trajectory is o b tain ed.
K E Y W O R D S：M obile ro b o t；D ynam ic obstacle av o id an ce；V elocity o b sta c le；E valuation fu n ctio n；Control set
i引言
随着机器人技术的发展，移动机器人越来越频繁的被用 于执行复杂环境中的任务。为移动机器人在动
态场景中安 全运行提供保障的避障技术成为研究热点。
速度障碍法(V elo city O bstacles -V0)最早由Fiorini 和S h ille r提出，通过构建导致碰撞的速度集合，引导机器人避障。有限时间速度障碍[2](F in ite Tim e V elocity O bstacle -
收稿日期:2019 - 08 - 09修回日期:2019 - 09 - 29F V O)在V0算法基础上考虑了碰撞发生的时间，进一步缩小了碰撞速度集合。文献[3] [4]在FV0的基础上建立了目标函数来寻优避障速度。文献[5]在V0基础上提出了量化碰撞危险的方法。文献[6]将V O算法用于船舶避障。上述算法简化了机器人模型，无法适用于非完整机器人。
广义速度障碍'7」（G eneralized V elocity O bstacles -GV0)将机器人运动模型考虑到避障中，构建导致碰撞的控制集合，引导机器人避障。由于G V O算法可以更直观的显示导致碰撞的控制，其被应用于航海避障系统[8]。文献[9]将动态窗口法与V0算法结合以满足无人船舶运动模型。广义
—281—
互惠避障[10]( Generalized reciprocal c o l l i s i o n avoidance - G R C A)对考虑机器人运动模型时的速度障碍提出了更统一 的形式，称作控制障碍。另一种考虑机器人运动模型的方法 是先使用V0算法生成最优避障速度，然后控制机器人跟踪 该速度[11]，该方法在多机器人协同避障时可以很好的作用，但面对被动障碍物时，无法保证安全性。
针对G V O算法计算量大、避障轨迹保守等问题，本文提 出了基于分级速度障碍的避障算法，先使用V0算法进行低 精度碰撞检测，如果当前控制生成的速度存在碰撞危险，再 使用G V O算法进行更高精度的碰撞检测，最终得到所有可 行控制的评价，选出当前时刻的最优控制。这种方法在不影 响安全性的情况下有效的减少了算法运算时间。通过建立 碰撞时间评价函数，进一步扩大了可行控制的分布。使用可 达控制集外的控制启发避障控制的生成，充分发挥了机器人 运动性能，更好的应对了 G V O算法无解时避障，生成了更合 理的运动。
2相关算法
2.1 V O算法
考虑简单场景，机器人速度为h = (4,V_)，障碍物速 度为6=(匕》，^^)，坐标原点为机器人的中心，机器人和障 碍物分别用圆心为h4，心）和,/%)、半径为~和~的圆形区域表示。为机器人与障碍物相对速 度，假设障碍物未来一段时间r内速度保持恒定，那么机器 人与障碍物之间的相对速度集合将导致在7■内发生碰撞，称 此相对速度集合为速度障碍，数学表达式为
y〇l〇(P〇M)= M e D(P0M/t,r/t) e (0,r] |(1) 其中:=尸o - h Q + r0 ,=匕-F0,
D(P〇M/T,r/T) = |t)l ||d-P0/i4/t||^r/r I
(a)机器人和障碍物的位置、速度、形状描述
通过设定最大允许碰撞时间可以有效的扩大可行速度集合，但不同情况下对r的选择不同。使用F0。进行保 守的碰撞检测，虽然会使碰撞速度集合变大，其可在快速碰 撞检测的同时避免对碰撞控制的漏检。
2.2 GVO算法
令/^(0为障碍物〇在《时刻的位置，为机器人/I 在i时刻的位置,u为机器人的控制，h(t，u)表示在控制U 作用下机器人4运动《时间间隔后的位置。机器人和障碍 物由圆形区域表示。控制集中的控制障碍[7]表示为
|ul 彐t > 0 丨丨/5“，，“）-P“〇||< q +r0| (2)通过判断+r…决定该控制u是否为可行 控制。
其中:D(*n i…(u)) = I l h G此（u)，u) -P0(*m i…(u)) I I，
f m,n(U) = arS min 丨丨h h u)-尸〇(0 lUmin (U)表示在控
t >0
制u作用下机器人4与障碍物〇之间距离最小的时刻。
可通过闭式运算（距离随时间变化的函数求一阶 导数的零点）或者采样计算获得。当机器人为线性运动时 CK0的定义与F0的定义相同，区别在于CF0包含了机器人 的运动模型。
2.3可达控制集
根据机器人速度约束，控制集应满足R
r0 ^v ^vm a r
U, =(v,u>)=I
*■_ ^^C〇,
其中:&…表示机器人模型允许的最大线速度；
人模型允许的最大角速度；
给定机器人当前线速度^…、角速度和采样间隔出，下一采样时刻的可达控制为％:
,,,、f^c u r r - ^^ «^c u r r + ^
Ud=(v,w) =j
*d t^^C〇c m r+〇)m^ * d t
(4)其中：表示机器人模型允许的最大线加速度；表示机器人模型允许的最大角加速度。
综合机器人速度和加速度约束得到可达控制集为t/= %n{/,，通过设置线速度分辨率和角速度分辨率如可生成一系列可达控制。
3分级速度障碍算法
由于CF0算法对控制进行评价时运算量较大，本文提 出分级速度障碍来简化无碰撞危险时的运算。计算每一个 控制“使机器人在下一采样时刻达到的线速度匕(&，!〇和位置P J d t w)，并与障碍物速度+ A)和位 置^(«_+出）建立如果相对速度匕。（屯《)处于 则进一步通过e r a算法检测该控制是否存在碰撞危 险，否则认为该控制暂时无碰撞危险。如图2所示，控制U，生成的相对速度处于F0.L中，需要进一步使用e r a算法对 控制U，进行碰撞检测。而控制u2、U3生成的相对速度处于
(3)
表示机器
—28
绿减肥产品
2
v o r d h ，下一时刻无碰撞危险，无需使用e r a 算法进行碰撞 检测。
由于v o 算法计算复杂度远低于G V O 算法，通过分级判 断碰撞危险，可有效的简化无碰撞危险时的运算，通过评价 函数可选出最优控制。3.1评价函数
3.1.1碰撞时间评价函数
G V O 算法中仅通过最近相遇点距离来判断该控制是否
安全，忽略了碰撞发生的时间，可能导致可行控制过少或者 可行控制集Y 为空，使得避障动作过于保守，有时还会错过 安全通过的时机。通过对不同碰撞时间的控制建立评价函 数[12]/#(<〇，可获得更多的可行控制。碰撞时间评价函数 人由下式表示
1
V A /〇(d t ,u ) ^ V 〇1,0
栅栏门
J
'
^
M
V ^0(d t ,a )e V 〇Z 〇
+^0
K c U u u (u )
and
渣土车管理系统) <
r A
+
r 0
冬[1 + tanh(------~r +--------~r)]
2
l d - tcollide ( U )
l ,~ 1 c ollide ( U )
h
<*c 〇«i *(u ) <t ,
and D
(t m i n (u )) <
r A +r 0
a n A D i t ^i u )) <r A +r 0
人确（“）=
10
(5)
其中：碰撞时间为控制u 作用下机器人/I 与障碍物 〇之间距离小于安全距离的最早时刻，其值等于碰撞时间 集合
T
= \ t
e R * \\\P A (t ,u ) -P 0(t )\\<r t +r 0,u e U \
其中的最小值7^…。t ，为危险碰撞时间，该参数允许算 法选择碰撞时间大于L 的控制作为可行控制。为安全碰 撞时间，该参数避免算法对碰撞时间最大的控制产生极大值 评价。
如果相对速度不属于返回碰撞时间 最大评价值1，否则计算/+U )。如果经e r a 算法判断不
存在碰撞危险，则返回碰撞时间最大评价值1，否则依据碰撞 时间评价函数的评价值对控制可行性进行划分。当 控制的碰撞时间评价不为零时，将其加人可行控制集y ，否 则将其加人不可行控制集/V;3.
1.2目标适应度评价函数
通过轨迹终点与目标点的关系建立目标适应度评价函 数，从而使机器人选取轨迹最接近目标点的可行控制。目标适应度评价函数A w U )由下式表示
,
M -丨丨户九）-d
g^
u> ~ \\PA(t P ,u ) -P T W
其中4为轨迹预测时间，为机器人目标位置。
(6)
综合考虑碰撞时间和目标适应度建立目标函数，将碰撞时间评价值和目标适应度评价值经归一化处理后代人目标函数，通过最大化评价值得到最优控制，，公式如下
“• = arg max(
人(u ) ) (7)
采用这两个评价函数来得到控制的评价，会存在局部极 值点，复杂环境需要全局规划来引导局部规划。3.2启发式紧急避障控制生成
G V O 算法采用单步可达控制匀速运动产生的预测轨迹 较保守，并不能完全代表机器人碰撞前可以实现的轨迹，可 能会导致可行控制集y 为空，合理扩大控制的可选范围可以 在保证安全的情况下提升机器人的运动性能。故可行控制 集5"为空时，应从多步可达控制集中选取最优控制为启 发控制，并从单步可达控制集t /中选择最接近该启发控制的 控制作为最优控制经过变速运动可达到该启发控制。
由于可行控制集F 为空时急需得到可行控制，故只对多 步可达控制集中最典型的9个控制进行评价，由下列线
速度、角速度组合生成
v e
I max(0,t )c u r r * 8<*),
v c u r r
, min( i ;C B … + am… * 8^ ,i >…… ) |
a ,
e I max( - <um… ,w
curr
-
*
S d t ),
〇)c u n.,
min ( 〇)c u n +
* 8, 〇)m t x ) |
多步可达控制启发下机器人运动轨迹由8个采样时间 的变速运动和达到多步可达控制后的匀速运动组
成。如图3 所示为单步可达控制集与多步可达控制集％…的轨迹分 布对比，（a )(6)分别为轨迹初始状态w >0、w =0的情况 <〇的情况与w >〇时对称。从多步可达控制集选取启 发控制可以在不违反机器人动态性能的情况下，扩大轨迹分
图3
单步可达控制集
U 与多步可达控制集118<1，的轨迹分布对比
—
283
—
避障过程时间/s
(d)
(a)
(c)
布范围，生成紧急情况下的避障控制。 法运行在配置为I n t e l i 5 -3230m (2.6G H z ) - 12G B R A M 的笔记本电脑中，算法中涉及到的参数见表1和表2。
4仿真与分析
在本节中，对所提算法进行了仿真以证明其有效性。算
表1
机器人物理限制
最大线速度
最小线速度
线加速度
最大角速度
最小角速度
角加速度
WmaxAdeg /s )
wm in /(deg /s )
〇)/(
deg /s 2 )
短路故障指示器1.5
0.4
40
-40
40
表2
算法参数
机器人与障碍物半径
时间分辨率
危险碰撞时间
安全碰撞时间
轨迹预测时间
距离阈值
R /(m )
dt /( s )
t 8/(s )
tp /(s )
distThers / ( m )
1
0. 1
0.8
3.8
4.5
2
表3机器人与障碍物初始状态
编号x /( m )
y /(m )
0/(deg )
v / (m /s )〇)/ ( rad / s )
机器人-1.0
-1.0
45 1.0
0.0障碍物1 6.0 5.01800.80.2障碍物211.0-0.51800.80.0障碍物3
-2.0
6.0
0.0
0.7
0.0
4.1多障碍物场景
机器人与障碍物以表3所示初始状态开始运动，机器人 目标位置/T "为（8,9)，避障过程中机器人可得障碍物的瞬 时速度。
对比图4(a) (b )，本文算法避障过程用时13. Is, G V O 算法避障过程用时19. 2s，本文算法避障时间更短、避障轨迹 更合理，这是由于G V O 算法在躲避障碍物1时产生可行控 制集为空的情况，使得机器人在避障过程中错过了避障时 机。而本文算法在可行控制集为空时，从多步可达控制集中 得到了启发控制，产生了可行控制，发挥了机器人运动性能。
通过对比图4(e)与图4(f)可以看出，G V O 算法在避障 过程中每一采样时刻算法运算时间整体大于本文算法。避 障过程中本文算法的平均运算时间为〇.44s，G V O 算法为 〇.68S。如图5所示，机器人与障碍物延伸出的实线表示其 预测轨迹，箭头表示其当前时刻速度，锥形表示根据机器人 和对应障碍物的速度、位置生成的速度障碍，机器人的控制 产生的速度未落人速度障碍V 01、速度障碍V 02和速度障 碍V 03，不需要进一步使用G V O 进行判断，省去了运算量。 对应图4(f)中6. 3s 时刻本文算法运算时间很短。本文算法 省去了一些对控制计算G V O 的过程，使算法运算时间少于 G V O 算法。
4.2多障碍物与多机器人并存场景
机器人与障碍物以表4所示初始状态开始运动，机器人 1目标位置/57；为（8,9)，机器人2目标位置/^^
为（2,5), 机器人3目标位置鬥f 为（10,0)，避障过程中机器人可得障碍物的瞬时速度。—284 —
避障过程时间/s 避障过程时间/*
(e)
⑴
GVO 算法
本文算法
图4
G V O 算法与本文算法在多障碍场景下避障效果对比
表4机器人与障碍物初始状态
编号x /(m )
y /(m )
6/(deg )v / ( m / s )〇)/ (rad /s )
机器人1-1.0
-1.0
45 1.0
0.0机器人211.0-0.51800.80.0机器人3-2.0 6.00.00.70.0障碍物1 6.0 5.01800.8
0.2障碍物2
10.0
10.0
-135
1.0
0. 25
由图6(a)(b )知本文算法避障过程用时13.3s，G V O 算 法避障过程用时19.5s，本文算法避障用时更短，其中G V O
b
一
避障过程时间/*
(c)
避障过程时间/s
(d)
I II ill IMai7.«ai IftM
图5本文算法多障碍场景避障过程6.3s 时刻状态图
避障过程时间、 避障过程时间/s
(e)
ffl
GVO 算法
本文算法
图6 G V O 算法与本文算法在同时存在多机器人和多
障碍物场景下避障效果对比
算法在避障过程4. 7S 时机器人1与障碍物1发生碰撞。分 别调整t p 为58、1〇3、153、2〇8,0¥0算法均无法安全完成避障 过程，表明G V O 算法仅获得障碍物瞬时速度的情况下无法 完成复杂避障，避障过程中可行控制集为空的情况导致机器 人停滞不前，并最终导致碰撞。
图6(e) (f)为算法平均运算时间对比，避障过程本文算 法平均运算时间为〇. 47s,G V O 算法平均运算时间为0. 69s, 本文算法用时更短。4.3
不同数量障碍物场景算法运算时间对比
通过对不同数量障碍物场景进行多次随机实验，每次实 验机器人都以（-1, -1)为起点、（8,9)为目标点，障碍物在
(-1，-1)到（8,9)之间随机分布，给定随机速度，障碍物每 个采样时刻改变角速度和线速度的概率为0. 2，对10次相同 数量障碍物场景实验得到的平均运算时间求均值，并以其为 数据进行线性拟合得到图7。
从图7中可看出本文算法与G V 0算法平均运算时间随 着障碍物数量增多而增长的速度不同，本文算法运算时间增 长较慢，即本文算法减少了不必要的复杂运算。但不同情况 下本文算法省去的运算时间不同，取决于机器人与障碍物生 成的速度障碍的分布情况。
障碍物数*
图7不同数置障碍物场景G V O 算法和本文算法 平均运算时间对比
表S 算法平均运算时间对比场景GV0算法平均运算时间/(S)
本文算法 本文算法与G V 0算法对比
场景10.440.37降低15.9%场景20.500. 38降低24%场景30. 620. 42降低32. 3%场景4
0.750. 46降低38. 7%场景5
0.79
0. 52
降低34. 2%
注：场景1 -场景5分别为1 -5个障碍物存在时的避障场景。
5结语
本文在动态环境下提出V O 与G V 0组成的分级速度障
碍算法，可有效简化G V O 算法中不必要的计算。建立碰撞 时间评价函数，使算法得到更多可行控制。引入启发式紧急 避障控制生成，改善了可行控制集为空时的避障。本文的局 限主要是假设障碍物运动参数已知，未来的工作重点是考虑 障碍物运动参数和位置不确定性的情况下使算法可靠运行。参考文献：
医疗箱
[1 ]
Fiorini P,Shiller Z. Motion Planning in Dynamic Environments U- sing Velocity Obstacles [ J ]. The International Journal of Robotics Research, 1998,17(7) ：760 -772.
(下转第 290 页）
i m m
—285
—
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议