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

Path Planning Based on Visibility Graph and A* Algorithm

作　　者：黎萍[1] 朱军燕 彭芳[1] 杨亮[1] 

机构地区：[1]电子科技大学中山学院,广东中山528402 [2]中山出入境检验检疫局技术中心,广东中山528403

出　　处：《计算机工程》2014年第3期193-195,200,共4页Computer Engineering

基　　金：国家科技型中小企业技术创新基金资助项目(12C26214405188);广东省教育部产学研基金资助项目(2011B090400371);电子科技大学中山学院博士启动基金资助项目(410YKQ01)

摘　　要：结合可视图的骨架构造方法和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.

关 键 词：路径规划 可视图 A＊算法 Lambda＊算法 路径平滑 

分 类 号：TP24[自动化与计算机技术—检测技术与自动化装置]