【机器学习】融合改进A算法和Morphin算法的移动机器人动态路径规划

第15卷第3期 智能系统学报 Vol.15 No.3 2020年5月 CAAI Transactions on Intelligent Systems May 2020 D0L:10.11992tis.201812023 融合改进A*算法和Morphin算法的 移动机器人动态路径规划 成怡，肖宏图 (天津工业大学电气工程与自动化学院，天津300387) 摘要：在动态未知环境下对机器人进行路径规划，传统A*算法可能出现碰撞或者路径规划失败问题。为了 满足移动机器人全局路径规划最优和实时避障的需求，提出一种改进A*算法与Morphin搜索树算法相结合的 动态路径规划方法。首先通过改进A*算法减少路径规划过程中关键节点的选取，在规划出一条全局较优路径 的同时对路径平滑处理。然后基于移动机器人传感器采集的局部信息，利用Morphin搜索树算法对全局路径 进行动态的局部规划，确保更好的全局路径的基础上，实时避开障碍物行驶到目标点。MATLAB仿真实验结 果表明，提出的动态路径规划方法在时间和路径上得到提升，在优化全局路径规划的基础上修正局部路径，实 现动态避障提高机器人达到目标点的效率。 关键词：移动机器人；A*算法；改进A*算法；Morphir搜索树算法；全局路径规划：局部路径规划；动态路径规 划：实时避障 中图分类号：TP242文献标志码：A文章编号：1673-4785(2020)03-0546-07 中文引用格式：成怡，肖宏图.融合改进A*算法和Morphir算法的移动机器人动态路径规划.智能系统学报，2020,15(3)： 546-552. 英文引用格式：CHENG Yi,XIAO Hongtu..Mobile-robot dynamic path planning based on improved A*and Morphin algorithms[J].CAAI transactions on intelligent systems,2020,15(3):546-552. Mobile-robot dynamic path planning based on improved A*and Morphin algorithms CHENG Yi,XIAO Hongtu (School of Electrical Engineering and Automation,University of Tianjin Polytechnic,Tianjin 300387,China) Abstract:The traditional A*algorithm can experience collisions or path-planning failure in dynamic complicated envir- onments.To meet global optimal requirements and achieve real-time obstacle avoidance in mobile-robot path planning, we propose a novel method that fuses an improved A*algorithm with a Morphin search tree algorithm.First,we im- proved the A*algorithm by reducing the selection of key nodes in the path-planning process and performing path smoothing when planning the global optimal path.Then,based on the local information obtained by the mobile-robot sensor,the Morphin search tree algorithm is used to dynamically localize the global path.Thus,obstacles are avoided both by ensuring a better global path and by real-time obstacle avoidance as the robot moves to the target.The MAT- LAB simulation results show that the proposed dynamic path-planning method improves both the time and path.The local path is corrected via the optimized global-path planning,dynamic obstacle avoidance,and the improved efficiency with which the robot reaches the target point. Keywords:mobile robot;A*algorithm;improved A*algorithm;Morphin search tree;global-path planning;local path planning;dynamic path planning;real-time obstacle avoidanc 收稿日期：2018-12-20. 基金项目：天津市自然科学基金项目(18 JCYBJC88400.18JCY. 当前移动机器人自主运动是衡量机器人性能 BC88300):天津市高等学校创新团队培养计划项目 的重要指标，而路径规划是完成这一指标的关键 (TD13-5036). 通信作者：肖宏图.E-mail:tvtmail@163.com, 技术。路径规划是指存在障碍物的环境中，按

