第3期 成怡，等：融合改进A*算法和Morphin算法的移动机器人动态路径规划 ·547· 照一定的评价标准，找到一条适当的从起点到终 同一直线上，则将当前节点保存到P中。然后对 点的路径，机器人在运动的过程中避开所有障 规划的路径平滑处理6，文献[16]中面对传统 碍。移动机器人路径规划大致分两种，分别是全 A*算法生成的路径转折角大且移动机器人转向 局路径规划方法2)和局部路径规划方法。目 困难等问题采用了创建函数判断连接点是否存在 前国内外路径规划算法主要采取的方法有：传统 障碍物，若无障碍物删除连线中间节点。而本文 方法，如A*算法、人工势场法、Bidirectional 利用移动平均滤波的方法进行路径平滑处理，实 RRT算法等6，智能算法，如神经网络算法、粒 现简单，效果同样明显。根据数据统计方法，将 子群算法和模糊控制算法等。这些算法各有优缺 连续的采样数据作为一个固定长度为N的队列， 点，例如：人工势场法实现简单，但容易陷入局部 在新的一次测量后，去掉上述队列中首数据，剩 最小值；Bidirectional RRT算法能够有效地解决高 余的N-1个数据依次前移，并将新的采样数据插 维空间和复杂约束问题，但路径由随机采样点搜 入新队列的队尾：最后对新队列进行算术运算· 索一次生成，缺乏可重复性，导致路径不是最优： 并将其结果作本次测量的结果。平滑处理之后寻 粒子群算法1©具有收敛速度快、设置参数少的特 迹时间与路径长度都会减少。改进A*算法的具 点，但寻优效率能力差；模糊控制算法山不需要 体步骤如下： 精确的数学模型，鲁棒性强，但是控制系统精度 1)初始化地图信息包括起点、目标点、障碍 降低，动态品质变差，缺乏系统性。国内外学者 物信息等： 针对每种算法存在的不足提出了很多方法：文献[8] 2)创建Open列表与Closed列表，将起点的 提出了基于双向势函数的抽样路径规划算法，通 节点信息放入Open列表中； 过启发式函数证明收敛得到路径最优解，文献[10] 3)如果Open列表中为空，表示没有找到路 提出一种与Morphin算法混合路径规划，同时改 径，退出： 进QPSO自适应局部搜索的策略，引入交叉操作， 4)寻找起点周围可以到达的方格（周围8个 提高性能避免局部最优。其中Morphin搜索树☒ 方格)，并把起点设置为这些方格的“父节点”，然 算法计算量小、实用性好，适合处理具有动态障 后把周围节点加入到“Open列表中”，根据列表中 碍物的路径规划问题。文献[13]中使用双层栅格 节点f(估计函数)的值进行从小到大排序： 地图方法对A*算法进行优化，高层A*算法决定 5)从Open列表中找到最佳节点，作为新 下一块大栅格局部地图，低层A*算法对合并的局 的“父节点”，并将上一个父节点移到Closed列 部地图进行路径规划。A*算法是一种搜索速度 表中： 快，使用广泛的路径规划算法。针对传统A*算法 6)在Closed列表中选取扩展节点，将扩展节 节点多，转折角大且无法动态避障等问题，本文 点的周围节点加入Open列表中。判断当前父节 提出一种融合改进A*算法与Morphin算法的结 点是否为目标点，如果是，则通过当前父节点向 合算法。该算法主要利用改进A*算法进行全局 上遍历到起点，找到组成路径的所有节点，否则， 路径规划，在全局路径的基础上，利用Morphin搜 转到4)： 索树算法进行局部路径修正，使移动机器人在遇 7)设置变量i(i≥3)，判断Closed列表中i-1 到行走的人、打开的门等动态障碍物时，进行局 i、i+1节点是否在同一直线上，如果在删除i节 部路径规划，绕过障碍物后回到全局路径上，实 点，否则全部保留，i增加1： 现动态避障。 8)将Closed列表中最后得到的路径节点进行 移动平均滤波处理，得到平滑路径。 1基于改进A*算法的全局路径规划 2 Morphin搜索树算法局部路径规划 传统A*算法)获取的路径存在搜索节点多、 折线多、转折角大等不足之处，本文针对上述问 2.1 Morphin搜索树算法 题主要对A*算法41进行了两方面改进。首先 Morphin算法是CMU根据Ranger)算法提 改进关键节点的选取方式，删除冗余节点，假设 出的基于地面分析的局部路径规划算法，也是一 P为保存路径的j行2列数组，每列元素分别代表 种基于先验栅格地图进行可行性统计分析的局 栅格地图中x轴与y轴上的坐标点，每次更新 部避障算法82。其核心思想是：根据机器人自 P时，对已知节点与当前节点进行判断是否在同 身的传感器对环境信息进行实时检测，根据不同 直线上，如果为真，则去除中间节点，如果不在 的转向角度生成一组可行驶路径集，然后根据机照一定的评价标准，找到一条适当的从起点到终 点的路径，机器人在运动的过程中避开所有障 碍。移动机器人路径规划大致分两种，分别是全 局路径规划方法[2-3] 和局部路径规划方法[4-5]。目 前国内外路径规划算法主要采取的方法有：传统 方法，如 A*算法、人工势场法、Bidirectional RRT 算法等[6-8] ；智能算法，如神经网络算法[9] 、粒 子群算法和模糊控制算法等。这些算法各有优缺 点，例如：人工势场法实现简单，但容易陷入局部 最小值；Bidirectional RRT 算法能够有效地解决高 维空间和复杂约束问题，但路径由随机采样点搜 索一次生成，缺乏可重复性，导致路径不是最优； 粒子群算法[10] 具有收敛速度快、设置参数少的特 点，但寻优效率能力差；模糊控制算法[11] 不需要 精确的数学模型，鲁棒性强，但是控制系统精度 降低，动态品质变差，缺乏系统性。国内外学者 针对每种算法存在的不足提出了很多方法：文献 [8] 提出了基于双向势函数的抽样路径规划算法，通 过启发式函数证明收敛得到路径最优解，文献 [10] 提出一种与 Morphin 算法混合路径规划，同时改 进 QPSO 自适应局部搜索的策略，引入交叉操作， 提高性能避免局部最优。其中 Morphin 搜索树[12] 算法计算量小、实用性好，适合处理具有动态障 碍物的路径规划问题。文献 [13] 中使用双层栅格 地图方法对 A*算法进行优化，高层 A*算法决定 下一块大栅格局部地图，低层 A*算法对合并的局 部地图进行路径规划。A*算法是一种搜索速度 快，使用广泛的路径规划算法。针对传统 A*算法 节点多，转折角大且无法动态避障等问题，本文 提出一种融合改进 A*算法与 Morphin 算法的结 合算法。该算法主要利用改进 A*算法进行全局 路径规划，在全局路径的基础上，利用 Morphin 搜 索树算法进行局部路径修正，使移动机器人在遇 到行走的人、打开的门等动态障碍物时，进行局 部路径规划，绕过障碍物后回到全局路径上，实 现动态避障。 1 基于改进 A*算法的全局路径规划 传统 A*算法[13] 获取的路径存在搜索节点多、 折线多、转折角大等不足之处，本文针对上述问 题主要对 A*算法[14-15] 进行了两方面改进。首先 改进关键节点的选取方式，删除冗余节点，假设 P 为保存路径的 j 行 2 列数组，每列元素分别代表 栅格地图中 x 轴与 y 轴上的坐标点，每次更新 P 时，对已知节点与当前节点进行判断是否在同 一直线上，如果为真，则去除中间节点，如果不在 N −1 同一直线上，则将当前节点保存到 P 中。然后对 规划的路径平滑处理[16] ，文献 [16] 中面对传统 A*算法生成的路径转折角大且移动机器人转向 困难等问题采用了创建函数判断连接点是否存在 障碍物，若无障碍物删除连线中间节点。而本文 利用移动平均滤波的方法进行路径平滑处理，实 现简单，效果同样明显。根据数据统计方法，将 连续的采样数据作为一个固定长度为 N 的队列， 在新的一次测量后，去掉上述队列中首数据，剩 余的 个数据依次前移，并将新的采样数据插 入新队列的队尾；最后对新队列进行算术运算， 并将其结果作本次测量的结果。平滑处理之后寻 迹时间与路径长度都会减少。改进 A*算法的具 体步骤如下： 1) 初始化地图信息包括起点、目标点、障碍 物信息等； 2) 创建 Open 列表与 Closed 列表，将起点的 节点信息放入 Open 列表中； 3) 如果 Open 列表中为空，表示没有找到路 径，退出； f 4) 寻找起点周围可以到达的方格 (周围 8 个 方格)，并把起点设置为这些方格的“父节点”，然 后把周围节点加入到“Open 列表中”，根据列表中 节点 (估计函数) 的值进行从小到大排序； 5) 从 Open 列表中找到最佳节点，作为新 的“父节点”，并将上一个父节点移到 Closed 列 表中； 6) 在 Closed 列表中选取扩展节点，将扩展节 点的周围节点加入 Open 列表中。判断当前父节 点是否为目标点，如果是，则通过当前父节点向 上遍历到起点，找到组成路径的所有节点，否则， 转到 4)； i i i−1 i i+1 i i 7) 设置变量 ( ≥3)，判断 Closed 列表中 、 、 节点是否在同一直线上，如果在删除 节 点，否则全部保留， 增加 1； 8) 将 Closed 列表中最后得到的路径节点进行 移动平均滤波处理，得到平滑路径。 2 Morphin 搜索树算法局部路径规划 2.1 Morphin 搜索树算法 Morphin 算法是 CMU 根据 Ranger[17] 算法提 出的基于地面分析的局部路径规划算法，也是一 种基于先验栅格地图进行可行性统计分析的局 部避障算法[18-20]。其核心思想是：根据机器人自 身的传感器对环境信息进行实时检测，根据不同 的转向角度生成一组可行驶路径集，然后根据机 第 3 期 成怡，等：融合改进 A*算法和 Morphin 算法的移动机器人动态路径规划 ·547·