第3期 成怡，等：融合改进A*算法和Morphin算法的移动机器人动态路径规划 ·549· 设定以机器人为中心的工作区域，依靠实时 成的环境下经过A*算法和改进A*算法全局路径 的传感器每隔一段时间以3个栅格的距离对周围 规划后的结果如图4所示。 环境信息进行采集，式(4)作为判断局部路径的 20 [-车.传统A*算法 评价函数。航向对目标的偏离角由Xm进行评 18 A 价，偏离越小数值越高；机器人在当前轨迹上与 最近障碍物之间的距离由Y进行评价，预测轨 迹的终点离最近障碍物的距离越近，Yt数值越 低，如果没有障碍物则设定为一个常量；机器人 的速度变化由Zec进行控制，动态窗口中考虑 机器人的平移速度与旋转速度，对允许速度进行 限制，因为速度随着障碍物信息变化而变化。在 468101214161820 X/m 室内平坦的地面上行驶动态窗口中α、B设定为 0.2,为2.0。局部规划算法步骤如下： 图3普通地图传统A*算法与改进A*算法实验 Fig.3 Experiment of traditional A*algorithms and im- 1)机器人根据探测障碍物信息每隔一段时间 proved A*algorithms on general map 更新栅格地图信息，同时保存当前节点； 2)确定将要驶向的子目标点； 20[--传统A*算法- 18 改进A*算法 3)以机器人当前节点为起点，画出指向子目 16 4 标点的直线，在直线两侧45均匀地画出弧线，弧 12 线利用附近的栅格点或已保存的节点表示： s10 4)根据评价函数G从备选路径中选择值最小 的弧线作为最优路径，按照路径移动后执行6)： 当几条预测路径都无法避开障碍物执行5)： 机 0 2 468101214161820 5)将机器人旋转一定角度或等待一段时间进 X/m 行尝试，如果不行，停止局部路径规划：调用A* 图4随机地图传统A*与改进A*算法实验 算法重新进行全局规划，然后返回1)： Fig.4 Randomly generated map traditional A*al- 6机器人成功绕开障碍物后回到全局路径上 gorithms and improved A*algorithms experiment 继续行驶到目标点。 对比2种算法路径规划结果，即起点与终点 3仿真结果与分析 间的连线，可以看出改进A*的路径比传统A*的 路径更平滑，路径中拐点的转折角得到了优化。 为了验证本文提出的A*算法与Morphin搜索 通过图3室内地图与图4随机地图的比较可 树算法相融合的方法的有效性，进行了多组仿真 知，该算法在复杂环境中依然可以选择出最优的 实验，首先对比分析传统A*算法与改进A*算法 路径。室内固定障碍环境只有1条或2条可到达 在全局路径规划中的效果，然后引入动态障碍 目标的路径，而随机障碍物具有多条可通行路 物，采用Morphin搜索树算法进行局部路径规划， 径，可选择的路径增加，而改进A*算法仍然可以 修正全局路径。仿真实验在MATLAB R2014a实 在多条路径中选择最优路径。表1是对两组A* 验平台上进行。计算机配置CPU2.5GHz,内存 算法与改进A*分别进行10次的平均值。 4GB。在栅格地图模型20×20（网格间距1m)下 表1传统A*算法与改进A*算法比较结果 进行多组传统A*与改进A*的对比实验。障碍物 Table 1 Comparison of traditional and improved A*al- 覆盖率为30%，实验中起点坐标为(2,2)目标点坐 gorithms 标为(18,18)。改变环境信息以验证改进算法优化 算法 平均时间s平均长度m节点个数平滑处理 效果明显。 改进A*算法 19.89 37.59 36 是 3.1A*算法与改进A*算法仿真实验对比分析 传统A*算法 18.20 31.74 23 否 在地图相同的情况下，使用传统A*算法与改 优化提升 8% 15% 36% 平滑 进A*算法进行路径规划，对比2种算法的仿真结 果。在普通室内环境，经过A*算法和改进A*算 从表1中可以看出，改进A*算法路径长度缩 法全局路径规划后的结果如图3所示。在随机生 短了15%，所耗费的时间缩短了8%，节点数减少Xangle Ydist Zvelocity α、 β λ 设定以机器人为中心的工作区域，依靠实时 的传感器每隔一段时间以 3 个栅格的距离对周围 环境信息进行采集，式 (4) 作为判断局部路径的 评价函数。航向对目标的偏离角由 进行评 价，偏离越小数值越高；机器人在当前轨迹上与 最近障碍物之间的距离由 进行评价，预测轨 迹的终点离最近障碍物的距离越近，Ydist 数值越 低，如果没有障碍物则设定为一个常量；机器人 的速度变化由 进行控制，动态窗口中考虑 机器人的平移速度与旋转速度，对允许速度进行 限制，因为速度随着障碍物信息变化而变化。在 室内平坦的地面上行驶动态窗口中 设定为 0.2, 为 2.0。局部规划算法步骤如下： 1) 机器人根据探测障碍物信息每隔一段时间 更新栅格地图信息，同时保存当前节点； 2) 确定将要驶向的子目标点； 3) 以机器人当前节点为起点，画出指向子目 标点的直线，在直线两侧 45°均匀地画出弧线，弧 线利用附近的栅格点或已保存的节点表示； 4) 根据评价函数 G 从备选路径中选择值最小 的弧线作为最优路径，按照路径移动后执行 6)； 当几条预测路径都无法避开障碍物执行 5)； 5) 将机器人旋转一定角度或等待一段时间进 行尝试，如果不行，停止局部路径规划；调用 A* 算法重新进行全局规划，然后返回 1)； 6) 机器人成功绕开障碍物后回到全局路径上 继续行驶到目标点。 3 仿真结果与分析 为了验证本文提出的 A*算法与 Morphin 搜索 树算法相融合的方法的有效性，进行了多组仿真 实验，首先对比分析传统 A*算法与改进 A*算法 在全局路径规划中的效果，然后引入动态障碍 物，采用 Morphin 搜索树算法进行局部路径规划， 修正全局路径。仿真实验在 MATLAB R2014a 实 验平台上进行。计算机配置 CPU 2.5 GHz，内存 4 GB。在栅格地图模型 20×20(网格间距 1 m) 下 进行多组传统 A*与改进 A*的对比实验。障碍物 覆盖率为 30%，实验中起点坐标为 (2,2) 目标点坐 标为 (18,18)。改变环境信息以验证改进算法优化 效果明显。 3.1 A*算法与改进 A*算法仿真实验对比分析 在地图相同的情况下，使用传统 A*算法与改 进 A*算法进行路径规划，对比 2 种算法的仿真结 果。在普通室内环境，经过 A*算法和改进 A*算 法全局路径规划后的结果如图 3 所示。在随机生 成的环境下经过 A*算法和改进 A*算法全局路径 规划后的结果如图 4 所示。 0 2 4 6 8 10 12 14 16 18 20 2 4 6 8 10 12 14 16 18 20 机器人 目标 X/m Y/m 传统A*算法 改进A*算法 图 3 普通地图传统 A*算法与改进 A*算法实验 Fig. 3 Experiment of traditional A* algorithms and im￾proved A* algorithms on general map 0 2 4 6 8 10 12 14 16 18 20 2 4 6 8 10 12 14 16 18 20 机器人 目标 X/m Y/m 传统A*算法 改进A*算法 图 4 随机地图传统 A*与改进 A*算法实验 Fig. 4 Randomly generated map traditional A* al￾gorithms and improved A* algorithms experiment 对比 2 种算法路径规划结果，即起点与终点 间的连线，可以看出改进 A*的路径比传统 A*的 路径更平滑，路径中拐点的转折角得到了优化。 通过图 3 室内地图与图 4 随机地图的比较可 知，该算法在复杂环境中依然可以选择出最优的 路径。室内固定障碍环境只有 1 条或 2 条可到达 目标的路径，而随机障碍物具有多条可通行路 径，可选择的路径增加，而改进 A*算法仍然可以 在多条路径中选择最优路径。表 1 是对两组 A* 算法与改进 A*分别进行 10 次的平均值。 表 1 传统 A*算法与改进 A*算法比较结果 Table 1 Comparison of traditional and improved A* al￾gorithms 算法 平均时间/s 平均长度/m 节点个数 平滑处理 改进A*算法 19.89 37.59 36 是 传统A*算法 18.20 31.74 23 否 优化提升 8% 15% 36% 平滑 从表 1 中可以看出，改进 A*算法路径长度缩 短了 15%，所耗费的时间缩短了 8%，节点数减少 第 3 期 成怡，等：融合改进 A*算法和 Morphin 算法的移动机器人动态路径规划 ·549·