陈 卓 茅云生 宋利飞 董早鹏 杨 鑫 房新楠

(武汉理工大学高性能船舶技术教育部重点实验室1) 武汉 430063) (武汉理工大学交通学院2) 武汉 430063)

0 引 言

水面无人艇(unmanned surface vehicle, USV)智能系统包括运动控制系统、传感器系统和通信系统，其中运动控制系统下的路径规划子系统则是无人艇实现自主航行的核心，在某种程度上代表了无人艇智能化水平的高低，同时也是无人艇安全航行和执行任务的基本保障[1-2]，因此，寻找一种合理高效的路径规划技术是无人艇研究的重要方向.

人工势场法作为一种广泛使用的路径规划算法，具有模型简洁、计算快速、路径光滑等优点[3]，是水面无人艇最常用的路径规划技术之一.但是势场模型本身具有局限性，在实际应用时往往需要加以改进.操文芷等[4-6]针对传统势场法中无人艇易陷入局部最小点的问题，分别提出了基于不同逃脱策略的改进势场法；刘建等[7-8]将势场法与栅格模型进行了结合，使得路径安全且较短，但是路径不光滑；Li 等[9]提出了切向势场法，克服了路径的局部抖动问题.但是，以上这些方法都是基于传统势场模型，没有考虑无人艇路径的最优化问题和合理性问题，导致路径只在某方面较优，而且没有考虑无人艇的运动能力约束，因而无法满足无人艇的实际规划要求.

微分进化算法(differential evolution algorithm，DE)是一种基于群体差异的启发式全局搜索算法，由Storn等[10-12]为求解Chebyshev多项式而提出.相比于传统的进化算法，DE算法具有模型简单、受控参数少、鲁棒性强的特点，近年来在优化计算等方面得到了广泛应用.本文将微分进化算法和人工势场模型进行结合，把DE算法的优化特性引入到传统势场模型中，提出了势场路径评价方程和基于进化策略的改进势场模型，实现了对势场路径的初步优化；并且在路径规划中考虑了以无人艇最大转向角为代表的无人艇运动能力约束，提出了平滑算法对局部路径进行二次优化.通过不同环境下的仿真试验对算法效果进行了验证.

1 势场模型

1.1 势场法路径规划原理

路径规划问题可以描述为这样的数学模型：在给定空间内，寻找出一条连接起始点与目标点并且满足一定优化条件的无碰曲线.实现对环境中的障碍物的避碰以及对目标点的追踪是路径规划中的两个关键点，直接决定了路径规划的结果.

人工势场法借鉴了物理学上的势场概念，将障碍物和目标点对无人艇运动轨迹的影响以虚拟势场的方式进行表征.在势场法中，目标点产生引力场，障碍物附近产生斥力场，环境中各点所受到的势场力与无人艇到各障碍物及目标点的距离有关，可由势场方程计算得到.无人艇在规划环境中沿着势场合力的方向从起始点向目标点运动，见图1.

图1 势场法路径规划

1.2 势场方程

采用一个标准引力方程和带有可调参数的斥力方程作为基本模型.其中无人艇在每一位置处的运动方向由目标点的引力和障碍物的斥力的矢量和所决定，引力和斥力的大小与无人艇的位置相关.

无人艇在环境中受到的引力为

(1)

式中：Fatt为目标点引力，方向由USV位置指向目标点；Dug为无人艇当前位置到目标点的欧式距离.

同时，无人艇在障碍物附近会受到斥力作用，斥力方程为

(2)

式中：Frel为障碍物斥力，方向由障碍物位置指向无人艇；Duo为无人艇当前位置到障碍物的最小距离；Dinf为斥力影响半径，即无人艇在障碍物的影响范围内时，才会受到斥力，否则斥力为零；a和b为斥力场形状系数，改变这两个系数的取值可以构造不同的势场模型.在传统势场模型中，a和b是固定的，一般取1和2，这导致其无法适应于较为复杂的环境.本文采用DE算法对a和b进行了实值寻优，对于不同的规划环境，可以得到不同的最优势场系数，从而构造不同的势场方程.

在确定势场系数后，可利用式(1)～(2)计算出无人艇在每一点处受到的势场合力及其方向：

F=Fatt+∑Frel

(3)

A=∠F

(4)

式中：F为无人艇在势场中所受的引力和斥力之和；A为合力F的方向角，直接决定无人艇下一步长内的航行方向.

2 基于进化势场模型的无人艇路径规划算法

