890 　　　　　

计算机测量与控制.2003.11(11)　

ComputerMeasurement&Control　

设计与应用

文章编号:1671-4598(2003)11-0890-03　　　　　　中图分类号:TP242　　　　　　文献标识码:

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

吴忻生,竹利平,胡跃明

(华南理工大学自动化科学与工程学院,广东广州　510640)

摘要:基于移动机器人的安全考虑,提出了一种改进的可视图法。该方法用尽可能远离障碍物的路径表示弧,先确

定可能的路径点作为节点,然后考虑可能路径,建立结点间的弧,并用Dijkstra算法求出图中的最短路径。最后通过仿真研究表明,用文章提出的方法规划的路径可以达到或接近最优路径。

关键词:移动机器人;带权图;Dijkstra算法

ImprovedGlobalPathPlanningAlgorithmofMobileRobots

WUXin2sheng,ZHULi2ping,HUYue2ming

(CollegeofAutomationScienceandEngineering,SouthChinaUniversityofTechnology,Guangzhou　510640,China)Abstract:Animprovedmethodofthevisibilitygraphtoensurethesafetyofrobotsispresented.Thisapproachbuildsthearcsfarawayfromthebarriers.Thepossiblepathnodesatthegrapharefirstdetermined,andthepossiblepathsarealsoconsideredtobuildthearcsamongnodes.TheshortestpathisthenobtainedbytheDijkstraalgorithm.Simulationresultsshowthatthepathde2rivedbythisapproachcanreachorapproximatetheoptimalpath.

Keywords:mobilerobot;weightedgraph;Dijkstraalgorithm

1　引言

移动机器人的路径规划根据路径的有无可以分为全

局路径规划和局部路径规划。全局路径规划是环境已知的一种规划方法,也叫基于模型的规划方法。而局部路径规划是环境未知或部分未知的,即障碍物的尺寸、形状和位置等信息必须通过传感器获得的一种规划方法,也叫基于传感器的路径规划。对于后者,目前已有许多研究者在进行研究,提出了很多方法,如基于路标的路径规划[1]、基于视觉的导航[2]、基于模糊控制的路径规划[3]等。相对而言,关于全局规划的研究显得较为单薄。其中研究较成熟的是自由空间法[4]和可视图法(VisibilityGraph)[5,6]。自由空间法的基本思想是采用预先定义的基本形状(如广义锥形,凸多边形等)构造自

收稿日期:2003-05-03。

基金项目:国家自然科学基金资助项目(69974015);广东省自然科学基金资助项目(990583);广东省教育厅“千百十工程”资助项目。

作者简介:吴忻生(1961-),男,浙江省云和县人,讲师,主要从事自动化技术和智能系统的工程应用的研究。

胡跃明(1960-),男,安徽省绩县人,教授,博导,并担任中国自动化学会控制理论专业委员会委员等学术职务,先后主持完成863计划智能机器人主题、国家自然科学基金等部门的研究开发项目10余项,出版专著4部(章)和重要学术论文60多篇,主要从事智能机器人控制技术、非线性控制理论与应用、基于视觉的检测与控制技术以及智能医疗器械等方向的研究。

由空间,并将自由空间表示为连通图,如何通过对图的搜索来规划路径。可视图法将所有障碍物的顶点和机器人起始点及目标点用直线相连,这些直线均不能与障碍物相交,而后采用某种方法搜索从起始点到目标点的最优路径。但是,在这种方法中,机器人若误解了自己的位置而离开路径,移动机器人碰撞障碍物的可能性会很高。为了安全起见,文章采用一种改进的可视图法。与传统的可视图法把障碍物的顶点作为图的节点、把障碍物的边作为弧相比,这种改进的算法则把障碍物顶点连线的中点作为节点,把这些节点间的某些连线作为弧。这种方法虽然从起始点到目标点的路径有些加长,但即便误解了自己的位置,偏离了规定的路径,也可避免碰撞障碍物。

2　一种改进的运动规划算法

首先,我们对环境空间作如下假设:(1)移动机器人在二维平面环境中运动,不考虑高度信息;(2)用多边形来描述环境的边界及障碍物轮廓(给路径宽度留出一定的裕度,如障碍物间的距离太窄,则可把两者连接成一个障碍物);(3)把障碍物径向扩张,机器人缩成一个点。在存在扩张了的障碍物的地图(平面)上,可以规划为点机器人的路径。

传统的可视图法可以归纳为以下3个步骤:(1)用直线划分自由空间为多边形区域;(2)将所有障碍物的顶点和机器人起始点及目标点用直线相连,把这些顶点及起始点和目标点作为节点,把他们的连线作为弧;(3)对这些弧加上权值。