移动机器人路径规划算法的研究

1、 文章编号：1674-8085（2010）02-0056-04移动机器人路径规划算法的研究*孙凌宇，冷 明，朱 平，周 宇1112(1. 井冈山大学信息科学与传媒学院, 江西，吉安 343009；2. 井冈山大学网络中心, 江西，吉安 343009摘 要：路径规划技术作为机器人研究领域中的一个重要分支，是依据某些优化准则，在其工作空间中找到一条从起始状态到目标状态的最优无碰路径。本文针对机器人路径规划技术进行了深入地研究，阐述了机器人路径规划问题的三个子问题等内容，讨论了传统路径规划方法和基于智能算法的路径规划方法。本文运用传统Dijkstra 算法的贪心策略，针对静态环境下移动机器人路径规划

2、的寻路径子问题，提出了一种改进的Dijkstra 路径规划算法。该算法借助具有“先进先出”特点的队列，采用广度优先遍历二维网络结点。该算法在选择邻接结点进行遍历的时候，采用的禁忌策略是禁止访问已经访问的结点，以及被标识为障碍物的结点。实验及分析表明，该算法能准确并快速地寻找到最优路径，且时间复杂度为O(4*n。 关键词：移动机器人；路径规划；贪心策略；中图分类号：TP391 文献标识码: A DOI:10.3969/J.issn.1674-8085.2010.02.012RESEARCH ON PATH PLANNING OF MOBILE ROBOT*SUN Ling-yu1, LENG M

3、ing1, ZHU Ping1, ZHOU Yu2(1. School of Information Science and Communication，Jinggangshan University，Jian，Jiangxi 343009，China ；2. Network Information Center，Jinggangshan University，Jian，Jiangxi 343009，ChinaAbstract ：Path planning, an important branch of the robotics research, generates a collision-

4、free path in workspace with respect to some criterion. We study on the path planning techniques of mobile robot, describe three sub-problems of path planning and discuss the traditional path planning algorithm and intelligent path planning algorithm. According to the greedy strategy of Dijkstra algo

5、rithm, we propose the Improved Dijkstra algorithm (ID algorithm in view of path planning in a static environment. The ID algorithm traverses the two-dimensional grid in breadth-first strategy by means of the FIFO queue. In the choice of adjacent grid node, the ID algorithm adopts the tabu search str

6、ategy whose tabu restriction is to forbid visiting tabu or traversed nodes. The experimental evaluations on four different grids and analysis show that the ID algorithm produces the shortest path very quickly and its time complexity is O(4*n.Key words：mobile robot；path planning；greedy strategy定义：路径规

7、划是自治式移动机器人的一个重要组0 引言成部分，它的任务就是在具有障碍物的环境内，按照一定的评价标准，寻找一条从起始状态(包括位置和姿态 到达目标状态(位置和姿态 的无碰路径。路径规划技术是机器人研究领域中的一个重要分支。蒋新松教授在文献1中为其做出了这样的收稿日期：2009-12-18；修改日期：2010-01-10基金项目：江西省自然科学基金项目(2009GQS0060）；江西省教育厅科学技术研究项目(GJJ10201, GJJ9590 作者简介：*孙凌宇(1976-），女，江西永丰人，副教授，硕士，主要从事算法分析与设计等研究(E-mail:sunlingyu；冷 明(1975-）， 男

8、， 江西高安人，副教授，博士，主要从事组合分析与优化算法，算法分析与设计等研究(E-mail:lengming）；朱 平(1955-），男，上海人，教授，硕士，主要从事智能计算、图形图像处理、插值逼近等研究(Email: zhuping； 周 宇(1974-），男，江西永新人，高级实验师，硕士，主要从事组合分析与优化算法等研究(E-mail: zy.井冈山大学学报(自然科学版57机器人路径规划问题在理论上主要存在三个子问题2： 环境表示问题：指环境中障碍物的表示和自由空间的表示。合理的环境表示才能有利于规划中搜索量的减少和时空开销的减少。 寻空确定物体A 的安全间问题：在某个指定区域R 中，位

9、置，使它不与己有的其它物体B j (j=1，2. ，m 相碰。寻路径问题：在某个指定区域R 中，确定使物体A 从初始位置移动到目标位置的安全路径，得移动过程中不发生A 与B j 的碰撞，即一系列安全位置就可以构成安全路径。路径规划问题具有如下特点3： 复杂性：在复杂环境下尤其是动态时变环境中，机器人路径规划非常复杂，且需要很大的计算量。 随机性：复杂环境的变化往往存在很多随机性和不确定因素。动态障碍物的出现也带有随机性。 多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器人的形状制约，而物理约束是指机器人的速度和能量等。 多目标：机器人运动过程中路径规划的性能要求存在多种目标，如路径

10、最短、时间最优、安全性能最好、能源消耗最小，但这些目标之间往往存在冲突。2.2 基于智能算法的路径规划方法 基于模糊逻辑的机器人路径规划。模糊逻辑方法是在线性规划中通常采用的一种规划方法，包括建模和局部规划。庄晓东等4提出了一种基于模糊概念的动态环境模型，参照物体的位置和运动信息构造二维隶属度函数，然后对各个方向进行模糊综合评价，得到搜索结果。李彩虹等 5提出了一种在未知环境下移动机器人的模糊控制算法。该算法鲁棒性强，使移动机器人的行为表现出很好的一致性、连续性和稳定性。Hartmut Surmann 等 6提出了一种未知环境下的高级机器人模糊导航方法。该方法在环境未知或发生变化的情况下表现较

11、好，但是当障碍物数目增加时，该方法的计算量会很大，影响规划结果。 基于神经网络方法的机器人路径规划。禹建丽等7提出了一种基于神经网络的机器人路径规划算法，研究了障碍物形状和位置已知情况下的机器人路径规划问题。陈宗海等8提出了一种在不确定环境中移动机器人的路径规划方法，将全局路径规划分解为局部路径规划的组合，满足了规划的实时性要求。禹建丽等9引进了线性再励的自适应变步长算法，实现了步长的自适应选择，使路径规划速度比原来的神经网络规划提高了10倍。 基于遗传算法的机器人路径规划。无论是单机器人静态工作空间，还是多机器人动态工作空间，遗传算法及其派生算法都取得了良好的路径规孙树栋等11采用遗传算法完

12、成了离散空划结果10。间下机器人的路径规划，并获得了较好的仿真结果，但要求工作空间中的障碍物位置是己知和确定的。周明11提出了一种连续空间下基于遗传算法的机器人路径规划方法。该方法先使用图论中算法粗略地搜索出可选路径，然后再使用遗传算法来调整路径点，逐步得到较优的行走路线。基于混合方法的机器人路径规划方法。1 移动机器人路径规划方法的分类1.1 传统路径规划方法 自由空间法。通常采用结构空间来描述机器人及其周围的环境，将机器人缩小成点，其周围障碍物及边界按比例相应地扩大，使机器人点能够在自由空间中移动到任意一点，而不与障碍物及边界发生碰撞。 图搜索法。该方法中的路径图是由捕捉到的存在于机器人一

13、维网络曲线（简称路径图）自由空间中的结点组成。路径的初始状态和目标状态同路径图中的点相对应，这样路径规划问题就演变为在这些点间搜索路径的问题。 栅格解耦法。该方法将机器人的工作空间解耦为多个简单的区域（简称栅格）。由这些栅格构成了一个连通图，在这个连通图上搜索一条从起始栅格到目标栅格的路径。人工势场法。传统的人工势场法把移动机器人在环境中的运动视为一种在抽象的人造受力场中的运动，目标点对移动机器人产生“引力”，障碍物对移动机器人产生“斥力”，最后通过求合力来控制移动机器人的运动。L.H.Tsoukalas 12提出了一种用于半自主移动机器人路径规划的模糊神经网络方法。这种方法采用模糊描述来完成

14、机器人的行为编码，同时使用神经网络自适应技术。此外，还有其他学者提出基于模糊神经网络、遗传算法、免疫算法的混合路径规划方法13-15。它们作为混合的机器人自适应控制方法，可以自适应调整机器人的行走路线，达到避障和路径最短的双重优化。58井冈山大学学报(自然科学版3 一种静态环境下移动机器人路径规划方法本文运用传统Dijkstra 算法的贪心策略，提出了一种静态环境下移动机器人路径规划方法，并从环境表示、寻空间和寻路径子问题对其进行阐述。 针对静态环境下移动机器人路径规划的环境表示子问题，本文采用传统的网格结点表示法表示移动机器人的工作平面。如图1(a所示，P 结点色结点表示工作平面的障碍物，且

15、被记录在列表O(x,y中。 (i,j处在结点(i-1,j、(i,j-1、(i+1,j、(i,j+1中间。通过将一系列的离散结点覆盖到工作平面区域，最终形成一个二维网络结点，如图1(b所示。假设径规划环境表示法Fig.1 Two-dimensional grid point representation of a planarworkspaceMaxRow 表示二维网络结点的行数，MaxCol 表示二维网络结点的列数，n 表示二维网络结点的结点总数，即MaxRow*MaxCol。在图1(b中所示的黑 针对静态环境下移动机器人路径规划的寻空间子问题，本文将移动机器人缩小成点，它的安全位置落在二维网

16、络结点的某个非障碍物结点上，即白色结点上。INPUT: 1. MaxRow ; 2. MaxCol ; 3.the list of obstacles O (x,y ; 4.a source node s ; 5.a target node g ; OUTPUT: 1.the shortest path p ;2 set tabu status in the matrix for grid nodes of O (x,y ; 3 initial empty queue and insert s into queue; 4 while (the queue is non-empty do 5 d

17、equeue v from queue;6 for (each uneighbors (v do 7 if (u s status=non-traversed status&&(u s status=non-tabu status then 8 if (u=g then 9 break; 10 else 11 insert u into queue;12 set traversed status in the matrix for u ; 13 record v as the source of u ; 14 end if 15 end if 16 end for 17 end

18、 while18 if (u=g then 19 trace the source information to obtain the shortest path p 20 end if图2 改进的Dijkstra 路径规划算法伪代码Fig.2 The pseudocode of the improved Dijkstra algorithm 传统Dijkstra 算法针对赋权有向图，求出从源点到其余各顶点之间的最优路径。该算法时间复杂度为O(n2 ，其中n 表示赋权有向图的顶点数。该算法在求解较大规模问题最优路径时效率较低。针对静态环境下移动机器人路径规划的寻路径子问题，本文基于传统Dijk

19、stra 算法的贪心策略，提出了一种改进的Dijkstra 路径规划(Improved问的结点，或者被标识为障碍物的结点。ID 算法伪其中函数neighbors(v表示依次访代码如图2所示，问二维网络结点中结点v 的四个邻接结点。4 算法分析及仿真实验4.1 时间复杂度和空间复杂度分析假设n 表示二维网络结点的结点总数。ID 算法时间复杂度主要包含两部分：步骤2对二维网络结点的障碍结点设置禁忌属性，时间复杂度为Dijkstra ，简称ID 算法。针对二维网络结点中每个结点之间的路径为单位权值，且每个结点最多只有四个邻接结点(即每个结点度数的最大值为4 ，ID 算法借助具有“先进先出”特点的队列

20、，采用广度优先遍历二维网络结点。该算法在选择邻接结点进行遍历的时候，采用的禁忌策略是禁止访问已经访O(n。步骤4步骤17的外循环，最坏的情况是除终点外的所有结点入队和出队，循环次数为n-1次；步骤6步骤16的内循环，最坏的情况需遍历结点v 的四个邻接结点，循环次数为4次；步骤4井冈山大学学报(自然科学版59步骤17的循环体时间复杂度为O(4*n。因此ID 算法的时间复杂度为O(4*n。本文运用传统Dijkstra 算法的贪心策略，针对静态环境下移动机器人路径规划的寻路径子问题，提出了一种改进的Dijkstra 路径规划算法。该算法借助具有“先进先出”特点的队列，采用广度优先遍历二维网络结点，在

21、选择邻接结点进行遍历的时候，采用的禁忌策略是禁止访问已经访问的结点，以及被标识为障碍物的结点。该算法相比传统ID 算法空间复杂度主要包含两部分： 步骤1步骤2，使用大小为MaxRow*MaxCol的二维矩阵存放结点的状态，其空间复杂度为O(n。步骤3，基于队列采用广度优先遍历二维网络结点，最坏的情况有一半结点入队，其空间复杂度为O(n/2。因此ID 算法的空间复杂度为O(3*n/2。 4.2 仿真实验Dijkstra 算法的时间复杂度O(n2 ，得到了很大的改进，其时间复杂度下降到O(4*n。通过基于ID 算法的静态环境下移动机器人路径规划仿真实验，得到的实验结果表明ID 算法能准确并快速地寻

22、找到最优路径。今后我们将对多机器人协调作业环境下的路径规划技术做进一步研究。由于障碍物及机器人数目的增加，极大地增加了路径规划的难度，我们拟引入可优化约简知识的粗糙集理论，简化规划条件，提取路径规划特征参数来解决多机器人路径规划问题。 参考文献:1 蒋新松. 机器人导论M. 沈阳: 辽宁科学技术出版社,1994.2 付岩. 智能水下机器人全局及局部路径规划技术研究 D. 哈尔滨：哈尔滨工业大学，2004.基于微软公司的MFC 基础类库，本文在Windows 平台下采用C+语言，设计并实现了一种静态环境下移动机器人路径规划仿真系统，其中求解寻路径子问题时采用了ID 算法。针对四种不同静态环境下移

23、动机器人的路径规划实例，在主频为800HMz 的AMD athlon2200的CPU 、512M 内存的PC 上进行求解，消耗时间不超过0.001 s。四种不同静态环境下的路径规划结果如图3所示，红色结点构成的安全路径为最优路径，表明ID 算法能准确并快速地寻找到最优路径。 3 戴光智. 智能吸尘器全覆盖路径算法研究和测控系统的设计 D. 广州：广东工业大学，2005.4 庄晓东, 孟庆春. 动态环境中基于模糊概念的机器人路径搜索方法 J. 机器人,2001, 23（5）：397-399.5 李彩虹, 李贻斌, 范晨. 移动机器人动态避障算法 J.山东大学学报:工学版, 2007, 37（5）

24、： 60-64.6 Surmann H, Nüchter A, Hertzberg J. An autonomous图3 四种不同静态环境下移动机器人的路径规划结果 Fig.3 The result of our experimental evaluations on fourdifferent gridsmobile robot with a 3D laser range finder for 3D exploration and digitalization of indoor environments J. Robotics and Autonomous Systems, 20

25、03, 45（3）：181-198.7 禹建丽, 韩平. 一种基于神经网络的机器人路径规划算法 J. 洛阳工学院学报, 2001, 22（1）： 31-34.5 结束语本文针对机器人研究领域的路径规划技术进行了深入地研究，阐述了机器人路径规划问题的环境表示、寻空间、寻路径三个子问题，以及路径规划问题具有复杂性、随机性、多约束、多目标等特点。本文还讨论了自由空间法、图搜索法、栅格解耦法和人工势场法等传统路径规划方法，以及基于模糊方法、神经网络和遗传算法等智能算法的路径规划方法。8 陈宗海, 陈锋. 一种不确定环境下移动机器人避障规划算法 J. 机器人, 2002, 24（4）： 359-361.

26、9 禹建丽, Roumov V, 孙增圻. 一种不确定环境下移动机器人避障规划算法 J. 机器人, 2007, 23（3）：201-205.(参考文献10- 15转第64页64井冈山大学学报(自然科学版效地避免了低优先级队列出现“饿死”的现象。而且队列长度抖动也很小。 参考文献：1 Gevros P,Crowcroft J, Kirstein P, et al.Congestioncontrol mechanisms and the best effort service model J. IEEE Network, 2001, 15( 3 : 16-26.2 DIOT C, BOUDEC J

27、 L. Control of best efforttrafficJ .IEEE Network, 2001, 15( 3 :14 - 15.3 Floyd S, Jacobson V. Random early detection gatewaysfor congestion avoidanceJ.IEEE ACM Transactions on Networking,1993,1(4:397 - 413.4 Firoiu V, Borden M. A study of active queuemanagement for congestion controlC.IEEE INFOCOM 2000 : 14