1、书书书北大中文核心期刊国外电子测量技术 ：基于改进 和 的移动机器人路径规划林俊志，席万强，周俊林思伟，李鹏，（南京信息工程大学 南京 ；南京信息工程大学南通研究院 南通 ；无锡学院 无锡 ）摘要：针对移动机器人路径规划人工势场法（，）的局部最小值和目标不可达问题，提出了概率路线图法（，）与人工势场法相结合的路径规划算法。首先，对全局路径规划 进行改进，引入椭圆约束，减少了冗余节点，提高了规划效率。其次，将 规划的路径节点作为人工势场法的虚拟目标点，利用改进的 法进行节点跟踪，解决了 法局部最小值问题；通过对 法的引力函数进行分段处理，对斥力函数加入移动机器人与目标点的相对距离因子来解决目标不
2、可达问题。最后，对改进的算法进行仿真，仿真结果表明，该算法不仅能有效解决传统 法的目标不可达和局部最小值问题，并且较未改进的融合算法时间和节点数量上分别减少了 、，路径长度也减少了 。关键词：路径规划；人工势场法；概率路线图法中图分类号：文献标识码：国家标准学科分类代码：，（，；，；，）：，：；收稿日期：基金项目：国家自然科学基金（）项目资助引言近年来，随着科技的发展，移动机器人已广泛应用于工业、医疗、农业等相关领域。路径规划是移动机器人进行自主导航与探索任务的前提，基于一些如路径短、高效率、无碰撞等指标，旨在找出一条从起始位置到目标位置的最优路径或次优路径，且该路径能够规避沿途的障碍物。常用
3、的移动机器人路径规划算法有 算法、概国外电子测量技术北大中文核心期刊率路线图法（，）、快速探索随机树（）算法、人工势场法（，）、蚁群算法，每种算法都有其优劣之处。法因其原理简单、实时性高、易与其他算法结合，在移动机器人避障路径规划领域得到了广泛应用。然而，法存在目标不可达和局部最小值问题。针对这些问题，文献 对“凹型障碍物”进行补齐操作，防止 法陷入局部最小值陷阱。文献 引入模拟等势线的概念，对 法斥力函数进行改进，解决了无人机逃离局部最小值的问题。文献 结合 法与带目标偏置的 算法，当 法规划陷入局部最小值陷阱时，切换带目标偏置的 算法进行规划，直至跳出局部最小值陷阱。文献 在通过将 与引入
4、“随机可达集”的人工势场法相结合，降低机器人轨迹规划时间，并提高机器人的避障成功率。上述方案中，虽能很好解决 法固有缺陷，但是在规划过程中未考虑与其融合的算法自身的局限性，例如 算法自身拓展速度慢、冗余节点多等缺陷。本文提出概率路线图法与人工势场法相结合的路径规划算法。首先对 的随机点进行椭圆约束，提出了改进的概率路线图法（，）。应用该算法规划的节点作为 法的虚拟目标点，以解决 法的局部最小值问题。其次提出改进人工势场 法（，），对 法引力函数进行分段处理、对斥力函数加入移动机器人与目标点的相对距离因子来解决目标不可达问题。改进后的算法有效解决目标不可达和局部最小值问题，提高了路径规划效率。最
5、后通过 仿真实验比较改进前后规划效果。结果证明，本文算法有效解决 法的固有缺陷。法 传统人工势场法 法是将移动机器人在规划空间中的运动看作一种虚拟力场中的受力运动，在障碍物周围构建斥力场，在目标附近构建引力场，斥力场叠加引力场形成复合场。在复合场中，移动机器人受目标引力和障碍物斥力所形成的合力作用下，从高势能向低势能处移动探索出一条无碰撞路径。（）（，）（）（）（，）（）（，）（，），（，），（，）（）（）（）（）（）式（）为目标引力，式（）为障碍物斥力，式（）为两者合力，其合力驱使着移动机器人朝目标点移动，如图所示。在障碍物斥力范围之外，移动机器人的驱动力仅有目标引力 ；当进入障碍物斥力范围
6、时，移动机器人受障碍物斥 力 和目 标 引力 共 同 作用，朝合 力 方 向移动。图移动机器人受力图 人工势场法的不足）局部最小值问题在移动机器人向目标移动的过程中，在某一时刻，障碍物的斥力与目标引力恰好大小相等、方向相反。此时，驱动机器人移动的合力变为，机器人无法继续移动，其受力情况如图（）、（）所示。图 算法固有缺陷）目标不可达问题由式（）、（）可知，当移动机器人离目标越近，目标对移动机器人的引力越小，而移动机器人离障碍物越近，障碍物对移动机器人产生的斥力越大。如图（）所示，当目标位置附近存在障碍物时，移动机器人受障碍物斥力的影响，此时引力不足或斥力过大均会导致机器人无法继续朝目标点移动。
7、改进人工势场法对于由引力不足引起的目标不可达问题，本文对引力势场函数进行改进，通过分段处理，将陷入目标不可达时北大中文核心期刊国外电子测量技术的移动机器人与目标之间的欧氏距离，作为调整强引力范围大小。其公式为：（），（），（），（），（），（）（）对式（）求负梯度，得引力函数：（），（），（），（），（）（）式中：、均为引力系数；，（）为一个距离矢量，其方向由移动机器人指向目标点。通过设置式（）中值大小，确保势能始终由起始点朝目标点减少。当移动机器人陷入目标不可达陷阱时，将移动机器人与目标间的欧氏距离作为强引力范围的值，并以目标为中心，在为半径的影响范围之外，移动机器人受全局引力作用朝目标点移
8、动；在为半径的影响范围之内时，移动机器人将在强于全局引力的作用力下向目标移动。当移动机器人面临目标不可达问题，并且大于初始值时，使强引力范围大小的值等于移动机器人与目标点的欧氏距离，以此增强移动机器人在近目标点处的引力。对于图（）这种情形，本文在斥力势场函数中引入移动机器人与目标之间的距离因子，障碍物斥力随着移动机器人与目标点的欧氏距离减小而减小，在一定程度上减小了目标附近障碍物的斥力作用。改进斥力势场函数及斥力函数如下：（），（）（），（），（），（）（）对式（）求负梯度，得斥力函数：（）（）（），（），（）（）（），（）（），（），（）（）（），（）（），（）（）式中：为正比例增益系数；，
9、（）为一个距离矢量，其方向由障碍物指向移动机器人；为障碍物对移动机器人产生作用的最大距离；为大于的斥力场系数常数。的方向由移动机器人指向目标，的方向由障碍物指向移动机器人。此时移动机器人受力情况如图所示。改进算法与传统算法相比较，如图（）和（）所示，改图改进方法受力情况图 法与 法比较进的方法能够合理解决 法目标不可达问题。算法刘玉等 将 算法规划的静态轨迹作为 法的引导轨迹，从而避免 法陷入局部最小值陷阱中。但从 算法的工作原理可知，在 算法规划的两个阶段中，最为影响算法效率的是查询阶段，若仅以最优路径作为指标，该方法在学习阶段中尽可能多地将可行采样点布满整个约束空间，即落在自由空间而不在障
10、碍物上的采样点，尔后将可行采样点归入集；通过将可行采样点进行连线，舍弃穿越障碍物的连线，从而作出网络路径，如图（）、（）所示。图 算法过程在查询阶段中，将可行采样点与其可行路径下的相邻点归入集中。依据算法的代价函数如式（）所示，对每个可行采样点进行路径评估，得出最优路径。（）（）（）（）式中：（）代表起始点到当前点所需路径代价；（）为估计代价，代表当前点与目标点之间的欧氏距离；（）代表路径总代价。当（）最小时，说明当前的采样点为最优国外电子测量技术北大中文核心期刊路径节点，并将该节点作为当前节点，继续评估周围相邻节点，直到找到目标点，图（）红线即为最优路径。对大量的冗余节点进行路径查询得出最优
11、路径，无疑降低了路径规划的效率。因此本文针对 算法冗余节点的问题，提出赋予随机采样点一个椭圆约束，减少冗余节点，提高路径规划的效率。椭圆约束以起始点（，）与目标点（，）为焦点，两点的中点为椭圆原点（，），约束方程如下：（）（）（）其中，为椭圆长轴系数，为椭圆短轴系数，椭圆约束示意图如图所示。通过赋予椭圆约束短轴系数初值，在路径无解时，逐次递增该系数直至找到可行路径。图椭圆约束示意图增加椭圆约束后，在相同采样点数量的前提下，算法规划时间从 下降到 ，改进前后规划路径如图所示。图改进 算法对比融合算法针对 法固有缺陷，本文提出 与 法相结合，首先通过 随机采样点，舍弃不符约束的点，进而对随机点进行
12、连线，并且舍弃穿越障碍物的线，其次通过 算法对采样点进行路径搜索，若搜索失败逐次增大椭圆约束短轴系数与采样点数量，直至找到可行路径。最后通过 法对 的路径节点依次进行路径追踪，当遍历完虚拟目标点而遇到目标不可达问题时调整值，使移动机器人进入强引力范围，继续进行人工势场路径规划。具体流程如图所示。图融合算法流程仿真结果与分析本文基于 环境编写仿真实验程序验证算法有效性；分别对 、算法进行仿真实验对比。相关仿真参数设定如下：设定地图范围为 ，起始点坐标为（，），目标点坐标为（，），分别 为 下 图 绿 点 与 蓝 粗 点。随 机 撒 点 数 量 为 个，随 机 撒 点 数 量 为 个，引 力 增
13、益 系 数 ，系数 ，斥力增益系数 ，椭圆约束短轴初始系数为，初始值为，种不同算法的仿真结果对比如图所示。由图（）看出，法因缺少全局环境信息导致移动机器人陷入局部最小值陷阱，因此将 算法规划的节点作为 法的临时目标点，如图（）所示。虽因 算法的引入，规避了局部最小值陷阱，但是却未能解决目标不可达问题。因此，进一步对 法势场函数进行改进，如 图（）所 示，法 能 够 合 理 解 决 法的固有缺陷。但由于 算法采样点的随机性，导致 算法在规划时出现大量的冗余节点，而这些节点大大增加了算法的计算量。鉴于此，图（）中，法提出对 算法采样点增加椭圆约束，可以看出 法规划路径不仅能够解决 法的固有缺陷，也
14、减少了大量的冗余节点。所生成路径较 算法也更为平滑。种算法在种地图环境下连续运行 次后得到平北大中文核心期刊国外电子测量技术图不同算法路径规划效果均仿真数据如图 所示，种地图环境的复杂程度依次递增，规划结果均为 法所规划。其中图（）为简单的避障环境；图（）和（）分别增加了局部最小值和目标不可达问题两种情况，图（）环境中既有局图 种地图环境部最小值陷阱，又有目标不可达情况。仿真实验数据如表所示，从表可以看出，在简单避障环境下，种算法均能规划出路径，但从时间和空间维度上考虑，本文提出的 算法更具优势。表中，未能规划出路径。表中，未能规划出路径，究其原因是仅对 法进行单一的改进不足以弥补 法的固有缺
15、陷，而在其余种算法中，本文提出算法更优。表表明，在复杂环境下，仅有 与 法能够顺利规划路径，并且本文提出的改进算法较 法，在规划时间和节点数量上分别减少了 和，且路径长度也减少了 。表种算法在地图下运行平均结果算法运行时间路径长度节点数量 表种算法在地图下运行平均结果算法运行时间路径长度节点数量 表种算法在地图下运行平均结果算法运行时间路径长度节点数量 表种算法在地图下运行平均结果算法运行时间路径长度节点数量 综上所述，法和 法无法在复杂环境下规划路径，而 虽能够顺利规划路径，但其路径规划时间及路径长度依旧不尽人意，本文提出 算法路径规划长度最短，运行时间最少，可靠性也是种算最好的。结论为了解
16、决 法固有缺陷 局部最小值和目标不可达问题，本文对 法进行改进，提出了 法，解决了目标不可达问题。进一步将该算法与 相结合，得到了 法。但其效率仍有待改善，因此提出 法。该算法避免了 规划时出现的大量冗余节点，提高了路径规划效率，并且为 法提供了全局环境信息解决了局部最小值问题。本文在 法的基础上，对引力函数提出分段处理，解决引力不足的问题；针对 法局部最小值问题，提出 法与 算法相结合，使得算法高效且最优；考虑 算法大量冗余节点的问题，提出了椭圆约束，减少了冗余节点，提高了算法效率。国外电子测量技术北大中文核心期刊参 考 文 献 ，：，（）：，（）：，姜媛媛，张阳阳改进邻域节点搜索策略算法的路径规划电 子 测 量 与 仪 器 学 报，（）：周相坡，周依尔，徐立军，等一种基于概率路线图的月球巡航车路径规划算法空间控制技术与应用，（）：，林依凡，陈彦杰，何炳蔚，等无碰撞检测 的移动机器 人 运 动 规 划 方 法 仪 器 仪 表 学 报，（）：程志，张志安，李金芝，等改进人工势场法的移动机器人路径规划计算机工程与应用，（）：王刚，张方，严大亮，等 基于改进蚁群算法的机器人三维路径规划 国
