粒子群算法的移动机器人路径规划

第9卷第2期 南京师范大学学报(_丁程技术版) V01．9No．2 2009年6月J0uRNALoFNANJINcNoRMAl-uNIVF=RsI‘rY(|’NGINEERINGAND1tcHNoI．oGYEDmoN)Jun．2()09 基于二进制粒子群算法的移动机器人路径 王艳，朱庆保 (南京师范大学计算机科学与技术学院，江苏南京210097) [摘要】 由于用Pso进行机器人路径规划的研究尚局限于用连续模型规划连续描述的环境中的路径，使算法受到一定的局 限性．为此。研究了一种伞新的基于栅格法的机器人路径规划二进制粒子群算法．首先用栅格法描述机器人工作环境，在此基础 上，将机器人路径表示为粒子位置的二进制编码，并以路径长度为适应值，产生初始种群后，再对粒子佗置和速度进行更新，经 过多次迭代，即可获得从起始点到目标点的一条全局最优路径．该方法模型简单，算法复杂度低，收敛速度快，计算机仿真实验 证明『，该方法的有效性和先进性． [关键词] 移动机器人，路径规划，二进制编码粒子群算法，栅格法 [中图分类号]TP242[文献标识码】A [文章编号]1672一1292(2009)02删"2JD7 PathPla蛐jngforMobileRobotB嬲edonBi衄ryPa币cleSwa咖Optinlizati蚰 WangYan，ZhuQingba0 (sch00l0fComputerScienc髑，NanjingNorrnaluniVe玛时，Nanjing210097，China) Abstmct：Atpre8ent，thestudyofthembotpathpl粕ningwithParticleSw删Optimization(Ps0)isstillco曲nedto u眈thecontinuousmodeltopl明thepath“thcon“nu伽smethod，∞thealgo—t}Imh鹊cenainlimitations．Thenadis． cretebinaryve璐ionofthePs0forpathpIanningofmbotbased∞妒dmethodispmposed．rI'Ilefi飓tstepofthealgo． rithmistomaketheworkenvironmentofmbot诵th加dmethod，b鹊edonwhichrobotrouteisexpresseda8binarycode ofthepaniclelocation，andthelen昏h0fthepathistakenast}le6tnessvalue，arIdafIertheinitialpopulationisgenera- ted，the10cati∞卸dvelocityof叫iclesareupdated．111entIlediscretebinaryve惜ionofthePsOisintmducedtoob- taindeaoptimizedpathbetweenstaning-point卸dgoal-poinlthmughm卸yiteratjons．111isalgorithmissimpleinmodel， lowina190一thmcomplexity，锄dmpidinc∞vergence．Thesimulationresultsarepmvidedtoverifyeffectivene豁and pr卵ticabilityo“hemethod． Keywords：mobilerobot，pathplaIlning，binaryparticlesw删optimization，画dmethod 移动机器人路径规划是移动机器人研究的基本问题之一，它是指在有障碍物的T作环境中，寻找一条 从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物， 且所走路径较短．已有路径规划方法包括启发式图搜索法、人‘T势场法、神经网络法等，这些算法使问题的 求解速度和规模有了不同程度的提高，但均存在一定的局限性．近年来，不少学者采用神经网络、蚁群算 法⋯等进行机器人路径规划，用仿生算法进行机器人路径规划成为明显的发展趋势．为了进一步探索新 的机器人路径规划方法，近年也有学者尝试用粒子群算法(Panicleswa硼0ptimization，Ps0)进行路径规 划【2’3】，且能够在较短时间内获得全局最优或基本最优的一条路径，取得了显著的成果．然而该方法主要 采用的是传统的粒子群算法，而传统的粒子群算法是一种用于连续优化的数学模型，这就限制了机器人的 工作环境不能是离散模型而必须是连续模型，因而使该算法具有一定的局限性，即不适合基于离散环境模 型下的机器人路径规划． 为弥补这一不足，受二进制编码粒子群算法(BinaryPanicleSwarnlOptimization)H3的启发，并以此为 基础，本文提出一种机器人工作环境为离散模型时的全新机器人路径规划的粒子群箅法．该算法采用最简 便的栅格法对机器人工作环境进行建模，在此基础上，将机器人路径表示为粒子位置的二进制编码，并以 收稿日期：2008舭m． 基金项目：国家自然科学基金(60673102)和江苏省自然科学基金(BK2006218)资助项目． 通讯联系人：朱庆保，教授，博士生导师，研究方向：人工智能与智能控制．E．mail：zIluqingbao@njnu．edu．cn 一72— 万方数据 王 丝：篁!堇王三垄型塾王登笪盗塑堑塑塑矍△堕堡塑型 路径长度为适应值，产生初始种群后，根据粒子更新策略进行更新等运算，经过多次迭代后即可获得从起 始点到目标点的一条全局最优路径．最后对机器人不同的工作环境进行了仿真实验，并和相关算法进行了 比较，其效果令人满意． 1 问题描述和模型的建立 路径规划的第一步就是要建立适当的环境模型．已有的建模方法有链接图法、顶点图像法等，虽然在 路径规划中也能得到精确解，但模型的建立和更新计算量很大，实际应用困难．本文采用栅格法b】，该方 法具有简单、直观、计算量小等特点． 记As为机器人R。b在二维平面上的凸多边形有限运动区域，其 D几T习了T-丌了r丌丁一内部分布着有限个静态障碍物6，，6z，⋯，6。．考虑A5为任意形状，因卜十引而t寸西啪此，可在A5边界补以障碍栅格，将其补为正方形或长方形．在As中以E市习百订对百喇 As的左上角为坐标原点o，以横向为z轴，纵向为y轴建立系统直角坐医玎iE寸i医1i冈 标系，如图l所示．其中，粗线表示25号栅格的邻域．假设机器人在水 l29阿阿l32陌l34I35I 平方向上的行走步长为6，并且As在菇、y方向的最大值分别为髫一和 |i!Ii：li!li!I竺l!!l竺l ，，一．以艿为步长对环境进行划分形成一个栅格，则每行的栅格数M= l竺l竺I竺I竺I!：I竺l竺I 茗。俗，每列的栅格数M=)，一绝其中6i(i=l，2，⋯，，1)占一个或多◆，， 个栅格，当不满一个栅格时算一个栅格． 图l栅格坐标与序号关系 图l中的每一个数字代表环境中一个位置．机器人运动轨迹由若 ng·l黜hH佃0f鲥d咖rdi眦恼and 干栅格序号组成．记g∈A5为任意栅格，A为AS中g的集合，记5= 恤辩删n哪咐 {6。，6：，⋯，6。}∈A为静态障碍集．Vg∈A在坐标系中都有确定的坐 标(茗，，，)，记做g(菇，，，)，算为g所在的行号，y为g所在的列号．令C={l，2，3，⋯，肘}为栅格序号集，g(1， 1)的序号为l，g(1，2)序号为2，g(2，1)序号为札+l⋯．＆∈A的坐标(算i，yi)与序号i∈c构成互为映 射关系，序号i的坐标可由式(1)确定： 茗f=((i—1)mod^1)+l，yi=(int)((i—1)／札)+1，(1) 式中，int为舍余取整运算，mod为求余运算． 对于任意二维凸多边地形，规划的目的是使机器人由任意起点Gkd。，安全地沿一条较短路径到达任 意终点G。Tld，且Gbe面。、G。l'd圣．s，其它约束条件为：begin，end∈C，begin≠end． 根据栅格环境模型，移动机器人在二维有限空间中可以朝着8个 方向中的任意一个前进，如图2所示．为方便且不失一般性，假定：在 机器人运动过程中，障碍物的几何形状、大小均不发生变化． 2 二进制编码的粒子群算法 二进制编码粒子群算法是Eberhart【41等提出的PSO的离散二进 制版，它通过优化可连续变化的二进制概率(即二进制变量为l的概 率)达到间接优化二进制变量的目的．本文提出的基于栅格法的机器 人路径规划算法就是以二进制编码的粒子群算法为基础的． 粒子群算法如式(2)和式(3)所示．在标准粒子群算法中， 给定一包含肘个粒子的种群，则第i个微粒的位置置=(x订，如，⋯， Xm)，其中D表示粒子的维数．它经历过的最好位置记为只=(P¨ NW N‘fth NE 气 J k ≯ ＼ ／ ’EastWest‘ ／ ‘＼． 0。 、 ， ‘～ SW SdJtll SE 圈2机器人运动方向示意图 №．2 Dired岫0fmembot咖6∞ P丑，⋯，P诏)，也称为Pk。，即历史最优解．种群中的所有微粒所经历过的最好位置记为t=(t，，P92，⋯， ％)，也称为6胁，即全局最优解．此外，微粒i的速度用向量K=(％，％，⋯，‰)表示．对每一次迭代， 其第J维(1≤，≤D)的位置和速度根据式(2)和式(3)进行更新： K(t+1)=∞％(t)+c—rand()(巳(￡)一蜀(f))+c：rand()(巳(￡)一墨(f))，(2) 如(t+1)=曩(￡)+K如)． (3) 式中，∞为惯性权重，c。和c：是加速常数，豫nd()为在[0，1]范围内变化的随机函数． 一73— 万方数据 南京师范大学学报(T程技术版) 第9卷第2期(2009年) 此外，微粒的速度％被一个最大速度‰所限制．如果当前对微粒的加速导致它在d维的速度％超 过该维的最大速度吃，则该维的速度被限制为吃． 在二进制编码的粒子群算法模型中，将每一维xif和巳限制为l或者o，而速度Kf不作这种限制．用速 度来更新位置时，如果％高一些，粒子的位置矗更有可能选l，K低一点则选o，阈值在[o，1]之间，而有 这种特点的函数就是Sigmoid函数： Sig(戈)=(1+exp(一髫))一1． (4) 这样，粒子的位置迭代公式可以变为： 功+1)：fo，若p≥sig(％(‘+1))。 (5)” 。 【1，若p10，则Sig函数将趋于0．因此，根据文献[4]本文取为6．0，此时sig函数的范围为0．0025 —0．9975，这表明随着圪增加，Sig函数将逐渐减少，但最低将达到0．0025，从而保证算法仍然能够有能 力发生变化，避免陷入局部最小值． 3．6 粒子位置和速度更新策略 粒子速度更新仍然采用标准Ps0算法中的速度更新公式，即式(2)． 粒子位置更新问题是机器人路径规划二进制PSO算法的最重要的部分．本文中的粒子位置的更新以 式(5)为基础．以下为本文采用的粒子位置更新策略： 由二进制PsO算法本身的特点，本文中对粒子的位置更新实际上是对粒子位置向量中的某一分量的 更新，假设第i个粒子的位置置=(Xn，如，⋯，x田)，则更新后的位置X’i=(x’订，X’也，⋯，X’∞)．从置到 一75— 万方数据 南京师范大学学报(工程技术版) 第9卷第2期(2009年) x’；的区别就在于其中某分量由原来的0变为l，或者由原来的1变为0．这样的改变有可能使x’j=(x’¨ x’矗，⋯，X’曲)对应的路径不能安全避障．因此，在改变粒子的位置置=(置，，x舯⋯，xm)中的某一维分量 的值时，均要进行避障检查和越界检查，检查改变后的位置向量x’i=(x7订，x’＆，⋯，x’。D)对应的路径是 否与障碍物相碰或是否超过视野域范围．若安全避障且未超过视野域范围，则允许将x。更新到x’。，否则 不允许更新． 设粒子更新后的位置向量x’i=(x7n，x’边，⋯，x’曲)，该向量只记录了某一视野域中所走过的可行栅 格，但是其中并未反映经过这些栅格的先后顺序．如由图3所示，其中位置向量x= 1000001100001000011000011．则可能的路径为l-+7—8-÷13—18一19_÷24_÷25或者l'+7—8— 13_÷19—18—24_25．在实际算法中，当位置向量可以代表多条路径时，只能选择其中之一． 这样，粒子位置更新的关键在于如何对更新后的位置向量x’i=(x7n，x’正，⋯，x’西)进行避障检查和 越界检查．本文采用的检查策略为将鼍=(置。，如，⋯，x田)中为1的栅格序号提取出来构成集合cGS= {uI比∈c，邑。=l}，进行全排列P：篡(由前面的视野域定义可得其排列的计算代价较小)，对P：篙：中的 每一个排列u。，u：，⋯，Ml蚴进行边界和避障检查：由定义7得“i％+，(1≤i≤IcGsI一1)表示栅格序号为 氓、‰+．的栅格中心的连线，则避障必须满足uiuⅢ不会穿过任何障碍栅格，不会出现图4所示的情况，且不 会超过当前视野域的任何一边．若至少存在一个排列符合要求，则允许更新，否则不可以更新． 3．7 算法步骤 假设种群规模为Ⅳ个粒子，维数为D．根据以上二进制编码 的粒子群算法原理以及与机器人路径规划问题的结合方法，机 器人路径规划的二进制编码的粒子群算法步骤描述如下： Step1 建立基于栅格的机器人工作环境，设置初始起始 点％。(戈嘶。，，，begi。)和目标点G。。。(算饥d，，，。I-d)，初始起始点Gbegi。 为机器人的当前位置．设置最大迭代次数如er一，变量i御保存 当前迭代次数，初始化粒子群算法中各个参数值∞、c。、c：、k、 ∞一、n，耐。，定义一个路径表Path，将结果用此路径向量表示； Step2 根据机器人当前位置和视野域信息采用3．3的方 法初始化种群中各粒子位置向量置和速度向量K(1≤i≤ Ⅳ)，若初始化失败则退出程序； Step3 由式(10)计算每一个粒子的适应值E(即目标函 数值)； Step4 由式(12)更新每一个粒千i(1≤i≤Ⅳ)的J力史最优解PⅫ； P‰ct+-，={0“二‘?]『繁翟：0Z乞≯麓：：0．c·2， Step5 由式(13)更新种群的全局最优解Gb。，其中i=1，2，⋯Ⅳ； G‰㈦吣{乏≥。u∽∽眈虢笳篇篡二∞㈣， step6 由式(2)更新每一个粒子的速度，若更新后的速度％(￡+1)大于+k或者小于一k，则 需要调整％(￡+1)，保证更新后速度不小于一k，且不大于+‰，调整方法如式(14)： 呻川={：鬈糍慧芝j ㈣， Step7 由式(5)采用3．6的方法更新每一个粒子的位置当前迭代次数iler加1，并由式(11)更新∞ 的值； Step8 若i￡er