基于混合A_算法的自动驾驶汽车轨迹生成_周苏.pdf

2023年 第2期周苏1,2王若伊1张友发2张岗1（1.同济大学汽车学院，上海 201804；2.同济大学中德学院，上海 201804）【摘要】自动驾驶汽车混合A*算法运行迅速，但是难以保证曲率的连续性和汽车舒适度，并且不能保证优化后的结果无碰撞。针对以上问题，以提高汽车舒适性为目的，基于最小冲击度对A*算法进行优化，在MATLAB和栅格地图中进行了算法预研，解决了低速场景下自动驾驶汽车运动过程中舒适度不足的问题。然后，针对优化算法可能导致轨迹碰撞的问题，对优化算法进行了改进，保证了汽车的安全性，并给出了“走廊”自动调整的策略。仿真结果表明：优化后的轨迹无碰撞且曲率更小，加速度不超出正常范围，可以满足正常驾驶需求。主题词：混合A*算法轨迹优化算法贝塞尔曲线自动驾驶中图分类号：U463.6；TP18文献标识码：ADOI:10.19822/ki.1671-6329.20220270Hybrid A*Algorithm Based Trajectory Generation for AutomatedDriving VehicleZhou Su1,2,Wang Ruoyi1,Zhang Youfa2,Zhang Gang1（1.School of Automotive Studies,Tongji University,Shanghai 201804;2.Sino-German College,Tongji University,Shanghai201804）【Abstract】The hybrid A*algorithm of automated driving vehicles runs quickly,but it is difficult to ensure thecontinuity of curvature and comfort of vehicles,and can not guarantee the optimized results without collision.Aiming at theabove problems,this paper aims to improve the comfort of vehicles,and optimize A*algorithm based on minimum impact.Algorithm pre-study in MATLAB and raster map is conducted to solve the problem of insufficient comfort during themotion of automated driving vehicles in low-speed scenarios.Then,the optimization algorithm is improved to ensure thesafety of vehicles for the problem that the optimization algorithm may lead to trajectory collision,and the strategy ofautomatic adjustment of the“corridor”is given.The simulation results show that the optimized trajectory is collision-freeand the curvature of the trajectory is smaller,and the acceleration does not exceed the normal range,which can meet thenormal driving requirements.Key words:Hybrid A*algorithm,Trajectory optimization algorithm,Bessel curve,Automateddriving基于混合A*算法的自动驾驶汽车轨迹生成【欢迎引用】周苏,王若伊,张友发,等.基于混合A*算法的自动驾驶汽车轨迹生成J.汽车文摘,2023(2):44-54.【Cite this paper】ZHOU S,WANG R Y,ZHANG Y F,et al.Hybrid A*Algorithm-Based Trajectory Generation for Automated DrivingVehiclesJ.Automotive Digest(Chinese),2023(2):44-54.1引言自动驾驶汽车配备先进的传感器、控制器和执行器，可以感知复杂环境、进行智能决策和运动控制，最终使车辆达到人类驾驶员驾驶水平1-2。规划作为驾驶自动化系统中不可缺少的环节3，不仅需要从感知层获取当前的周围环境信息和自身定位信息，还需要将规划好的动作信息传到控制层，再交由控制层对汽车进行控制。一个规划迅速、反应良好的规划层直接影响无人驾驶汽车的性能。20世纪至今，规划方法发展迅速，根据具体的计算方法，规划算法分为5类：（1）基于图搜索的规划算法；（2）基于采样的规划算法；（3）基于插值的规划算法；（4）基于数值优化的规划算法；汽车文摘44汽 车 文 摘（5）基于机器学习的规划算法。各类规划算法研究进展如下：（1）基于图搜索的规划算法图搜索算法主要指遍历从起点到终点的状态空间以搜索出当前最优的结果，一般使用栅格、格子来表示一个点的状态。迪杰斯特拉算法是1种单源最短路径的最优路径规划算法，在迪杰斯特拉算法中配置状态空间，一般被离散为单元网格后再进行搜索4。Dijkstra最早给出了这种算法的严格证明5。在自动驾驶领域，迪杰斯特拉算法已经被应用于多车仿真中6，本-富兰克林车队（The Ben Franklin Racing Team）和维克多-探戈（Vector Tango）将其应用于 DARPA 城市挑战赛中7。A*算法是带有启发式函数的迪杰斯特拉算法，非常适合已知地图下的路径规划问题8，但是当要搜索的区域过大时，其所耗费的内存空间也会随之增大，搜索速度随之下降。A*类算法家族具有很多成员，这些A*类算法相比A*有了很多的提升，也被广泛应用到自动驾驶、机器人等领域。比较常见的有Hybrid A*算法、D*算法（Dynamic A*,D*）、Field A*算法9、Theta*算法10、ARA*算法（Anytime Reparing A*,ARA*）和 AD*算法（Anytime D*,AD*）11。在自动驾驶领域中，Ziegler等12在文献中实现了A*算法用于非结构化空间下（停车场）的规划。混合状态A*算法被斯坦福大学用于DARPA挑战赛13。2007年的DARPA挑战赛获胜车辆Boss 也使用了 AD*算法14。Saeid 等15使用了 HybridA*算法实现了停车场中实验车辆的自动泊车。Francesco等16则通过减少车辆转弯和向后行驶，提高了乘客在自动泊车时的乘坐舒适度。Silvana等17使用正态分布变换算法建图后，使用Hybrid A*算法进行路径规划，并使用模型预测控制算法进行控制器设计，实现了在园区内稳定运行的高尔夫球车。Howard等18将状态栅格法应用于崎岖地形下的轮式移动机器人的全局规划和局部规划。Likhachev等8根据控制复杂度将状态空间离散化，而McNaughton等19-22考虑了时间和速度，将状态根据时间空间离散化。（2）基于采样的规划算法基于采样的算法中也有很多实用且高效的算法。如概率路图法（Probabilistic Roadmap,PRM）23，快速搜索随机树算法（Rapidly-Exploring Random Trees,RRT）24。其中，RRT算法也已经被应用到自动驾驶领域。RRT算法是一种快速的在线搜索算法25，可以在半结构化空间中进行快速规划，考虑了非完整约束24。MIT将该算法应用到了DARPA挑战赛中26，但其结果并不稳定，而且曲率也不连续。与A*类算法一致，RRT 类算法也有很多成员，如 RRT*算法27、Informed RRT*算法28、Anytime RRT*算法29，以及Kino-Dynamic RRT*算法29。（3）基于插值的规划算法Reeds等31-32使用了直线和圆弧插值算法来近似汽车规划。螺旋曲线插值中对应的曲线是根据菲涅尔积分定义而来的33，使用回旋曲线可以定义曲率线性变化的轨迹，平滑过渡直线段和弯曲线段34。多项式插值算法非常适合多段轨迹的插值问题。Piazzi等在文献35、36和37中分别阐述了相关的计算方法。贝塞尔曲线插值广泛应用于航空航天、汽车设计、游戏众多领域，在自动驾驶领域的研究中，三阶和四阶的贝塞尔曲线被用来规划当前可以转弯、避障的轨迹38-39。（4）基于数值优化的规划算法基于数值优化40-41的方法时间上是使受不同约束的函数最大化或者最小化，大多数是基于凸优化的算法，还有一些是基于非线性优化的算法。这种算法实际上已经被广泛应用于移动机器人在狭窄通道中避障的势场方法（Potential Field Method,PFM），其轨迹可以包含一阶连续性42甚至更高阶（速度、加速度、冲击度等）连续性的轨迹。（5）基于机器学习的规划算法基于机器学习的方法具有较快的计算速度和较强的泛化能力，但是使用机器学习的方法之前需要进行一定的离线学习。以下机器学习相关的方法被应用在规划领域：强化学习43、流形学习44、卷积神经网络45、隐马尔可夫模型46、高斯混合模型47和径向基函数神经网络48。通过以上分析，目前自动驾驶车辆的运动规划算法存在以下缺陷：（1）考虑了汽车动力学的规划算法计算较慢，且不能保证规划处的路径总是无碰撞的。（2）汽车的路径规划与某些机器人和无人机的路径规划不同，汽车的运动规划属于非完整约束问题，且大多数规划算法规划出的结果是路径，并没有规划出其轨迹。而且即便是有轨迹规划的算法，其路径和速度是不匹配的，需要对速度重新进行规划。（3）大多数规划算法并没有考虑多车协同问题。现在绝大多数的规划算法都是考虑已知地图下的单Automotive Digest452023年 第2期车规划问题。因此，本文以提高汽车舒适性为目的，基于汽车的最小冲击度进行建模，在MATLAB和栅格地图中进行了算法预研，解决了自动驾驶汽车运动过程中舒适度不足的问题。然后，针对优化算法可能导致轨迹碰撞的问题，对优化算法进行了改进，保证了汽车的安全性，并给出了“走廊”自动调整的策略。2基于混合状态A*算法的路径规划模型混合状态A*算法最早出现于2007年美国DRAPA挑战赛49，它并不像迪杰斯特拉算法、A*算法那样经过数学推导而得出，但这并不影响该算法的实用性。2007年，斯坦福大学的车队就是使用该算法跑完了全程。混合A*算法是A*算法的一种变体，它不仅继承了A*算法的特性，还可以在更高维度的状态空间进行搜索，并提出新的状态更新规则。相比A*算法，混合状态A*算法具有更高的搜索维度，主要体现在以下方面：（1）一般混合状态A*算法会在x坐标、y坐标、朝向角和转弯半径4个维度进行路径规划。而A*算法会选取当前累计代价和启发式函数代价最小的点作为下一点来膨胀；（2）与此类似，混合状态A*算法则是基于A*算法和Reeds_Shepp曲线31来决定下一节点，其节点可以不是栅格的顶点。图1是混合状态A*算法的流程图。3基于最小冲击度的优化模型由于很多路径规划算法会将汽车视为点来进行路径规划，这导致某些规划算法规划出的路径超出了汽车的正常行驶范围，且不能保证车内乘客的舒适性。为了提高汽车在运动过程中的舒适性，本文将对混合A*算法的结果基于最小冲击度进行优化。3.1基于最小冲击度的一维优化模型的建立本文建立的基于最小冲击度的优化模型，取最小冲击度的L2范数的平方作为优化的目标函数，优化目标是最小化最小冲击度的平方，目标函数如式（1）所示。Jk=1T0Tjk(t)2dt（1）