2. 燕山大学 信息科学与工程学院, 河北 秦皇岛 066004
2. School of Information Science and Engineering, Yanshan University, Qinhuangdao Hebei 066004, China
智能机器人研究不断取得新的成果,机器人应用也越来越多地渗透到社会的各个领域。在智能机器人的控制过程中,机器人导航是移动机器人研究的一个重点领域,其中路径规划的研究更是机器人导航能力的一个重要体现[1]。
移动机器人的路径规划主要目标是使得机器人在从起始点到目标点运动的过程中避免出现碰撞,因此需要寻找一条最优的路径实现机器人在移动过程中的无碰撞运动[2]。
国内外学者作了大量的研究并提出了很多方法,目前移动机器人的路径规划方法主要有全局路径规划和局部路径规划[3-4], 其根据传感器获取的信息寻找躲避障碍物的最优路径,并根据传感器信息实时调整路径寻优的策略。可视图算法[5]根据图搜索的完备性理论可以实现最优路径搜索,但是该算法由于计算量大,收敛速度慢,寻优的能力较差,在实时性和可靠性高的要求中无法满足需求[6]。随着遗传算法和神经网络算法的深入研究,很多学者将这些启发式的路径规划算法引入到了机器人的路径规划中实现局部路径规划[7];但这些算法大多存在局部最优的问题,因此为了解决这一问题需要不断地引入新的算法实现路径的最优规划,与此同时增加了算法的复杂度[8]。粒子群优化(Particle Swarm Optimization, PSO)算法[9]具有计算简单、全局寻优能力强、收敛速度快等优点,在各类多维连续空间优化问题上取得了非常好的效果。许多学者对粒子群优化算法在路径规划领域的应用展开了研究。
文献[10]首次将PSO算法引入移动机器人路径规划中,该算法首先采用链接图建立机器人工作空间模型,用Dijkstra算法求得链接图最短路径, 然后用PSO算法对此路径进行优化,得到全局最优路径;但是由于链接图并不能完全体现实际规划环境中的信息,二次优化后得到的路径不一定是全局最优路径, 因此该方法限制了PSO算法的全局寻优能力。文献[11]利用三次Ferguson样条算法对移动机器人路径规划进行描述,将路径规划问题转化为三次样条的参数优化问题,为PSO算法在机器人路径规划中的应用提供了新的思路;但是,由于PSO算法普遍存在早熟收敛问题使得规划结果容易陷入局部极值。文献[12]针对三次样条早熟收敛问题,提出了具有速度变异的PSO算法,从而改善了早熟收敛问题。针对PSO算法在移动机器人的全局路径规划过程中容易出现由于过早收敛导致算法陷入局部最优的问题,文献[13]提出了一种带扰动机制的PSO算法。当算法在搜索最优解的过程中陷入局部最优时,采用粒子修正方法产生新的粒子替代原来的粒子,以此来引导算法摆脱局部最优值,搜索可行路径。为了充分利用PSO算法的全局寻优能力,文献[14]采用罚函数法表示粒子适应度函数,解决过早收敛的问题;并且为了缩短算法的执行时间,在执行过程中加入碰撞能量测试点,但没有给出碰撞和距离能量函数的权重比,因此最佳路径的寻优无法保证。
针对当前移动机器人路径规划中的算法收敛速度慢和局部最优的问题,本文将斥力势场引入PSO算法,首先采用栅格法对机器人的移动路径进行初步规划,并将栅格法得到的初步路径作为粒子的初始种群;然后根据粒子之间的相互协作实现对粒子的位置和速度的不断更新;最后采用障碍物斥力势场构造高安全性适应度函数,从而得到一条机器人从开始位置到目标的最优路径。
1 栅格法实现路径规划的数学建模 1.1 栅格法表示机器人工作空间栅格法将机器人的工作空间表示成一个二维区域,该二维区域进行栅格划分,分解成一系列的以基本元素为单元的最小栅格,在二维区域的自由区域基本元素取值为0,在图 1中用白色表示;障碍物区域取值为1,在图中用灰色表示,如图 1所示为机器人工作空间的栅格法表示。
设机器人在平面上运动的二维区域为AS,原点坐标为(0, 0),任意栅格表示为g(x, y)∈AS,其中x表示该栅格所在的行号,y表示该栅格所在的列号;S={1, 2, …, n}表示所有栅格的集合。x和y方向的最大值分别为xmax和ymax,机器人行走的步长为δ,则机器人工作空间中的每行和每列的栅格数分别为Nx=xmax/δ和Ny=ymax/δ。对于任意的栅格g(xi, yi)与栅格序号集合互为映射关系,则第i个栅格可表示为:
$ \left\{ \begin{align} & {{x}_{i}}=\left( \left( i-1 \right)\bmod {{N}_{x}} \right)+1 \\ & {{y}_{i}}=\operatorname{int}\left( {\left( i-1 \right)}/{{{N}_{x}}}\; \right)+1 \\ \end{align} \right. $ | (1) |
其中:mod为模运算,int为向下取整运算。
1.2 确定栅格由图 1可见,当划分的栅格粒度越小时,障碍物的表示越精确,但是工作空间划分得越细所占用的存储空间会越大,同时会导致算法的复杂度增加;如果选择的栅格粒度太大又容易造成路径规划不准确。因此在栅格法的初步规划中,粒度大小的选择是栅格法面临的主要问题。
在得到机器人工作空间的地图之后,首先根据障碍物的不同的形状进行剖分,其中椭圆和不规则图形按照能覆盖的最小长方形计算,凸多边形则进行三角剖分,根据剖分的结果计算地图中障碍物所占的总面积;然后根据障碍物所占的整个地图的总面积的比例来决定栅格的粒度大小。栅格粒度大小的计算方法如下:
步骤1 在地图中任意选择一个障碍物进行剖分和面积计算。对于椭圆和不规则图形的剖分则需要找到障碍物中所有顶点的中点,然后以(xmax, ymax)和(xmin, ymin)这两个点为对角线绘制矩形,并计算这个矩形的面积;而凸多边形则以某一个顶点为基准点将其剖分为多个三角形,并计算各个三角形的面积。三角形的面积计算按照公式
步骤2 查询地图中是否还存在障碍物,如果存在则转到步骤1继续执行;如果不存在则计算障碍物的总面积
步骤3 根据地图总面积和障碍物的总面积计算栅格粒度。定义hmax和hmin分别为栅格的最大和最小边长,h为栅格的最终边长,计算栅格边长
$ h = \left\{ \begin{array}{l} {h_{{\rm{temp}}}}, \;\;{h_{{\rm{temp}}}} > {h_{{\rm{min}}}}\\ {h_{{\rm{min}}}}, \;\;{\rm{其他}} \end{array} \right. $ | (2) |
机器人移动的二维区域中k个障碍物的集合为B=(b1, b2, …, bk),机器人的自由区域ASfree满足ASfree=B且ASfree∩B=∅。设机器人的起始点为p0=(x0, y0),目标点的位置为pend=(xend, yend)。机器人的行进路径P由工作空间中的点序列Ppath=(p0, p1, …, pm, pend)组成,其中(p1, p2, …, pm)表示全局地图一条路径,即一个点序列,pi为非障碍点。
在XOY地图上建立以为p0为原点,pend为终点的新的X′轴,与之垂直的为Y′轴,则原坐标系中的点在新坐标系中的表示为:
$ \left[\begin{array}{l} {x'}\\ {y'} \end{array} \right] = \left[\begin{array}{l} \cos \alpha \begin{array}{*{20}{c}} {} & {-\sin \alpha } \end{array}\\ \sin \alpha \begin{array}{*{20}{c}} {} & {\cos \alpha } \end{array} \end{array} \right]\left[\begin{array}{l} x\\ y \end{array} \right] + \left[\begin{array}{l} {x_{{p_0}}}\\ {y_{{p_0}}} \end{array} \right] $ | (3) |
其中α为X坐标轴与X′的夹角。
将p0pend线段作m+1垂直等分处理,将pend写为pm+1,其中与X′垂直的平行线簇(l1, l2, …, lm)与X′的交点的序列(p1, p2, …, pm)即为路径的序列,如图 2所示。
规划路径的长度LP为:
$ \begin{align} & {{L}_{P}}=\sum\limits_{i=0}^{m}{\sqrt{{{\left( x_{{{p}_{i}}}^{'}-x_{{{p}_{i+1}}}^{'} \right)}^{2}}+{{\left( y_{{{p}_{i}}}^{'}-y_{{{p}_{i+1}}}^{'} \right)}^{2}}}=} \\ & \sum\limits_{i=0}^{m}{\sqrt{{{\left( \frac{{{L}_{{{p}_{0}}{{p}_{\rm{end}}}}}}{m+1} \right)}^{2}}+{{\left( y_{{{p}_{i}}}^{'}-y_{{{p}_{i+1}}}^{'} \right)}^{2}}}} \\ \end{align} $ | (4) |
由式(4) 可见路径规划问题转化为了在y′pi(i=1, 2, …, m)的空间中寻找最优解。将y′pi(i=1, 2, …, m)的集合作为机器人在行进过程中的初始粒子种群。
2 改进的PSO算法实现路径优化 2.1 粒子速度与位置更新PSO算法是模拟鸟类觅食行为的速度-位置搜索模型,其粒子的优劣程度由粒子的适应度函数f(x)决定,而且每一个粒子在运行的过程根据自身的个体极值Pbest和整个种群目前最优解的全局极值Gbest来更新位置和速度,以在搜索空间中向更好的位置运动,从而搜索全局最优解[14]。
在1.3节介绍的路径规划方法中采用垂直等分的形式按照式(4) 进行处理,所以采用PSO算法时的粒子维数为m,而垂线li上点的Y′坐标则构成粒子的位置编码。
由图 2可见可将粒子定义为由起始点p0经过不同的连接线到达终点pend的距离,即每一个粒子代表一段距离。粒子的适应度函数即为路径长度表达式(4),因此当适应度函数的值越小则得到的解即为最优解。
在m维空间中,第i个粒子的位置可表示为向量Xi=(xi1, xi2, …, xim),通过向量Xi可以确定每个粒子点在链接线上的坐标,计算相邻两点之间的距离,从而计算适应度值。根据适应度值的大小决定当前的解是否为局部最优,如果是则替换历史局部最优Pbest。
局部最优Pbest的适应值随着迭代的进行不断进行更新; 而全局最优Gbest则是与各个Pbest进行比较,如果局部最优Pbest的适应值小于全局最优Gbest则更新全局最优的值为该Pbest的值。
为了得到移动机器人的全局最优路径,需要在计算过程中不断更新粒子的速度和位置,其中粒子i表示为向量Xi=(xi1, xi2, …, xim),粒子的飞行速度为Vi=(νi1, νi2…, νim)。则粒子的速度和位置更新公式如下:
$ \left\{ \begin{array}{l} {\mathit{\boldsymbol{V}}_{i, j}}\left( {t + 1} \right) = \omega {\mathit{\boldsymbol{V}}_{i, j}}\left( t \right) + {c_1}{r_1}\left( {{\mathit{\boldsymbol{P}}_{i, j}}\left( t \right) - {\mathit{\boldsymbol{X}}_{i, j}}\left( t \right)} \right)\\ \begin{array}{*{20}{c}} {\begin{array}{*{20}{c}} {} & {} \end{array}} & {} & {} \end{array} + c{}_2{r_2}\left( {{\mathit{\boldsymbol{G}}_j}\left( t \right) - {\mathit{\boldsymbol{X}}_{i, j}}\left( t \right)} \right)\\ {\mathit{\boldsymbol{X}}_{i, j}}\left( {t + 1} \right) = {\mathit{\boldsymbol{X}}_{i, j}}\left( t \right) + {\mathit{\boldsymbol{V}}_{i, j}}\left( {t + 1} \right) \end{array} \right. $ | (5) |
其中:vi, j(t+1) 和xi, j(t)分别表示t时刻第i个粒子在j维的速度和位置;ω为惯性权重因子,ω取值越大则算法具有较高的全局搜索能力,反之则具有较强的局部搜索能力。惯性权重ω随着迭代次数的增加线性减少,可以使粒子种群在开始时进行大范围的最优解空间的搜索,然后随着迭代次数的增加逐渐缩小搜索范围,从而加强搜索现有解空间的能力。因此本文设计惯性权重ω的取值方法如下:
$ \omega = {\omega _{\max }} - {k_i} \times \frac{{{\omega _{\max }} - {\omega _{\min }}}}{{{k_{\max }}}} $ |
其中:ω的最大值和最小值在本文的实验中取ωmax=0.9,ωmin=0.4;ki为当前的迭代次数,kmax为最大迭代次数。
c1、c2分别为个体和全局的加速因子,即每个粒子受到个体极值Pbest和全局极值Gbest位置吸引的加速度的权重。加速因子使得每个粒子都具有自我总结并向群体中其他优秀个体学习的能力,从而使粒子在前进的过程中向自己的历史最优点以及群体内的全局最优点靠近。其中c1调节粒子飞向自身最好位置方向的步长,c2调节粒子飞向全局最好位置方向的步长。r1、r2为随机数,一般取。Pi, j(t)和Gj(t)分别表示到t时刻为止第i个粒子在j维分量搜索到的个体最优位置以及整个种群粒子的第j维分量搜索到的最优位置。
2.2 构造高安全性适应度函数将人工势场原理引入到适应度函数的构建中,使移动机器人在人工势场中移动时,同时受到目标位置的引力场的引力和障碍物的斥力场的斥力两种力的共同作用。由于斥力场与障碍物有关,因此,机器人在运动的过程中距离障碍物越近则产生的斥力就越大,同时机器人碰触障碍物的危险系数越高。由于引力场的作用与机器人的运动目标位置有关,因此从算法的复杂度考虑,本文构建高安全性适应度函数时只考虑斥力场的作用。
障碍物附近的斥力场函数表示为:
$ {U_{{\rm{rep}}}} = \left\{ \begin{array}{l} \frac{1}{2}\eta {\left( {\frac{1}{{\rho \left( p \right)}} - \frac{1}{{{\rho _0}}}} \right)^2}, \begin{array}{*{20}{c}} {} & {\rho \left( p \right) < {\rho _0}} \end{array}\\ 0, \begin{array}{*{20}{c}} {} & {} & {} & {} \end{array}\begin{array}{*{20}{c}} {} & {} & {\rho \left( p \right) \ge {\rho _0}} \end{array} \end{array} \right. $ | (6) |
其中:η为障碍物的斥力系数;p为机器人在空间中移动时的任意位置,ρ(p)为移动机器人到障碍物的最短距离;ρ0为障碍物的斥力场的作用距离。
为了保证在整个势力场中只有在目标点位置时全局最小,因此在式(6) 的基础上引入机器人与目标点的相对位置,即在原有的基础上乘以一个距离因子:
$ \begin{array}{l} {U_{{\rm{rep}}}} = \\ \left\{ \begin{array}{l} \frac{1}{2}\eta {\left( {\frac{1}{{\rho \left( p \right)}} - \frac{1}{{{\rho _0}}}} \right)^2}{\left( {p - {p_{{\rm{end}}}}} \right)^n}, \rho \left( p \right) < {\rho _0}\\ 0, \begin{array}{*{20}{c}} {} & {} & {} & {} \end{array}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\begin{array}{*{20}{c}} {} & {} & {\rho \left( p \right) \ge {\rho _0}} \end{array} \end{array} \right. \end{array} $ | (7) |
斥力为斥力势函数的负梯度,则可得斥力为:
$ \begin{array}{l} {F_{{\rm{rep}}}} = - {\rm{grad}}\left( {{U_{{\rm{rep}}}}} \right) = \\ \left\{ \begin{array}{l} \begin{array}{*{20}{c}} {\eta {{\left( {\frac{1}{{\rho \left( p \right)}} - \frac{1}{{{\rho _0}}}} \right)}^2} \times \frac{1}{{{\rho ^2}\left( p \right)}}\partial \rho \left( p \right), } & {\rho \left( p \right) < {\rho _0}} \end{array}\\ 0, \begin{array}{*{20}{c}} {} & {} & {} & {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\begin{array}{*{20}{c}} {} & {\rho \left( p \right) \ge {\rho _0}} \end{array}} \end{array} \end{array} \right. \end{array} $ | (8) |
机器人在移动过程中由于路径点的安全性不仅与障碍物的远近有关,还与空间中障碍物的分布密集程度有关,因此由式(8) 可得,移动机器人在空间中的任意位置xi, j处的安全度为:
$ \begin{array}{l} saf{e_{i, j}} = \\ \left\{ \begin{array}{l} 255 - \sum\limits_{m = - s}^s {\sum\limits_{n = - s}^s {sign(m, n)} \sqrt {{{\left( {s - \left| m \right|} \right)}^2} + {{\left( {s - \left| n \right|} \right)}^2}}, } \\ \begin{array}{*{20}{c}} {} & {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{x_{i, j}}不是障碍物点} \end{array}\\ 0, \begin{array}{*{20}{c}} {} & {} & {} & {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{x_{i, j}}{\rm{为障碍物点}}} \end{array} \end{array} \right. \end{array} $ | (9) |
其中:s为模板窗口尺寸因子,并且窗口的实际尺寸为(2s+1)2,当s减小时,窗口中会包含较少的障碍物信息,此时安全系数safei, j增大;sign(m, n)为点xi+m, j+n处的障碍物标志,当xi+m, j+n点为障碍物时sign(m, n)=1,否则,sign(m, n)=0。因此可由式(9) 计算出机器人在移动的过程中所处位置的安全性系数。
则由式(9) 可得路径Ppath的安全度为:
$ {M_P} = {d_0} + \sum\limits_{j = 1}^m {{d_{{p_j}}} + {d_{{\rm{end}}}} = \sum\limits_{j = 0}^{m + 1} {{d_{{p_j}}}} } $ | (10) |
其中:d0为起始点的安全度,
由式(4) 和式(10) 可得路径Ppath的优化函数为:
$ {f_P} = {\omega _1}{L_P} + {\omega _2}{M_P} $ | (11) |
通过调整加权因子ω1和ω2来调整LP和MP在路径规划中所占的比重,从而选择路径和安全性均适中的路线。
2.3 路径优化算法实现设定义n个m维粒子,采用式(11) 作为第i个粒子的适应度函数:
$ {f_P} = {\omega _1}\sum\limits_{j = 0}^n {\sqrt {{{\left( {\frac{{{L_{{p_0}{p_{{\rm{end}}}}}}}}{{m + 1}}} \right)}^2} + {{\left( {y_j^i - y_{j + 1}^i} \right)}^2}} } + {\omega _2}\sum\limits_{j = 0}^{n + 1} {{d_{{p_j}}}} $ | (12) |
其中:1≤i≤m,1≤j≤n,yji为第i个粒子的第j维分量的位置, yji与式(4) 中的y′pi相等。两端和边界的约束分别为:y0i=ym+1i=0和yjmin≤yji≤yjmax,yjmin和yjmax的取值取决于(l1, l2, …, lm)与地图边界的交点。
利用适应度函数对所得的路径集合进行优化, 从而求解全局最优路径,适应度函数得到的值越小,所得的解越优。
算法实现的具体步骤如下:
步骤1 根据图 2的坐标变换求解(l1, l2, …, lm)与地图边界的交点得到yjmin和yjmax。
步骤2 对栅格化得到的粒子种群进行初始化,初始化内容包括:种群的粒子数n、维数m,初始化第i个粒子第j维的初始位置yj0和初始速度vj0。由于vjmax规定了粒子在一次迭代的过程中能够飞行的最大的距离,在本文的取值为位置变化范围的10%,公式表示如下:
$ v_j^{\max } = \left( {y_j^{\max } - y_j^{\min }} \right) \times 0.1 $ | (13) |
由式(5) 得到粒子的第i个粒子第j维的初始速度和位置为:
$ \left\{ \begin{array}{l} v_{i, j}^0 = \left( {2r - 1} \right) \times v_j^{\max }\\ y_{i, j}^0 = \left( {y_j^{\max } - y_j^{\min }} \right) \times r + y_j^{\min } \end{array} \right. $ | (14) |
其中:r一般取[0,1]上的随机数,初始化yj0需要注意两端与边界约束条件。
步骤3 根据式(12) 计算各粒子的初始适应度函数f(yi, j0),得到初始的个体极值pi, j0为每个粒子的当前位置;全局极值pg, j0为个体极值中最好的粒子的当前位置。
步骤4 根据粒子的当前适应值评价每一个粒子。比较当前粒子的历史最优Pi, jt与上次迭代的历史最优值Pbest的关系,计算两者差的绝对值,并保存绝对值差最大的粒子。如果绝对值差最大的粒子历史最优值大于Gbest,则将全局最优值设置为该粒子的位置。
步骤5 对每个粒子按照式(5) 中的位置和式(6) 的速度进行更新,注意粒子两端和边界的约束。
步骤6 对每个粒子求取t时刻的粒子适应度f(yi, jt)以及pi, jt和pg, jt。
步骤7 如果达到了最大迭代次数或者是最小精度要求,则输出最优路径,否则转到步骤4继续执行。
算法流程如图 3所示。
为了验证算法的有效性,以Visual studio 2010为平台,C#语言为编程环境进行仿真。实验的硬件平台为:Intel Core i5 3.20 GHz CPU;4 GB内存;500 GB硬盘,Windows 10操作系统。
为了验证本文算法的有效性,在相同的环境模型下将本文方法与线性递减惯性权重粒子群优化算法(Linearly Decreasing Weight Particle Swarm Optimization, LDWPSO)[13]进行对比实验。
参数设置如下:种群粒子数n=50,粒子的维数m=20,粒子变量维的最大速度vjmax=10,粒子加速度因子c1=c2=0.85;由于粒子的速度计算公式受惯性权重因子ω的影响,并且ω的变化与最大迭代次数有关,因此最大迭代次数需要在开始之前确定,本文的最大迭代次数设定为Itermax=50,而惯性权重因子ω选择从0.9变化到0.4。
3.1 最优路径与收敛性比较采用1.2节的方法确定栅格,经过多次对不同实验环境(包括本文的实验环境1、2以及图 8所示环境)的测试,取lmax=20,lmin=3时栅格粒度较适合实验目的。实验环境1和2相对障碍物较少,因此栅格粒度较大;而图 8中的实验环境下障碍物较密,因此栅格粒度较小。
实验环境1参数描述:实验环境采用15×15方格的环境,环境中障碍物数目为42,每一个方格表示一个障碍物。移动机器人运动起点为(0, 0),终点位置为(14, 14)。
如图 4所示为本文算法与LDWPSO的最优解对比结果。LDWPSO算法在第32次迭代时找到了最优解,本文算法则是在第25次迭代时已经找到了符合终止条件的最优解。因此从算法的收敛性上来看本文算法优于LDWPSO算法,并且寻找的最优路径的栅格长度本文算法为17,LDWPSO算法为19。
图 5给出了本文算法的避障过程,在由第17次向第18次迭代的过程中,能够明显地躲避障碍,并且在搜索的过程中搜索范围较大,能够跳出局部最优。
实验环境2参数描述:实验环境采用10×10方格的环境,环境中障碍物数目为31,每一个方格表示一个障碍物,并且分布无序;移动机器人的起始位置为(0, 0),终点位置为(9, 9)。
由图 6可以看出本文算法克服了局部最优的缺陷并成功搜索到了最优路径,本文算法搜索路径的栅格长度为12,而LDWPSO算法则为14。
图 7给出了两种算法的收敛性比较,可以看出:本文算法在50次的迭代过程中都在第6次找到了局部最优解,第12次迭代之后找到了最优解,并稳定在最优解;而LDWPSO算法则在第17次达到了局部最优并且没有跳出局部最优解。因此从算法的收敛性和克服局部最优解方面本文算法优于LDWPSO算法。
在本实验中采用相同的实验地图,但是实验环境中的障碍物数目、位置以及状态不同。实验结果如图 8所示,由图可以看出对于不同的实验环境,本文算法都能得到最优的路径规划,说明本文算法对于复杂环境具有较高的适应性。
4 结语本文针对传统的粒子群优化(PSO)算法实现移动机器人路径规划中的局部极值问题以及适应度函数在计算过程中的粒子安全性问题,提出了斥力势场下粒子群优化的移动机器人路径规划算法,该算法为移动机器人在复杂环境下的路径规划提供了一种有效的选择。该算法主要有以下特点:1) 该算法利用栅格法实现机器人路径的初步规划,并将初始规划的路径作为粒子的初始种群;2) 根据粒子之间的相互协作实现对粒子的位置和速度的不断更新,解决路径规划中的局部极值问题;3) 采用障碍物斥力势场构造高安全性适应度函数。通过实验仿真验证本文算法能获得路径寻优的最优解,并且算法的收敛速度快。
[1] | 朱大奇, 颜明重. 移动机器人路径规划技术综述[J]. 控制与决策, 2010, 25(7): 961-967. (ZHU D Q, YAN M Z. Survey on technology of mobile robot path planning[J]. Control and Decision, 2010, 25(7): 961-967.) |
[2] | 蔡自兴, 贺汉根, 陈虹. 未知环境中移动机器人导航控制理论与方法[M]. 北京: 科学出版社, 2009: 8-12. (CAI Z X, HE H G, CHEN H. Mobile robot navigation in unknown environment control theory and method[M]. Beijing: Science Press, 2009: 8-12.) |
[3] | CLERC M, KENNEDY J. The particle swarm-explosion, stability and convergence in a multidimensional complex space[J]. IEEE Transactions on Evolutionary Computer, 2002, 6(1): 58-73. DOI:10.1109/4235.985692 |
[4] | SHI P, HUA J N. Mobile Robot dynamic path planning based on artificial potential field approach[J]. Advanced Materials Research, 2012, 490-495: 994-998. DOI:10.4028/www.scientific.net/AMR.490-495 |
[5] | SUD A, ANDERSEN E, CURTIS S, et al. Real-time path planning in dynamic virtual environments using multiagent navigation graphs[J]. IEEE Transactions on Visualization and Computer Graphics, 2008, 4(3): 526-538. |
[6] | TAVARES R S, MARTINS T C, TSUZUKI M S G. Simulated annealing with adaptive neighborhood:a case study in off-line robot path planning[J]. Expert Systems with Applications, 2011, 38(4): 2951-2965. DOI:10.1016/j.eswa.2010.08.084 |
[7] | GHATEE M, MOHADES A. Motion planning in order to optimize the length and clearance applying a Hopfield neural network[J]. Expert Systems with Applications, 2009, 36(3): 4688-4695. DOI:10.1016/j.eswa.2008.06.040 |
[8] | 杜宗宗, 刘国栋. 基于遗传模拟退火算法的移动机器人路径规划[J]. 计算机仿真, 2009, 26(12): 118-121. (DU Z Z, LIU G D. Path planning of mobile robot based on genetically simulated annealing algorithm[J]. Computer Simulation, 2009, 26(12): 118-121. DOI:10.3969/j.issn.1006-9348.2009.12.032) |
[9] | ZENG N, ZHANG H, CHEN Y, et al. Path planning for intelligent robot based on switching local evolutionary PSO algorithm[J]. Assembly Automation, 2016, 36(2): 120-126. DOI:10.1108/AA-10-2015-079 |
[10] | 秦元庆, 孙德宝, 李宁, 等. 基于粒子群算法的移动机器人路径规划[J]. 机器人, 2014, 26(3): 222-225. (QIN Y Q, SUN D B, LI N, et al. Path planning for mobile robot based on particle swarm optimization[J]. Robot, 2014, 26(3): 222-225.) |
[11] | SHENG J W, HE G H, GUO W B et al. An improved artificial potential field algorithm for virtual human path planning[C]//Proceedings of the 2010 International Conference on Entertainment for Education Digital Techniques & Systems, LNCS 6249. Berlin:Springer-Verlag, 2010:592-601 |
[12] | SETHANAN K, NEUNGMATCHA W. Multi-objective particle swarm optimization for mechanical harvester route planning of sugarcane field operations[J]. European Journal of Operational Research, 2016, 252(3): 969-984. DOI:10.1016/j.ejor.2016.01.043 |
[13] | TANG Z, ZHOU Y. A glowworm swarm optimization algorithm for uninhabited combat air vehicle path planning[J]. Journal of Intelligent Systems, 2014, 24(1): 69-83. |
[14] | TANG B, ZHU Z, LUO J. A convergence-guaranteed particle swarm optimization method for mobile robot global path planning[J]. Assembly Automation, 2017, 37(1): 114-129. DOI:10.1108/AA-03-2016-024 |