基于可视图与A*算法的路径规划

详细信息    查看全文 | 推荐本文 |

英文篇名：Path Planning Based on Visibility Graph and A* Algorithm 作者：黎萍 ; 朱军燕 ; 彭芳 ; 杨亮 英文作者：LI Ping;ZHU Jun-yan;PENG Fang;YANG Liang;Zhongshan Institute,University of Electronic Science and Technology of China;Technical Center,Zhongshan Entry-Exit Inspection and Quarantine; 关键词：路径规划 ; 可视图 ; A~*算法 ; Lambda~*算法 ; 路径平滑 英文关键词：path planning;;visibility graph;;A* algorithm;;Lambda* algorithm;;path smoothing 中文刊名：JSJC 英文刊名：Computer Engineering 机构：电子科技大学中山学院;中山出入境检验检疫局技术中心; 出版日期：2014-03-15 出版单位：计算机工程 年：2014 期：v.40;No.436 基金：国家科技型中小企业技术创新基金资助项目(12C26214405188);; 广东省教育部产学研基金资助项目(2011B090400371);; 电子科技大学中山学院博士启动基金资助项目(410YKQ01) 语种：中文; 页：JSJC201403041 页数：4 CN：03 ISSN：31-1289/TP 分类号：199-201+206

摘要

结合可视图的骨架构造方法和A~*图搜索方法,采用矩形包络障碍物,在障碍物顶点外延生成路径点。在此基础上,提出一种新的路径规划算法Lambda~*,与A~*算法类似,搜索过程需要2张表,但CLOSED表保存从起始节点开始的路径节点,OPEN表保存CLOSED表中扩展节点的后续节点,可减少在OPEN表中保存的节点数量,减少计算量和耗时,并通过增加SMOOTH过程以提高路径的平滑度。将算法应用于二维空间环境进行机器人路径规划仿真实验,结果表明,与A~*算法相比,Lambda~*算法能够以增加较少路径长度为前提,大幅降低路径规划的耗时。
        Inspired by skeleton construction method visibility graph and graph search methods A*,obstacles are enveloped by rectangles,path points are generated as obstacle vertices' extension,and a new path planning algorithm Lambda* is presented,which needs two lists.But differently,CLOSED list in Lambda* is used to store the path nodes from starting node sequentially,and OPEN list is used to save subsequence nodes for the extending node in CLOSED list.What's more,SMOOTH process is added to smooth the path saved in CLOSED.For validation verification.Lambda* is used in 2D simulation environment.The simulation results show that Lambda* algorithm's time consuming is decreased substantially with little increase of path length compared with A* algorithm.

引文

[1]朱大奇,颜明重.移动机器人路径规划技术综述[J].控制与决策,2010,25(7):961-967.
    [2]成伟明,唐振民,赵春霞,等.移动机器人路径规划中的图方法应用综述[J].工程图学学报,2008,29(4):12-20.
    [3]Oommen B,Iyengar S,Rao N S V,et al.Robot Navigation in Unknown Terrains Using Learned Visibility Graphs[J].IEEE Journal of Robotics and Automation,1987,3(6):672-681.
    [4]Choset H,Burdick J.Sensor Based Planning,Part I:The Generalized Voronoi Graph[C]//Proc.of IEEE International Conference on Robotics and Automation.[S.l.]:IEEE Press,1995:1643-1648.
    [5]Parsons D,Canny J F.A Motion Planner for Multiple Mobile Robots[C]//Proc.of IEEE International Conference on Robotics and Automation.[S.1.]:IEEE Press,1990:8-13.
    [6]Liu Yunhui,Arimoto S.Computation of the Tangent Graph of Polygonal Obstacles by Moving-line Processing[J].IEEE Transactions on Robotics and Automation,1994,10(6):823-830.
    [7]Papadatos A.Research on Motion Planning of Autonomous Mobile Robot[D].Monterey,USA:Naval Postgraduate School,1996.
    [8]Stentz A.The Focussed D*Algorith(?)for Real-time Replanning[C]//Proc.of the 14th International Joint Conference on Artificial Intelligence.San Francisco,USA:ACM Press,1995:1652-1659.
    [9]Daniel K,Nash A,Koenig S,et al.Theta*:Any-angle Path Planning on Grids[J].Journal of Artificial Intelligence Research,2010.39(1):533-579.
    [10]汪首坤,邸智,王军政,等.基于A*改进算法的机械臂避障路径规划[J].北京理工大学学报,2011,31(11):1302-1306.
    [11]贾庆轩,陈钢,孙汉旭,等.基于A*算法的空间机械臂避障路径规划[J].机械工程学报,2010,46(13):109-115.
    [12]Botea A,MQIler M,Schaeffer J.Near Optimal Hierarchical Path-ftnding[J].Journal of Game Development,2004,1(1):7-28.
    [13]Lozano PT,Wesley M A.An Algorithm for Planning Collision-free Paths Among Polyhedral Obstacles[J].Communications of the ACM,1979,22(10):560-570.