基于人工势场法的多智能体编队避障方法

郑延斌，席鹏雪，王林林，樊文鑫，韩梦云

(1.河南师范大学 计算机与信息工程学院，河南 新乡 453007； 2.智慧商务与物联网技术河南省工程实验室，河南 新乡 453007)(*通信作者电子邮箱xipengxue@163.com)

0 引言

多智能体编队问题是指多智能体在执行任务的过程中相互之间保持某种几何形状不变。编队问题是多智能体系统研究的热点问题之一，在许多领域都有很好的应用，如军用、民用、游戏等。受环境因素的制约，多智能体编队在执行任务的过程中，不可避免地会遇到环境中的静态障碍(如环境中的山川、河流、房屋、树木等)和动态障碍(如环境中其他移动的智能体)，如何合理地避开这些障碍物，又能最大限度地保持编队队形，是多智能体编队研究的关键问题之一，目前研究者提出了许多解决的方法。

常用的多智能体编队避障算法有：领航跟随法[1]、人工势场法(Artificial Potential Field method, APF)[2]、虚拟结构法[3]、基于行为法[4]等。其中人工势场法具有结构简单、实用性好、实时避障且路径平滑的优点，但容易陷入局部最优。针对此问题研究者提出许多改进方法如：仇国庆等[5]提出了将多智能体系统与传统遗传算法相结合的编队控制方法，利用最优染色体调节智能体的运动参数至最佳状态，同时将领航跟随法与人工势场法结合，有效地保持队形的稳定性，人工势场法中归一化其超过最小安全距离的斥力，达到有效避障目的；Kowdiki等[6]提出了领航跟随法框架的混合编队控制技术，用人工势场法规划领航智能体的导航路径，使整个编队控制具有稳定性；Dang等[7]在动态环境下，利用旋转势场和排斥力使得机器人逃离障碍物并避免局部极小问题。编队避障过程中存在的“局部困扰”[7-8]情况，加入了“回环力”，使多智能体编队能够通过障碍物区域。然而这些方法没有考虑随机性障碍物对编队控制及避障的影响。

人工势场法中增益系数设置的局限，使得该算法不适应随机性障碍物的动态环境，近几年为了增加避障算法的环境适应性，研究者对人工势场法的增益系数进行改进，如：张立阳等[9]提出了将模糊控制法与人工势场法结合，实时调整斥力与引力的增益系数，实现轨迹跟踪与避障；翟红生等[10]提出了将量子粒子群算法引入到人工势场法，优化斥力与引力势场的增益系数，实时控制机器人的运动。这些方法解决的是单个智能体的避障问题，没有涉及多个智能体的避障。有涉及多个智能体避障并修改其增益系数的方法，比如：Chatraei等[11]使用Mamdani模糊系统所给出的人工势场斥力与引力的增益系数来验证该系统的避障效果。

针对动态环境中，多智能体编队耗时长、环境适应度差的问题[12]，本文在动态队形变换策略[12-13]的异构模式下，使用人工势场法对编队中各个智能体实时规划避障；针对人工势场的引力增量系数和斥力增量系数设置的局限，利用布谷鸟搜索算法(Cuckoo Search algorithm, CS)[14]，随机搜索适合当前环境的引力和斥力增量系数。使用效率函数对实验的数据进行评价及分析，验证本文优化方法的合理性及有效性。

1 相关基础

1.1 多智能体动态队形变换避障策略

多智能体编队在进行编队避障时，需要根据所处环境的约束，进行实时有效的避障。本文用文献[13]提出的伸缩因子，选择适合的编队队形避障方法。伸缩因子是指多个智能体组成的队形维持现有形状不变，只是在大小上实现伸缩的参数[13]。伸缩因子用符号ρ表示，ρ≥ρm，而ρm表示队形伸缩因子的阈值。利用伸缩因子来确定避障的队形变换模式指令σ(σ∈{σi|0,1,2|})，伸缩因子计算式如式(1)所示：

ρ=Dmax/D

(1)

其中：D表示智能体小组队列的宽度；Dmax表示障碍环境下智能体小组运行路线的可通行路径的最大宽度。

动态队形变化策略的模式如下：

1)零变换模式(σ=0)：若ρ≥1，则Dmax≥D，表明编队中的智能体不需要改变现有队形即可通过障碍区。

2)同构变换模式(σ=1)：若ρ<1且ρ≥ρm，表明智能体编队不能直接通过障碍区，但是可以压缩队形大小、不改变队形形状的方式通过障碍区。

3)异构变换模式(σ=2)：当两种模式均不成立时，即ρ<ρm时，表明只能破坏多智能体编队现有的队形，才能通过障碍区。

1.2 人工势场法

传统人工势场法的基本思想是编队中各个智能体所处的环境充斥着混合势力场，环境中的目标点充斥着引力势场，方向是由智能体指向目标点；环境中的障碍物充斥着斥力势场，方向是由障碍物斥力的合力指向智能体。多智能体编队在人工势场法的引力和斥力的合力状态下朝向目标点运动，并且规划出一条平滑无碰撞的路径。

