第28卷第6期　2006年11　　月

文章编号:100220446(2006)0620593205

机器人　ROBO　T

Vol.28,No.6

　Nov.,2006

一种新的移动机器人全局路径规划算法

化建宁

1,2

3

,赵忆文,王越超

11

(1.中科院沈阳自动化研究所机器人学重点实验室,辽宁沈阳　110016;　2.中国科学院研究生院,北京　110049)

摘　要:提出了一种新的移动机器人全局路径规划算法.该算法不需要对环境中的障碍物特征做任何假设,也不需要建立障碍物的连通图模型,有效地克服了传统路径规划算法因为搜索而带来的计算复杂性问题,提高了算法的适应性和实时性.仿真结果证明了算法的有效性.

关键词:地图;移动机器人;全局路径规划中图分类号:　TP24　　　　文献标识码:　B

APliMobileRobot

Jian2ning,ZHAOYi2wen,WANGYue2chao

1,2

1

1

(1.RoboticsLaboratory,ShenyangInstituteofAutomation,ChineseAcademyofSciences,Shenyang110016,China;

2.GraduateSchooloftheChineseAcademyofSciences,Beijing100049,China)

　Abstract:Anewglobalpathplanningalgorithmformobilerobotisproposed.Neitherassumptiononobstaclecharacteris2

ticsnorconnectedgraphmodelsforobstaclesareneededinthismethod.Suchdefectsascomputationcomplexityexistingintraditionalmethodscausedbysearchingcanbeavoided,andasaresult,theapplicabilityandreal2timeperformanceareim2provedgreatly.Simulationresultsverifytheefficiencyofthismethod.

　Keywords:map;mobilerobot;globalpathplanning

1　引言(Introduction)

路径规划是移动机器人导航中最重要的任务之

[1,2]

一.移动机器人的路径规划方法可分为两类,一种是基于环境完全信息的全局路径规划,另一种是基于传感器信息的局部路径规划.全局路径规划根据环境模型找出从起始点到目标点的符合一定性能要求的可行或最优路径,涉及的基本问题是环境模型的描述和搜索策略.全局路径规划按环境模型的表示方式可分为两种比较典型的方法,即构型空间[3,4][5]法和自由空间法.构型空间法的基本思想是将机器人简化为一点,同时根据机器人的形状和尺寸将障碍物进行相应的膨胀处理,其中研究比较成熟的是可视图法.该方法将所有障碍物的顶点和机器人起始点及目标点用线段连接,这些线段不能和障碍物相交,即为“可视的”,然后采用某种方法搜索从

[6]3

起始点到目标点的最优路径,如Dijkstra法、A搜索算法等.自由空间法的基本思想是采用预先定义

3收稿日期:2005-12-19

的基本形状构造自由空间,并将自由空间表示为连通图,然后通过对图的搜索来规划路径.传统的路径

规划算法存在的主要问题是:(1)要求对障碍物的形状做一些近似和假设(如要求障碍物为凸多边形).由于实际障碍物形状及轮廓是非常复杂的,障碍物并不都可以用多边形近似,所以假设往往脱离了实际情况,导致算法的应用范围有限,甚至造成本来有解的问题变得无解.在环境模型的处理方面,传统的路径规划算法除了要对障碍物进行处理以外,还要对障碍物的顶点按照逆时针或顺时针进行排序、对障碍物的顶点进行凹凸性判断以及截角等操作.当障碍物的轮廓比较复杂时,这些处理是非常困难的,甚至是不可能的;(2)在进行路径规划之前需要建立路径的连通模型,然后基于连通模型用某种搜索算法得到所求路径.在假定障碍物为多边形的情况下,连通模型的建立相对容易一些,但是当环境比较复杂时,连通模型的建立非常困难.而且当环境发生变