1. 研究目的与意义（文献综述）
智能车辆在国内外方兴未艾，是研究的热点，也有巨大的发展前景。面对巨大的市场，智能车辆要想扩大其应用，就必须要满足更高的性能和安全要求。而智能车辆要满足这一系列要求就必须提升在一系列重要问题上的表现，包括环境感知、决策规划和运动控制等。路径规划问题是智能车辆领域的重要问题，是连接环境感知与运动控制之间的桥梁。路径规划算法是解决路径规划问题的关键，其根据感知层建立的地图信息和所选策略，在起始状态和目标状态之间规划一条无碰撞的最优或次优的轨迹或路径。
目前，国内外路径规划算法主要分为三类：一是基于环境信息的全局路径规划如a*算法[1]。a*算法在静态环境中进行路径规划时可迅速高效地求解最优路径。但a*算法在相对复杂的状态环境下，计算量增加，路径规划时间增加。二是基于传感信息的局部路径规划如人工势场算法[2]。人工势场法实时性好， 便于实现，但是容易陷入局部极小值且不利于增加约束条件。三是将人工智能算法如强化学习和神经网络引入路径规划之中[3]。人工智能算法可在整个生命周期内自我学习优化，但仍需其它路径规划算法的结果进行训练。
路径规划算法首先被应用于机器人领域，之后被引入智能车辆的路径规划问题。最简单的路径规划算法是宽度优先搜索算法（breadth first search,bfs）。宽度优先搜索算法将边界向全方向进行扩展直至达到终点或遍历全图结束。bfs的优点在于其算法简单，便于实现并且可以在各种场景下应用，然而其全方位遍历的做法带来了计算量大、计算时间长的代价。在bfs的基础上出现了狄克斯特拉算法（dijkstra’s algorithm）。狄克斯特拉算法引入了代价的概念，在不同区域每移动一步的代价是不同的。狄克斯特拉算法使地图中可以增加地形等复杂度，但狄克斯特拉算法的边界仍然是在每个方向上进行扩展的，计算代价大的问题仍然存在。为解决该问题，诞生了a*算法及其一系列变种。a*是一种启发式算法，其中加入了对距离终点距离的估计值作为启发式，从而a*算法在计算时不再对边界进行全方位扩展，而只对特定方向进行扩展，大大减少了计算量，提升了计算速度。至此，a*算法已经能很好的应对静态地图中的路径规划问题。然而智能车辆需要面对行驶的车辆和附近的行人以及各种突发情况，其工作场景要求更快的计算速度，所以我们需要一种性能更好的算法——即ara*算法[4]。ara*算法（anytime repairing a*）首先快速找到一条到达终点的次优解并执行，然后在允许的时间内，在次优解的基础上进行再次搜索，直至找到最优解。ara*算法在保证精度的同时，极大地提升了速度，满足了智能车辆应用中的要求。
2. 研究的基本内容与方案
1）研究A*算法及其衍生的ARA*算法。通过阅读国内外文献，学习一系列路径规划算法。算法的学习顺序应循序渐进，依次为宽度优先搜索算法，狄克斯特拉算法，A*算法，D*算法[5]，Theta*算法，ARA*算法。其中重点掌握A*算法和ARA*算法，做到掌握算法的推导过程，原理，编程代码和应用方法。对以A*算法为基础的其它优化算法如D*算法做到基本了解。
（2）构建特殊环境下的栅格地图。首先需要查阅文献了解用于路径规划的不同地图类型，并理解它们之间的区别及在本论文的研究中如何选择。利用github平台的共享资源学习如何使用编程语言构建栅格地图，并在MATLAB中利用A*算法和ARA*算法进行路径规划的仿真。对仿真结果（两种算法的计算时间和计算量以及得到的轨迹）进行归纳、比较。
（3）将路径规划算法与智能车辆结合起来，关注算法如何在智能车辆上实现并需要做哪些相应的调整，比较A*算法和ARA*算法在智能车辆路径规划上的优劣。对当前流行的优化方法如跳点等方法进行思考，其是否能够用于智能车辆的路径规划上，能带来什么样的效果。最终得到关于A*和ARA*算法在智能车辆路径规划问题上的应用前景的结论。3. 研究计划与安排
1（8 学期第1周） 方案构思、文献检索、完成开题报告。学习a*算法及其衍生算法，了解国内外发展现状。
2～3（8学期第2-3周） 外文翻译、资料再收集。
4～6（8学期第4-6周） 完成算法的编程语言编写。
4. 参考文献（12篇以上）
[1] hart p e, nilsson n j,raphael b. a formal basis for the heuristic determination of minimum costpaths[j]. ieee transactions on systems science and cybernetics, 1968, 4(2):100-107.
[2]赵鑫,胡广地.平滑ara*算法在智能车辆路径规划的应用[j].机械科学与技术,2017,36(8):1272-1275.
[3]余伶俐,邵玄雅,龙子威, 等.智能车辆深度强化学习的模型迁移轨迹规划方法[j].控制理论与应用,2019,36(9):1409-1422.