1.2.1 引力势场函数

在混合势场中，目标点对于智能体产生引力，算法中所用到的引力势场函数如式(2)所示：

Uatt(q)=katt×(q-qg)2/2

(2)

式中:Uatt(q)为引力场;q为当前的智能体;katt为引力增量系数，其值大于零；qg为智能体与目标点的相对距离。引力Fatt(q)是由引力势场函数的负梯度所得，计算式为式(3)所示：

Fatt(q)=-▽Uatt(q)=-katt|q-qg|

(3)

1.2.2 斥力势场函数

在混合势场中，障碍物对于智能体产生斥力，算法中所用到的斥力势场函数，计算式如式(4)所示：

(4)

式中：q-q0表示多智能体与障碍物的距离;ρ0为障碍物的影响距离;krep为斥力增量系数。斥力Frep(q)是由斥力势场函数的负梯度所得，大小为式(5)所示：

Frep(q)=-▽Urep(q)=

(5)

文献[15]在斥力的分量进行了改进，解决了人工势场法的局部极小值问题，如式(6)～(7)所示：

(6)

(7)

则在混合势场中，智能体所受的合力如式(8)所示：

(8)

1.3 布谷鸟搜索算法

布谷鸟搜索算法(CS)是由Yang等[14]提出的一种群智能优化算法，也是一种新型的启发式搜索算法。该算法思想来自于布谷鸟的繁殖行为和育雏习性，主要的两个策略是布谷鸟的巢寄繁殖方式和莱维飞行(Lěvy flight)机制。通过随机游走的方式搜索得到一个最优的鸟窝来孵化自己的鸟蛋，这种方式可以达到一种高效的寻优模式[16]。莱维飞行是一类非高斯随机过程，其平稳增量服从Lěvy稳定分布[17],其优点是在飞行过程中，利用步长较小的短距离与较大步长的长距离行走相互交替，提高了全局搜索能力，不易陷入局部最优。利用L(λ)的随机搜索路径思想，随机步长的Lěvy分布如(9)所示：

L(s,λ)～s-λ； 1<λ≤3

(9)

式中s为莱维飞行得到的随机步长。

2 基于APF与CS的编队避障方法

针对动态环境下的随机性障碍物，使用动态队形变化策略下的异构模式进行编队避障，并利用布谷鸟搜索算法(CS)改进人工势场法(APF)的增益系数设置的局限，用领航跟随法[1]控制编队队形，本文提出了基于APF与CS的编队避障方法。

2.1 改进引力与斥力的增益系数

考虑到环境障碍物的随机分布特性，故利用布谷鸟搜索算法中莱维飞行机制的随机搜索思想，产生增量系数，消除增量系数的固定值所带来的局限性。

使用莱维飞行机制的Lěvy分布函数式(9)，改进引力场函数中的增量系数katt和斥力场函数的增量系数krep，由于编队方向始终是朝向目标点的引力方向，式(9)所产生的集合，故选择引力增量系数与斥力增量系数的值分别如式(10)、(11)所示：

katt=max(a-λ)；λ∈(1,3]

(10)

krep=min(a-λ)；λ∈(1,3]

(11)

式中a是由莱维飞行得到的随机增量系数。

改进式(2)、(4)，如下所示：

(12)

(13)

改进后对应的引力与斥力如式(14)、(15)所示：

Fatt(q)=-▽Uatt(q)=-a-λ|q-qg|

(14)

Frep(q)=-▽Urep(q)=

(15)

2.2 效率函数

环境适应度函数[12-13]用来评价编队队形适应当前环境的程度，其值越小，说明该队形变换对环境的适应度越好,计算式如式(16)所示：

fenvfit=Ifdd+Iect+Ifcct

(16)

其中：Ifdd表示为队形失真度；Iecr表示为能量消耗率；Ifcct表示为队形变换收敛时间比。

本文为了验证多智能体编队在随机性障碍物环境的适应性，利用方差作为效率函数评价避障方法的有效性和合理性，如式(17)所示：

fenvfit=Iδ

(17)

式中：Iδ表示编队避障过程的时间方差，其值越小说明编队避障方法的环境适应性越强。

2.3 多智能体编队避障方法

该方法的主要思想为：先建立常用的智能体队形知识库，当检测到障碍物区域仅有有一条路径，计算伸缩因子，选择适合当前避障的最佳队形；检测到多条路径时，使用人工势场法

进行编队避障，并使用领航跟随法保持队形通过障碍区。多智能体编队避障流程如图1所示。

图1 多智能体编队避障方法流程Fig. 1 Flow chart of obstacle avoidance method of multi-agent formation

3 仿真实验及分析

为了充分验证本文方法的有效性和合理性，进行了3组仿真实验。选取的编队队形为V型(此队形的密集编队覆盖观察角最大，不易丢失队形),使用领航跟随法控制编队队形。每个智能体的速度为0.1 m/s，匀速运动，队形的夹角设置为45°，环境中的障碍物个数设为150(障碍物的位置随机生成)。为了适应环境中不同方向的编队避障，选取3个方向：(0，π/4)，π/4，(π/4，π/2)，对应3个目标点为：(15，23)，(23，23)，(23，15)。每组实验对比3种方法，每种方法实验10次，得到相应编队避障时间结果数据如表1所示，编队避障时间是指编队从初始点到目标点整个过程所需的时间。从表1中可以看出，本文方法的避障效率更高。

