姜 康，王 皓，陈佳佳

(合肥工业大学 汽车与交通工程学院，安徽 合肥 230009)

0 引 言

智能车辆研究的关键问题有：定位、感知、规划、决策以及控制。路径规划是规划的重要一环，在机器人领域又称为运动规划，是指用于将期望的运动任务分解成离散的运动，以满足运动的限制，并可能优化运动的某些方面。智能车中的路径规划，是指生成一条从起点到终点的可行驶路径，同时满足时间、环境以及车辆动力学等约束[1]。

智能汽车可理解为一种多轮机器人，因此智能车路径规划算法与机器人领域相关算法一脉相承。常见有模糊规则法、遗传算法、神经网络、蚁群优化算法等，但这些算法的复杂度会随着自由度增加呈指数级增长，并不适合解决复杂障碍物下的规划问题。此外还有基于图的算法例如A*算法[2]、D*算法、人工势场法[3,14]等，这类算法虽满足路径规划的实时性和最优性要求，但规划的路径并未考虑车辆的动力学特性，使规划路径不一定符合智能汽车的运动约束。

基于采样空间的算法，搜索速度快且算法复杂度不会随着自由度的增加转向指数级增长，比较适合智能车的规划问题。快速随机搜索树(rapidly-exploring random tree，RRT)作为此类算法的代表[4]，由LAVALLE提出，但是此算法存在3点缺陷：①在全局使用均匀采样，虽保证了算法的概率完备性，却导致算法的开销过大，降低了收敛速度；②原始的最邻近算法在存在复杂约束时算法可能多次失效，因而无法满足实时性要求；③在全局的随机采样，导致生成路径不平滑，无法满足智能车的动力学约束。……