基于改进智能水滴算法的移动机器人路径规划

李登峰，杨 曦

(长安大学 电子与控制工程学院，陕西 西安 710064)

0 引 言

近年来，智能优化算法得到了广泛的研究和应用，取得了很好的效果。智能水滴算法(intelligent water drop，IWD)是一种新的仿生优化算法，其主要设计思路来自于对河流中水滴的运行观察和模拟，实际环境中如果不存在障碍，水流将径直流向目标即为最佳流动路径[1-2]。但是实际上河流中存在大量的障碍物，但是水滴的运行过程能够采取最合理方式绕过障碍物，实现路径的最佳选取，因此智能水滴算法就是模拟水滴流动行为，构建了类似于水滴运行过程的避障算法，从而查找到目标位置的最优路径[3]。与经典的水滴种群、差分进化、粒子群等算法相比，智能水滴算法的避障原理与机器人的路径规划中的障碍物规避问题具有很多相似点，因此采用智能水滴算法进行机器人路径的最优规划具有原理上的优势。

但是在实际研究中，IWD算法是一种新兴的优化算法，利用IWD算法进行机器人路径规划层面的研究不多，但是可以借鉴其在车辆等系统路径规划中的研究成果。例如，文献[4-6]中分别采用传统的IWD算法进行实际问题的研究，有效解决了车辆路径优化问题，并对优化系统的开发进行了研究和设计；文献[7]从改善算法进化种群多样性的层面对IWD算法进行研究，并将其应用到车辆路径优化问题中，实现了算法优化效果的提升，获得更为理想的车辆路径规划效果；文献[8]从多目标优化角度对车辆路径优化问题进行研究，并结合IWD算法进行了多目标优化算法的研究，实现了更为理想的车辆路径规划效果。尽管IWD算法应用在路径规划研究中已有成功经验[9-11]，但是整体研究仍然较少，特别是IWD算法应用到机器人路径规划中的研究成果更少。

文中主要是针对机器人路径规划问题，利用IWD算法进行规划设计，同时为了提高路径规划的效果，对IWD算法进行了同步改进，利用邻域水滴个体的扰动搜索实现进化过程的改进，实现了更为理想的机器人路径规划结果。

1 机器人路径规划问题

1.1 模型描述

首先对仿人机器人运行模型进行研究[12]，其运行结构示意见图1。

图1 仿人机器人运行模型

图1中，角度参数φh、φk、φa分别关系着腿髋、膝部以及脚踝关节的行进轨迹，并将其设定成采用时间变量的运行函数。同时设定脚踝关节、小腿部以及大腿部与机器人脚底位置上的部件长度分别是la、lk、lh。基于图1的仿人机器人运行模型，可构建数理模型形式为：

x[φh(t),φk(t),φa(t)]=lhsin[φh(t)]+

lksin[φh(t)+φk(t)]+lasin[φh(t)+φk(t)+φa(t)]

(1)

对模型1所示仿人机器人运行模型进行求导，可得机器人脚部位置的速度参数vf：

(2)

仿人机器人在运行过程中，机器人脚部与地面的接触点是x(t)，假定仿人机器人匀速运行，且其速度为vTM，则可得接触点x(t)的计算模型是：

(3)

其中，参数t0是仿人机器人脚跟部与地面接触的时刻；参数x0是仿人机器人脚跟部与地面接触的初始位置。

在机器人行动过程中，如果式2、式3对于运行过程的计算不存在误差，则可得理想模型vf=vTM，而接触点位置上的摩擦力能够产生保持机器人运动的动力。否则，如果计算存在误差，则可得模型vf≠vTM，进而导致仿人机器人脚位置与真实的平移距离之间存在一定偏差，该偏差值可采用积分形式表示为：

(4)

其中，偏移项e0=x(φ(t0))-x(t0)，参数项e0是仿人机器人脚部的初始点位置。如果模型4计算得到的误差数值过大，则会导致仿人机器人脚部与接触地面之间产生过大的摩擦力，不利于运行流畅性的提高。因此，在仿人机器人运行轨迹优化过程中需要考虑机器人运行速度的合理性。

1.2 栅格目标模型构建

将机器人运行区域构建成栅格模型，同时将机器人的运行环境建立成数字地图模型形式，模型中的所有环境信息均可表示成序号的索引形式，常采用两种方法进行：序号表示方法以及坐标表示方法。栅格地图模型中，可利用其所处的二维平面的位置坐标(xg,yg)进行栅格的表示，其与序号表示方法可实现相互转换，转换模型形式为：

(5)

式中，参数Num表示栅格地图模型的序号编码；参数N表示栅格地图模型的列参数取值。

