基于定向极限环的Cucker-Smale群体避障模型

张 浩， 陈 熙， 王 震， 蔚 涛， 钟苏川

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

1 引 言

生物体普遍存在群体避障行为，如森林中穿梭的鸟群，湖泊里游动的鱼群，地上寻找食物的蚁群等生物群体仅依靠简单的规则和局部通讯便能顺利避开运动过程中的障碍到达目标，且整个过程中呈现出整体协调有序的行为表现.

在工程领域，考虑到无人机、机器人等自主智能体在多障碍物环境很容易发生碰撞，也有必要研究群体实时避障问题.为此，国内外学者做了大量研究，提出了多种方法，如模型预测控制法[1]、人工势场法[2]、极限环法[3-6]等.其中，针对多无人机协同规避控制的问题，文献[1]构建多目标优化控制模型，通过纳什最优的分布式预测控制方法实现了多无人机防撞.针对无人机集群内部防碰撞以及遭遇突发障碍时的集群防碰撞问题，文献[2]引入力学概念及集群内部吸引力、排斥力以及编队构型力等概念，通过集群个体间的信息共享以及类脑知识发育构建了基于群信息共享和类脑反射的无人机防碰撞模型.文献[4]基于生物群集理论，提出了基于极限环理论的智能体避障控制算法，实现了静态障碍环境下的多智能体编队避障.文献[5]将势场法和极限环相结合，实现了机器人在人和静态障碍物混合场景中避障.文献[6]根据极限环设计了并行椭圆极限环(PELC)和多准则优化(PELC *)算法，实现车辆有效、快速、安全避开任何形状障碍物.

然而，上述文献大多仅研究单个或少量个体的实时避障，而密集群体内部的个体碰撞很容易产生链式效应，因而采用上述方法很难取得较好的大规模群体避障效果.此外，文献[7-8]通过将障碍物定义为特殊智能体来避免碰撞，但未考虑复杂场景.文献[9-10]则考虑设置虚拟领导点减少群体避障过程中的碰撞，但是虚拟领导点的路径需要提前规划，不适合未知复杂环境下的实时避障.针对上述多障碍物环境下的大规模群体避障问题，本文在传统极限环避障和现有群体模型[12]基础上改进了多障碍物合并方法，引入了定向的运动规则，提出了一种基于改进Cucker-Smale模型的定向极限环群体避障算法.

2 极限环避障算法

极限环避障方法是一种局部路径规划方法[3]，其实质是个体能够与障碍物保持一定距离，按照顺时针或者逆时针的方向绕过障碍物边沿，以避免与其发生碰撞.其非线性动力系统的方程如下：

(1)

其极限环如图1所示，其中平衡点为x1=x2=0，当01时,轨迹向内旋转.

图1 系统(1)的极限环Fig.1 Limit cycle diagram of system(1)

为了减少个体不必要地绕行，通常引入感知-规避方法中的碰撞锥思想[12-14]来设计极限环避障判断规则.碰撞锥思想广泛应用于实时碰撞检测和威胁评估，其原理是仅基于个体和障碍物相对位置矢量和相对速度矢量的简单几何关系实现个体与障碍物碰撞检测与评估.考虑到个体感知能力有限，本文在传统碰撞锥上加入个体探测范围(蓝色圆)，如图2所示.

图2 个体的障碍物探测示意图

(2)

基本的极限环避障步骤如下.

(ii) 计算避障判定系数，如果为1则继续后面步骤，否则障碍物om对个体ui作用力设为0，即

(3)

(iii) 根据以下二阶非线性方程来计算个体ui在任意位置的作用力：

(4)

则避障加速度为

aoi=koHmPui

(5)

3 群体避障模型

对于有多个障碍物存在的场景，一般的处理方式是简单合并邻近障碍物[4]，其前提是环境是已知的.本文考虑在未知环境下模型根据所设计的群体避障模型的障碍物合并方法和定向避障规则，不断探测障碍物环境逐步获得环境信息，进而采取合适的策略，最终快速通过多障碍物区域，朝向目标点运动.

3.1 避障模型

为了群体能顺利通过障碍区域，模型采用文献[12]的群体模型，并在此基础上引入避障绕行项如下：

(6)

h(pui,Ω,info)=HPui=

(7)

3.2 障碍合并方法

当探测到多个障碍物时，模型将处理分为两个阶段.

第一阶段，群体对探测范围内的障碍物进行两两通道测量，并将获得的通道近似值传递给邻域其它个体.如图3所示，两个体ui和uj都探测到两个障碍物o1、o2，并分别获得其探测通道dci，dcj.推广到一般情况，对于可探测到障碍物o1、o2的个体u1,…,ui,…,un，其探测通道分别为dc1,…,dci,…,dcn，则该通道的近似值取

dcmin=min{dc1,…,dci,…,dcn}.

图3 个体的通道示意图

第二阶段，根据通道近似值判定当前两个障碍物o1、o2是否需要合并.

(i) 当d(o1,o2)=dcmin

