《密集障碍物环境下移动机器人全局路径规划.docx》由会员分享，可在线阅读，更多相关《密集障碍物环境下移动机器人全局路径规划.docx（8页珍藏版）》请在三一文库上搜索。
1、密集障碍物环境下移动机器人全局路径规划路径规划/双层粒子群/启发式搜索/脱障算子1引言路径规划是机器人导航技术的重要部分，研究的内容是在已知或未知的环境中，寻找一条从起点到终点的满 足一定优化指标的无碰撞路径。据机器人对环境的掌握状况，已有的路径规划方法可分为基于模型的全局路径规划和基于信息检测的局部路径规划。全局路径规划的基本问题是环境建模和路径寻优，重点在于开发高性能的搜索算法，使得规划的路径全局最优。目前，用于全局路径规划的方法主要有基于图论、栅格等的传统方法1和基于进化算法的智能方法2。这些方法各具优点，但又都有不足之处3。粒子群优化是Kennedy等借鉴鸟群的集体捕食行为，提出的一种
2、随机群进化方法4。相对传统的优化方法， 该方法易于实现、可调参数少，以及收敛速度快，已成功应用于函数优化、模式识别、神经网络训练、数据挖掘，以及路径规划等领域。但是，利用粒子群优化进行机器人路径规划，存在局部收敛、效率低下，以及精度不高等缺点，尤其是含有非规则密集障碍物的复杂环境，优化的路径多与障碍物碰撞。针对粒子群优化用于密集障碍物环境机器人全局路径规划存在的问题，本文提出一种双层微粒群优化方法(Two-layer particle swarm optimization, LPSO)。首先，采用坐标变换法构建环境模型，将路径规划问题表达为一个约束优化函数问题。接着，通过在评价函数中引入罚函数
3、，将约束优化转变为无约束优化。随后，定义脱障算子，给出双层粒子群优化算法的思想及步骤。最后，仿真验证本文所提算法的有效性。2问题描述与建模为了规划机器人路径，首先需要建立问题的数学模型。如图 1所示，在机器人工作空间建立两维绝对坐标系:O _ XY, ，其中，S为机器人的起点，G为终点，多边形物体表示障碍物。当起点与终点的连线与X轴不重合时,建立如下相对坐标系 S-xy:以S和G间的连线为轴，过S点且垂直SG的直线为y轴5。两坐标系间的变 换公式为：式中，(X,Y)和(x,y)分别为点在坐标系 O-XY和S-xy的坐标，笈为坐标轴X与x的夹角，、为S在坐 标系O-XY的坐标。对线段SG进彳f
4、D+1等分，并过每个等分点作SG的垂线，可以得到平行直线族 ”卜一5:该直线族与路径的交点，即为规划的目标点序列机器人路径规划，就是在相对坐标系S-xy中，寻找一个目标点序列路径，使得构成的5，里p尔心)满足期望的性能指标。这里，对点封笈的约束是：F后不在障碍物上或内部，且P展与相邻点的连线也不与障 碍物相交。对于路径P =/”定义5为出，相对坐标为LT；. ； ： I G为无7 ,相对坐标为UFm.JA。，那么，p的长度，记为“，可以表示为:式中，入g为S和G间的距离电国1 环境里型机器人路径规划问题，可以建模为一个约束优化问题，通过惩罚不可行路径，得到如下无约束优化问题：min Fp ：
5、= L(p) Cl -V()式中，贫为F与障碍物碰撞的次数。由式 可知,p与障碍物碰撞的次数越多，受到的惩罚程度越大，该 路径的性能越差。3基于双层粒子群优化算法的机器人全局路径规划3.1启发式搜索一一脱障算子采用微粒群优化进行机器人路径规划时，如果能够根据机器人的起点和终点位置，以及障碍物的位置，引导微 粒的搜索，那么，将会提高优化解成为可行路径的概率。基于此 ，当某路径不可行时，说明该路径的某段与障碍 物相交，对该路径实施脱障操作，也即对微粒的相应分量定向定步长变异，以避免机器人与障碍物碰撞。假设路段赢二代联Q-4与障碍物色;相 交，那么,采用下式对乩.及的纵坐标定向定步 长变异：y -i
6、 之o或占斗廿 h - ，上 Hu. 4 anLiX J11”13其它式中，i -1, J.和分别为障碍物。勺各顶点纵坐标的最大和最小值；;为变异步长，过大，扰动 后的路段一匚 将与其它障碍物相交，相反，方匚将 依然与内端交.在问题建模时，路径段的个数D与环 境中的障碍物个数相关，本文取（=衣（3-lic当障碍 物较多时，D较大，F较小;反之，I较大口由式可知，当y0或比整个障碍物或其大部分位于A轴的上方；相反，当 ”宝 或Jtmx i brcir. |时,整个障碍物或 其大部分位于工轴的下方。通过变异使路径点内和 外一向.V轴平移i ,可以远离障碍物。斗,进而使路径成 为可行的。由式（5）可
7、知，这样可以提高微粒的适应值.图2给出了脱障操作的过程，图中，1线为原来的路径，由于与障碍物相交，因此，是不可行的。口线为脱障操 作后得到的路径，不再与障碍物相交，从而成为可行路径。图2 汽直操华过程需要注意的是，对微粒实施月障操作后，如果微粒的某维，如超出了取值范围，那么，采用下式进一步调整3.2 双层粒子群优化算法在复杂、密集障碍物的环境中，采用粒子群优化算法进行机器人全局路径规划时所得结果大多为非可行路径，既使为可行路径，也多为局部最优的。而调整粒子群优化算法的参数，已不能有效解决算法后期早熟收敛的问题。为此，本文基于算法结构，提出一种双层粒子群优化算法。该算法包括两层，底层粒子群优化算
8、法主要在决策变量的取值空间中执行全局搜索，并采用脱障算子动态调整其全局极值点，以快速定位最优路径的大致位置。循环运行若干次底层算法、快速获取若干条无碰路径后，将其上传到顶层，作为顶层种群的部分粒子，进而为顶层算法确定重点搜索区域。为提高底层算法的全局搜索能力，本文采用基于线性递减惯性权值的更新公式更新粒子的速度和位置，具体更新公式如下：v = 口(门一G(p&5匚 Cr = -.v.(ril ，/A。，/7出(第物(t)-x. (0), ,，(s)= x. (r) - V. (t + 1)式中,用1二八为粒子群规模；=L J, 号为决策变量维数；反、g”叮分别为粒子的个体极值 点*全局极值点j
9、 q * Cj是学习因子，取q =匕：2 3、r; 是(0, 1)之间的随机数；二：是惯性权,用来控制先前速度 对当前速度的影响,从而协调粒子的全局搜索和局部搜 索能力，本文取山“)=白- 一(5tl- - cj-l，)i I(9)其中三7分别为最大、最小权重取=0.9、%广0.4是当前迭代次数,T是既迭代次数。顶层粒子群优化算法接收底层搜索的若干条较优路径后进行局部搜索，并采用脱障算子动态扰动调整其全局极值点。为克服早熟收敛，顶层算法在初期仍需具有好的全局搜索能力。为此，在迭代过程中，顶层算法的 惯性权重订和个体学习因子 S采用线性递减方式，社会学习因子 一值采用线性递增。具体公式如下do)
10、二工工-(公二(。=%说 + (%就 一%&* T其中3 %；、匚上分别为最大和最小值，取匚h =2. 5、3.3 算法步骤基于双层粒子群优化算法的机器人全局路径规划方法可描述如下：Stepl:由第2节所提方法，建立问题的环境地图，给出问题的无约束最小优化模型。Step2:给定种群规模产于二。变量维数D,令底层算法运行次数计数器；=：Step3:随机初始化底层种群。计算每个粒子的评价值并令该值为其个体极值点。.，求出种群的全局极值、全局极值点一点五令底层算法迭代计数器厅二：。Step4:据式(8)和(9)更新底层种群，进而更新其个体极值点C?, K*Step5:检测全局极值点一是否为碰撞路径布
11、是,执行脱障操作，否则存储该全局极值点并进至Step7oSteps： ； = j如果:(二匚葭，返回step4, Step7: i = f +1如果！ 二返回stepS;Q.（门Step8:随机初始化顶层种群，令 *二.为种群的部分初始粒子。计算每个粒子评价值并令该值为其个体极值点为七进而求出全局极值点0总富一。令顶层算法迭代计数器 k=1Step9:根据式（8）和（10）更新顶层种群，进而更新其个体极值点 外;广、全局极值点 “旧”；Step10检测全局极值点.r是否为碰撞路径 .是，执行脱障操作。Stepll: y 7如果入心，返回step9。否则，输出算法搜索结果。4仿真实验及结果分析为
12、验证所提算法的有效性，将本文算法应用到障碍物密集分布的环境中，并与仅含脱障算子的改进粒子群优化算法（OPSO）、标准粒子群优化算法（SPSO）以及遗传算法（GA）比较。算法所需参数设置：底层和顶层算法皆取粒子群规模N=20，维数D=10,最大迭代次数Y=1000OPSO、SPSO的参数设置均同本文底层粒子群优化算法，但在OPSO中利用了本文的脱障算子。GA的种群规模N=40，维数D=10,最大迭代次数T=300，采用比例选择复制，单点交叉概率,变异概率以=0,09- ： Xx06 %,（大适应度，小概率变异）。实验的运行环境为PC机,Intel Celeron M-1.6GHz CPU,504
13、MB RAM,以及 MATLAB7.4 。图3四种算法所得最好结果图4四种算法所得最差结果障碍物密集分布的环境如图 3-4所示，在的正方形环境中有12个静态障碍物，其顶点坐标已知，机器人始点终 点坐标已知。运行上述四种算法各 30次，图3-4和表1分别出示了四种算法所得的最好优化结果、最差优 化结果及统计数据。表1 四种算法分别运行30次所得优化结果的数据比较算法均值方差运行时间可行解比例LPS047. 6S10, 1753515.851000PS051, 8614. 25169. 6541100即雨93. 27426. 9059. 123530CA77. 625. 37353. 66867由
14、表1可知,在障碍物密集分布的环境，SPSO运行30次存在21条碰撞路径，可见SPSO若不改进已不能应用于障碍物密集分布环境的路径规划。而OPSO 以 100%的比例找到问题的可行路径,且平均运行时间与SPSO相近，可见脱障算子显著提高了OPSO的可行性。然而，OPSO的所得路径均值、方差均明显差于LPSO算法，体现了 OPSO仍存在不足，即在SPSO中仅引入脱障算子仍不能完全克服局部早熟。LPSO运行30次均能得到接近理论全局最优解的无碰撞最优路径,且方差很小,这表明LPSO 具有较好的鲁棒性。虽然LPSO运行时间均值长于 SPSO,但是相对优异的行走路径，稍长的时间花费是可以接受的。GA运行的结果与 SPSO 相似。由此可见,相对其余三种算法,LPSO 具有较强的全局寻优能力和较快的收敛速度。5 结束语本文针对标准粒子群优化算法早熟收敛、效率低的缺点,给出了一种用于障碍物密集分布环境下机器人全局路径规划的双层粒子群优化算法。通过定义基于障碍物顶点信息的脱障算子,启发、引导全局极值点向理论全局最优解趋近,有效改善了标准粒子群优化算法的全局寻优能力。采用双层的算法结构,有效解决了早熟收敛问题。仿真结果表明本文所提算法的可行性和有效性。曾现峰