路径规划是机器人技术的重要组成部分，在很多领域中广泛应用，如机器人自主无碰行动、无人机避障飞行、导航、道路网规划、资源配置和路由问题等．路径规划旨在在有障碍物的环境中规划出从起点到目标点的无碰撞最优或次优路径[1]．实际应用中，移动机器人所处的环境不仅存在静态的障碍物，还存在运动的障碍物，如何统一障碍物环境表示并快速规划出无碰撞最优路径，在机器人路径规划中具有重要的研究意义．传统的路径规划算法存在计算效率低和易陷入局部极值等缺点，智能算法与传统算法结合已经成功引入路径规划问题求解中．文献[2]将滚动优化和粒子群优化算法相结合，搜索符合精度要求的路径．文献[3]将免疫算法和人工势场结合，解决动态路径规划中的局部最小值问题．文献[4]在将卷积结构嵌入到神经网络中形成值迭网络的基础上，增加网络的深度和宽度，结合人工势场方法，用势能地图作为网络的输入，增强网络的特征提取能力，提高复杂环境下的路径规划成功率．粒子群优化(PSO)算法作为一种迭代的启发式智能优化算法，具有容易实现、收敛速度快等特点，在很多领域得到广泛应用[5]．基于PSO算法的机器人路径规划具有计算简单、参数少、全局搜索能力强等优点，受到许多研究者的关注[6]．文献[7]采用粒子群优化算法规划了静态环境下的无碰撞折线路径．文献[8]将三次样条函数和粒子群优化算法与平滑路径结合，但对障碍物的检测效率较低．文献[9]将粒子群优化算法与神经网络算法结合，实现矩形障碍物避障的路径规划，但可行路径对编码维度的依赖度较高．粒子群优化算法是机器人路径规划中的高效方法，但仍存在迭代时间长、易陷入局部最优、路径不平滑等问题[10]．本研究提出一种基于神经网络的改进粒子群优化(NNPSO)算法，统一了障碍物环境表示和碰撞检测模型，提高了路径碰撞检测效率和光滑度，可以快速规划复杂障碍物环境下机器人的移动路径．1 神经网络建模与碰撞检测神经网络采用并列连接网络结构，对不同形状的静态、动态障碍物统一建模．路径用起点到终点的点集表示，障碍物用一组线性不等式表示[11]．若路径点的坐标在不等式约束条件内，则表示该点在障碍物内部，否则表示该点在障碍物外部．神经网络可以对路径点集进行规划，由于增加路径点及障碍物个数仅增加网络的规模，不增加总计算时间，因此可以快速实现路径与所有障碍物的碰撞检测．假定：a. 机器人在二维有限范围的笛卡尔坐标空间内运动；b. 机器人环境空间中分布多个障碍物，障碍物简化为矩形或外接圆；c. 障碍物边缘向外扩展机器人尺寸的一半，机器人用质点表示．如图1所示，采用神经网络对环境建模，图中：圆圈表示节点；虚线框表示同类障碍物节点；线条表示不同层间的连接关系；底层的2个节点x和y分别为路径点的坐标值；Im和Om分别为矩形障碍物中间层输入和输出；IC和OC分别为圆形障碍物中间层输入和输出；CR和CC分别为矩形障碍物和圆形障碍物的碰撞检测结果；每一个中间层节点对应障碍物的一个不等式约束条件；中间层和底层的连接权值ω对应不等式中的系数；θTR和θTC分别为矩形障碍物和圆形障碍物顶层节点的阈值；θ1,θ2,θ3,θ4为不等式中的常数项；(θa,θb)为圆形障碍物圆心坐标值；中间层到顶层的连接权值均为1；顶层节点的阈值取中间层节点个数减去0.5后的负值；激发函数f(∙)为阶跃函数[11]．10.13245/j.hust.210207.F001图1障碍物的神经网络建模建立三层神经网络，每一层的输出作为下一层的输入．底层输入为机器人路径点坐标值，顶层输出为路径点与障碍物的碰撞检测结果．根据随时间步长变化的阈值，将路径点同时与所有障碍物进行碰撞检测，提高检测效率．1.1　矩形障碍物模型矩形障碍物以四个顶点为约束条件，以四个不等式的系数和常数分别作为中间层与底层连接的权值和阈值．图1左侧虚框为矩形障碍物的神经网络模型．运动矩形障碍物神经网络表示的输入与输出运算关系为CRt=f(TRt)；(1)TRt=∑m=1GROmt+θTR；(2)Omt=f(Imt)；(3)Imt=ωxm(x+vRxt)+ωym(y+vRyt)+θmt，(4)式中：CRt和TRt分别为顶层节点t时刻的输出和输入；GR为中间层节点数量；Omt为中间层第m个节点的输出；ωxm和ωym为输入层到中间层的权值；Imt为输入层第m个节点的输出；θmt为输入层第m个节点的阈值；vRxt和vRyt分别为矩形障碍物速度矢量的x分量和y分量．式(1)表示底层输入与输出之间的关系；式(2)表示底层输出作为中间层的输入，经激发函数得到中间层的输出；式(3)表示中间层所有节点的输出加上阈值作为顶层输入；式(4)表示顶层的输入经激发函数得到路径点与障碍物的碰撞结果．1.2　圆形障碍物模型圆形障碍物以半径为约束条件，以圆心坐标为中间层节点的阈值．图1右侧虚框为圆形障碍物的神经网络模型．运动圆形障碍物神经网络表示的输入与输出运算关系为CCt=f(TCt)；(5)TCt=OCt+θTC；(6)OCt=f(ICt)；(7)ICt=R2-(x-θa-vCxt)2-(y-θb-vCyt)2，(8)式中：CCt和TCt分别为顶层节点t时刻的输出和输入；OCt为中间层节点输出；ICt为中间层节点输入；vCxt和vCyt分别为圆形障碍物速度矢量的x分量和y分量．式(5)~(8)的含义与矩形障碍物的运算关系相似，不同的是式(5)以半径R为约束条件，以圆心坐标(θa,θb)为中间层节点的阈值．若是静态矩形或圆形障碍物，则速度矢量的两个分量分别为：vRxt=vRyt=0;vCxt=vCyt=0．1.3　障碍物碰撞检测路径点与矩形障碍物和圆形障碍物碰撞检测的输出分别为CRt和CCt，当其值为1时表示路径点位于障碍物内，当其值为0时表示位于障碍物外．设机器人工作环境中有QR个矩形障碍物和QC个圆形障碍物．对路径曲线上的Qe个等分点与环境中的所有障碍物进行碰撞检测E=∑k=1Qe∑j=1QRCRkj+∑k=1Qe∑j=1QCCCkj．(9)式中：CRkj为第k个等分点与第j个矩形障碍物碰撞检测的神经网络输出；CCkj为与圆形障碍物碰撞检测的神经网络输出．若E=0，则所有路径点均不在障碍物上，路径可行；若E0，则部分路径点位于障碍物上，该路径有碰撞．神经网络建立的碰撞检测模型可同时检测路径与所有障碍物是否碰撞，缩短计算时间．2 基于改进粒子群优化算法的路径规划2.1　粒子群优化算法的迭代公式采用带惯性权重的低维度粒子群优化算法快速搜索路径，通过三次样条函数进行平滑处理．设路径起点和终点位置由用户设置，中间d个路径节点通过粒子群优化算法搜索．定义粒子群种群规模为n，粒子维度为d，速度和位置的迭代公式为Vijk+1=ωVijk+h1r1(Pbij-Pijk)+h2r2(Pgj-Pijk)；(10)Pijk+1=Pijk+Vijk，(11)式中：Pijk和Vijk分别为粒子i(i=1,2,⋯,n)第j(j=1,2,⋯,d)维分量在第k代的位置和速度；r1和r2为[0，1]上的随机数；h1和h2为学习因子，分别用以调节粒子的自身经验和群体经验权重，h1和h2取值范围为[0，4][12]；Pbij为粒子本身个体极值；Pgj为全局极值；ωPSO为惯性权重，按下式进行线性递减ωPSO=ωmax-(ωmax-ωmin)k/Kmax，(12)其中，Kmax为最大迭代次数，ωmax和ωmin分别为最大权重和最小权重．ωPSO随着迭代次数k的增加逐代递减．式(10)中惯性权重系数与粒子速度相乘，当ωPSO值较大时，粒子的搜索范围大；当ωPSO值较小时，在较小范围内精细搜索．线性惯性权重可以使算法在初期具有较强的全局搜索能力，后期具有较强的局部搜索能力，从而提高整体性能．2.2　路径曲线平滑处理针对粒子i对应的路径，以路径起点pi0、位置向量pij(j=1,2,⋯,d)及终点pi,d+1作为型值点，两两形成子区间，对每个子区间作三次样条平滑处理．设其中子区间[pij,pi,j+1]的路径曲线段为Lij(u)=aiju3+biju2+ciju+dij((i=1,⋯,n;j=0,1,⋯,d),u∈[0,1]).若将d+1个子区间的三次样条曲线拼接成平滑的路径曲线，则曲线函数具有二阶连续导数，系数aij,bij,cij,dij须满足约束条件：Lid(1)=pi,d+1,Lij(0)=pij    (j=0,1,⋯,d)；Lij(1)=Li,j+1(0)    (j=0,1,⋯,d-1)；Lij'(1)=Li,j+1'(0),Lij''(1)=Li,j+1''(0)(j=0,1,⋯,d-1).增加首末端点的一阶导函数值作为边界条件求解方程，求出所有子区间曲线的系数，得到平滑路径曲线．2.3　适应度函数对平滑路径曲线进行Qe等分，设等分路径点为qik，其中路径曲线起点qi0=pi0，终点qi,m+1=pi,d+1．以路径长度为适应度值，粒子i的适应函数为Fi=∑k=0Qe||qi,k+1-qik||，(13)式中||qi,k+1-qik||为qi,k+1和qik之间的距离．2.4　算法流程NNPSO算法通过神经网络对环境建模和碰撞检测．首先在粒子群优化算法中以较低的编码维度构造路径，然后将路径节点的坐标代入三次样条曲线函数中进行平滑处理，最后利用神经网络对平滑后的曲线路径等分点集进行碰撞检测．算法通过多次迭代优化路径，实现步骤如下，图2为算法流程．10.13245/j.hust.210207.F002图2NNPSO算法流程图输入 地图、障碍物信息输出 全局极值路径步骤1 神经网络进行动态障碍物环境建模，设置路径起点和终点，当前迭代次数设置为0；步骤2 随机生成粒子群初始种群；步骤3 三次样条函数对路径作平滑处理，并等分曲线得到等分点；步骤4 根据式(13)计算各粒子的适应度值；步骤5 根据式(9)进行碰撞检测，若E0，则更新适应度值Fi←EFi；步骤6 根据粒子的适应度值更新个体极值和全局极值；步骤7 根据式(12)更新惯性权重；步骤8 当前迭代次数加1，若达到最大迭代次数，则输出最优路径，结束算法，否则按式(10)和(11)更新各粒子的位置和速度，并转步骤3．3 仿真实验与结果分析在静态环境(障碍物均静止不动)和动态环境(存在运动的障碍物，不考虑障碍物间的碰撞)下采用Matlab进行路径仿真实验．NNPSO算法的参数设置为：种群规模n=50；最大迭代次数Kmax=100；两个学习因子h1=h2=2；最大权重ωmax=0.9；最小权重ωmin=0.4．仿真环境范围按比例缩放至20 m×20 m．3.1　静态环境设置障碍物较多和障碍物很多两种不同的静态环境进行仿真实验．图3给出障碍物较多环境下NNPSO算法与传统粒子群优化(SPSO)算法路径规划对比．图3(a)中NNPSO算法的规划效果明显比SPSO算法的平滑．图3(b)中NNPSO算法在迭代次数为20时就开始收敛，在迭代次数为30时已逐渐收敛到最短路径，而SPSO算法直到迭代次数为40时才开始逐渐收敛．NNPSO算法比SPSO算法更快收敛，得到的路径长度也更短．NNPSO算法和SPSO算法最终收敛到的路径长度分别为31.015 8 m和34.629 8 m．10.13245/j.hust.210207.F003图3障碍物较多环境下的路径规划图4给出障碍物很多环境下NNPSO算法与遗传算法路径规划对比．图4(a)中遗传算法规划的路径转折数量比较少，但在转折点处转向角度比较大，而NNPSO算法规划的路径没有明显的转折，路径曲线整体比较平滑．图4(b)中NNPSO算法的收敛速度略快于遗传算法，在第15次迭代已逐渐收敛，而遗传算法在第20次迭代后才逐渐收敛．NNPSO算法比遗传算法更快收敛，得到的路径长度更短．NNPSO算法和遗传算法最终收敛到的路径长度分别为30.871 2 m和33.430 9 m．10.13245/j.hust.210207.F004图4障碍物很多环境下的路径规划从两组对比实验可以看出：NNPSO算法在局部转折位置上比较平滑，转折处理比SPSO算法和遗传算法好，路径振荡较少，所获得的路径更短，收敛至最短路径的迭代次数更少．3.2　动态环境如图5(a)所示，设置存在两个动态障碍物的工作环境，其中矩形和圆形运动障碍物分别沿x轴和y轴正方向运动，到达边界后停止，运动障碍物和机器人的移动速度相同．10.13245/j.hust.210207.F005图5动态环境下的路径规划重复做30次实验，所获得的平均路径长度为35.204 5 m，方差为7.46×10-3．多组路径长度偏差较小，说明在动态障碍物环境中NNPSO算法是稳定有效的．收敛到最短路径的平均迭代次数为45．图5(a)是其中一次实验所获得的路径，可以看出NNPSO算法能够快速有效检测路径是否与动态障碍物碰撞，并及时对路径进行调整，所规划的路径平滑，局部波动较小．图5(b)为路径长度随迭代次数变化曲线，可以看出NNPSO算法在迭代次数为10时已经逐渐收敛，最终可在较少的迭代次数内收敛至最短路径．本研究提出一种基于神经网络和三次样条曲线函数的改进粒子群优化算法，采用神经网络统一静态和动态障碍物环境表示和碰撞检测模型，快速规划出光滑的无碰撞机器人路径．仿真实验结果验证了该算法在机器人路径规划方面的可行性和有效性．