(ii) 当d(o1,o2)=dcmin>C，即通道近似值小于通道最小安全距离时，模型认为群体不能从当前障碍物间通过，此时合并障碍物并取离个体最近的障碍物的极限环作用力为该个体避障作用力.如图3所示，离个体ui最近的障碍物是o1，则该个体所受避障作用力为aoi=koH1Pui.

一般情况下，对于两个及以上数量的障碍物，可两两合并形成障碍物群Μ，其充分条件如下：

(I) ∀oi,oj∈Ω，有d(oi,oj)

(II) ∃oi,oj∈Ω，有d(oi,oj)≥C时，若在om,…,on∈Ω,使得d(oi,om)

3.3 定向避障规则

在障碍物绕行过程中，真实障碍物的形状大小以及威胁程度往往未知，个体基于当前位置和障碍物极限环确定的绕行方向不一定合适，从而可能会在绕行过程中出现回头的现象，因而需要对个体绕行方向进行定向，以确保在连续障碍场景的时候不会出现群体紊乱.具体规则是：当个体探测到新的障碍物时，所受作用力大小由当前最近障碍物极限环避障作用决定，作用力方向需要根据当前障碍物与上一个时刻障碍物关系进行规定.

图4 个体绕行场景1

图5 个体绕行场景2

4 仿 真

在MATLAB仿真环境中进行实验，计算机配置为AMD锐龙R5 4600六核处理器，16 G内存，3 GHz主频，Window10操作系统.

实验一，邻近多障碍静态场景避障.

为验证邻近多障碍静态场景群体避障效果，设置该场景有四个静态障碍物o1,o2,o3,o4，其中o1和o2，o1和o3，o2和o4通道分别为dc1,dc2,dc3，且dc1C.群体避障过程图和轨迹图如图6，7所示，图中箭头为个体速度矢量，虚线圆半径表示个体的群体内部期望保持间距(即群体内部排斥力作用范围)，实心圆表示障碍物，轨迹图中不同颜色表示不同时刻(如橙黄色表示初始时刻，红色表示最终时刻)，下同.

由群体避障过程图6和轨迹图7可以看出，个体在探测到障碍物群o1o2和单个障碍物o1、o2时，依据当前状态选择合适的绕行方向，并在离开障碍物区域后重新聚集在一起，朝向目标点运动.

作为对照，传统极限环避障模型在该场景中的仿真见图8.

(a)

(b)

(d)

图7 实验1中的群体避障轨迹

(a)

(b)

在图8(a)中，群体在从障碍物o1，o2间的狭窄通道通过时与障碍物发生碰撞，可见传统算法不能很好处理邻近障碍物场景.图8(b)中，群体通过探测障碍物o1，o2间的通道确定其不能从该通道通过后便根据定向规则，沿着障碍物边沿绕行.可见，相比较于传统算法，新算法在保证实时的前提下，能有效处理邻近多障碍物场景，避免碰撞发生.

实验二,复杂障碍物群场景避障.

为验证新算法对于连续墙及对称矩形等复杂障碍物群的避障效果，我们设置实验二场景为由阻挡群体前进的五个障碍物o1o2o3o4o5组成的障碍物群，孤立障碍物o6、o7、o8和对称矩形障碍物o9、o10、o11、o12.群体避障部分过程图和轨迹图如图9、10所示.

图10 实验二群体避障轨迹

如图9(a)所示，不同于简单合并障碍物的模型，本模型建立在对未知环境不断探测的基础上，根据定向思想使群体一直沿着障碍物边沿运动，最终绕出障碍物群o1o2o3o4o5o6o7，避免个体回头与其邻近个体发生碰撞.如图9(b)所示，群体可以顺利通过对称障碍物，无需考虑局部极小值问题[15]，减少了算法设计难度.在整个过程中群体都能顺利通过复杂障碍物场景，表明算法效果较好.

为验证在不同群体规模和随机初始状态下本算法的适应性和有效性，我们以实验1中的场景进行仿真，取同一群体规模下200次仿真结果平均值为群体避障仿真结果.传统算法(第2节中的极限环避障法)与本算法对比如图11所示.

由图11(a)知，当群体规模扩大时，本算法的平均碰撞个数有所增加.在个体数为200时碰撞个数为6.97，最高碰撞概率为3.48%，远低于传统算法的最高碰撞概率25.55%.由图11(b)可知，群体规模较小时本算法避障时间远小于传统算法.随着群体规模扩大，本算法的避障时间与传统算法趋于相等.综上，随着群体规模扩大，采用本算法群体能安全快速通过该实验场景.相比于基本极限环避障法，本文算法在保证一定避障效率的条件下，群体避障的安全性有了较大提升.

5 结 语

本文研究大规模群体在多障碍物环境的避障问题.首先，为解决多障碍物场景群体避障问题，我们改进了障碍物合并方法，设计了定向规则，进而提出定向群体避障模型.仿真结果表明，采用本算法，群体能顺利安全通过多障碍区域，且算法对于不同群体规模和初始条件适应性较好.