一个复杂有界环境下的改进极限环避障算法

王 震， 陈 熙， 张 浩， 蔚 涛， 邓 科，季袁冬

(1.四川大学空天科学与工程学院, 成都 610064；2.四川大学数学学院, 成都 610064)

1 引 言

近年来，模仿自然界生物群体行为的群体智能理论逐渐成为研究热点.避障是一种最基本的群体行为.相应地，现有的避障算法主要基于虚拟势场，主要有两类：一类是人工势场，包括传统人工势场以及对其势场函数[1-3]、增量系数[4]、避障机制[1,5]等的改进，该类算法根据形成的虚拟势场，沿着势能降低的方向实时规划避障路径；另一类则以圆形[6-8]、椭圆形[9-10]等极限环作为势场，该类算法利用二阶非线性函数的极限环特性和障碍的位置信息实时得出障碍绕行路线.

但是，随着研究的深入，人们发现传统的人工势场法与极限环法在处理复杂环境下的群体避障问题时存在不足，障碍的不规则性、非预知性与环境的有界性特别是不能很好地应对的挑战.近年来，大量学者对此开展了研究.如文献[10-12]针对凹型不规则障碍，通过设置虚拟目标点或虚拟牵引力来引导智能体对其进行绕行，解决了传统方法在此类环境下的目标不可达问题.针对既不规则又非预知的障碍，文献[1]以虚拟目标点解决不规则障碍绕行问题，仅利用局部信息计算所得的虚拟势场便实现了对非预知障碍的成功绕行.值得注意的是，上述研究仅针对预知/非预知复杂环境下的单智能体避障，无法从原理上避免局部极小值与路径抖动.此外，针对带边界环境下群体避障问题，文献[13]提出了基于速度场这一虚拟势场的群体避障算法，但其通过边界完成群体聚集这一特性使其无法适应大规模边界场景或开放场景.

鉴于现有对于不规则、非预知障碍与有界环境下的避障算法研究中针对群体避障的研究较少，对三种问题同时存在的复杂环境下的群体避障算法研究更少，我们提出以下方案：仅利用单个智能体的有限探测信息，在局部可视不规则障碍的边缘设置平衡点，以该点为中心建立局部极限环，群体沿所有局部极限环的包络对该障碍进行绕行.另一方面，我们将群体在局部可视边界上的投影点设置为虚拟障碍，以改进的人工势场斥力函数作为该虚拟障碍的势场函数，以避免与边界发生碰撞.

2 避障算法

2.1 极限环

极限环[10]是非线性方程(组)的相平面中的一个孤立闭曲线，最早由Van de Pol发现并用图解法证明了曲线的存在性.

考虑如下二阶非线性系统方程：

(1)

其中x1和x2是系统的状态变量，γ∈{-1,1}表示旋转方向(γ=1表示沿顺时针旋转，γ=-1表示沿逆时针旋转)，α1和α2是两个正常数，ρ=1-(x1/R)2-(x2/R)2，用于确定极限环的形状.文献[6]利用李雅普诺夫函数证明了该方程是全局渐近稳定的.为了展示系统方程的极限环，我们将其改写为

(2)

其中

xff=[x2,-x1]T，

α=diag([α1,α2])，

xfb=ρ[x1,x2]T.

图1 圆形极限环轨迹示意图：顺时针(a)，逆时针(b)

2.2 局部极限环避障

传统极限环避障算法以障碍为中心设计环形虚拟势场，智能体在该势场引导下进行障碍绕行.当障碍不规则时，上述方法得到的绕行路径通常存在冗余，如图2所示.此外，当障碍非预知时，我们无法观测到障碍的完整信息，上述方法无法使用，如图3所示.为此，我们将局部极限环与包络的思想引入极限环避障算法中，得到了局部极限环避障算法.

Fig.2 Obstacle-avoiding path of an agent

图3 智能体的感知范围

鉴于障碍不规则与智能体探测能力有限，我们利用局部极限环法来实时规划避障路径，即智能体根据传感器探测到的障碍局部边缘信息，以距离智能体最近的边缘点为平衡点，以该点为中心建立局部极限环，通过绕行一系列局部极限环来实现避开障碍的效果，相应的绕行路径为上述局部极限环的包络，如图4所示.

图4 智能体的局部极限环避障

局部极限环避障算法的具体实施步骤如下.

(i) 初始化智能体i的位置、速度、绕行方向及目标点的位置，其中绕行方向γi=0.

(ii) 根据第i个智能体和设定目标点的位置信息，写出过两点的直线方程Li:ax+by+c=0,其中a≥0.

(iii) 若障碍在智能体的探测范围内，且直线方程Li穿过所探测到的局部障碍，则继续后面步骤.

(iv) 设(oxi,oyi)为群体中第i个智能体在障碍边缘的可变平衡点.若此智能体绕行方向γi取值为0，则执行步骤(v)，否则执行步骤(vi).

(vi) 设(xi,yi)为群体中第i个智能体的位置，rv为预设极限环半径.我们用下式来计算智能体i的速度：

(3)

这样，随着群体的运动，直线方程Li和平衡点(oxi,oyi)不断变化，但绕行方向一旦确定则维持不变.重复步骤(ii)～(vi)，直至绕开障碍.

借助人工势场的思想，我们在边界处引入一个虚拟斥力场，使智能体在力场中受力运动，从而避免与边界碰撞.

