资源描述：
《全局路径规划中基于改进可视图法的环境建模_李善寿》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第25卷第6期华东交通大学学报Vol.25No.62008年12月JournalofEastChinaJiaotongUniversityDec.,2008文章编号:1005-0523(2008)06-0073-05全局路径规划中基于改进可视图法的环境建模1,31,322李善寿,方潜生,肖本贤,齐东流(1.安徽建筑工业学院电子与信息工程学院,安徽合肥230022;2.合肥工业大学电气与自动化工程学院,安徽合肥230009;3.安徽省智能建筑重点实验室,安徽合肥230022)摘要:主要针对静态已知环境下的全局路径规划作了研究,在切线
2、图和Voronoi图的基础上,考虑安全性与路径最优化,论文采用一种改进的可视图法建立环境模型和确定AGV向目标点运动的有效路径.与传统的可视图法把障碍物的顶点作为图的节点、把障碍物的边作为弧相比,这种改进的方法把障碍物顶点连线的中点作为节点,把这些节点间的某些边线作为弧.最后使用遗传算法进行全局路径规划,并对规划出的各节点采用十进制任意编号,把路径编码成定长的十进制染色体串,通过MAT-LAB仿真,结果证明了该方法的可行性.关键词:全局路径规划;改进可视图法;遗传算法;定长十进制编码;仿真中图分类号:TP24,TP273文献标识码
3、:AAGV的路径规划对于保证其安全航行有着重要意义,多年来一直受到研究工作者的重视,也一直是机器人学中的研究热点之一.它研究的是在有障碍物的环境中,如何为机器人寻找从起点到目标点避开障碍的[1]合理、有效的路径.路径规划的第一步就是要建立适当的环境模型.建模的方法有很多,如栅格法、顶点图像法、广义锥法等,这些方法在路径规划时可得到精确解,但模型建立与更新的计算量相当大,实际应用当中存在不小困难.[2]而采用链接可视图法建立的AGV工作空间模型会大大减少建模的复杂性,且能够得到优化路径.因此,这里对AGV在静态已知环境下进行全局路径
4、规划时,采用该方法进行环境建模.首先,对环境空间作如下假设:(1)AGV在二维平面环境中运动,不考虑高度信息;(2)用多边形来描述环境的边界及障碍物轮廓;(3)把障碍物径向扩张,AGV缩成一个点.最终在存在扩张了的障碍物的地图上,可以规划出点AGV的路径.1链接可视图的概念在静态已知的全局路径规划中,障碍物位置已知,AGV与障碍物共同模型组成地图,一般有地图的全局路径规划称为基于模型的路径规划.在基于模型的全局路径规划中,用所谓图的数据结构表示地图,如图1.图中节点表示AGV的位置,弧表示两个位置间的移动.在图上给出距离、工作量或
5、时间等,把希望的最佳值作为费用赋予弧上.能在两个方面移动的用无向弧,否则用有向弧.一个障碍物顶点到其它障碍物顶点之间的连线称为链接线,链接线不与任何障碍物相交.传统的链接可视图法可归纳为3个步骤:(1)用直线划分自由空间为多图1用节点和弧表示图边形区域;(2)将所有障碍物的顶点和AGV的起始点及目标点用直线相连,把这些顶点、起始点、目标点作为节点,把他们的连线作为弧;(3)对这些弧加上权值.收稿日期:2008-08-31基金项目:安徽省自然科学基金资助项目(070414176)作者简介:李善寿(1979-),男,安徽金寨人,讲师,
6、研究方向为嵌入式系统.74华东交通大学学报2008年常用的图有切线图与Voronoi图.切线图是管理从起始节点ns到目标节点ng的最短路径;Voronoi图是连接节点的安全路径,即管理尽量离开障碍物的路径.图2、图3分别表示切线图与Voronoi图.在切线图上虽然可选择ns到ng的最短路径,但AGV几乎接近障碍物行走,即切线图是把障碍之间的切线图形化得到的;它用节点表示切点,用弧线表示连接两切点的路径,这时弧上可附加两端点间距离作为费用.Voronoi图可选择从ns到ng的安全路径,AGV能够在离障碍物足够远的路径上行走;即Vor
7、onoi图可用弧表示距两个以上障碍物和墙壁表面等距离的点阵,用节点表示它们的交叉位置.这时,弧费用可用连接节点点阵距离给出.对于切线图,如果在控制过程中产生位置误差,AGV碰撞障碍物的可能性会高;对于Voronoi图即使产生位置误差,AGV也不会碰撞障碍物,但会增加距离.图2切线图图3Voronoi图2环境模型的建立考虑安全性与路径最优化,论文采用一种改进的可视图法.与传统的可视图法把障碍物的顶点作为图的节点、把障碍物的边作为弧相比,这种改进的方法则把障碍物顶点连线的中点作为节点,把这些节点间的某些边线作为弧.与切线图相比,这种方
8、法虽然从起始点到目标点的路径有些加长,但即便误解了自己的位置,偏离了规定的路径,也可避免碰撞障碍物;与Voronoi图相比,其路径又有所减小.改进后的方法如下:(1)作各障碍物的链接线;(2)删去多余的链接线,使链接线与边界、障碍物边线围成的每一个
