摘要： 结合可视图的骨架构造方法和A*图搜索方法，采用矩形包络障碍物，在障碍物顶点外延生成路径点。在此基础上，提出一种新的路径规划算法Lambda*，与A*算法类似，搜索过程需要2张表，但CLOSED表保存从起始节点开始的路径节点，OPEN表保存CLOSED表中扩展节点的后续节点，可减少在OPEN表中保存的节点数量，减少计算量和耗时，并通过增加SMOOTH过程以提高路径的平滑度。将算法应用于二维空间环境进行机器人路径规划仿真实验，结果表明，与A*算法相比，Lambda*算法能够以增加较少路径长度为前提，大幅降低路径规划的耗时。

关键词: 路径规划, 可视图, A*算法, Lambda*算法, 路径平滑

Abstract: 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.

Key words: path planning, visibility graph, A* algorithm, Lambda* algorithm, path smoothing

中图分类号: 

• TP24