表1 不同方法10次实验编队避障时间Tab. 1 Formation obstacle avoidance time of different methods in ten experiments

实验1 选取的目标点是(15，23)，V型编队中的每个智能体的初始坐标分别是(0，0)，(-1，1)，(-1，-1)，(-2，2)，(-2，-2)。(0，0)点是领航智能体的坐标，其他的是跟随智能体坐标。选择本文方法、文献[12]方法和文献[5]方法，针对随机障碍物的不同分布情况做了10次实验，对应最优的多智能体编队避障图如图2中所示。

由图2(a)可知，在随机障碍物分布的环境中，多智能体编队从开始点计算伸缩因子选择异构模式的人工势场法进行动态避障，平滑的避障轨迹经过障碍物区域，过程中用领航跟随法保持编队队形。从整个编队避障时间可以得出，本文方法优于文献[12]方法、文献[5]方法，队形保持相对稳定。

由图2(b)中可知，环境中的随机障碍物个数多，文献[12]方法用环境适应度函数获得最佳队形，使用的是柱型编队进行避障。V型编队从初始队形变换成柱型队形，然后开始进行编队避障，到达目标点恢复到原来的队形。此方法在初始点编队队形变换目标队形需要一定的时间，在到达目标点后恢复到原来的队形也需要时间，这两次的时间增加了整个编队避障的时间。

从图2(c)中可知，在避障过程中编队的队形无法保持良好，文献[5]方法是编队避障过程中，利用遗传算法得到最优染色体，进行反变化换形成解数据，得到智能体的姿态信息，动态调整编队中的智能体。虽然此方法可以将智能体的运动参数调整到最佳状态，但是在障碍物个数多的环境中，这样的方法实时调整智能体的姿态反而增加了等待时间，整个编队避障效率将会降低。

实验2 选取的目标点是(23，23)，选用本文方法、文献[12]方法与文献[5]方法进行对比，三种方法相应最优的多智能体编队避图如图3所示。

从图3可知，本文方法的多智能体编队避障时间是相比较优的，而且在避障过程中的编队队形保持良好；文献[5]方法在避障过程中没有保持好队形，但比文献[12]方法的编队避障时间优；文献[12]虽然避障时间较长，但在编队过程中不用考虑队形保持问题。

实验3 选取的目标点是(23，15)，选用本文方法、文献[12]方法与文献[5]方法进行对比，三种方法相应最优的多智能体编队避如图4所示。

图2 实验1不同方法最优多智能体编队避障(目标点(15,23))Fig. 2 Optimal multi-agent formation obstacle avoidance of different methods in experiment 1 (object point (15, 23))

图3 实验2不同方法最优多智能体编队避障(目标点(23,23))Fig. 3 Optimal multi-agent formation obstacle avoidance of different methods in experiment 2 (object point (23,23))

图4 实验3不同方法最优多智能体编队避障(目标点(23,15))Fig. 4 Optimal multi-agent formation obstacle avoidance of different methods in experiment 3 (object point (23,15))

从图4可知，本文方法的多智能体编队避障时间相比较优，本文方法与文献[5]方法的编队队形都能保持队形。

为了进一步验证本文方法的性能，使用随机障碍物进行50次实验，对本文方法、文献[12]方法与文献[5]方法作对比，结果如图5所示。由图5可知，本文方法在不同目标点的避障时间都优于文献[12]方法和文献[5]方法。

图5 不同目标点不同方法的50次实验结果对比Fig. 5 50 experimental result comparison of different methods with different target points

使用效率函数对这10次以及50次的各个目标点编队避障进行评价，结果如图6所示。由图6可知，本文方法的编队避障时间方差相比文献[12]方法、文献[5]方法偏低，表明本文方法在随机障碍物分布的动态环境下，具有较好的环境适应性以及避障高效性。

图6 不同方法10次及50次实验避障时间方差对比Fig. 6 Variance comparison of obstacle avoidance time for different methods between 10 and 50 experiments

4 结语

本文提出了一种人工势场法与布谷鸟搜索算法相结合的多智能体编队避障方法，考虑随机性障碍物对动态队形变换策略的影响，改进异构模式下的避障方法。首先，根据检测到的障碍物信息，计算伸缩因子选择异构模式，在此模式下使用人工势场法进行编队避障，为每个智能体规划平滑无碰撞的路径，并用领航跟随法保持编队的队形；其次，针对人工势场法的引力增益系数和斥力增益系数设置的局限性，使用布谷鸟搜索算法中莱维飞行机制的随机搜索思想，搜索出适应环境的增益系数，增强了人工势场法的环境适应性。仿真实验结果验证了所提方法既能动态控制编队避障和队形，又能适应当前环境。