1 研究目的及意义

近年来,中国经济不断增长，国内的汽车保有量不断增加，交通资源和交通需求之间供需不平衡的矛盾亟待解决。同时，正在召开的十九大，李克强总理的政府工作报告提及了，要进一步推动集成电路、第五代移动通信，飞机发动机，以及新能源汽车等产业发展，同时二氧化硫、氮氧化物排放量要下降3%。智能交通系统应运而生，利用智能交通系统来解决上述问题已成必然趋势。现如今，不仅仅各大汽车厂商投入大量资金研发相关技术，互联网与移动通信公司也争相进入了这一领域。无人驾驶汽车路径规划技术是智能交通系统的一个重要领域，北京理工大学的相关研究学者^[1]这样定义无人驾驶汽车路径规划：无人驾驶汽车路径规划是指在一定环境基础上，给定无人驾驶汽车起始点与目标点后，按照性能指标规划出一条无碰撞、能安全到达目标点的有效路径。由此可知路径规划技术的优劣在某种程度上代表了无人驾驶车辆的智能化水平。因此对无人驾驶汽车的路径规划技术进行研究很有必要。路径规划技术主要问题在于如何建立环境模型以及选取适合的路径搜索策略两个子问题。无人驾驶汽车领域的路径规划技术主要继承了机器人研究领域的相关研究成果，相关的技术已经取得非常瞩目的成就。但在相关研究成果中还有值得改进的部分，故本次研究旨在通过选取一种目前已有的路径规划算法实现无人驾驶汽车路径规划，并解决该算法中存在的部分问题。

2 国内外研究现状

从20世纪70年代开始，美国和欧洲等科技强国就开展对智能汽车无人驾驶的相关研究^[2]，并取得了一系列的成果。1989年，美国卡耐基梅隆大学（Carnegie Mellon University）首次运用神经网络（Neural Network）控制一辆翻新的陆军救护车-NLVINN，实现了车辆的自动驾驶^[3]，最高时速达88km/h。国内在这一方面的研究相对于国外稍晚，最早始于20世纪80年代，1985年期间，由北理工等五家单位负责研制的我国第一辆无人车-ATB1（AutonomousTest Bed-1），最高时速达21km/h^[4]。涉及到智能汽车或机器人相关领域，路径规划是其中的一个必不可少的环节，对于无人车驾驶领域里的路径规划技术的研究也有很多学者进行了研究。路径规划技术的重点主要包括环境建模和路径搜索策略以及多约束问题等。在环境建模方面，环境地图的表示方法主要包括度量地图表示法、拓扑地图表示法和混合地图表示法三种。在度量地图表示法中，根据坐标系中的栅格是否被障碍物占据，分为几何表示法和空间分解法。几何表示法在位置估计和目标识别方面有独特的优势，不足在于环境几何特征提取困难。常用的可视图，Voronoi图等。可视图法^[5]是T.Lozano-Perez和M.A.Wesley等人在1979年提出的一种无碰撞路径规划算法—位姿空间法，并基于位姿空间法提出了可视图法。可视图法的优点是概念直观，实现简单，缺点是缺乏灵活性，且算法的复杂性和障碍物的数量成正比，不是什么时候都可以获得最优路径。Voroni图法^[6-7]是基于可视图法的改进方法，是俄国数学家Voronoi最早提出的，它是从起始点到目标点的最短路径图，即机器人必须靠近障碍物行走，不足在于对控制精度要求高，机器人碰撞障碍物的几率大。相对于可视图法，Voronoi图法实时性比较好，生成的路径也比较平滑，但是它不能获得最短路径。空间分解法一般包括均匀分解法和递阶分解法。递阶分解法克服了均匀分解法在大规模环境下计算复杂的问题，常用的四叉树分解法就是基于递阶分解实现的。拓扑地图表示法选用节点表示在道路上的特定位置，并用节点与节点之间的关系表示道路间联系，其优势是结构简单、效率高、鲁棒性好。劣势是在大规模环境下，所含的信息不充分。混合地图表示法综合了前述两种的特点，结合了度量地图的高精度和拓扑地图的高效率，降低了计算法复杂性，同时也满足了对精度的要求。

路径规划方法是在环境建模的基础上采用有效的路径搜索策略并进行合理的优化。通过国内外学者的不懈努力，这方面的研究成果丰硕，从最开始的人工势场法^[8~11]，Dijkstra算法^[12~15]，A*算法^[16~19]，D*算法^[20]，以及各种智能算法，如神经网络算法^[21~23]、模糊逻辑算法^[24]、遗传算法^[25~28]等等。通过总结可以发现，主要常见的规划方法包括两大类：一是基于地图的路径搜索策略，二是基于采样的路径规划策略。基于地图的路径搜索策略对于环境建模通常是采用单元分解法或道路图法建立环境模型，这类路径搜索策略中主要有深度优先搜索（Depth-first Search）、广度优先搜索（Breadth-first Search）、迭代加深搜索（Iterative-deepeningSearch）、等代价搜索（Uniform-cost Search）以及启发式搜索（Heuristic Search）。对于环境中节点数目少时，采用DFS，BFS，IDS以及HS搜索策略比较有效。著名的Dijkstra算法就是广度优先搜索算法（BFS）的典型代表，它的每一步都选择局部最优解，按长度路径递增次序产生的最短路径。但对于环境中节点较多时，启发式路径搜索策略由于采用一个评价函数来表示从初始节点到任意节点的代价，以此选择下一节点位置，提高了效率。A*算法就是一种经典的启发式搜索算法，它在搜索过程中通过建立估价函数判断优先搜索节点，目前应用比较广泛，A*算法的关键在于选取合适的代价函数。ARA*算法在建立代价函数的同时还引入了v(n)值和一个INCONS表，相对于A*算法，它提高了求解的效率，缺点是当环境变化时，存在无法处理的情况。LPA*算法是用来处理动态环境的路径规划算法，它是基于A*算法改进的，相比于A*它的规划时间短且能实现最优。AD*算法结合了ARA*和LPA*的优点，主要解决了路径规划中的实时性和最优性问题。

基于采样的路径规划策略，常见的有概率图算法（PRM）,它是通过建立随机状态之间的关系得到概率图。它的优势是只要给定了初始状态和目标状态后，该算法通过快速搜索概率图，便得到了路径。但该算法在引入运动约束存在计算量剧增的问题。由LaValle和Kuffner提出的快速随机扩展树算（RRT）^[29~30]是基于树结构的典型算法，同时又是基于随机采样的规划方法，不需要预处理，搜索效率高，在高维空间的优势明显，近年来得到了广泛的应用。概率图算法（RPM）和快速随机扩展树算法（RRT），它们的相同点是均不考虑障碍物在C-space中的分布情况，而是采用碰撞检测函数对几个随机采样点进行碰撞检测，满足概率完备，规划效率高。但是由于随机采样引入的随机性，导致用户无法对结果进行预判，每次的规划结果不一致，不能满足工业上对稳定性的要求。目前，路径规划领域的研究也主要集中在对PRM和RRT的改进上，力求解决该类算法的不确定性问题。目前，针对这类算法提出的改进算法有RRT^*、Informed-RRT^*等。

2. 研究的基本内容与方案

1.1 研究的基本内容、目标：

（1）了解智能车路径规划技术国内外的研究现状