1、 年 月第 卷 第 期机床与液压 .：.本文引用格式：齐凤莲，王晓庆，张帼英改进 算法的 避障路径规划研究机床与液压，（）：，（）：收稿日期：作者简介：齐凤莲（），女，博士，副教授，主要研究方向为机电一体化技术、自动控制系统。：.。通信作者：王晓庆（），男，硕士研究生，主要研究方向为机电控制系统、路径规划及轨迹跟踪。：.。改进 算法的 避障路径规划研究齐凤莲，王晓庆，张帼英（.沈阳建筑大学机械工程学院，辽宁沈阳；.内蒙古北方重工集团防务部，内蒙古包头）摘要：针对传统 算法在复杂栅格地图规划的路径不平滑存在多余转折点和多余共线节点，使用传统八叉树搜索策略时，易发生碰撞障碍物现象，在复杂环境中随机
2、出现在全局路径上的障碍物无法实现动态避障等问题，提出一种改进 算法。由于传统 算法的搜索效率主要取决于估价函数的设计，因此引入启发式函数的权重系数提高 算法的搜索效率；设置障碍物安全距离，为判断障碍物区域内当前障碍物是否影响 通行提供参考，再次改进原有八叉树搜索策略提升避障性能，然后对得到的无碰撞路径进行路径优化处理，保留关键转折点；最后实现 和 算法融合，进一步优化路径，并实现全局动态路径规划。实验结果表明：融合算法使得路径更加平滑，提高了算法的避障性能，表明了融合算法在机器人路径规划中的可行性。关键词：避障路径规划；改进 算法；融合算法中图分类号：，（.，；.，）：，：；前言随着经济的发展
3、，国内人口红利正在逐渐消失，各大电商平台和工厂企业急切进行新旧动能转换，以自动化产品替代人工完成高难度、劳动密集型的工作，达到提高工作效率和降低成本的目的，在这一趋势下自动导引车（，）的研究将具有重要意义。实现 自主移动关键技术就是路径规划技术，其中常用路径规划算法大致分为 类：（）智能算法，如遗传算法、蚁群算法等；（）树状式搜索算法，如 算法；（）图搜索（栅格）算法，如 算法、算法、算法等。在静态栅格环境下 算法具有原理简单、搜索效率高、容易实现的优点，所以 算法在栅格环境路径规划中被广泛应用，国内学者也对传统算法做出了许多改进。文献提出了一种结合节点负载情况的改进 算法，各个节点的负载从初
4、始值开始，根据相应的动态负载计算公式，动态更新该节点的负载。在 算法的启发函数中引入负载，使节点负载影响 路径选择，避开高负载节点。文献选择不同的象限进行节点拓展，判断待扩展节点与目标点之间有无障碍物，但改进后的算法在栅格规划下路径存在转折点过多，并没有对已规划的路径进行二次优化。文献采用双向 寻路搜索，基于人工势场法引力思想，设定双向搜索中心虚拟目标点，建立从搜索起点到双向搜索的中点的距离衰减函数，吸引双向搜索在中间区域相遇，设置避障策略，但改进的 算法搜索路径曲折，路径中存在大量节点，并且路径紧贴障碍物。文献通过计算斜率消除多余共线节点，计算向量叉积消除多余转折点，减少了路径中的节点。文献
5、提出删除多余节点进行优化路径，但是并未提出具体实施方法，算法规划的路径在躲避障碍物方面存在缺陷。文献提出利用高斯核函数动态改变 算法代价函数的权重系数和多步长优化，但算法规划出的路径仍存在大量节点，没有进行一定的清除，并且实验仅在障碍物排列整齐的环境中进行，没有验证在障碍物排列凌乱的环境中算法的有效性。文献提出基于象限的节点扩展算法，改进后的算法向目标点所在的象限搜索，但搜索具有一定盲目性，一味向目标点方向搜索，如果目标点周围障碍物凌乱当前方向不能通行时，可能会出现规划失败的现象，且使用四邻域节点扩展法搜索的路径长度过长。文献提出利用计算节点间斜率消除多余转折点，减少了 的转向次数。文献和文献
6、改进算法规划的路径易与障碍物发生碰撞。综上所述，为改进传统 算法和上述学者改进算法的一些缺陷，本文作者提出相应的改进方法。传统 算法作为启发式搜索吸收了深度优先搜索和广度优先搜索的优点，利用启发函数对搜索方向进行指引，在搜索方式上与盲目式搜索有所区别，可以实现高效的路径搜索。算法的核心即为代价函数，其代价函数公式如下：（）（）（）（）式中：（）为实际代价函数，由起点至节点 的实际代价；（）为估计代价函数，由节点 至目标点的估计代价；（）为估价函数，由起点经由节点 至目标的估价值。其中（）称为启发式函数。其中，欧氏距离是上述 个启发式函数（见图）公式运算量最大的，但是求得的路径质量最好，因此文中
7、采用的启发式函数公式为欧氏距离。图 三种启发函数.改进 算法.改进估价函数为减少算法扩展节点，搜索时更具有方向性，设计启发式函数的权重系数如下：（）距离权重系数公式如下（）（）障碍物占百分比权重系数公式如下（）（）当前点至目标点的距离公式如下 （）（）当前起点至目标点的距离公式如下 （）改进后的估价函数如下（）（）（）（）（）其中：为单步移动代价；为障碍物个数；为地图大小（地图总节点个数）。.设置安全距离障碍物安全距离示意如图 所示，设安全距离为.，当前点（，），目标点（，），障碍物坐标（，）。由当前点和目标点的直线方程至障碍物点的距离为（）（）（）防止碰到障碍物的安全距离表达式为（）（）（）
8、第 期齐凤莲 等：改进 算法的 避障路径规划研究 图 障碍物安全距离.优化八叉树搜索策略首先八叉树搜索可以斜向运动，因此搜索路径存在斜穿 个对角障碍物组成的障碍物区域和斜穿障碍物顶点现象。其次十字搜索的路径虽然达到了避障效果，但是十字搜索方式不能斜向运动，因此会造成搜索的路径节点过多，这也会造成后面的路径优化困难。因此为了改善上述现象，提高寻径质量，文中将传统 的八叉树搜索策略进行改进：（）判断 个斜向节点是否是障碍物。（）如果 个斜向节点都不是障碍物，再判断 个斜向节点的临近 个节点（比如，子节点 不是障碍物时，再判断子节点 和子节点），如果临近 个节点都不是障碍物，则将当前斜向节点添加到待
9、考察集合，反之舍弃。（）当前父节点周围的 个斜向节点均是障碍物，那么仅判断当前父节点周围上、下、左、右节点。重复上述（）（）直至扩展至终点。搜索方式如图 所示。图 改进搜索策略.路径优化策略算法搜索的全局路径中存在多余共线节点和转折点。这些节点将影响规划的路径质量，因此需要进行一定的清除。（）共线节点的判断方法。在算法搜索出一条初始路径之后，根据采样的思想首先取前 个节点。设临时起点坐标为（，），临时中间点坐标为（，），临时终点坐标（，）。（）（）分别计算节点 和节点 的斜率，节点 和节点 的斜率。如果，则点 为多余共线节点，应该删除节点，此时临时中间节点切换为节点，临时终点切换为节点，见图
10、（）。（）多余转折点的判断方法。此时临时起点为节点，临时中间节点为，临时终点为。分别计算节点 和节点 的斜率，节点 和节点 的斜率，如果，则中间节点 为转折点，见图 （）。（）判断当前转折点是否为关键转折点，以及是否更新局部路径。设障碍物距离当前起点 和当前终点 的直线方程距离为，如果 （安全距离），此时转折点 是关键转折点，不更新路径，见图（），切换临时起点为节点，切换临时中间点为节点，临时终点为节点 的下一节点。如果 （安全距离），那么转折点 节点为多余转折点，更新路径，并删除该转折点，见图 （），临时起点不变仍为节点，切换临时中间节点为节点，临时终点为节点 的下一节点。（）重复上述（）（
11、）（）直至临时中间节点是终点，此时退出路径优化策略，并输出保留关键转折点的全局优化路径。图 路径优化.：（）；（）；（）；（）机床与液压第 卷 融合 实现全局动态规划经过上述第.节保留关键转折点的优化之后，虽然减少了路径的节点个数，但是路径仍然不平滑，对于突如其来的障碍物不能及时做出避障，规划的路径对于机器人不适用。（动态窗口法）原理可简述为：依托车载传感器采样多组速度，模拟出速度对应的轨迹，对其进行评分，选出评分最高的轨迹对应的速度，驱动机器人运动。.机器人的运动学模型建立在动态窗口法中要模拟移动机器人的轨迹，需要知道运动学模型。当前采用的是两轮差速移动机器人的运动模型。假设、是移动机器人在
12、 时刻的线速度和角速度。在采样时刻，因为位移小，所以假设移动机器人的轨迹是一段直线。运动学模型如下所示：|（）.机器人的动态速度窗口范围确定由于动态窗口法是将位置控制转化为速度控制，并且传感器采样的速度（，）有无穷多组，因此根据机器人本身的限制和环境限制，可以将采样的速度控制在一个窗口范围内。（）机器人受自身最大速度最小速度限制：，（）（）机器人受电机性能的影响机器人的速度应控制在最大的加减速范围之内。（，），（）式中：、分别为当前速度和角速度；、分别为机器人的最大减速度和最大加速度；、分别为机器人的最大角减速度和最大角加速度。（）机器人安全距离约束（，）（，）（，）（）式中：（，）表示以当前
13、速度对模拟轨迹末端距离最近障碍物的距离。（）结合上面 种速度约束可以得到机器人速度动态窗口的范围：（）.评价函数通过评价函数对采样的每个速度对进行评价，从中选出评分最高的速度对应的轨迹，保证动态窗口法动态规划的路径靠近 规划的全局静态路径。其评价函数表达式为（，）（，）（，）（，）（）式中：（，）为方向角评价函数；（，）为安全距离评价函数；（，）为速度评价函数；、分别对应上述 个评价函数的权重系数。实验仿真.改进算法仿真实验仿真实验在 环境下进行，为验证算法的有效性以及适应性，采用障碍物摆放较多且摆放凌乱的栅格场景地图。在栅格地图中，表示机器人初始位置，表示目标点。传统 算法与改进 算法的仿真
14、结果如图 所示，性能比较如表 所示。图 传统 与改进.：（）；（）；（）表 传统 与改进 性能对比.算法路径规划长度 路径节点个数 个路径碰撞次数 次转折次数 次传统 改进八叉树搜索策略路径优化策略 由图 和表 可知：传统 搜索路径出现碰撞第 期齐凤莲 等：改进 算法的 避障路径规划研究 障碍物现象，而改进后的 避免了上述缺点，并且经过 次优化后，在保证不与障碍物发生碰撞的前提下，可以求得最优路径，同时也是最短路径。.融合算法仿真实验融合算法的仿真实验是在改进 算法的实验环境下添加 个随机静态障碍物和一个随机动态障碍物。融合算法评价函数的各项权重系数为：.，.，.，障碍物碰撞半径.。融合算法仿
15、真实验结果如图 所示。可知：搜索的路径相比于改进 搜索的路径更加平滑，其路径更加适用于 使用，并且对于动态障碍物和未知静态障碍物都有很好的避障效果，实现了全局动态路径规划。图 融合算法路径规划.：（）；（）；（）；（）总结由于传统 算法规划的路径存在多余节点和多余转折点，使得路径曲折不平滑，以及容易发生碰撞障碍物现象等缺点，不满足机器人实际需求。文中引入距离权重系数到传统 算法的评价函数中，优化八叉树搜索策略，使得路径的搜索随着当前起点距离目标点的距离和环境复杂度的变化实现自适应调整。基于采样点计算节点间斜率的思想设计路径平滑算法，删除多余节点，保留关键转折点，使得路径减少转折，平滑了路径。通
16、过保留改进 算法的关键转折点作为 算法的临时目标点，以改进 算法规划的全局路径作为 算法的参考路径进行动态规划，实现了算法的融合。实验结果表明：融合算法使得路径更加平滑，提高了算法的避障性能，表明了融合算法在机器人路径规划中的可行性。参考文献：张红梅，李明龙，杨乐基于改进 算法的移动机器人安全路径规划计算机仿真，（）：，（）：赵晓，王铮，黄程侃，等基于改进 算法的移动机器人路径规划机器人，（）：，（）：陈若男，文聪聪，彭玲，等改进 算法在机器人室内路径规划中的应用计算机应用，（）：机床与液压第 卷 ，（）：陆皖麟，雷景森，邵炎基于改进 算法的移动机器人路径规划兵器装备工程学报，（）：，（）：吴鹏，桑成军，陆忠华，等基于改进 算法的移动机器人路径规划研究计算机工程与应用，（）：，（）：陈荣军，谢永平，于永兴，等基于改进 算法的无人配送车避障最优路径规划广东技术师范大学学报，（）：，（）：刘子豪，赵津，刘畅，等基于改进 算法室内移动机器人路径规划计算机工程与应用，（）：，（）：杨瑶，付克昌，蒋涛，等一种改进 算法在智能车中的应用研究重庆理工大学学报（自然科学），（）：，（），（）：王保剑，