韩丰键，邱书波，李庆华*，刘海英

(齐鲁工业大学(山东省科学院)a. 电气工程与自动化学院；b. 电子信息工程学院(大学物理教学部)，山东 济南 250353)

随着工业生产对圆盘移动机器人要求的不断提高，路径规划已经成为一个重要研究领域，传统路径规划算法主要有A*算法[1]、蚁群算法[2]、人工势场算法[3]、遗传算法[4]等。尽管这些算法在处理低维空间路径规划问题具有一定的优越性，但是当空间维度较高时，算法在精确表达构型空间上需要占用大量的计算资源。基于采样思想的路径规划算法，如概率路线图算法(probabilistic roadmap method,PRM)[5-7]、快速扩展随机树算法(rapidly exploring random trees，RRT)[8-10]，不需要精确表达构型空间，而是通过在构型空间内获取自由构型形成构型图，以描述构型空间的连通性，这类算法在机械臂、人型机器人等高维构型空间上所体现出的优势更为明显。

Lavalle等[9]首次提出了RRT算法，基于随机采样的思想获取自由构型，用以构建一个树形网络表达自由构型空间。该算法避免了对整个环境空间建模，在高维构型空间的路径规划问题中优势更为明显。但是RRT算法采用的随机采样思想，也导致了节点的扩展无目标导向性，容易出现大量冗余节点，算法的收敛速度过慢。针对RRT算法生成构型无目标导向性、收敛速度慢、路径拐点多的缺点，Urmson等[11]提出了路径代价函数的概念以表征路径的优化程度，面向目标路径越优则路径代价越小。该算法在扩展中，不再选择距离随机构型最近的节点，而是选择k个较近的节点进行扩展，提升了已扩展RRT树内距离随机构型较近节点的搜索性能。……