在传统人工势场法中，智能体、障碍物是运动空间中的质点.假设q=(x,y)、qo=(xo,yo)分别代表它们的位置.传统人工势场法中的斥力势场函数定义为

(4)

其中krep为斥力增益系数，ρ(q)为智能体到障碍的空间距离，ρ0为障碍对智能体的影响半径.对上式求负梯度可得如下斥力函数：

Frep(q)=-∇Urep(q)=

(5)

当智能体采用传统斥力势场函数进行避障时，一旦智能体进入边界的影响半径，就会受到其斥力势场影响.然而，并不是所有情况都需要势场的影响.如图5所示，智能体的位置虽然处于边界势场的影响范围之内，但其运动速度并未指向边界，不存在与边界发生碰撞的风险，因而并不需要采取避障措施.因此，在设计边界势场时，我们有必要将智能体的位置与速度同时纳入考虑.

图5 一个非必要的势场影响

(6)

进一步，我们定义智能体i在二维空间中qi点的改进斥力势场函数如下：

(7)

其中λ为斥力势场判定系数，krep为斥力增益系数，ρ(qi)=|qi-qoi|为智能体到可变投影点的距离，ρ0为斥力的作用距离.此时，智能体i在qi点受边界的斥力为斥力势场函数的负梯度

Frep(qi)=-∇Urep(qi)=

(8)

在上述改进的斥力势场函数的引导下，智能体可望成功避免与边界发生碰撞.

3 仿 真

为了验证本算法的适应性和有效性，我们设计了不规则障碍和带边界障碍两种典型场景，然后在相同的群体模型[15]下对本文方法与基于人工势场的避障方法进行了对比性仿真.

3.1 不规则障碍场景下的群体避障

在不规则障碍的情况下，算法绕行路径往往存在冗余，本算法可以较好地解决这一问题.如图6所示，在避障过程中，智能体以实时探测得到的边界平衡点为中心建立局部极限环，按照该局部极限环进行动态避障，得到了近似所有局部极限环包络的一条绕行路径.较传统极限环的绕行路径而言，该绕行路径消除了路径冗余.

图6 不规则障碍场景下的局部极限环群体避障

在不规则障碍场景下，基于局部极限环法与人工势场法的100个智能体的避障仿真结果对比如图7，8所示，图中箭头代表智能体的速度矢量，下同.

在图7(a)和图8(a)中，当t=26.4s时，局部极限环算法的避障进程快于人工势场法，速度匹配程度地更高，说明本算法在避障初期的表现较人工势场法为优.

在图7(b)和图8(b)中，在不规则障碍场景下，人工势场法中少部分智能体会陷入虚拟势场的局部极小点，进而随着大部分智能体朝目标点运动，这部分智能体受智能体间吸引力的影响最终会脱离局部极小点，但仍造成了如图8(b)所示的“拖尾”和“落后”现象.而本算法较好地解决上述问题，在不规则障碍场景下具有更好的适应性.

为进一步对比本文算法与人工势场法的适应性和有效性，在不规则障碍场景下，我们对不同的群体规模分别进行200次仿真，然后对其统计结果进行了对比参见图9.

从图9(a)可见，该场景下两种方法均能有效的避免碰撞.在图9(b)中，基准线表示算法规定的总仿真时长，基准线以下的点表示群体在总仿真时长内完成了整个避障过程，基准线上的点则表示群体在总仿真时长内未完成避障过程，避障过程自动终止.仿真结果表明，本算法在不同群体规模下均能够完成避障，且避障时间受群体规模的影响较小.相对而言，人工势场法仅在群体规模较小(本文仿真中群体规模小于50)时能完成整个避障过程，但避障时间受群体规模影响较大.可见本文算法的适应性和有效性均优于人工势场法.

将改进的人工势场斥力与局部极限环结合，我们可以解决带边界障碍场景下的群体避障问题.为验证其适应性与有效性，我们设计了由边界和不规则障碍组成的带边界障碍场景，然后进行仿真，并与人工势场法进行对比.两种算法(取100个智能体)的仿真结果如图10所示.

由图10可以看出，人工势场法在边界的约束下有不少智能体陷入局部极小点，路径抖动现象剧烈.另一方面，基于改进斥力函数的局部极限环法避免了路径抖动现象，能产生较为平滑的轨迹.可见本算法在带边界障碍场景下的适应性和有效性较好.

进一步，在带边界场景下，我们进行同3.1小节类似的统计仿真，结果如图11所示，图中的基准线含义参见3.1小节.由图11(a)可见，随着群体规模的扩大，两种算法都可以有效地避免碰撞，但随着碰撞个数的上升，本算法适应性较好.可见在带边界障碍场景中，本算法能够完成不同群体规模下的避障任务，避障时间随着群体规模的增加而小幅上升，而人工势场法仅能完成小规模群体(群体规模小于30)的避障任务，且避障时间随着群体规模的增加而大幅上升.

面向障碍形态多样及带边界的非预知环境，我们提出了一种局部极限环群体避障算法.该算法在传统极限环法的基础上加入了改进的边界斥力函数.仿真结果显示，相比人工势场法，本算法可有效克服局部极小点与路径抖动问题，使避障路径更合理，运动轨迹更平滑.此外，本算法可有效避免碰撞且避障时间短，具有较好的有效性与适应性.