在所构建的栅格地图模型中，为了简化计算方法，提高机器人控制响应能力，机器人的运行并不是随意的，将其限定在8个方向，见图2。

图2中，机器人运行的8个方向是上下左右，此外还有45度角的四个方向，分别是左前(F-L)、左(L)、右(R)、左后(B-L)、右后(B-R)、右前(F-R)、后(B)、前(F)。在构建上述栅格地图模型以后，利用数据传感器可对机器人运行的环境信息进行检测，并将障碍物位置进行标记，对于不存在障碍物的位置设定成自有区域，采取膨化方式对栅格地图模型中的障碍物进行处理，并将机器人模型进行简化，得到其运行的点模型。然后对机器人的运行路径进行规划，路径可采用集合形式进行表示：

图2 机器人行进方向

Patht={S,P1,…,Pi,…Pk,G}

(6)

其中，参数S是机器人运行的起点位置；参数G是机器人运行的终点位置；参数Pi是机器人运行的一系列中间点位置，可表示为Pi=(xgi,ygi)或者Pi=Numi，则可得地图坐标转换模型形式为：

(7)

其中，参数(x,y)是机器人运行区域所处的二维坐标系；参数w是机器人运行区域栅格模型结构的分辨率，由此可得机器人运行路径长度为：

(8)

基于以上模型定义，机器人运行过程中的路径规划可采用栅格数据的组合优化策略进行模型的构建，具体形式为：

(9)

其中，参数项C(PLt)是机器人运行过程模型的约束模型，其主要是避免路径中的障碍物与机器人出现碰撞事故；参数项minL是PLt选取的路径最小值。参数项C(PLt)的计算形式为：

(10)

基于以上模型定义，可将机器人运行过程模型的路径规划建模为约束优化问题，其优化目标是获得一条最短的不存在障碍物的线路，保证机器人可顺畅地最快速运行到目标终点。

2 智能水滴算法改进

2.1 IWD算法

IWD算法运行中主要涉及两个参数：水滴泥土参量参数soil(IWD)以及水滴运行速度velocity (IWD)。在水滴算法进化过程中这两个参数是时变的[13-14]，在水滴由位置i到位置j的流动过程中，水滴运行的速度变化量是Δvelocity(IWD)，该参数值与运行河道路径上的泥土参数量soil(i,j)具有典型的反比函数关系：

(11)

其中，参数项av、bv和cv是算法参数的预设定制。算法进化过程中参数soil(IWD)和velocity(IWD)的变化具有一致性，可表示为：

Δsoil(IWD)=Δsoil(i,j)

(12)

同时，soil(IWD)和velocity(IWD)之间具有耦合关系，soil(IWD)取值会对velocity(IWD)取值产生一定影响，这种影响具有非线性特性，可表示为：

(13)

其中，参数项av、bv和cv是算法参数的预设定制，另一参数time(i,j)物理学计算模型为：

(14)

具体到IWD算法中，可利用算法参数进行如下定义：

(15)

其中，参数HUD(i,j)是IWD算法中定义的启发函数，该函数为反向函数。

则soil(IWD)参数量的剩余量是：

soil(i,j)=ρ0×soil(i,j)-ρn×Δsoil(i,j)

(16)

其中，参数ρ0和ρn是IWD算法中定义的权重量，并且满足：

ρ0+ρn=1

(17)

水滴内soil(IWD)更新计算如下：

soil(IWD)=soil(IWD)+Δsoil(i,j)

(18)

河道路径中soil(IWD)的取值越大，水滴的运行速度越慢，其对于水滴的运行起到阻碍作用，因此水滴会根据河道中soil(IWD)取值大小进行路径的自适应选取，具体到IWD算法中则采用概率p(i,j)对其进行表示，形式为：

(19)

其中，参数ε是恒定正值；参数g可确保soil(IWD)参数转换是正值：

(20)

其中，参数项min(soil(i,j))为IWD算法运行过程中河道环境最小泥土量soil(IWD)取值。

2.2 邻域扰动IWD算法

在以上定义的IWD算法中，仅对水滴途径的河道soil(IWD)取值进行更新，并未对整体的流经河道soil(IWD)取值变化情况进行考虑。为了增加水滴成功运行的几率，提高水滴到达目标的成功率，具体见图3。

图3 邻域扰动过程

