面向自动泊车的改进混合A＊最优路径算法研究.pdf

为解决混合 算法在自动泊车中搜索时间慢的问题提出了融合双向搜索算法和混合 算法的优化方案 首先利用栅格法优化双向搜索算法解决了在搜索时正向搜索和反向搜索的子节点不重合的问题然后针对搜索时间慢的问题优化混合 算法的节点搜索过程融合了双向搜索算法最后设计仿真垂直入库和侧方位停车两种场景验证了融合算法能够缩短搜索时间关键词:自动泊车混合 算法路径规划双向搜索中图分类号:文献标识码:文章编号:()收稿日期:修回日期:通信作者:崔立堃()男内蒙古武川人博士副教授主要研究方向为新能源汽车能量管理控制策略、自动驾驶控制算法汽车的出现使人们的出行交通更加便利但这种便利也带来了许多现实问题其中泊车就是一大难题 泊车受限于狭窄的视野环境不可控的紧张情绪还要同时面对不同的泊车环境一不当心就会发生事故 自动泊车系统()的出现便能很好地降低事故的发生概率将其限制在一个可控的范围内 自动泊车系统也分为垂直停车和平行停车 垂直停车也就是倒车入库一般用于停车场、车库停车平行停车也就是侧方位停车一般用于路边停车在国内外研究者的持续努力下自动泊车技术研究取得了许多显著成果 混合 算法于 年由斯坦福的 等首次提出该算法是一种基于车辆运动学的规划算法能够满足车辆运动学的要求解决了连续空间内规划车辆朝向和位置的问题但规划效率低下、规划时间过长、规划路径无法保证成功率 等将著名的混合 搜索引擎与 规划相结合在混合(连续离散)环境下寻找最短的非完整路径为混合 规划非完整约束下的最优路径提供了正确的路径点但需要一定要求的高清静态地图部署 瑞典斯德哥尔摩 皇家理工学院综合交通研究实验室()的研究概念车()开发了适用于概念车的混合 算法路径规划算法生成的算法需要以一种便于部署的方式进行包装并且可以与研究车上的其他不同系统进行交互同时也对实现实验测试所需的实时能力的方法以及如何建立模拟和调试的可视化环境提供见解证明了混合 算法的实用性但对算法的运行效率没有显著提升 中国学者 等提出了一种基于 算法和 算法的路径规划算法该算法引入了导引点的概念通过 算法直接生成无碰撞路径并针对各种工作场景采用混合 算法离线计算导引点提升了算法的运行效率但失去了算法最优路径的效果且无法保证完全不会碰撞障碍物 因此本文提出了融合双向搜索的混合 算法在保证避免碰撞且保持最优路径的前提下提升算法的运行效率本文主要设计了一种融合双向搜索算法的改进混合 算法同时设置起点和终点作初始点结合车辆碰撞信息并设置合理的代价函数相互搜寻最佳路径信息能有效地缩减单向搜索后期繁多的无效节点并减少搜索次数同时利用栅格法划分地图有效地避免了在相同区域内重复搜索的可能性同时结合栅格法和双向搜索算法极大地提高了正反向搜索过程中相交的可能性 算法概述.传统混合 算法混合 算法是自动驾驶汽车常用的全局路径规划算法其方法可以看作是 算法结合实际汽车动力学模型后生成的算法其原理与 算法类似从起点开始向四周搜索子节点并计算子节点的代价值取其中最小代价值的点为下一个父节点直至搜索到终点 不同于 算法的是混合 算法搜索方式主要分为前进和后退两种模式并结合车辆模型平均分割其转角并在转角范围内进行子节点的搜索计算当前的车辆位姿到子节点的车辆位姿变换是否会与障碍物发生碰撞并建立 表接收转角范围内搜索到的子节点建立 表接收已经选取过的父节点和最小代价的子节点图()所示为 算法搜索点的搜索模式图()所示为混合 算法搜索邻近点所遵循动力学约束的搜索模式()算法搜索方法 ()混合 算法搜索方法图 两种算法搜索路径对比混合 算法的代价函数为()()()()其中()为当前节点 的代价值()表示起始点到当前点 的路径代价值()为当前点到目标点的预估代价值 混合 算法沿用 算法的启发函数主要有曼哈顿距离、欧氏距离、切比雪夫距离等 其中欧式距离在程序中容易实现只占用少量的计算资源且适合数据的值域比较相似的场景因此本文选用欧氏距离来计算节点的预估代价值()欧氏距离表达式为()()()()其中()为当前点()为终点传统的混合 算法虽然比 算法更加贴合无人驾驶的实际应用场景但也存在些许不足例如在泊车搜索路径中若存在障碍物较多搜索过程就会比较缓慢若搜索路径较长搜索节点数会迅速增大搜索时间会比较长 为了使混合 算法在以上情况也能保持良好的时效性本文选择双向搜索算法和混合 算法相融合以解决混合 算法在障碍物较多时搜索时间较长的问题.双向搜索算法地图数据通常可以用图()这类数据结构表示在图结构中用到的搜索算法就叫图搜索算法 双向搜索算法是一种图搜索算法用于寻找图中一点到另一点之间的路径 在 年第一次设计并实现了双向启发式搜索算法该算法同时从起点和终点进行搜索当两者在中间搜索的点重复时链接两条路径并停止搜索所得到的由两条路径拼接后的生成路径就是双向搜索算法的最 陕西理工大学学报(自然科学版)第 卷图 双向搜索原理示意图佳路径如图 所示假设我们要查找 到 的路径普通搜索流程是从节点 开始查找每个节点查找一次共需要 次而双向搜索各自从节点 和 同时开始查找在查找到 时就已经找到了 到 的节点路径 假设搜索一棵分支因子为 的树初始节点到目标节点的距离为 该算法的正向和反向搜索复杂度都是(/)算法路径复杂时两者相加远远小于单向搜索的复杂度()算法优化与融合.双向搜索算法优化从起点到终点的搜索过程是具有不确定性的即从起点到终点的搜索路径与从终点到起点的搜索路径不一定能完全相交而不相交的情况下两条路径都会执行至搜索到目标点为止但这并不利于优化混合 算法 本文为了解决路径不一定相交的问题运用栅格法划分地图将地图按一定规律进行行和列的规则划分形成许多有规律的网格来方便管理已扩展节点和未扩展结点之间的关系 当正向搜索和反向搜索的子节点在同一个栅格中时中断搜索过程链接反向搜索的父节点至正向搜索的子节点最后输出整个路径这样就得到了一条由正向搜索和反向搜索组成的最终路径 优化算法前后的最终输出路径如图 所示()算法优化前 ()算法优化后图 双向搜索优化图图()为算法优化前的双向搜索交互情形图()为算法优化后的双向搜索交互情形 图()描述了原来双向搜索算法搜索过程中正向搜索与反向搜索同时进行时即使大致方向一致正常相遇的情况下其正向搜索的子节点与反向搜索的子节点也不一定会完全重合其搜索的子节点不同时在正反向搜索的 表中则正反向搜索过程都不会中止最终会形成两条搜索路径 利用地图尺寸与设置的栅格分辨率划分栅格把路径末端点的实际坐标转换为栅格坐标公式为()/()/()/()式中、为栅格坐标的行索引、列索引、朝向编号、为当前路径末端点的横坐标、纵坐标、车辆摆角 为路径分辨率 为车辆摆角分辨率 当正向搜索和反向搜索的路径末端点的栅格行索引和列索引相同时只保留正向搜索的子节点并与反向搜索的父节点重新执行混合 算法保留正向搜索的子节点至 表搜索成功后合成正向搜索和反向搜索的搜索路径并输出曲线第 期 刘知阳崔立堃耿玺钧等 面向自动泊车的改进混合 最优路径算法研究 .算法融合本文在传统混合 算法中融入双向搜索算法得到改进混合 搜索算法 其中的正向搜索算法流程图见图 图 改进混合 算法正向搜索流程图其反向搜索流程大体与正向一致 判断 是否为 若不为 则进入反向搜索流程 经过与图 的正向搜索流程相同的反向搜索若没有找到路径则重置 为 再次经过判别式并进入正向搜索流程 如此循环直到输出最终路径整体代码设计流程:预先设置地图形状、车辆的参数信息和运动分辨率再设置起点和终点的位姿信息()其中、为坐标及车辆偏角的真实值在已知车辆的起始位置、最终停车位置和地图信息后开始自动泊车全局路径的路径规划初始化栅格和 个列表计算起始点到终点的欧氏距离并以此为混合算法的启发值正向搜索以车辆目前位置为起始点最终停车位置为终点(反向搜索相反)选取最小代价值的节点作为父节点利用混合 算法搜寻邻近点并每搜寻一次邻近点就获得搜寻行为的代价值判断父节点到子节点的代价值和子节点到终点欧氏距离的代价值获得预估代价()判断父节点到起始点的花费获得实际代价()判断正向搜索和反向搜索是否有相同的扩展点重复操作直至正反向搜索有相同的扩 陕西理工大学学报(自然科学版)第 卷展点合并列表并输出曲线信息 实验与分析经由 搭建仿真平台对混合 双向搜索算法的时效性、可行性、可靠性进行验证通过仿真平台模拟真实车辆的行驶情况模拟垂直入库实验和侧方位停车实验从中选出一条符合动力学逻辑最小代价的路径并验证该算法的可靠性和时效性同时对比传统的混合 算法对双向搜索的混合 算法的时效性进行比较验证这里比较改进前后的算法在垂直入库和侧方位停车时的搜索时长和路径节点搜索情况.垂直入库实验与分析垂直入库实验通过上述仿真平台模拟自动泊车中垂直入库的情况 该实验只对其路径规划的长度、车辆前进后退的频率、转向的曲率大小作要求不对车辆的速度、受力做分析垂直入库是大部分停车时要遇到的情况且通常困难的情况是空出一个车位的同时两旁的车位都已经被占用这里就仿真该情况下采用改进混合 算法来进行路径规划的过程 垂直入库实验具体路线如图 所示 图 传统混合 算法路径曲线图分析图 可知传统混合 算法规划的路径并非实际最优还存在转角倒车的情况虽然符合车辆运动的动力学要求但是改变方向的实际代价值很高因此最终代价值就不一定是最小代价值最后路径生成曲线就不一定是最优路径更换融合算法后我们保持相同的环境再次重复相同的步骤并保持相同的起点位姿为()其中 为车辆矩形框中心点的 坐标值 为车辆矩形框中心点的 坐标值 为车辆矩形框车头方向(的反方向)与 轴的夹角 图 为更换融合算法后生成的路径曲线图其中图()是在无阻挡物时生成的路径曲线图()是在设置了阻挡物后生成的路径曲线图 ()融合算法路径曲线 ()改变障碍物生成路径 图 融合算法生成路径曲线图分析图()可知在与传统混合 算法相同的条件下本文改进的混合 算法生成路径曲线降低了车辆改变方向的次数运行轨迹虽然不平滑但无停车和倒车的情况降低了融合算法中实际路径代价值且其路径搜索时间比传统混合 算法路径搜索时间更短 图 中无障碍与有障碍物两种情况对比可知融合算法生成路径受障碍物影响较大当障碍物产生不同的变动时其路径规划的时间存在较大的波动其产生的结果不利于直观地比较数据间的差异 因此可以改变不同起点位姿比较改进混合 算法的单向路径搜索和双向路径搜索的搜索时间、改变方向次数、节点数其结果见表 第 期 刘知阳崔立堃耿玺钧等 面向自动泊车的改进混合 最优路径算法研究 表 垂直入库改进算法比较起点终点单向搜索时间/改变方向次数节点数双向搜索时间/改变方向次数节点数()(/).()(/).()(/).()(/).改进算法搜索时间减少率.由表 可知在垂直入库实验中融合算法在路径搜索时间上比传统混合 算法用时平均减少了.传统混合 算法至少改变一次行驶方向而融合算法则减少了改变方向次数减少了部分实际路径代价值的生成表中双向搜索节点数虽然有部分的减少但也有未改变的情况这与设置的起点和终点位姿有关设置的起点位姿不同生成节点数就不固定单向搜索出个别路径时双向搜索则无法更新最优路径生成的节点数也无法减少 图 传统混合 算法侧方位停车路径图.侧方位停车实验与分析侧方位停车通常是在道路旁停车与倒车入库实验相同用融合算法和传统混合 算法对该情况进行路径规划传统混合 算法侧方位停车路径曲线如图 所示在该侧方位停车的过程中起点位姿为()终点位姿为(.)由图 可知侧方位停车中传统混合 算法生成路径时路径存在多次改变行驶方向的问题且其重复路径 图 融合算法侧方位停车路径图规划过多无法在狭窄的环境中准确生成适合的路径曲线实际代价值过大无法确保该路径曲线为最优路径 由图 可知在侧方位停车实验中融合算法能更好地规划正确的路径减少改变行驶方向的次数且在狭窄的空间中也能很好地完成路径规划比传统混合 算法生成的路径实际代价值更低更接近最优路线的标准更改起始点比较传统混合 算法和融合算法在侧方位停车情况下的搜索路径时间、改变方向次数、节点数结果见表 表 侧方位停车改进算法比较起点终点单向搜索时间/改变方向次数节点数双向搜索时间/改变方向次数节点数()(.).()(.).()(.).()(.).改进算法搜索时间减少率.由表 可知在侧方位停车中融合算法的路径搜索时间比传统混合 算法平均减少了.减少了改变方向次数与垂直入库情况相同的是当单向搜索算法搜索到个别路径时双向搜索算法无法更新最优路径搜索的路径节点数无法减少综合分析垂直入库和侧方位停车融合算法比传统混合 算法的搜索时间平均缩短了.陕西理工大学学报(自然科学版)第 卷 结语针对传统混合 算法在自动泊车路径规划过程中搜索时间过长的问题本文提出了融入双向搜索算法的混合 算法设计了融合方法制定了算法的具体计算流程 并针对双向搜索中正向搜索和反向搜索扩展节点不容易重合的问题引用栅格法优化了双向搜索算法来解决该问题 对比了传统混合 算法与融合算法的搜索时间、改变方向次数、节点数结果表明融合算法不仅比传统混合 算法的搜索时间平均缩短了.而且改变方向次数普遍比传统混合 算法少 说明融合算法最后路径执行代价更小、实时性更好更能满足车辆的运动条件本文虽然融合了双向搜索算法利用栅格法优化了双向搜索时的相遇机率但还是存在有双向搜索无法相遇的情况导致生成的路径并非最短路径这也是后续研究需要解决的问题 参 考 文 献 吴飞龙.自动泊车系统路径规划及其跟踪控制算法研究.青岛:青岛理工大学.():./().:.:.:./().:.齐尧徐友春李华等.一种基于改进混合 的智能车路径规划算法.军事交通学院学报():.田海波李陆军畅科剑等.用于无人车路径规划的改进 算法.现代制造工程():.赵明郑泽宇么庆丰等.基于改进人工势场法的移动机器人路径规划方法.计算机应用研究(增刊):.邓圣乾李宏伟赵家瑶等.面向多值栅格地图的 最优路径算法改进.测绘科学技术学报():.杨明亮李宁.改进 算法的移动机器人路径规划.机械科学与技术():.叶小艳钟华钧邓可儿.一种基于改进 算法的室内导航路径规划方法.计算机技术与发展():.王雪犇.自动驾驶车辆垂直车位自动泊车控制算法研究.长春:吉林大学.():.陈德童刘贤达刘生伟.基于双向搜索改进 算法的自动导引车路径规划.计算机应用(增刊):.付久鹏曾国辉黄勃等.基于双向快速探索随机树的狭窄通道路径规划.计算机应用():.师颖慧张冰赵强.改进型 算法的水下机器人三维全局路径规划.软件导刊():.高涛.基于 算法的无人车路径规划.江苏工程职业技术学院学报():.杜轩欧资臻.改进 和人工势场法的移动机器人路径规划研究.制造业自动化():.赵盼杜兆才刘江等.基于改进 算法的超冗余度机器人末端避障路径规划.航空制造技术():.谭波罗均罗雨松等.改进 算法的机器人路径规划/.重庆大学学报:().:/./.责任编辑:魏 强(下转第 页)第 期 刘知阳崔立堃耿玺钧等 面向自动泊车的改进混合 最优路径算法研究 ./:.?/:./:.责任编辑:谢 平 .:./.:(上接第 页):.:第 期 王丰平张云 融合 与时序 的动态手势识别