DOI: 10.11992/tis.201812023 融合改进 A*算法和 Morphin 算法的 移动机器人动态路径规划 成怡，肖宏图 （天津工业大学 电气工程与自动化学院，天津 300387） 摘 要：在动态未知环境下对机器人进行路径规划，传统 A*算法可能出现碰撞或者路径规划失败问题。为了 满足移动机器人全局路径规划最优和实时避障的需求，提出一种改进 A*算法与 Morphin 搜索树算法相结合的 动态路径规划方法。首先通过改进 A*算法减少路径规划过程中关键节点的选取，在规划出一条全局较优路径 的同时对路径平滑处理。然后基于移动机器人传感器采集的局部信息，利用 Morphin 搜索树算法对全局路径 进行动态的局部规划，确保更好的全局路径的基础上，实时避开障碍物行驶到目标点。MATLAB 仿真实验结 果表明，提出的动态路径规划方法在时间和路径上得到提升，在优化全局路径规划的基础上修正局部路径，实 现动态避障提高机器人达到目标点的效率。 关键词：移动机器人；A*算法；改进 A*算法；Morphin 搜索树算法；全局路径规划；局部路径规划；动态路径规 划；实时避障 中图分类号：TP242 文献标志码：A 文章编号：1673−4785(2020)03−0546−07 中文引用格式：成怡, 肖宏图. 融合改进 A*算法和 Morphin 算法的移动机器人动态路径规划 [J]. 智能系统学报, 2020, 15(3): 546–552. 英文引用格式：CHENG Yi, XIAO Hongtu. Mobile-robot dynamic path planning based on improved A* and Morphin algorithms[J]. CAAI transactions on intelligent systems, 2020, 15(3): 546–552. Mobile-robot dynamic path planning based on improved A* and Morphin algorithms CHENG Yi，XIAO Hongtu (School of Electrical Engineering and Automation, University of Tianjin Polytechnic, Tianjin 300387, China) Abstract: The traditional A* algorithm can experience collisions or path-planning failure in dynamic complicated envir￾onments. To meet global optimal requirements and achieve real-time obstacle avoidance in mobile-robot path planning, we propose a novel method that fuses an improved A* algorithm with a Morphin search tree algorithm. First, we im￾proved the A* algorithm by reducing the selection of key nodes in the path-planning process and performing path smoothing when planning the global optimal path. Then, based on the local information obtained by the mobile-robot sensor, the Morphin search tree algorithm is used to dynamically localize the global path. Thus, obstacles are avoided both by ensuring a better global path and by real-time obstacle avoidance as the robot moves to the target. The MAT￾LAB simulation results show that the proposed dynamic path-planning method improves both the time and path. The local path is corrected via the optimized global-path planning, dynamic obstacle avoidance, and the improved efficiency with which the robot reaches the target point. Keywords: mobile robot; A* algorithm; improved A* algorithm; Morphin search tree; global-path planning; local path planning; dynamic path planning; real-time obstacle avoidanc 当前移动机器人自主运动是衡量机器人性能 的重要指标，而路径规划是完成这一指标的关键 技术。路径规划[1] 是指存在障碍物的环境中，按 收稿日期：2018−12−20. 基金项目：天津市自然科学基金项目 (18JCYBJC88400，18JCY￾BJC88300)；天津市高等学校创新团队培养计划项目 (TD13-5036). 通信作者：肖宏图. E-mail：tvtmail@163.com. 第 15 卷第 3 期 智 能 系 统 学 报 Vol.15 No.3 2020 年 5 月 CAAI Transactions on Intelligent Systems May 2020

第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·