图3(a)和图3(b)分别是文中选取的IWD算法以及设计的基于邻域扰动的改进算法示意。根据图3(b)可知，IWD算法中，水滴由位置S1移向S2过程中，会不断地对节点当前位置上的邻域位置进行广播探测，并根据河道中的soil(IWD)取值进行实时调整，可实现算法优化过程的性能改进。例如，机器人从位置S1移向S2过程中，需要选取一跳最佳的运行轨迹，其途径目的地b，在这个过程中，机器人会实时广播soil(IWD)信息数据包，对节点j邻域区间内的soil(IWD)数值进行实时更新，从而实现对IWD算法的实时更新。

soil(IWD)数值更新可采用式6进行，对于水滴个体j邻域区间内的位置k，若其与目标位置b的间距比其与目标位置j的间距小，则edge(k,j)的泥土信息数据不发生更新操作，否则位置k上将生成新的进化个体IWD'。该个体的soil(IWD)初始值设定成0，速度参数velocity(IWD')的初始值设定成InitVel，其更新模型为：

(21)

由此可得edge(k,j)中soil(IWD)参数变化量计算如下：

(22)

进而可得edge(k,j)中的soil(IWD)参数更新如下：

soil(k,j)=(1-ρn)soil(k,j)-ρn(1+hdk-hdj)Δsoil(k,j)

(23)

2.3 算法描述

在机器人路径规划中，机器人运行过程中的路径编码是实现优化过程的前提，水滴个体可模拟机器人的实时运行个体，机器人从初始位置出发，此时将机器人的路径集更新为空集。水滴个体可对机器人运行过程进行模拟，选取下一个最佳的路径途径位置[15]。基于以上过程，可设计邻域扰动IWD算法，伪代码如下：

初始化：av,bv,cv,as,bs,cs,ρn,d、ini_soil(i,j)、ini_velIWD；

while算法未终止 do

for∀IWD do

设定候选表是∅；

while路径未构建do

IWD：=empty vehicle；

current nodei:=depot；

while限制条件不满足do

决策路径位置(j)；

current nodei:=next nodej；

更新机器人路径数据；

endwhile

endwhile

评价路径选取效果；

endfor

更新最佳路径TSe；

更新全局最佳路径GBS；

for水滴精英个体do

邻域更新；

endfor

endwhile

return最佳路径方案。

3 实验分析

硬件配置：CPUi5-3500k，内存16 G ddr3 2400k。软件平台：数值模拟软件matlab2012a。利用计算机模拟标准测试方式实现对所提邻域扰动智能水滴算法的性能验证。

3.1 标准测试

首先选取标准测试函数对邻域扰动智能水滴算法的优化性能进行研究，选取的测试对象形式如下：

算例1：

算例2：

为更加清晰地对算法性能进行验证，选取原始的IWD算法、文中算法以及差分进化算法进行实验分析。实验对比结果见图4。

(a)算例1

(b)算例2

图4分别展示了原始IWD算法、文中算法以及差分进化算法在选取的算例1和算例2上的实验对比结果。根据实验结果可知，虽然在算法前期集中算法的收敛过程相差不明显，但是在中后期文中算法的收敛速度和收敛精度要显著优于选取的对比算法，体现了文中算法较好的收敛性能和精度指标，以及改进有效性。

3.2 路径规划实验

机器人路径规划过程中，设定栅格地图路径模型的分辨率指标是1，水滴种群规模是40，α=2，β=15，引力增益指标p=100，障碍物指标设定为ρ0=2，μ=2，ε=2，实验区域设定为30×30栅格地图模型，对比算法选取原始智能水滴算法和文中改进的智能水滴算法。针对不同的栅格地图模型，设置智能水滴算法的迭代上限是50，则设定的实验对象的路径优化结果见图5。

在对比实验中，虽然两种测试算法均获得了优化结果，但是文中算法相对于原始智能水滴算法具有更快的收敛速度，其速度提升幅度达到1倍以上，并且在收敛精度上，文中算法可获得比原始智能水滴算法更短的机器人路径规划结果。根据以上实验结果可知，文中算法的收敛速度和机器人路径的优化结果均得到了全面提升。

(a)原始智能水滴算法

(b)文中改进智能水滴算法

(a)原始智能水滴算法

(b)文中改进智能水滴算法

4 结束语

文中提出一种基于改进智能水滴算法的移动机器人路径规划算法，主要贡献如下：(1)针对移动机器人路径规划问题，利用栅格模型对其进行模型构建，将其简化为优化问题；(2)引入智能水滴算法，并采用邻域扰动过程对算法性能进行改进；(3)利用Matlab软件建立了移动机器人路径规划问题仿真平台，具有研究拓展性。下一步主要是对算法的计算时效性进行改进，主要从两个方面，即设计并行化的路径优化算法以及对算法本身进行改进，从而提高算法的收敛速度。