基于关键节点的改进A_无人车路径规划算法_张辉.pdf

汽车技术【摘要】针对传统A*算法在结构化道路场景下进行无人车路径规划时存在搜索路径多曲折、紧贴障碍物边界、不平滑及搜索时间随栅格规模增大而呈现指数型增长趋势等缺陷，提出一种改进A*算法，首先应用地图预览模块提取栅格地图关键节点，同时引入基于安全距离的碰撞场模型改进代价函数，基于关键节点信息判断开启增量扩展搜索，直至搜索到目标节点，最后应用准均匀三次 B 样条曲线对生成路径进行平滑得到最终的规划路径。仿真结果表明，与传统 A*算法和Weighted-A*算法相比，改进A*算法提高了搜索效率，改善了路径的安全性和可行性。主题词：路径规划A*算法关键节点碰撞场模型中图分类号：TP301.6文献标识码：ADOI:10.19620/ki.1000-3703.20220144Key Nodes-Based Improved A*Algorithm for Path Planningof Unmanned VehicleZhang Hui1,Zhang Ruiliang1,2,Xu Xiaoqing1,Fan Zhengwu1,2（1.Taiyuan University of Technology,Taiyuan 030024;2.Shanxi Automotive Design Engineering Technology ResearchCenter,Taiyuan 030024）【Abstract】For the defects of traditional A*algorithm in unmanned vehicle path planning in structured road scene,such as multiple twists and turns of search path,close to obstacle boundary,unsmooth and exponential growth trend ofsearch time with the increase of grid scale,this paper proposed an improved A*algorithm.Firstly,the map preview modulewas used to extract the key nodes in the grid map,then the collision field model based on the safe distance was introducedto adjust the cost function.The algorithm conducted incremental extended search based on the information of key nodesuntil the target node was identified.Finally,the generated path was smoothed by quasi uniform cubic B-spline curve toobtain the final planned path.The simulation results show that compared with the traditional A*and weighted-A*algorithm,the improved A*algorithm proposed in this paper improves the search efficiency,path security and feasibility.Key words:Path planning,A*algorithm,Key node,Collision field model张辉1张瑞亮1,2许小庆1范政武1,2（1.太原理工大学，太原 030024；2.山西省汽车设计工程技术研究中心，太原 030024）通讯作者：张瑞亮（1977），博士，教授，主要研究方向为智能驾驶汽车系统研发、专用车设计与开发，rl_。基于关键节点的改进A*无人车路径规划算法汽车技术 Automobile Technology【引用格式】张辉,张瑞亮,许小庆,等.基于关键节点的改进A*无人车路径规划算法J.汽车技术,2023(3):10-18.ZHANG H,ZHANG R L,XU X Q,et al.Key Nodes-Based Improved A*Algorithm for Path Planning of Unmanned VehicleJ.Automobile Technology,2023(3):10-18.1前言无人车系统主要包括感知、决策、规划和控制4个模块1，其中规划模块负责基于目标任务生成最优路径。按照搜索方式可将路径规划算法分为基于图搜索、基于采样及基于人工智能的方法。其中，基于图搜索的A*算法因其寻优能力强、场景适应度高等特性而得到广泛应用2。陈若男等3结合距离及角度信息改进传统A*算法代价函数，设计邻域选择策略，提升了算法效率和路径安全性。杨瑶等4通过改进距离估算方式，引入车身轮廓代价和障碍物距离代价，提升了A*算法规划效率和路径安全性。冯来春等5将A*算法和快速搜索随机树（Rapid-Exploring Random Tree，RRT）算法结合，降低了RRT算法的采样盲目性。孟珠李等6将A*算法与B样条曲线结合，改善了A*算法规划路径的平滑性。余文凯等7采用K-均值（K-Means）聚类算法对地图进行预处理，量化不同区域地图复杂度，依据复杂度设置搜索权重，应用弗洛伊德（Floyd）算法对路径进行平滑，提高了路径规划效率和路径平滑性。祁玄玄等8从目标性拓-102023年第3期张辉，等：基于关键节点的改进A*无人车路径规划算法展等多个方面对传统A*算法进行改进，提升了A*算法的搜索效率。Frantisek等9研究了各种改进A*算法，如跳点搜索（Jump Points Search，JPS）、Phi*等，并基于部分算法进行了仿真验证。Hao等10提出了一种可以自适应调整搜索深度的Cell A*算法，使高复杂度场景地图下的计算耗时进一步缩短。Zahra等11在A*算法中引入动态可变栅格，增加了危险惩罚代价，提升了路径安全性和计算效率。搜索效率和路径安全性及可行性是规划算法的核心，但A*算法多循环判断机制导致其路径性能和计算效率难以同时得到有效改善。因此，本文提出一种改进A*算法，基于地图预览模块提取栅格地图关键节点，规划模块依据关键节点信息判断是否开启增量式扩展搜索，引入基于安全距离的碰撞场模型改进代价函数，应用准均匀三次B样条曲线对生成路径进行平滑处理得到最终的规划路径。最后与对比算法在不同复杂度场景下进行仿真验证。2传统A*算法传统 A*算法融合了广度优先搜索（Breadth FirstSearch，BFS）算法和深度优先搜索（Depth First Search，DFS）算法的优势3，其基于当前节点与起点和目标点之间的距离信息进行节点扩展和选择。传统A*算法作为典型图搜索算法，其规划地图通常以栅格地图形式表达，如图1所示为某栅格地图示例。栅格地图尺寸决定了地图表达的精度和规模12，广义栅格地图仅包含障碍物信息。如图1所示，在规划过程中，车辆从起点出发，通过扩展循环最终行驶至目标点，传统A*算法具体流程如图2所示。节点扩展时依据场景特点及无人车运动学特性选取四邻域方式进行节点扩展；代价函数f(N)通过当前节点与起始点间的真实距离g(N)和当前节点与目标节点间的预估距离 h(N)累加得到13-16，h(N)一般采用曼哈顿（Manhattan）、欧 几 里 得（Euclidean）、切 比雪夫（Chebyshev）距离。3改进A*算法传统A*算法存在搜索路径多曲折、紧贴障碍物边缘、不平滑及搜索时间随栅格地图规模增大而呈现指数型增长趋势等缺陷。一般结构化道路作为车辆的主要应用场景，其特点为道路多正向直行区间、多交叉区域、空间障碍物类型较多，因此其规划的路径无法直接适应无人车在此类环境下的工作需求。本文针对此类场景需求提出改进A*算法，流程如图3所示。开始加载栅格地图，确定起始节点，设点目标节点是否回溯，输出路径并进行平滑处理结束地图预览得到道路关键转向节点和死角节点基于当前节点目标向量选取下一关键转向节点基于当前节点与所选取关键节点形成搜索域目标节点被选中区域内存在障碍物否是是否到达选取节点基于改进代价函数进行增量扩展搜索，并寻找最小代价值节点将车辆由当前节点直接转移至选取节点处关键转向节点关键死角节点目标点起点SG图1栅格地图开始加载栅格地图，确定起始节点，设点目标节点将起始节点加入open列表中open列表为空是否输出无可行路径由代价函数选择open列表中的最小代价值节点，并置于close列表是否该节点是目标节点回溯，输出路径将未在open列表中的四邻域节点移入open列表结束图2传统A*算法流程图3改进A*算法流程-11汽车技术相对于传统A*算法，算法的主要改进如下：a.引入地图预览模块提取道路转向关键节点和道路死角关键节点，并基于目标向量信息选取关键节点，基于当前节点和拟选择关键节点形成搜索域，基于障碍物判定规则判断是否开启增量式扩展搜索；b.对不同类型障碍物进行分类，提出一种基于安全距离的碰撞场模型，并结合其对传统A*算法代价函数进行改进；c.应用准均匀三次B样条曲线对规划路径在转折处进行平滑，生成满足车辆运动学约束的最终路径。3.1基于关键节点信息的扩展搜索策略3.1.1关键节点信息获取传统栅格地图作为地理信息载体17，其将环境抽象为栅格状态，仅反映不同位置障碍物信息。为进一步提高算法效率，本文提出一种基于地图预览模块获取栅格地图关键节点的方式。获取栅格地图后，地图预览模块从栅格群中提取关键节点至关键节点列表中，并将道路边界节点集合提取至道路边界节点列表中。其中，关键节点包括道路转向关键节点和道路死角节点两类，分别存放于关键节点列表的不同列中，两类节点见图1，其中，道路死角关键节点仅能作为起点位置，一旦规划过程拟选定道路死角关键节点，则放弃该操作，重新进行节点选择。3.1.2目标向量定义无人车在进行节点选择时，依据当前节点与目标点间向量，即目标向量进行判断，选取策略如图4所示，其中，S节点为起点，A、B、C、D节点为车辆可选关键节点，G节点为目标点。车辆从起点S出发，并基于当前位置的向量SG（当车辆行驶至新位置时，目标向量由当前节点与目标点构成）选择方向趋近于目标点的关键节点，判定拟选定的关键节点是否为道路死角关键节点，如果是，则放弃此节点，重新选择其他可行节点，反之，判断当前节点至拟选定节点间搜索域内是否存在障碍物，如果不存在，则直接将车辆从当前位置节点移至拟选定关键节点处，如果存在，则进行增量式扩展，得到该区域内无碰撞的安全路径。当车辆驶至拟选定关键节点后，依据直行优先原则，结合当前节点至目标节点向量进行关键节点选择，直至到达目标点G，跳出循环，输出最终路径。3.2改进代价函数传统A*算法的代价函数仅考虑当前节点与起始点和目标点之间的距离关系。其中：当前节点与起始节点之间真实距离代价g(N)可使已搜索路径最优，但无法抑制无效节点扩展；当前节点与目标节点之间的预估代价h(N)可以有效改善算法节点扩展盲目性，但目标趋向也将导致A*算法规划路径过早转折或紧贴障碍物边界，不利于行车安全。因此，本文结合地图预览模块获得的关键节点信息和道路边界信息，对A*算法进行改进。3.2.1距离表达函数为了适应结构化道路特性和无人驾驶汽车运动学特性，本文选用Manhattan函数计算当前节点至目标节点的距离18。Manhattan距离是为规划方型建筑区块的最短行车路径而提出的，因此采用Manhattan函数预估结构化道路中两点之间距离更接近真实值19。以图1为例，节点S与目标点G的距离为：dM=|Gx-Sx|+|Gy-Sy|（1）式中，dM为当前节点与目标节点之间的Ma