2.1 势场路径评价方程

路径规划的目的是在充分考虑路径代价的基础上生成最优或满意路径，传统势场模型缺乏路径评价机制，虽然能生成一条路径，却未必最优.因此，文中提出了势场路径评价方程，用于评估不同势场模型下的路径性能.在无人艇路径规划中，避碰系数、长度系数和光滑度系数是需要考虑的三个主要因素.避碰系数是路径安全性的保障，长度系数和光滑度系数影响无人艇的航行效率.

避碰系数由在斥力影响范围内的所有路径点到相应障碍物的距离之和表示，见图2.为环境中第i个障碍物；Dinf为障碍物的影响半径；Pj,…,Pj+m为落在该障碍物斥力圈内的路径点.

图2 路径避碰系数

路径的整体避碰系数为

(5)

式中：M为障碍物总数；m为该障碍物斥力影响范围内的路径点总数；d(Oi,Pj)为第i个障碍物Oi到第j个路径点Pj的最小距离.fa越大，表示路径整体到障碍物的距离越大，避碰程度越高，路径越安全.

路径光滑度由路径上所有的相隔路径点之间的距离和来表示，见图3.其中Pi，Pi+1，Pi+2为三个连续的路径点，d为PiPi+2间的直线距离，由几何关系可知，d值越大，Pi，Pi+1，Pi+2三点所成的夹角越大，路径在该局部就越光滑.

图3 路径光滑度系数

路径的整体光滑度为

(6)

式中：N为路径点总数；d(Pi,Pi+2)为相隔路径点(Pi,Pi+2)之间的直线距离.fs越大，路径整体曲率变化越小，减少了不必要的转向次数，因而操纵系统越高效.

路径长度由各相邻路径点之间的距离和来近似表示，路径的长度系数为

fl=Nl

(7)

式中：N为路径点总数；l为无人艇运动步长.fl越小，路径总长度最短，无人艇执行任务过程中所消耗的源和时间就越少，效率越高.

结合以上路径性能系数，本文构造了如下的势场路径评价方程.

f=αfa+βfs-γfl

(8)

式中：α，β，γ对应系数的权重，满足α+β+γ=1.在应用时，可根据不同的规划要求为三个系数设置不同的权重.

2.2 基于DE算法的进化势场模型

DE算法采用了与遗传算法相似的的进化流程，但是在变异操作时使用了差分策略，即利用种群中个体的差分向量对个体实现扰动，实现个体变异.这种变异方式有效地利用了种群分布特征，提高了算法的搜索能力，弥补了遗传算法中变异方式的不足.

DE算法采用实数编码方式，在实值参数寻优上具有优势，因此本文采用DE算法来对势场系数进行优化.

步骤1种群初始化 选择势场形状参数a和b组成实数串：xi=(xi,1,xi,2)，作为种群中的“染色体”，xi,1,xi,2代表这个二维“染色体”上的基因.然后以随机方式产生初始种群：

i=1,2,…,NP;j=1,2，…,D

(9)

步骤2变异操作 DE算法利用差分策略来实现染色体变异：从种群中随机选取两个不同的个体，求出其向量差，将向量差按一定比例缩放后与待变异个体进行相加，即得到变异个体：

vi(g+1)=xr1(g)+F·(xr2(g)-xr3(g)),

i≠r1≠r2≠r3,

(10)

式中：F为缩放因子；xi(g)为第g代种群中的第i个个体；vi(g+1)为第g代个体xr1(g)变异后产生的中间体.

步骤3交叉操作 对第g代种群{xi(g)}及其变异中间体{vi(g)}进行个体间的交叉操作：

(11)

式中：xi,j(g)为第g代种群中第i个个体上的第j个基因值；vi,j(g+1)为其对应的变异中间体上的等位基因值；CR为交叉概率，jrand为1，2，…,D的随机整数，j=jrand保证了变异中间体上至少有一个基因遗传到了下一代.

在进化过程中，为保证解的有效性，需要判断个体中的各“基因”是否满足边界条件.如果不满足，则取为相应的边界值.

步骤4选择操作 DE算法采用贪婪算法来选择下一代种群的个体.

(12)

式中：适应度函数f取为势场路径评价方程，即以每个个体所对应的势场路径的整体性能来评价该个体的适应度.适应度值越大，该个体上的信息被遗传到下一代的可能性越大.