·548· 智能系统学报 第15卷 器人当前的状态，包括俯仰角、转向角以及前方 会选择碰撞机率最小的路径，7条弧线中AB与 路径的可通行率、安全性，选出一条最适宜通行 AC为无碰撞的备选路径，AC路径到达目标点会 的路径。该算法不仅计算量较少、效率较快，能 导致路径复杂，因此AB路径更加合理。对于 够较好地处理环境建模的不确定性，也能较好地 Morphin搜索树算法产生的多条备选路径规划用 与全局路径规划算法结合，共同决策机器人的运 评价函数决定最优度，评价函数为 动行为l。Morphin算法预测线如图1所示，其 了一{+预钱士有物无跨得物 (3) 中圆环为机器人，Target菱形为目标，黑色块为 障碍物。 式中：L与M为弧线长度及拐点个数；△d为弧线 的每个栅格点到子目标点平均距离：N为弧线终 章碍物 ◆目标 点和子目标点连线与障碍物栅格相交次数；y1、 障碍物 2、⅓和⅓为各参数权值。当弧线存在障碍物时 f为无穷大；∫为最小值时，对应的弧线为局部规 障碍物 划的最优路径。 2.2局部规划与动态路径规划流程 本文算法的流程如图2所示。机器人首先基 机器人 于改进A*算法进行全局规划，然后根据自身传感 图1 Morphin算法路径选择 器实时检测周围环境信息，并感知是否存在未知 Fig.1 Path selection by Morphin algorithm 障碍物，预测障碍物的运动轨迹与速度，判断机 Morphin算法由运动模型和评价函数两部分 器人是否会与障碍物发生碰撞，如果与未知障碍 组成。运动模型的核心思想是根据前进方向按照 物碰撞，调用Morphin算法进行局部规划。 同样的时间、不同的转移角生成一组路径，利用 开始 评价函数对每条路径进行估计，得到最优路径。 Morphin算法运动模型的建立就是建立搜索路径 组和搜索弧线组四。搜索路径组是指由当前环境 初始化参数 信息得到的可能运行的位置。搜索弧线组由多条 预测线组成。已知机器人当前位置、速度及运动 重新设置 改进A*算法 方向角，即[x(),y(①，v(0),()l。可以推算出搜索路径组： 起点位置 x(t+μ)x(t) v(t)μcos0,(t) t+四0 v(t)μsin0,(t) (1) N 全局路径规划 局部避障 式中：4为搜索路径的时间段长度，必须大于与障 成功 碍物保持最小安全距离所需的运动时间；O,()和 0x分别表示t时刻搜索转弯角和最大转向角， Morphin算法 -0x≤0，(t)≤0x。搜索弧组建s立方法如下： 未知障碍物 xt+的1 xt+i-1)】[ v(t)tcos0,(t) t+)= t+i-1》 v(t)tsin0,(t) (2) N 是否碰撞 式中：（为时间步长：i为时间步长计数，也表示搜 N 索弧组的计数，i=1,2,…,:n表示搜索范围大小， 是否终点 (相等条件下，n越大搜索精度越高，计算量越 大，可根据实际情况人为设定：1为机器人开始运 行的时间。式(1)与式(2)中：x()、y)为t时刻 结束 机器人的位姿，v()、)为t时刻的瞬时速度与运 图2融合算法流程图 动方向角。设机器人在二维栅格地图中进行运 Fig.2 Flow chart of the fusion of algorithms 动，选定中心弧线方向始终朝向目标点，为计算 融合算法中的Morphin算法基于动态窗口原 简单只在图1中机器人前方画7条弧线，且中心 理，采用时间滚动窗口思想搜索可行轨迹空间。 弧线两侧45均分。 根据动态窗口中评价函数来进行动态预测： 从图1中可以看出，机器人为了避开障碍物 G=aXamgle +B.Ydist +Zvelocity (4)

器人当前的状态，包括俯仰角、转向角以及前方 路径的可通行率、安全性，选出一条最适宜通行 的路径。该算法不仅计算量较少、效率较快，能 够较好地处理环境建模的不确定性，也能较好地 与全局路径规划算法结合，共同决策机器人的运 动行为[21]。Morphin 算法预测线如图 1 所示，其 中圆环为机器人，Target 菱形为目标，黑色块为 障碍物。 A C B 障碍物 目标 障碍物 机器人 障碍物 图 1 Morphin 算法路径选择 Fig. 1 Path selection by Morphin algorithm [x(t), y(t), v(t), θ(t)] Morphin 算法由运动模型和评价函数两部分 组成。运动模型的核心思想是根据前进方向按照 同样的时间、不同的转移角生成一组路径，利用 评价函数对每条路径进行估计，得到最优路径。 Morphin 算法运动模型的建立就是建立搜索路径 组和搜索弧线组[22]。搜索路径组是指由当前环境 信息得到的可能运行的位置。搜索弧线组由多条 预测线组成。已知机器人当前位置、速度及运动 方向角，即 。可以推算出搜索路径组： [ x(t+µ) y(t+µ) ] = [ x(t) y(t) ] − [ v(t)µcos θs(t) v(t)µsinθs(t) ] (1) µ θs(t) θmax t −θmax ⩽ θs(t) ⩽ θmax 式中： 为搜索路径的时间段长度，必须大于与障 碍物保持最小安全距离所需的运动时间； 和 分别表示 时刻搜索转弯角和最大转向角， 。搜索弧组建 s 立方法如下： [ x(t+ℓi) y(t+ℓi) ] = [ x(t+ℓ(i−1)) y(t+ℓ(i−1)) ] − [ v(t)ℓ cos θs(t) v(t)ℓ sinθs(t) ] (2) ℓ i i = 1,2,··· ,n n ℓ n t x(t)、y(t) t v(t)、θ(t) t 式中： 为时间步长； 为时间步长计数，也表示搜 索弧组的计数， ； 表示搜索范围大小， 相等条件下， 越大搜索精度越高，计算量越 大，可根据实际情况人为设定； 为机器人开始运 行的时间。式 (1) 与式 (2) 中： 为 时刻 机器人的位姿， 为 时刻的瞬时速度与运 动方向角。设机器人在二维栅格地图中进行运 动，选定中心弧线方向始终朝向目标点，为计算 简单只在图 1 中机器人前方画 7 条弧线，且中心 弧线两侧 45°均分。 从图 1 中可以看出，机器人为了避开障碍物 会选择碰撞机率最小的路径，7 条弧线中 AB 与 AC 为无碰撞的备选路径，AC 路径到达目标点会 导致路径复杂，因此 AB 路径更加合理。对于 Morphin 搜索树算法产生的多条备选路径规划用 评价函数决定最优度，评价函数为 f = { ∞, 弧线上有障碍物 γ1L+γ2M +γ3∆d +γ4N, 无障碍物 (3) L M ∆d N γ1 γ2 γ3 γ4 f f 式中： 与 为弧线长度及拐点个数； 为弧线 的每个栅格点到子目标点平均距离； 为弧线终 点和子目标点连线与障碍物栅格相交次数； 、 、 和 为各参数权值。当弧线存在障碍物时 为无穷大； 为最小值时，对应的弧线为局部规 划的最优路径。 2.2 局部规划与动态路径规划流程 本文算法的流程如图 2 所示。机器人首先基 于改进 A*算法进行全局规划，然后根据自身传感 器实时检测周围环境信息，并感知是否存在未知 障碍物，预测障碍物的运动轨迹与速度，判断机 器人是否会与障碍物发生碰撞，如果与未知障碍 物碰撞，调用 Morphin 算法进行局部规划。 结束 N Y Y Y N N N Y 开始 初始化参数 改进A*算法 局部避障 成功 全局路径规划 未知障碍物 是否终点 是否碰撞 Morphin算法 重新设置 起点位置 图 2 融合算法流程图 Fig. 2 Flow chart of the fusion of algorithms 融合算法中的 Morphin 算法基于动态窗口原 理，采用时间滚动窗口思想搜索可行轨迹空间。 根据动态窗口中评价函数来进行动态预测： G = α· Xangle +β ·Ydist +λ ·Zvelocity (4) ·548· 智 能 系 统 学 报 第 15 卷

第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·

·550· 智能系统学报 第15卷 了36%。在时间、距离、节点数等方面优化了传 况，小球C速度为0.4m/s,短时间内从机器人要 统A*算法。 行驶的通道内出来并且不阻挡机器人的运动。如图8 3.2引入Morphin算法后动态避障效果分析 所示，机器人在D2点等待球C运动出来，再按照 图5是动态障碍物在初始位置时的地图。机 规划好的全局路径行驶到目标点。 器人首先按照改进A*算法规划的全局路径行 20 目标 驶。假设在机器人行驶过程中栅格地图中存在 18 16 A、B、C3个动态障碍物小球，实验参数如下：小 14 球平均速度为0.23m/s,小车平均速度为2.2m/s。 小球位置分别为(6,10)、(11,8)、(15,13)：Bidirec- 号10 tional RRT算法每步搜索节点为l0,搜索次数最 大值1O00,RRT双向搜索树算法在相同地图下进 机器人 行对比实验，如图6所示：模糊控制算法中初始航 0 向为45°，机器人的安全距离为1m,距离阈值偏 2 468101214161820 m 差为30cm,最大转向角60°，如图7所示，对于动 图7模糊控制算法规划路径 态算法的时间、路径、精度进行对比。 Fig.7 Path planned by fuzzy control algorithm 20 18F 20 16 18 16 14 10 机器人上上 机器人 2468101214161820 X/m 0 2468101214161820 X/m 图5动态障碍物运动前位置 图8全局路径动态避障 Fig.5 Initial position before dynamic obstacle movement Fig.8 Global-path dynamic obstacle avoidance 20上+-+++ 第2种情况小球C速度为0.1m/s,运动之后 18 16 停在通道内，机器人无法按照规划好的全局路径 14 行驶，障碍物之间的通道被堵住，如图9所示。此 12 时，机器人重新调用改进A*算法进行全局路径规 10 划，修改原来的规划路线，行驶到目标点。 20 18 16 0 68101214161820 14 X/m 号10 图6 Bidirectional RRT算法规划路径 Fig.6 Path planned by Bidirectional RRT algorithm Morphin算法对机器人与障碍物是否碰撞进 机器人 行预测，从而进行局部路径规划，如图8所示。由 0 2468101214161820 于小球A与小车运动路线无干扰，小车正常行 X/m 驶；通过预测可知在虚线的D,点，将会与小球 图9动态避障重新规划路径 B碰撞，小车进行局部避障选择预测弧线G值最 Fig.9 Re-planned path using dynamic obstacle avoidance 小的路径，避开后回到全局路径继续行驶。运动 图6与图7的对比实验静态与动态障碍物相 小球C在障碍物之间的通道中，此处机器人无法 同。Bidirectional RRT算法通过生成随机数的方 通过。对于运动小球C有2种情况。第1种情 式来搜索可通行路径，缺乏可重复性，找到的路

了 36%。在时间、距离、节点数等方面优化了传 统 A*算法。 3.2 引入 Morphin 算法后动态避障效果分析 图 5 是动态障碍物在初始位置时的地图。机 器人首先按照改进 A*算法规划的全局路径行 驶。假设在机器人行驶过程中栅格地图中存在 A、B、C 3 个动态障碍物小球，实验参数如下：小 球平均速度为 0.23 m/s，小车平均速度为 2.2 m/s。 小球位置分别为 (6,10)、 (11，8)、(15,13)；Bidirec￾tional RRT 算法每步搜索节点为 10，搜索次数最 大值 1 000，RRT 双向搜索树算法在相同地图下进 行对比实验，如图 6 所示；模糊控制算法中初始航 向为 45°，机器人的安全距离为 1 m，距离阈值偏 差为 30 cm，最大转向角 60°，如图 7 所示，对于动 态算法的时间、路径、精度进行对比。 机器人 目标 C A B 0 2 4 6 8 10 12 14 16 20 18 2 4 6 8 10 12 14 16 18 20 X/m Y/m 图 5 动态障碍物运动前位置 Fig. 5 Initial position before dynamic obstacle movement A B C 0 2 4 6 8 10 12 14 16 20 18 2 4 6 8 10 12 14 16 18 20 X/m Y/m 目标 机器人 图 6 Bidirectional RRT 算法规划路径 Fig. 6 Path planned by Bidirectional RRT algorithm Morphin 算法对机器人与障碍物是否碰撞进 行预测，从而进行局部路径规划，如图 8 所示。由 于小球 A 与小车运动路线无干扰，小车正常行 驶；通过预测可知在虚线的 D1 点，将会与小球 B 碰撞，小车进行局部避障选择预测弧线 G 值最 小的路径，避开后回到全局路径继续行驶。运动 小球 C 在障碍物之间的通道中，此处机器人无法 通过。对于运动小球 C 有 2 种情况。第 1 种情 况，小球 C 速度为 0.4 m/s，短时间内从机器人要 行驶的通道内出来并且不阻挡机器人的运动。如图 8 所示，机器人在 D2 点等待球 C 运动出来，再按照 规划好的全局路径行驶到目标点。 A B C 0 2 4 6 8 10 12 14 16 20 18 2 4 6 8 10 12 14 16 18 20 X/m Y/m 目标 机器人 图 7 模糊控制算法规划路径 Fig. 7 Path planned by fuzzy control algorithm 机器人 目标 0 2 4 6 8 10 12 14 16 20 18 2 4 6 8 10 12 14 16 18 20 X/m Y/m A B D2 C D1 图 8 全局路径动态避障 Fig. 8 Global-path dynamic obstacle avoidance 第 2 种情况小球 C 速度为 0.1 m/s，运动之后 停在通道内，机器人无法按照规划好的全局路径 行驶，障碍物之间的通道被堵住，如图 9 所示。此 时，机器人重新调用改进 A*算法进行全局路径规 划，修改原来的规划路线，行驶到目标点。 C 机器人 目标 0 2 4 6 8 10 12 14 16 20 18 2 4 6 8 10 12 14 16 18 20 X/m Y/m A B D1 D2 图 9 动态避障重新规划路径 Fig. 9 Re-planned path using dynamic obstacle avoidance 图 6 与图 7 的对比实验静态与动态障碍物相 同。Bidirectional RRT 算法通过生成随机数的方 式来搜索可通行路径，缺乏可重复性，找到的路 ·550· 智 能 系 统 学 报 第 15 卷

第3期 成怡，等：融合改进A*算法和Morphin算法的移动机器人动态路径规划 ·551· 径并不是最优的。同时在初始阶段双向搜索树会 [2]SONG Baoye,WANG Zidong,ZOU Lei.On global 对地图进行大面积探索，包括不可通行的死区， smooth path planning for mobile robots using a novel mul- 导致节点增多，占用内存增加。模糊算法根据设 timodal delayed PSO algorithm[J].Cognitive computation, 定的转向角、阈值、安全距离等因素会出现死锁 2017,9(1):5-17. 现象，使机器人停在原地无法移动到目标。同时 [3]LEE J.Heterogeneous-ants-based path planner for global 在复杂的室内环境转向困难当转向角过大将会陷 path planning of mobile robot applications[J].Internation- al journal of control,automation and systems,2017,15(4): 入死锁。所以同等环境下本文动态算法在灵活性 17541769 与适应性方面更优。表2是A*算法、改进A*算 [4]李元，王石荣，于宁波.基于RGB-D信息的移动机器人 法、Bidirectional RRT、模糊控制算法、动态算法的 SLAM和路径规划方法研究与实现).智能系统学报， 数据对比。 2018.13(3):445-451 表2路径规划算法比较结果 LI Yuan,WANG Shirong,YU Ningbo.RGB-D-based Table 2 Comparison of path planning results SLAM and path planning for mobile robots[J].CAAI 算法 平均时间s平均长度/m节点个数平滑处理 transactions on intelligent systems,2018,13(3):445-451. [5]FAZLOLLAHTABAR H.HASSANLI S.Hybrid cost and 传统A*算法 20.14 38.68 36 否 time path planning for multiple autonomous guided 改进A幸算法 18.08 32.03 23 是 vehicles[J].Applied intelligence,2017,48(2):482-498. 动态算法 18.75 40.22 32 是 [6]HAN J,SEO Y.Mobile robot path planning with surround- 模糊控制 33.71 47.87 142 是 ing point set and path improvement[J].Applied soft com- 双向RRT 22.24 51.55 103 否 puting,2017,57:35-47. [7]SUDHAKARA P,GANAPATHY V.PRIYADHAR- 通过动态算法在相同环境下与Bidirectional SHINI B,et al Obstacle avoidance and navigation plan- RRT算法和模糊控制的对比可以看出，在路径长 ning of a wheeled mobile robot using amended artificial 度、耗费时间、与路径节点等方面得到明显的改 potential field method[J].Procedia computer science,2018, 善。耗费更少的资源得到更优的结果同时保证机 133:998-1004. 器人安全有效地到达目标点。 [8]TAHIR Z,QURESHI A H,AYAZ Y,et al.Potentially guided bidirectionalized RRT*for fast optimal path plan- 4结束语 ning in cluttered environments[J].Robotics and autonom- ous systems,.2018,108:13-27. 本文针对传统A*算法面对动态障碍发生碰 [9]朱大奇，孙兵，李利.基于生物启发模型的AUV三维自 撞或者路径规划失败问题，提出了一种改进A*算 主路径规划与安全避障算法J几控制与决策，2015. 法与Morphin算法相结合的动态路径规划方法。 30(5):798-806. 首先对A*算法进行改进，优化传统A*算法的搜 ZHU Daqi,SUN Bing,LI Li.Algorithm for AUV's 3-D 索节点多，路径不平滑，不易运动控制等问题。 path planning and safe obstacle avoidance based on biolo- 并根据改进的A*算法进行路径规划；然后机器人 gical inspired model[J].Control and decision,2015,30(5): 按照规划出的全局路径行驶，如果碰到未知的静 798-806. 态或动态障碍物时，根据传感器检测到的信息调 [1O]伍永健，陈跃东，陈孟元.改进QPSO和Morphin算法 用Morphin算法进行局部规划。通过仿真验证了 下移动机器人混合路径规划.电子测量与仪器学报. 改进A*算法规划出的路径更加平滑，搜索节点更 2017,31(2):295-301 少；Morphin算法可以有效地避开动态障碍物。 WU Yongjian,CHEN Yuedong,CHEN Mengyuan.Hy- brid path planning of mobile robot based on improved 动态算法通过A*算法与Morphin算法相融合，使 QPSO and Morphin algorithm[J].Journal of electronic 机器人获得最佳的路径、时间，有效地提升了机 measurement and instrumentation,2017,31(2):295-301. 器人的工作效率和安全性。 [11]MAOUDJ A.HENTOUT A.BOUZOUIA B.et al.On- 参考文献： line fault-tolerant fuzzy-based path planning and obstacles avoidance approach for manipulator robots[J].Interna- [1]QURESHI A H,AYAZ Y.Potential functions based tional journal of uncertainty,fuzziness and knowledge- sampling heuristic for optimal path planning.Autonom- based systems,2018,26(5):809-838 ous robots,2016,40(6):1079-1093. [12]万晓凤，胡伟，郑博嘉，等.基于改进蚁群算法与Moph

径并不是最优的。同时在初始阶段双向搜索树会 对地图进行大面积探索，包括不可通行的死区， 导致节点增多，占用内存增加。模糊算法根据设 定的转向角、阈值、安全距离等因素会出现死锁 现象，使机器人停在原地无法移动到目标。同时 在复杂的室内环境转向困难当转向角过大将会陷 入死锁。所以同等环境下本文动态算法在灵活性 与适应性方面更优。表 2 是 A*算法、改进 A*算 法、Bidirectional RRT、模糊控制算法、动态算法的 数据对比。 表 2 路径规划算法比较结果 Table 2 Comparison of path planning results 算法 平均时间/s 平均长度/m 节点个数 平滑处理 传统A*算法 20.14 38.68 36 否 改进A*算法 18.08 32.03 23 是 动态算法 18.75 40.22 32 是 模糊控制 33.71 47.87 142 是 双向 RRT 22.24 51.55 103 否 通过动态算法在相同环境下与 Bidirectional RRT 算法和模糊控制的对比可以看出，在路径长 度、耗费时间、与路径节点等方面得到明显的改 善。耗费更少的资源得到更优的结果同时保证机 器人安全有效地到达目标点。 4 结束语 本文针对传统 A*算法面对动态障碍发生碰 撞或者路径规划失败问题，提出了一种改进 A*算 法与 Morphin 算法相结合的动态路径规划方法。 首先对 A*算法进行改进，优化传统 A*算法的搜 索节点多，路径不平滑，不易运动控制等问题。 并根据改进的 A*算法进行路径规划；然后机器人 按照规划出的全局路径行驶，如果碰到未知的静 态或动态障碍物时，根据传感器检测到的信息调 用 Morphin 算法进行局部规划。通过仿真验证了 改进 A*算法规划出的路径更加平滑，搜索节点更 少；Morphin 算法可以有效地避开动态障碍物。 动态算法通过 A*算法与 Morphin 算法相融合，使 机器人获得最佳的路径、时间，有效地提升了机 器人的工作效率和安全性。 参考文献： QURESHI A H, AYAZ Y. Potential functions based sampling heuristic for optimal path planning[J]. Autonom￾ous robots, 2016, 40(6): 1079–1093. [1] SONG Baoye, WANG Zidong, ZOU Lei. On global smooth path planning for mobile robots using a novel mul￾timodal delayed PSO algorithm[J]. Cognitive computation, 2017, 9(1): 5–17. [2] LEE J. Heterogeneous-ants-based path planner for global path planning of mobile robot applications[J]. Internation￾al journal of control, automation and systems, 2017, 15(4): 1754–1769. [3] 李元, 王石荣, 于宁波. 基于 RGB-D 信息的移动机器人 SLAM 和路径规划方法研究与实现 [J]. 智能系统学报, 2018, 13(3): 445–451. LI Yuan, WANG Shirong, YU Ningbo. RGB-D-based SLAM and path planning for mobile robots[J]. CAAI transactions on intelligent systems, 2018, 13(3): 445–451. [4] FAZLOLLAHTABAR H, HASSANLI S. Hybrid cost and time path planning for multiple autonomous guided vehicles[J]. Applied intelligence, 2017, 48(2): 482–498. [5] HAN J, SEO Y. Mobile robot path planning with surround￾ing point set and path improvement[J]. Applied soft com￾puting, 2017, 57: 35–47. [6] SUDHAKARA P, GANAPATHY V. PRIYADHAR￾SHINI B, et al Obstacle avoidance and navigation plan￾ning of a wheeled mobile robot using amended artificial potential field method[J]. Procedia computer science, 2018, 133: 998–1004. [7] TAHIR Z, QURESHI A H, AYAZ Y, et al. Potentially guided bidirectionalized RRT* for fast optimal path plan￾ning in cluttered environments[J]. Robotics and autonom￾ous systems, 2018, 108: 13–27. [8] 朱大奇, 孙兵, 李利. 基于生物启发模型的 AUV 三维自 主路径规划与安全避障算法 [J]. 控制与决策, 2015, 30(5): 798–806. ZHU Daqi, SUN Bing, LI Li. Algorithm for AUV’s 3-D path planning and safe obstacle avoidance based on biolo￾gical inspired model[J]. Control and decision, 2015, 30(5): 798–806. [9] 伍永健, 陈跃东, 陈孟元. 改进 QPSO 和 Morphin 算法 下移动机器人混合路径规划 [J]. 电子测量与仪器学报, 2017, 31(2): 295–301. WU Yongjian, CHEN Yuedong, CHEN Mengyuan. Hy￾brid path planning of mobile robot based on improved QPSO and Morphin algorithm[J]. Journal of electronic measurement and instrumentation, 2017, 31(2): 295–301. [10] MAOUDJ A, HENTOUT A, BOUZOUIA B, et al. On￾line fault-tolerant fuzzy-based path planning and obstacles avoidance approach for manipulator robots[J]. Interna￾tional journal of uncertainty, fuzziness and knowledge￾based systems, 2018, 26(5): 809–838. [11] [12] 万晓凤, 胡伟, 郑博嘉, 等. 基于改进蚁群算法与 Morph- 第 3 期 成怡，等：融合改进 A*算法和 Morphin 算法的移动机器人动态路径规划 ·551·

·552· 智能系统学报 第15卷 in算法的机器人路径规划方法[.科技导报，2015 ized path planning with preferences in highly complex dy- 33(3:84-89 namic environments[J].Robotica,2013,31(8): WAN Xiaofeng,HU Wei,ZHENG Bojia,et al.Robot 1195-1208. path planning method based on improved ant colony al- [20]诸葛程晨，唐振民，石朝侠.基于多层Morphin搜索树 gorithm and Morphin algorithm[J].Science&technology 的UGV局部路径规划算法[J].机器人，2014,36(4) review,2015,33(3):84-89. 491-497. [13】秦玉鑫，王红旗，杜翠杰.基于双层A*算法的移动机器 ZHUGE Chengchen,TANG Zhenmin,SHI Zhaoxia.A 人路径规划[J.制造业自动化，2014,36(24)：21-25,40. local path planning algorithm for UGV based on multilay- QIN Yuxin,WANG Hongqi,DU Cuijie.A path planning er Morphin search tree[J].Robot,2014,36(4):491-497. approach to moving robot based on double layer A*Al- [21]曹清云，倪建军，王康，等.一种改进的未知动态环境下 gorithm[J].Manufacturing automation,2014,36(24): 机器人混合路径规划方法].计算机与现代化， 21-25.40 2016(4):54-58 [14]XU Yaru,LIU Rong.Path planning for mobile articu- CAO Qingyun,NI Jianjun,WANG Kang,et al.A robot lated robots based on the improved A*algorithm[J].Inter- hybrid path planning algorithm under improved unknown national journal of advanced robotic systems,2017,14(4): and dynamic environment[J].Computer and moderniza- 1-10 tion.2016(4:54-58. [15]ZHANG Hongmei,LI Minglong.Rapid path planning al- [22]张兆宁，魏中慧.危险天气下基于多重Morphin算法的 gorithm for mobile robot in dynamic environment[J].Ad- 终端区三维实时改航方法)南京航空航天大学学报， vances in mechanical engineering,2017,9(12):1-12. 2015,47(4:467-473 [16]王红卫，马勇，谢勇，等.基于平滑A*算法的移动机器 ZHANG Zhaoning,WEI Zhonghui.3-D real-time devi- 人路径规划[].同济大学学报（自然科学版），2010， ation method for avoiding hazardous weather in terminal 38(11):1647-1650. airspace based on Morphin planning algorithm[J.Journ- WANG Hongwei,MA Yong,XIE Yong,et al.Mobile ro- al of Nanjing University of Aeronautics and Astronautics, bot optimal path planning based on smoothing A*al- 2015,47(4):467-473 gorithm[J].Journal of Tongji University (Natural Science),2010,38(11):1647-1650. 作者简介： [17]SIMMONS R,KROTKOV E,CHRISMAN L,et al.Ex- 成怡，副教授，博士，主要研究方 perience with rover navigation for lunar-like terrains 向为视觉导航技术、智能算法优化、控 [C]//Proceedings of 1995 IEEE/RSJ International Confer- 制系统建模。主持及参与国家、省部 级科研项目5项，获2013年天津优秀 ence on Intelligent Robots and Systems.Human Robot In- 青年教师资助计划。发表学术论文 teraction and Cooperative Robots.Pittsburgh,USA,1995: 30余篇。 441-446. [18]张飞，白伟，乔耀华，等.基于改进D*算法的无人机室 内路径规划[智能系统学报，2019,14(4)：662-669， 肖宏图，硕士研究生，主要研究方 ZHANG Fei,BAI Wei,QIAO Yaohua,et al.UAV in- 向为路径规划算法、移动机器人。 door path planning based on improved D*algorithm[J]. CAAI transactions on intelligent systems,2019,14(4): 662-669. [19]BELGHITH K,KABANZA F,HARTMAN L.Random-

in 算法的机器人路径规划方法 [J]. 科技导报, 2015, 33(3): 84–89. WAN Xiaofeng, HU Wei, ZHENG Bojia, et al. Robot path planning method based on improved ant colony al￾gorithm and Morphin algorithm[J]. Science & technology review, 2015, 33(3): 84–89. 秦玉鑫, 王红旗, 杜翠杰. 基于双层 A*算法的移动机器 人路径规划 [J]. 制造业自动化, 2014, 36(24): 21–25, 40. QIN Yuxin, WANG Hongqi, DU Cuijie. A path planning approach to moving robot based on double layer A* Al￾gorithm[J]. Manufacturing automation, 2014, 36(24): 21–25, 40. [13] XU Yaru, LIU Rong. Path planning for mobile articu￾lated robots based on the improved A* algorithm[J]. Inter￾national journal of advanced robotic systems, 2017, 14(4): 1–10. [14] ZHANG Hongmei, LI Minglong. Rapid path planning al￾gorithm for mobile robot in dynamic environment[J]. Ad￾vances in mechanical engineering, 2017, 9(12): 1–12. [15] 王红卫, 马勇, 谢勇, 等. 基于平滑 A*算法的移动机器 人路径规划 [J]. 同济大学学报 (自然科学版), 2010, 38(11): 1647–1650. WANG Hongwei, MA Yong, XIE Yong, et al. Mobile ro￾bot optimal path planning based on smoothing A* al￾gorithm[J]. Journal of Tongji University (Natural Science), 2010, 38(11): 1647–1650. [16] SIMMONS R, KROTKOV E, CHRISMAN L, et al. Ex￾perience with rover navigation for lunar-like terrains [C]//Proceedings of 1995 IEEE/RSJ International Confer￾ence on Intelligent Robots and Systems. Human Robot In￾teraction and Cooperative Robots. Pittsburgh, USA, 1995: 441–446. [17] 张飞, 白伟, 乔耀华, 等. 基于改进 D*算法的无人机室 内路径规划 [J]. 智能系统学报, 2019, 14(4): 662–669. ZHANG Fei, BAI Wei, QIAO Yaohua, et al. UAV in￾door path planning based on improved D* algorithm[J]. CAAI transactions on intelligent systems, 2019, 14(4): 662–669. [18] [19] BELGHITH K, KABANZA F, HARTMAN L. Random￾ized path planning with preferences in highly complex dy￾namic environments[J]. Robotica, 2013, 31(8): 1195–1208. 诸葛程晨, 唐振民, 石朝侠. 基于多层 Morphin 搜索树 的 UGV 局部路径规划算法 [J]. 机器人, 2014, 36(4): 491–497. ZHUGE Chengchen, TANG Zhenmin, SHI Zhaoxia. A local path planning algorithm for UGV based on multilay￾er Morphin search tree[J]. Robot, 2014, 36(4): 491–497. [20] 曹清云, 倪建军, 王康, 等. 一种改进的未知动态环境下 机器人混合路径规划方法 [J]. 计算机与现代化, 2016(4): 54–58. CAO Qingyun, NI Jianjun, WANG Kang, et al. A robot hybrid path planning algorithm under improved unknown and dynamic environment[J]. Computer and moderniza￾tion, 2016(4): 54–58. [21] 张兆宁, 魏中慧. 危险天气下基于多重 Morphin 算法的 终端区三维实时改航方法 [J]. 南京航空航天大学学报, 2015, 47(4): 467–473. ZHANG Zhaoning, WEI Zhonghui. 3-D real-time devi￾ation method for avoiding hazardous weather in terminal airspace based on Morphin planning algorithm[J]. Journ￾al of Nanjing University of Aeronautics and Astronautics, 2015, 47(4): 467–473. [22] 作者简介： 成怡，副教授，博士，主要研究方 向为视觉导航技术、智能算法优化、控 制系统建模。主持及参与国家、省部 级科研项目 5 项，获 2013 年天津优秀 青年教师资助计划。发表学术论文 30 余篇。 肖宏图，硕士研究生，主要研究方 向为路径规划算法、移动机器人。 ·552· 智 能 系 统 学 报 第 15 卷