基于栅格法的机器人路径规划调节
罗竹青 江苏食品职业技术学院计算机应用技术系，江苏 淮安 223003
摘要：针对栅格法建模的不足，本文研究了一种基于栅格的机器人路径规划调节方法。该方法首先用栅格法建立机器人运动空间模型,在此基础上利用局部规划方法进行搜索得到全局导航路径，然后用微粒群算法局部垂直和水平调节导航路径上的路径点，得到更优路径。计算机仿真实验表明，利用本方法可以规划出一条全局优化路径，且能安全避障。
关键词：机器人；路径规划；导航路径；粒子群算法
中图分类号：TP2 文献标识码：A 文章编号：1003-9767(2009)11-0029-02
Robot path planning regulation based on Grid method
Luo Zhuqing, Grid-based method for robot path planning regulation, Jiangsu, Huaian 223003
Abstract:For the lack of modeling the grid method, this paper studied a Grid-based robot path planning adjustment. The method was established by fi rst using the grid space robot model, based on the use of local programming method to search to be global navigation path, and then PSO local vertical and horizontal adjustment path points on the navigation path, get a better path. Computer simulation results show that using this method can work out a global optimization path, and can safely evade the barrier.
Keywords: Robot; path planning; navigation path; particle swarm optimization
1. 引言
移动机器人路径规划是指在有障碍物的工作环境中，寻找一条从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径较短。这方面的研究已有广泛的报道，例如用遗传算法[1]、蚂蚁算法[2]等方法对机器人路径进行规划，这些算法使问题的求解速度和规模有不同程度的提高。栅格法[3、4]建模是常用的建模方法之一，但它存在一个缺陷：在无障碍物区，机器人还是按照栅格走折线路径，而折线是次优路径，增加了机器人到达目的地的时间。文献[3、4]采用了垂直方向调节，但当得到的导航路径较差时，并不能得到最优解。
基于对已有成果的研究并针对已有算法的不足，本文提出了一种全新的机器人路径规划方法，首先用栅格法建立机器人运动的环境模型，在此基础上先用已有局部规划方法规划一条无碰较优导航路径；再用粒子群算法通过垂直和水平调节优化该路径，从而得到全局近似最优的路径。
最大值分别为Xmax和Ymax。以δ为步长形成一个栅格。则每行的栅格数Nx=Xmax/δ,每列的栅格数Ny=Ymax/δ。其中bi（i=1,2…,n）占一个或多个栅格，当不满一个栅格时算一个栅格。
3. 机器人路径规划调节
栅格法建模有一定的缺点如：划分的粒度难控制，栅格粒度越小，障碍物的表示会越精确，但同时会占用大量的存储空间；栅格的粒度太大，规划的路径会很不精确。如图2所示的路径由于采用栅格法建模得到的路径并非最优路径，为了解决此不足，本文算法首先用局部路径规划方法找到一条无碰较优导航路径，得到初始的路径点；再用粒子群算法调整每一个初始路径与栅格边界的交点，每一个粒子的每一维代表一个交点，每个粒子从低维到高维的逐一连线就构成了新的路径，通过若干次迭代从而得到全局近似最优路径。垂直调节过程如图2所示。让导航路径上的每一个与栅格边界相交的xd点在xdmin、xdmax两点间的线段上滑动，用粒子群算法来搜索最佳xd，使得寻找的路径最短。xd只在无障碍的竖直方向滑动，保证了xd在线段xdmin、xdmax上滑动时形成的新路径上点与点之间是相通的从后最终优化出的路径不会与障碍物相交。对每个路径点都这样调节后, 这些新的路径点就组成了一条新的机器人移动路径。垂直调节后，再对调节后的路径再进行水平调节，水平调节如图3所示。水平调节和垂直调节过程基本相似。
Step1: 利用局部路径规划方法计算出导航路径。
Step2: 计算出导航路径与垂直方向栅格边界的交点的个数Pnum，
即每个粒子有Pnum维，并计算出粒子第d维的滑动范围[xdmin、xdmax]。
Step3: 初始化粒子数Pn，在允许的范围内随机初始化粒子c的位置 和速度 ，把粒子c的初始化位置视为其初始最优位置pc ，设定并令n=0。
Step4:依据定义8和式（11）计算每个粒子c的适应
、
、，
、和最大迭代次数
2. 环境描述
首先假设环境中的障碍物都是膨胀过的即机器人可以沿着障碍物边界行走。
记AS为机器人Rob在二维平面上的凸多边形有限运动区域,其内部分布着有限个静态障碍物b1 ,b2 ,……, bn。在AS中以AS的左上角为坐标原点0，以横向为X 轴，纵向为Y 轴建立系统直角坐标系，如图1。假设机器人在水平方向上的行走步长为δ,并且AS在X、Y方向的
图1 栅格坐标与序号关系图2 垂直调节示意图图3 水平调节示意图
(下转第31页)
很多软件基于开源软件来做，所以它开发迅速。在开源的应用方面，可以在原软件的基础上集成创新。要善于利用开源软件，要站在巨人的肩膀上创新[6]。从以上这段话和开源软件应用成功的案例中可以得出结论，第一，正确的开源软件的应用是软件开发的新模式；第二，只有基础扎实、动手能力强的开发人员才能利用好开源软件。
基于以上的两点结论，开源软件引入课程教学改革的具体实施中，本科的教学中可以在操作系统课程的讲授中，结合Linux源代码进行讲解和分析；可以开设Linux课程的教学或讲座；介绍和推广部队信息化建设中急需的功能的软件。由于武警部队正处在信息化建设的起步阶段，课题项目还不是特别丰富，有时学员得不到充分的锻炼和提高。这种情况下，可以鼓励学员特别是研究生学员积极参与开源社区中项目的开发、测试、文档撰写工作，利用好社会资源培养部队的人才。相信经过开源社区的开发模式的培养，学员的编程能力、文档编辑撰写能力和项目协作管理能力都会得到相应的提高。
取、项目调研、学术交流、科研项目分配上给予适当的支持。四是在引入过程中注意保密，防止出现泄密事件。
五、总结与展望
开源软件的引入、应用和开发，对于武警部队的信息化建设来说，不失为一种节约科研经费、缩短软件开发周期、提高自研项目质量的方式，可以有效提高信息化建设的速度和质量，并与我国鼓励支持开源软件项目的信息产业政策相符合。在院校的教学中，引入开源软件也可以帮助学员提高计算机的知识积累、专业基础和开发能力。由于开源软件对于院校教学还是一个新课题，它的推广和应用需要在信息化建设的实际中不断的总结研究。
参考文献：
[1]宋鲁毅，霍国庆.军队信息化的动因、任务及对策探讨[J]. 中国软科学,2002(4):27-22
[2]陈伟. 开源软件新的挑战[J]. 软件世界,2006.8:61-62
[3]郭强,李京鹏. Linux在军事领域应用前景分析[C]. 中国通信学会国防通信技术委员会学术研讨会论文集,2005:409-413
[4]陈昔.嵌入式—PC 时代的软件金矿[N].中国教育报, 2006-4-10,(6)[5]刘东升.大力加强信息化人才队伍建设[N]. 人民武警,2006-6-7,(3)[6]倪光南. 培养开源人才是中国软件发展的根本[EB/OL].
四、引入开源软件需要注意的问题
目前开源软件种类繁多，数量较多，而且水平良莠不齐。为了能更好的利用开源软件，在引进过程中，应当注意如下问题：一是转变教员的思想观念，扩大对开源软件的了解和认识，加大对开源软件的关注力度和研究投入。二是在引入时，应当广泛阅读参考文献，选择适当的项目，把握好开源软件的质量。三是主管部门应该在信息获
(上接第29页)
4. 实验结果
为了体现该算法的有效性及其特点，作者对本文调节方法分别在10维进行了大量测试，效果都十分令人满意，其中局部路径规划方法采用遗传算法。
其中红色线是遗传算法获得的导航路径。黑色线给出了经过调节后用微粒群思想优化导航路径后得到的更优路
图3 导航路径最优情形
图4 (a)仅通过垂直调节 图4 (b)再通过水平调节后路径
径。图3中红色细线长为15.656，黑色粗线为13.3315，很显然经过微粒群优化后
度Fc，适应度最小的粒子位置记为Pg。
Step5:依据式（12）更新粒子c的各维速度，依据式（13）更新粒子c的位置。其中若
；若,则令
是[0,1]之间的随机数，若则令。
；若
则令
则令；
的路径比蚂蚁算法获得的路径要优化的多。图4中所示的蚂蚁算法得到的导航路径并不是最优的，文献[3、4]得到的最终路径仅仅是经过垂直调节得到的路径，如图4(a)所示，但经过本文的微粒群垂直和水平调节优化后得到的路径（如图4(b)所示）和图3情形的基本相当。
5. 结语
本文采用栅格法对机器人运动环境进行建模，使算法简单容易实现。在此基础上，用局部路径算法快速搜索出一条全局导航路径，然后对该路径上的点用微粒群思想进行垂直和水平调节，得到近似最优路径。仿真实验表明本文的调节方法可以有效地解决栅格法建模的缺陷，快速搜索出一条近似最优化路径。
参考文献：
Step6：依据（11）式计算每个粒子的适应度Fc(x(t+1))，更新pc、。pg。n自动增1，
Step7：若n
Step8：若已进行了水平调节则输出最优路径，结束。否则继续。
Step9: 计算出垂直调节后的路径与水平方向栅格边界的交点的个数Pnum，即每个粒子有Pnum维，并计算出粒子第d维的滑动范围[xdmin，xdmax]。转step3。
[1] Yanrong Hu and Simon X. Yang. A Knowledge Based Genetic A1gorithm for Path Planning of a Mobile Robot[C]. Proceedingsof the 2004 IEEE international Conferenceon Robotics&Automation NewOrleans，2004：4350－4355
[2] Mohd M.Mohamad，Matthew W.Dunnigan， Nicholas K.Taylor.Ant Colony Robot Motion Planning[C]. EUROCON 2005 IEEE：213－216
[3]国海涛,朱庆保,司应涛.一种蚂蚁遗传融合的机器人路径规划新算法.小型微型计算机系统.2008，29(10),1838-1841.
[4]梁明，徐守江。微粒群与蚂蚁融合的机器人路径规划新算法.计算机工程与应用.2009，45（6），43-45.
基于栅格法的机器人路径规划调节
罗竹青 江苏食品职业技术学院计算机应用技术系，江苏 淮安 223003
摘要：针对栅格法建模的不足，本文研究了一种基于栅格的机器人路径规划调节方法。该方法首先用栅格法建立机器人运动空间模型,在此基础上利用局部规划方法进行搜索得到全局导航路径，然后用微粒群算法局部垂直和水平调节导航路径上的路径点，得到更优路径。计算机仿真实验表明，利用本方法可以规划出一条全局优化路径，且能安全避障。
关键词：机器人；路径规划；导航路径；粒子群算法
中图分类号：TP2 文献标识码：A 文章编号：1003-9767(2009)11-0029-02
Robot path planning regulation based on Grid method
Luo Zhuqing, Grid-based method for robot path planning regulation, Jiangsu, Huaian 223003
Abstract:For the lack of modeling the grid method, this paper studied a Grid-based robot path planning adjustment. The method was established by fi rst using the grid space robot model, based on the use of local programming method to search to be global navigation path, and then PSO local vertical and horizontal adjustment path points on the navigation path, get a better path. Computer simulation results show that using this method can work out a global optimization path, and can safely evade the barrier.
Keywords: Robot; path planning; navigation path; particle swarm optimization
1. 引言
移动机器人路径规划是指在有障碍物的工作环境中，寻找一条从给定起始点到终止点的较优的运动路径，使机器人在运动过程中能安全、无碰撞地绕过所有的障碍物，且所走路径较短。这方面的研究已有广泛的报道，例如用遗传算法[1]、蚂蚁算法[2]等方法对机器人路径进行规划，这些算法使问题的求解速度和规模有不同程度的提高。栅格法[3、4]建模是常用的建模方法之一，但它存在一个缺陷：在无障碍物区，机器人还是按照栅格走折线路径，而折线是次优路径，增加了机器人到达目的地的时间。文献[3、4]采用了垂直方向调节，但当得到的导航路径较差时，并不能得到最优解。
基于对已有成果的研究并针对已有算法的不足，本文提出了一种全新的机器人路径规划方法，首先用栅格法建立机器人运动的环境模型，在此基础上先用已有局部规划方法规划一条无碰较优导航路径；再用粒子群算法通过垂直和水平调节优化该路径，从而得到全局近似最优的路径。
最大值分别为Xmax和Ymax。以δ为步长形成一个栅格。则每行的栅格数Nx=Xmax/δ,每列的栅格数Ny=Ymax/δ。其中bi（i=1,2…,n）占一个或多个栅格，当不满一个栅格时算一个栅格。
3. 机器人路径规划调节
栅格法建模有一定的缺点如：划分的粒度难控制，栅格粒度越小，障碍物的表示会越精确，但同时会占用大量的存储空间；栅格的粒度太大，规划的路径会很不精确。如图2所示的路径由于采用栅格法建模得到的路径并非最优路径，为了解决此不足，本文算法首先用局部路径规划方法找到一条无碰较优导航路径，得到初始的路径点；再用粒子群算法调整每一个初始路径与栅格边界的交点，每一个粒子的每一维代表一个交点，每个粒子从低维到高维的逐一连线就构成了新的路径，通过若干次迭代从而得到全局近似最优路径。垂直调节过程如图2所示。让导航路径上的每一个与栅格边界相交的xd点在xdmin、xdmax两点间的线段上滑动，用粒子群算法来搜索最佳xd，使得寻找的路径最短。xd只在无障碍的竖直方向滑动，保证了xd在线段xdmin、xdmax上滑动时形成的新路径上点与点之间是相通的从后最终优化出的路径不会与障碍物相交。对每个路径点都这样调节后, 这些新的路径点就组成了一条新的机器人移动路径。垂直调节后，再对调节后的路径再进行水平调节，水平调节如图3所示。水平调节和垂直调节过程基本相似。
Step1: 利用局部路径规划方法计算出导航路径。
Step2: 计算出导航路径与垂直方向栅格边界的交点的个数Pnum，
即每个粒子有Pnum维，并计算出粒子第d维的滑动范围[xdmin、xdmax]。
Step3: 初始化粒子数Pn，在允许的范围内随机初始化粒子c的位置 和速度 ，把粒子c的初始化位置视为其初始最优位置pc ，设定并令n=0。
Step4:依据定义8和式（11）计算每个粒子c的适应
、
、，
、和最大迭代次数
2. 环境描述
首先假设环境中的障碍物都是膨胀过的即机器人可以沿着障碍物边界行走。
记AS为机器人Rob在二维平面上的凸多边形有限运动区域,其内部分布着有限个静态障碍物b1 ,b2 ,……, bn。在AS中以AS的左上角为坐标原点0，以横向为X 轴，纵向为Y 轴建立系统直角坐标系，如图1。假设机器人在水平方向上的行走步长为δ,并且AS在X、Y方向的
图1 栅格坐标与序号关系图2 垂直调节示意图图3 水平调节示意图
(下转第31页)
很多软件基于开源软件来做，所以它开发迅速。在开源的应用方面，可以在原软件的基础上集成创新。要善于利用开源软件，要站在巨人的肩膀上创新[6]。从以上这段话和开源软件应用成功的案例中可以得出结论，第一，正确的开源软件的应用是软件开发的新模式；第二，只有基础扎实、动手能力强的开发人员才能利用好开源软件。
基于以上的两点结论，开源软件引入课程教学改革的具体实施中，本科的教学中可以在操作系统课程的讲授中，结合Linux源代码进行讲解和分析；可以开设Linux课程的教学或讲座；介绍和推广部队信息化建设中急需的功能的软件。由于武警部队正处在信息化建设的起步阶段，课题项目还不是特别丰富，有时学员得不到充分的锻炼和提高。这种情况下，可以鼓励学员特别是研究生学员积极参与开源社区中项目的开发、测试、文档撰写工作，利用好社会资源培养部队的人才。相信经过开源社区的开发模式的培养，学员的编程能力、文档编辑撰写能力和项目协作管理能力都会得到相应的提高。
取、项目调研、学术交流、科研项目分配上给予适当的支持。四是在引入过程中注意保密，防止出现泄密事件。
五、总结与展望
开源软件的引入、应用和开发，对于武警部队的信息化建设来说，不失为一种节约科研经费、缩短软件开发周期、提高自研项目质量的方式，可以有效提高信息化建设的速度和质量，并与我国鼓励支持开源软件项目的信息产业政策相符合。在院校的教学中，引入开源软件也可以帮助学员提高计算机的知识积累、专业基础和开发能力。由于开源软件对于院校教学还是一个新课题，它的推广和应用需要在信息化建设的实际中不断的总结研究。
参考文献：
[1]宋鲁毅，霍国庆.军队信息化的动因、任务及对策探讨[J]. 中国软科学,2002(4):27-22
[2]陈伟. 开源软件新的挑战[J]. 软件世界,2006.8:61-62
[3]郭强,李京鹏. Linux在军事领域应用前景分析[C]. 中国通信学会国防通信技术委员会学术研讨会论文集,2005:409-413
[4]陈昔.嵌入式—PC 时代的软件金矿[N].中国教育报, 2006-4-10,(6)[5]刘东升.大力加强信息化人才队伍建设[N]. 人民武警,2006-6-7,(3)[6]倪光南. 培养开源人才是中国软件发展的根本[EB/OL].
四、引入开源软件需要注意的问题
目前开源软件种类繁多，数量较多，而且水平良莠不齐。为了能更好的利用开源软件，在引进过程中，应当注意如下问题：一是转变教员的思想观念，扩大对开源软件的了解和认识，加大对开源软件的关注力度和研究投入。二是在引入时，应当广泛阅读参考文献，选择适当的项目，把握好开源软件的质量。三是主管部门应该在信息获
(上接第29页)
4. 实验结果
为了体现该算法的有效性及其特点，作者对本文调节方法分别在10维进行了大量测试，效果都十分令人满意，其中局部路径规划方法采用遗传算法。
其中红色线是遗传算法获得的导航路径。黑色线给出了经过调节后用微粒群思想优化导航路径后得到的更优路
图3 导航路径最优情形
图4 (a)仅通过垂直调节 图4 (b)再通过水平调节后路径
径。图3中红色细线长为15.656，黑色粗线为13.3315，很显然经过微粒群优化后
度Fc，适应度最小的粒子位置记为Pg。
Step5:依据式（12）更新粒子c的各维速度，依据式（13）更新粒子c的位置。其中若
；若,则令
是[0,1]之间的随机数，若则令。
；若
则令
则令；
的路径比蚂蚁算法获得的路径要优化的多。图4中所示的蚂蚁算法得到的导航路径并不是最优的，文献[3、4]得到的最终路径仅仅是经过垂直调节得到的路径，如图4(a)所示，但经过本文的微粒群垂直和水平调节优化后得到的路径（如图4(b)所示）和图3情形的基本相当。
5. 结语
本文采用栅格法对机器人运动环境进行建模，使算法简单容易实现。在此基础上，用局部路径算法快速搜索出一条全局导航路径，然后对该路径上的点用微粒群思想进行垂直和水平调节，得到近似最优路径。仿真实验表明本文的调节方法可以有效地解决栅格法建模的缺陷，快速搜索出一条近似最优化路径。
参考文献：
Step6：依据（11）式计算每个粒子的适应度Fc(x(t+1))，更新pc、。pg。n自动增1，
Step7：若n
Step8：若已进行了水平调节则输出最优路径，结束。否则继续。
Step9: 计算出垂直调节后的路径与水平方向栅格边界的交点的个数Pnum，即每个粒子有Pnum维，并计算出粒子第d维的滑动范围[xdmin，xdmax]。转step3。
[1] Yanrong Hu and Simon X. Yang. A Knowledge Based Genetic A1gorithm for Path Planning of a Mobile Robot[C]. Proceedingsof the 2004 IEEE international Conferenceon Robotics&Automation NewOrleans，2004：4350－4355
[2] Mohd M.Mohamad，Matthew W.Dunnigan， Nicholas K.Taylor.Ant Colony Robot Motion Planning[C]. EUROCON 2005 IEEE：213－216
[3]国海涛,朱庆保,司应涛.一种蚂蚁遗传融合的机器人路径规划新算法.小型微型计算机系统.2008，29(10),1838-1841.
[4]梁明，徐守江。微粒群与蚂蚁融合的机器人路径规划新算法.计算机工程与应用.2009，45（6），43-45.