通过DE算法对势场形状系数进行优化后，可以得到无人艇在环境下的最优势场系数，再次利用势场法原理即可获得其对应的势场路径.

2.3 基于最大转向角的路径平滑处理

图4 无人艇相邻步长内的最大转向角

由图4中几何关系，可求得两步长间的最大转向角为

(13)

式中：路径步长l在势场法中设定；最小回转半径R可由无人艇的回转实验测得.

基于进化势场模型所产生的路径在避碰系数、光滑度和长度等性能上得到了改善，但是由于势场法本身的局限性，无人艇的最大转向角约束无法被兼顾，因而可能会出现局部路径转角过大、出现多余弧度的问题，无法保证所规划路径的合理性和可行性.为此提出了基于无人艇最大转向角的简单平滑算法来对势场路径进行二次优化.算法的思路是：从初始点开始，到最后一个路径点为止，依次从路径中取出三个连续路径点Pi、Pi+1和Pi+2，并判断该三点所形成的角度φ是否满足最大转向角要求.如果夹角φ大于最大转向角φ，则删除中间路径点Pi+1，并更新路径，直到路径上的所有点都满足最大转向角约束，见图5.

图5 基于无人艇最大转向角的路径平滑算法

2.4 算法流程图

基于进化势场模型的无人艇路径规划算法分别从势场模型层面和路径点层面实现了对无人艇路径的优化.在势场模型层面，在给定环境条件的前提下，以势场路径评价方程的形式评估不同势场模型下的路径，并使用DE算对势场模型系数进行进化寻优，以得到势场模型下的最优路径；考虑到势场模型本身的局限性，对势场路径的局部路径点进行二次平滑处理，以使其满足无人艇的最大转向角要求.算法的具体流程图见图6.

图6 基于进化势场模型的无人艇路径规划算法流程图

3 仿真实验及结果分析

图7为基于传统势场模型和进化势场模型所得到的路径.两图中环境信息完全相同，环境参数设置如下：无人艇从航行起始点(0，0)驶向任务目标点(10，10)，其中，障碍物半径robs和影响半径Dinf均取0.5，无人艇运动步长l设为0.2，两步长内最大转向角φ=30°.表1为此相同环境下基于这两种势场模型的无人艇路径的性能对比.

图7 基于传统势场模型和进化势场模型的无人艇路径规划

从仿真结果可以看出，基于进化势场模型的无人艇路径规划算法所得到的路径在整体性能上明显优于基于传统势场模型所得到的路径.在路径长度上，基于进化势场模型的路径长度为14.319 7，相比于传统势场模型，缩短了约9.75%；在操纵性方面，传统势场模型的路径在经过平滑算法处理后，仍需要以较大角度转舵5次来实现对障碍物的避碰，而基于进化势场模型的路径只进行了两次舵角微调就有效完成了避碰，而且路径平滑前后的差别不大，这表明了在势场模型层面对路径进行优化的有效性.

表1 基于传统势场模型与进化势场模型的无人艇路径性能对比

同时，为了验证本文算法在实际环境下的适应性，对复杂海事环境下的无人艇路径规划也进行了仿真.仿真结果见图8.图中的障碍物分布是基于真实海事地图的模拟，其中海岛以多个圆形的组合体来近似表示.从仿真结果可以看到，在复杂海事环境下，采用本文算法后的无人艇能够有效地避开各个岛型障碍，到达目标点，而且路径长度较短.图9为该路径下无人艇航向角改变量随运动步长数变化的曲线图，由图9可知，无人艇的整体航向角改变很小，稳定在-10°～15°；在第5步、35步及40步附近，出现了较大的航向改变，但是也远小于无人艇的最大转向角φ=30°，这表明路径在操纵性和跟随性方面也能很好地满足无人艇的实际运动要求.

图8 复杂海事环境下基于进化势场模型的无人艇路径规划

图9 无人艇单位步长内的航向角改变量

4 结 束 语

无人艇的路径规划问题是无人艇领域最基本的问题之一，针对传统势场模型在路径最优性上的不足，文中提出了一种基于进化势场模型的无人艇路径规划算法.通过在势场模型中引入DE算法和路径平滑算法，分别从模型层面和路径点层面实现了对路径的优化，有效地提升了无人艇的航行效率.仿真结果表明，本文算法继承了势场法计算简单、路径安全可靠的优点，同时兼顾了无人艇对路径的优化性要求和无人艇的运动约束条件，所规划出的路径短且平滑， 很好地满足了无人艇的实际规划要求.