基于动态五邻域搜索的改进Astar算法路径规划研究.pdf

中国新技术新产品2024 NO.4（上）-1-高 新 技 术路径规划是解决移动机器人导航问题的关键技术之一。现阶段路径规划方法主要分为 2 类，一类是以 A*算法（Astar）1为主的静态全局路径规划算法2，另一类是以动态窗口算法（Dynamic Window Approach）3为主的动态局部路径规划算法4。Astar 算法能在提升搜索效率的同时能兼顾寻找较优路线，已经成为机器人应用中最普遍的全局路径规划算法5。但是 Astar 算法也有局限性，例如当面对复杂场景时，由于障碍物增多，因此 Astar 算法会搜索大量非必要节点，导致搜索效率降低。针对传统 Astar 算法存在的缺陷，国内学者进行了广泛研究，远子涵等6提出一种 12 方向二十四邻域搜索方式的改进 Astar 方法，该方法减少了搜索路径的拓展节点，节约了搜索时间，但是其规划路径并非最优路径；孔继利等7在传统 Astar 算法中引入双向搜索机制，减少了对拓展节点的搜索，但是未解决规划路径节点冗余、计算时间过长等问题。针对上述问题，笔者提出一种基于动态五邻域搜索的改进 Astar 算法。该方法通过在启发函数中融入混合距离度量和动态加权机制提高了节点的搜索效率，解决了在搜索过程中内存消耗的问题，并对最终路径进行平滑处理，使机器人行驶轨迹更平滑。1 传统 Astar 算法1.1 Astar 算法原理Astar 算法利用启发式函数来估计从当前节点到目标节点的代价，从而引导搜索方向，减少搜索空间，提高搜索效率8。Astar算法结合了最佳优先搜索和Dijkstra算法的特点，当寻找起始节点至目标节点的路径时，效率很高，应用价值广泛。用 Astar 算法的节点定义评估函数 f（n），如公式（1）所示。f(n)=g(n)+h(n)（1）式中：g（n）为从起始节点到当前节点的实际距离；h（n）为当前节点到目标节点的启发式估计距离9。Astar 算法的关键是设计启发式函数 h（n）。在理想情况下，h（n）应该精确反映从节点 n 到目标的成本。然而，在实际应用中，Astar 算法通常使用欧式距离、曼哈顿距离和切比雪夫距离来近似表示 h（n）。1.2 Astar 算法与 WAstar 算法比较Astar 算法基于启发式搜索的思想，估计从起始状态到目标状态的代价，并结合搜索路径中已知的信息来指导搜索过程，以找到最优路径或者满足特定条件的路径。传统 Astar算法路径规划效果如图 1 所示。WAstar 算法是在 Astar 算法的基础上添加启发函数的权重因子，以路径最优性换取搜索速度，WAstar 算法路径规划效果如图 2 所示。在图 1 和图 2 中，深色圆点为起点，深色叉号为终点，基于动态五邻域搜索的改进Astar算法路径规划研究王洋（黑龙江科技大学电子与信息工程学院，黑龙江 哈尔滨 150022）摘 要：针对传统 Astar 算法在复杂场景下的路径规划任务中存在路径搜索效率低、路径转折次数多等问题，本文提出一种基于动态五邻域搜索的改进 Astar 算法。通过改进算法的启发函数，将曼哈顿距离与欧式距离融合得到的距离度量代替传统 Astar 算法的单一距离度量，引入动态加权机制，并将传统的固定八邻域搜索策略改进为动态五邻域搜索策略。通过剔除最终路径的冗余节点并进行贝塞尔曲线平滑处理，使最终路径更平滑。试验表明，与传统 Astar 算法相比，采用本文算法的路径搜索时间减少了约69%，路径拓展节点数减少了约66.35%，路径包括节点数减少了约38.8%，路径寻优能力较好。关键词：Astar；路径规划；贝塞尔平滑曲线；混合加权；邻域搜索中图分类号：TP393文献标志码：A图 2 WAstar 算法路径规划效果图 1 传统 Astar 算法路径规划效果中国新技术新产品2024 NO.4（上）-2-高 新 技 术浅色叉号为搜索节点。从图 2 可以看出，与传统 Astar 算法相比，WAstar 算法的搜索节点数量明显减少，搜索速度更快，但是规划的路径并不是最佳路径。2 改进 Astar 算法2.1 混合动态加权Astar 算法的效率和准确性深受其启发式函数 h（n）的影响。尽管 WAstar 算法对 h（n）进行了加权处理，与传统的Astar 算法相比，搜索效率有了很大程度提升，但是 WAstar算法存在一定缺陷，例如无法根据当前结点位置动态选择合适的权重，在 WAstar 算法中的单一距离度量有一定局限性。基于上述问题，本文在改进的 Astar 算法的启发函数中，引入动态加权机制，如公式（2）所示。f(n)=(1-)g(n)+h(n)（2）式中：为动态加权因子，随当前点的变化而改变，如公式（3）所示。?111h nLstartgoal_（3）式中：Lstart_goal为起始点到目标节点的欧氏距离；h1（n）为当前点到目标点的欧式距离。该方法使启发函数能够根据实际搜索情况动态调整权重。这种动态加权策略可以更好地平衡搜索的广度和深度，从而提高搜索效率。针对传统Astar 算法中单一距离度量的局限性，笔者融合曼哈顿距离与欧式距离，作为新的启发函数距离度量 hEM（n），如公式（4）所示。hnh nhnhnEM?1231?（4）式中：h2（n）为当前点到目标点的曼哈顿距离；h3（n）为起始点到目标点的曼哈顿距离；为可变倍数。曼哈顿距离和欧式距离各有特点，曼哈顿距离更适合网格状地图的路径搜索，欧式距离更适合连续空间的路径规划。融合这 2 种距离度量方式，新的启发函数能够更全面地考虑路径的特性和环境的几何信息，生成更优质的路径。改进后的 Astar 算法评估函数如公式（5）所示。f(n)=(1-)g(n)+hEM(n)（5）2.2 动态五邻域搜索在 Astar 算法中，传统的八邻域搜索是在二维平面上的节点周围考虑 8 个可能的移动方向。如果缩小这个范围，只考虑以目标点为导向的 5 个方向（如图 3 所示），则可以进一步减轻算法运算负担，从而提高 Astar 算法的整体运行效率。仅考虑以目标点为导向进行单一五邻域搜索，当 5 个邻域方向均存在障碍物时，Astar 算法会在该区域陷入死锁状态，无法有效规划路径。为避免发生以上情况，引入动态五邻域搜索理念，在搜索过程中，实时判断当前节点与目标点之间的相对位置关系，方向搜索规则见表 1。再根据表 1 进行动态调整，避免 Astar 算法陷入死锁状态，更集中地搜索可能包括最优路径的节点，从而提高搜索效率。表 1 方向搜索规则当前点与目标节点相对位置保留搜索方向舍弃搜索方向第一象限O2，O3，O4，O5，O6O1，O7，O8第二象限O4，O5，O6，O7，O8O1，O2，O3第三象限O6，O7，O8，O1，O2O3，O4，O5第四象限O8，O1，O2，O3，O4O5，O6，O72.3 路径平滑处理传统的 Astar 算法规划的最终路径存在节点冗余、转折点过多等问题，导致移动机器人当沿该路径导航时需要频繁转弯。因此，本文从最终路径起始点开始删除当前节点与前一节点同向运动的节点，进而去除冗余节点。分段处理最终路径，每 4 个节点 1 组进行三阶贝塞尔曲线平滑处理，处理规则见表 2。如果节点数 4 个，则根据表 2 进行贝塞尔曲线平滑处理，从而提高规划路径的可行性。表 2 分段贝塞尔曲线平滑处理规则分段节点数贝塞尔曲线策略4三阶贝塞尔曲线3二阶贝塞尔曲线3一阶贝塞尔曲线三阶贝尔塞尔曲线原理如图 4 所示，选取平面内任意 4个节点 P1、P2、P3和 P4作为控制点，在线段 P1、P2上选取点 A，在线段 P2、P3上选取点 B，在线段 P3、P4上选取点C，如公式（6）所示。注：图中18为8个不同方向。图 3 改进五邻域搜索12348765O注：P1、P2、P3和P4为控制点；A、B、C、D、E和F为平面上的点。图 4 三阶贝塞尔曲线原理示意图P1P2P4P3AFDBEC中国新技术新产品2024 NO.4（上）-3-高 新 技 术PAAPP BBPPCCP122334=（6）连接线段 AB 与线段 BC，在线段 AB 上选取点 D，在线段 BC 上选取点 E，如公式（7）所示。ADDBBEECPAAPP BBPPCCP=122334 （7）连接 DE，在 DE 上选取点 F，如公式（8）所示。DFFEADDBBEEC=（8）将所有满足上述条件的点 F 相连接，生成的线段就是三阶贝塞尔曲线平滑处理后产生的路径。3 仿真验证及结果为了提高 Astar 算法的有效性，本文基于 PC 实验平台、Intel Core i7-7500U CPU、GPU NVIDIA GeForce 940MX 和 12 RAM，分别对传统 Astar 算法、混合动态加权后的 Astar 算法和基于动态五邻域搜索的改进 Astar 算法进行 2 组不同地图下的仿真试验，以避免由于改进后的算法更适用于某单一场景，因此导致试验结果出现偶然性的情况。2 组不同地图的路径规划效果如图 5、图 6 所示。同时对比 3 种算法在 2组不同场景的路径长度、搜索时间、路径拓展节点数和路径 包括节点数，对比结果见表 3、表 4。表 3 不同场景的路径长度与搜索时间数据对比Astar算法路径长度/m搜索时间/s地图一地图二地图一地图二传统Astar124.36109.884.865.50混合动态加权127.88117.882.103.78动态五邻域搜索122.14112.391.501.69由表 3 可知，使用混合动态加权改进传统 Astar 算法的启发函数后，与传统 Astar 算法相比，混合动态加权算法的搜索时间平均缩短了 44%，在混合动态加权的基础上引入动态五邻域搜索的改进 Astar 算法，与传统 Astar 算法相比，搜索时间平均缩短了约 69%。在路径长度方面，当面对场景较为简单的地图时，基于动态五邻域搜索的改进 Astar 算法路径长度优于传统 Astar 算法。表 4 不同场景的路径拓展节点数与路径包括节点数数据对比Astar算法路径拓展节点数/个路径包括节点数/个地图一地图二地图一地图二传统Astar5056205246混合动态加权2384245550动态五邻域搜索1642163228由表 4 可知，使用混合动态加权改进传统 Astar 算法的启发函数后，与传统 Astar 算法相比，其搜索效率有显著提升，路径拓展节点数平均减少了 42.24%。在混合动态加权的基础上引入动态五邻域搜索的改进 Astar 算法进一步提升了图 5 第一组地图的路径规划效果对比（a）传统 Astar 算法（b）混合动态加权改进后的 Astar 算法（c）动态五邻域搜索改进后的 Astar 算法图 6 第二组地图的路径规划效果对比（a）传统 Astar 算法（b）混合动态加权改进后的 Astar 算法（c）动态五邻域搜索改进后的 Astar 算法中国新技术新产品2024 NO.4（上）-4-高 新 技 术加固液晶显示模块广泛应用于机载显示领域1，模块的基本功能是与夜视成像系统（Night Vision Imaging System，NVIS）兼容的飞机内部照明设计。模块的夜视兼容设计方法主要有 2 种，一种是在源头控制，采用符合光谱设计要求的背光源，规避影响夜视兼容的光谱波段2；另一种是在常规LED 白光背光源的基础上，利用滤光片截止夜视兼容影响较大的波段光谱能量，设计夜视兼容3。本文研究了在原有单白光 LED 设计的产品的基础上增加截止滤光片的方案，改进液晶显示模块夜视兼容。1 夜视兼容改进设计原液晶显示模块采用常见的底背光设计，产品的光路设计由前到后。1）显示组件。由 3 个部分构成，前端为减反射功能玻璃，主要用于降低产品反射以及提升整机强度；中间为液晶屏，用于接收视频信号，显示画面；后端为加热功能玻璃，其作用是低温加热。2）光学膜组件。其包括扩散膜和增亮膜，其主要作用是亮度增益以及匀光。3）背光组件。其包括白光 LED 和 PCB 灯板，为产品提供背光源。中小尺寸的液晶显示模块多为黑底白字、黑底绿字的单色显示模式，结合夜视兼容标准中关于单色、彩色显示的相关要求，兼顾产品夜视 A 类、B 类设计需求，在前期产品的基础上，增加昼夜 2 种显示模式，分别采用不同的电流控制背光，满足 2 个模式的调光要求。按照光路分析，在显示组件与背光组件之间增加截止滤光片，对背光中波长为 570 nm100 0 nm 的光线进行截止。基于液晶显示模块的内部结构设计，本文设计了 2 种增加截止滤光片的夜视兼容改进方案，方案一是在显示组件与光学膜组件之间添加截止滤光片一，安装在光学膜的上表面；方案二是在光学膜组件的前后端添加截止滤光片一和截止滤光片二，安装在光学膜组件的前后面，如图 1 所示。基于截止滤光片的液晶显示模块夜视兼容改进卢业能（中航华东光电有限公司，安徽 芜湖 241000）摘 要：本文研究采用截止滤光片在原有单白光 LED 设计的产品的基础上兼容改进液晶显示模块夜视的方法。通过分析液晶显示模块结构以及改进夜视兼容的需求，采用截止滤光片的夜视兼容改进方案，设计了相应的单片和2片截止滤光片的验证试验。结果表明，采用增加单片截止滤光片的方案，在降低亮度以及红色显示能力后，可满足彩色显示的 A 类、B 类的辐亮度要求，关键显示画面白场和绿场可满足单色显示的 B 类的辐亮度要求，接近 A 类的辐亮度要求，夜视兼容性能显著提升。关键词：机载显示系统；显示模块；截止滤光片；夜视兼容中图分类号：TN141文献标志码：A算法的搜索效率，与传统 Astar 算法相比，路径拓展节点数平均减少了约66.35%。经过冗余节点剔除处理与贝塞尔平滑处理后，规划路径转折点更少，平滑度更高，与传统 Astar算法相比，路径包括节点数减少了 38.8%。4 结论为提高 Astar 算法的搜索效率，本文提出在传统 Astar 算法的基础上优化其启发函数，设置动态权重因子，并将欧氏距离启发函数替换为融合曼哈顿距离与欧氏距离优势的混合启发函数 hEM（n），缩短了寻优时间，提高了搜索效率。将传统 Astar 算法中八邻域搜索改为动态五邻域搜索，算法目标导向性增强，也避免了在定向五邻域搜索中出现在复杂情况下找不到最优路径的问题。针对传统 Astar 算法规划的路径节点冗余、转折点过多和平滑度差等现象，对改进后的 Astar 算法进行三阶贝塞尔曲线平滑处理，并剔除最终路径冗余节点，减少了转折点个数，提高了路径质量。参考文献1DECHTER R，PEARL J.Generalized best-first search strategies and the optimality of A*J.Journal of the ACM，1985，32（3）：505-536.2ZAID T，QURESHI A H，YASAR A，et al.Potentially guided bidirectionalized RRT*for fast optimal path planning in cluttered environmentsJ.Robotics and Autonomous Systems，2018（108）：13-27.3 朱茂飞，胡方亚，李娜可，等.无人驾驶汽车路径规划算法综述 J.农业装备与车辆工程，2023，61（11）：18-22.4 李晓旭，马兴录，王先鹏.移动机器人路径规划算法综述 J.计算机测量与控制，2022，30（7）：9-19.5 李晨辉，王泽峰，胡德燕，等.移动机器人的路径规划技术研究 J.机电工程技术，2023，52（1）：5-9.6 远子涵，张皓，左晋，等.基于12方向24邻域的 A*算法路径规划研究 J.北京印刷学院学报，2023，31（9）：38-43.7 孔继利，张鹏坤，刘晓平.双向搜索机制的改进 A*算法研究 J.计算机工程与应用，2021，57（8）：231-237.8 刘梦杰，朱希安，王占刚，等.基于双向 A*算法的矿井水灾逃生路径应用研究 J.煤炭工程，2019，51（9）：42-47.9 胡杰，朱琪，陈锐鹏，等.引入必经点约束的智能汽车全局路径规划 J.汽车工程，2023，45（3）：350-360.