特征地图的室内机器人路径规划融合算法

刘 朋，任工昌

陕西科技大学 机电工程学院，西安 710021

随着自动化与人工智能技术的发展，在工农业生产和日常生活中出现了越来越多的移动机器人，它们能够完成多种任务，减轻人们的劳动负担。例如在工业领域，存在着大量物料抓取及搬运工作，但车间内的工作环境一般存在温度高、湿度大、声音嘈杂，甚至有毒等问题，而且各类设施密集，空间环境复杂，各项工作重复性高，因此特别适合移动机器人替代人来完成。

机器人在室内自主移动，先要进行路径规划，环境地图作为先验信息是路径规划中不可或缺的。机器人技术中环境地图常使用特征地图和栅格地图。特征地图[1]简单直观、模型数据量少、计算效率高，适用于结构化较好的室内环境，但是特征地图中常用的角点或线段中点等点特征对环境细节表达不足，因此很难直接用于路径规划，一般常被用于机器人定位算法。栅格地图因其简单，易于创建和维护，不受地形限制等众多优点被大部分路径规划算法所采用，但是，随着环境规模扩大，使用栅格地图时消耗算力和存储空间的增长速度远高于环境规模的增长速度，因此使用栅格地图的算法在环境规模较大时普遍存在计算效率较低的问题[2]。

在路径规划方面，根据机器人对地图掌握的情况，可以分为全局路径规划与局部路径规划[3]。全局路径规划算法种类较多，以蚁群算法[4-5]、遗传算法[6-7]、人工神经网络[8-9]和粒子群算法[10-11]为代表的智能算法适用于复杂问题的求解和优化，易于实现并行性，但是容易陷入局部最优解或出现收敛速度慢的问题。以快速扩展随机树（rapidly-exploring random tree，RRT）算法[12-13]为代表的随机采样算法搜索能力强，在高维状态空间应用广泛，但是该类算法运算成本高、随机性强。以A*算法[14-15]为代表的启发式搜索算法是目前使用较广泛的一种路径规划算法，但是其存在搜索效率低、拐点多、路径不平滑等缺点。Petri网建模与整数线性规划也被用来解决路径规划问题，但是这些方法必须事先建立好Petri 网模型，无法进行实时路径规划，一般应用于多任务、多约束的复杂场景[16]。Bug 系列算法[17]属于应激式算法，在计算实时性方面有非常突出的表现，但由于其完全应激的基本特性，得到的路径长度明显较长。Dijkstra 算法也是一种较为常用路径规划算法，其优点是算法简单方便，可以获取全局最优路径，但是同样存在计算效率低、冗余拐点多、离障碍物近等问题[18]。文献[19]利用几何拓扑学方法，结合实际场景信息，对Dijkstra 算法规划的路径进行平滑处理，减少了路径中的冗余节点和机器人的累计转弯角度，但仍没有改变算法计算效率低的问题。人工势场法[20]和动态窗口法（dynamic window approach，DWA）[21]是普遍使用的局部路径规划算法。人工势场法结构简单，能够实现实时避障，但其存在规划路径过长和局部最优点的情况[22]。DWA通过当前时刻对周围环境采样，获得下一时刻机器人的运动状态，因此，规划的路径平滑性更好，但该算法缺少前瞻性，且高度依赖全局参数，容易陷入局部最优解，出现路径规划失败[23]。为了克服以上单一算法的不足，多采用算法融合的方法，文献[24]提出一种融合改进A*蚁群算法与动态窗口法的平滑路径规划方法，解决前期蚁群效率低、易陷入局部最优等问题，而且使用贝塞尔曲线对规划的路径进行平滑化处理，使路径更接近实际移动路径；文献[25-26]分别采用关键点优化策略和双向搜索的方法对A*算法进行改进，通过改进的A*搜索出全局最短路径的关键节点，再融合DWA算法规划节点间的路径，使整条路径平滑；文献[27]在算法融合时，对航向角的选择进行了优化，使规划的路径更平滑。但以上融合算法均使用栅格地图，且关键节点的搜索使用A*算法，仍然无法避免出现算法计算效率低的问题。

特征地图中的点（线段中点）特征无法直接用于路径规划，但是线段本身可以表达障碍物的轮廓，且其具有方向、长度等属性，因此，包含完整属性的线段特征不仅可以进行路径规划，还可以提高路径搜索的速度，并且充分体现特征地图计算效率高的优点。本文提出一种基于特征地图的路径规划融合算法。首先，给出了线段特征的表达方式和障碍物检测方法；然后，结合Bug算法的基本原理，提出一种基于特征地图的搜索优化算法，通过先搜索再优化的方式快速获得最优路径的关键节点；接下来，分析了DWA算法中全局参数在不同阶段对规划路径的影响程度，对目标函数进行改进，降低了DWA 算法对全局参数的敏感性；最后，将提出的搜索优化算法与改进后的DWA进行融合，使算法的计算效率大幅度提高，同时规划出的路径更优。

1 特征地图及障碍物检测

特征地图是将原始观测数据经过分割、合并后提取出的点、线、弧等几何特征，并用这种离散特征来描述环境的地图形式。路径规划时，特征地图中的线段特征能够表示环境中障碍物的范围和方向，因此，地图可表示为线段特征的集合QL：

其中，(xi,yi)为线段中点的坐标，θi为线段的倾角，li为线段的长度。

在栅格地图中，进行障碍物检测时，应计算机器人与地图中障碍物（点）间的距离，而在特征地图中则转换为计算机器人到特征地图中障碍物（线段）间的距离。机器人与障碍物线段间的距离有两种情况：如果机器人中心点到障碍物线段的投影在该线段上，则该距离为投影点至机器人中心的距离，如图1（a）所示；如果机器人中心到障碍物线段的投影点在该线段外，则该距离为机器人至线段端点（距离投影点较近的端点）的距离，如图1（b）所示。如果di大于阈值，则检测到障碍物。图1 中，蓝色圆圈表示机器人，pR为中心点，Li为障碍物线段，为点pR在线段Li或其延长线上的投影，pLi为线段Li的端点。

图1 机器人与障碍物距离示意图Fig.1 Diagram of distance between robot and obstacle

机器人与障碍物间距离的计算步骤为：

（1）根据机器人中心点pR的坐标(xR,yR)和障碍物线段Li的特征QLi，计算投影pR′的坐标(,)；

（2）计算pR′到障碍物线段中点(xi,yi) 的距离；

（3）如果≤li/2，则在线段Li上，di为pR与两点之间的距离，dp=0；

（4）否则，在线段Li的延长线上，分别计算其与线段Li两端点pi1和pi2之间的距离dp1和dp2，dp=min(dp1,dp2)，为pR与两点之间的距离，则：

2 全局路径搜索及优化

全局路径规划时，A*的计算效率较低，规划的路径拐点较多，也影响了融合算法的结果。因此，结合特征地图中障碍物具有方向性的特点，使用Bug算法的原理，快速搜索可行路径节点，再经过节点优化得到最优路径，可以大幅提高算法的计算效率。

2.1 Bug算法简介

Bug算法原理类似昆虫爬行的运动决策策略，其包括两种基本运动模式：模式1，在未遇到障碍物时，沿直线向目标运动；模式2，在遇到障碍物后，沿着障碍物边界绕行。通过两个模式互相转换，Bug算法可实时调整其路径规划策略直到抵达终点。不同的Bug 算法主要区别在于其障碍物绕行策略及模式切换策略不同。如图2 所示为Bug1 算法原理示意图，灰色矩形表示障碍物，绿色圆圈为起点，红色三角为目标点，虚线箭头表示搜索的路径。爬虫先以起点和目标点连线方向作为爬行方向，当遇到障碍物时，沿障碍物外围轮廓爬行，当再回到目标连线上后，继续沿目标方向爬行，直至到达目标点。

图2 Bug1算法原理示意图Fig.2 Schematic diagram of Bug1 algorithm principle

Bug 算法能够在未知环境的情况下，根据自身位置、目标及传感器测量信息，实时地规划出到达终点的路径。但该算法应用于全局路径规划时，由于其基于有限的局部路径信息做出的决策缺乏对路径长度的考虑，通常规划的路径会远超过最优路径长度，而且平滑性较差，不能很好适应机器人的运动特性。

2.2 搜索优化算法原理

在进行路径搜索时，机器人从起点沿终点方向以单位步长向前搜索，检测到障碍物时，即图1 中di小于安全距离dsafe时，该位置为转折点。如果转折点处障碍物Li倾角为θi，且该转折点为首次出现，如图3（a）中点，则在此处机器人转向θi方向搜索；如果该转折点已在其他路径中出现过，如图3（b）中点，则机器人在此处转向θi+π 方向搜索，直至远离障碍物Li，机器人重新沿终点方向搜索。当机器人与终点连线和所有障碍物线段均不相交，而且与障碍物间距离大于安全距离时，该条路径搜索结束。图3中，Li为障碍物线段，绿色△表示目标位置，绿色〇表示机器人起点位置，蓝色虚线〇表示路径节点位置，、、分别表示转折点、角点和障碍物端点，桔色箭头表示路径搜索方向。

一条路径搜索完成后，将起点至终点间的所有节点pi作为该条规划路径。如果搜索时某个节点在同一条搜索路径中第二次出现，则该条路径不可行，进入下一条路径搜索。为了避免出现搜索路径重复或遗漏，应依次从所有已出现的转折点中的最后一个开始判断。搜索出所有可行路径后，将路程最短的一条进行节点优化，获得最优路径的关键节点。图3中共搜索出3条可行路径，路径3的路程最短，但其中是多余节点，经过优化后的最优路径如图3（d）所示[28]。

搜索优化算法利用Bug算法搜索效率高的优点，使用特征地图又进一步降低障碍物碰撞检测和沿障碍物边界搜索时的计算难度，提高了计算效率；同时，通过节点优化可以使得最终规划路径为最优路径，避免出现Bug算法搜索路径过长的问题。

2.3 角点问题

室内环境中存在着许多拐角，对应于特征地图中的角点，也代表着两条线段特征相交于此点。根据机器人与角点之间的位置关系，可将角点分为内角点与外角点，如图4 所示。La、Lb表示障碍物线段，蓝色圆圈表示机器人，黑色箭头表示机器人当前位置的航向角，绿色箭头表示机器人移动路径。

图4 角点位置示意图Fig.4 Diagram of corner point position

如果机器人处于内角点位置，则其搜索路径的方向是确定的，如图4（a）所示，机器人应转向与线段Lb平行且竖直向下的方向搜索；如果机器人处于如图4（b）所示外角点位置，则其应以线段La为障碍物，继续沿当前方向搜索，直至远离线段La后，再沿目标位置方向搜索；如果机器人处于如图4（c）所示外角点位置，则选择与当前搜索方向相交的线段Lb作为障碍物，按前述方法继续搜索。

2.4 障碍物端点绕行问题

当机器人沿障碍物线段搜索并远离该障碍物后，如果目标位置与机器人当前搜索方向相反，则可能出现机器人与目标位置的连线始终和障碍物相交的情况，如图5中桔色虚线箭头所示。在障碍物端点处机器人应采取绕行的方式，即先沿垂直于障碍物的方向移动一段距离，离开障碍物后再继续沿目标位置搜索。图5 中，机器人在蓝色虚线〇位置时，dpi大于安全距离dsafe，表示机器人已离开当前障碍物线段Li，然后搜索转向沿与障碍物线段垂直的方向，在蓝色实线〇位置，大于安全距离dsafe，则可转向目标位置方向搜索，其中虚线与实线桔色箭头分别表示机器人在虚线与实线位置与目标位置的方向。

图5 线段端点绕行搜索示意图Fig.5 Schematic diagram of searching for going around endpoint of line segment

2.5 路径优化

由于搜索时，大部分路径是沿着与障碍物线段平行方向搜索，搜索后路程最短的一条也可能不是最优路径，还需要对其进行优化，删除冗余节点，如图3（c）中pt1。在待优化的路径中，假设连续相邻的3个节点分别是pi-1、pi、pi+1，如果由节点pi-1和pi+1作为端点构成的线段Lpi与地图内任意障碍物线段Li均不相交，且与Li之间距离大于安全距离dsafe，则可将节点pi从路径中删除，否则，节点pi不能删除。

相邻两节点间路径如果过长，则可能导致无法合并的情况，同时为了提高优化算法的计算效率，使用了一种变分割参数的方法。算法流程图如图6 所示，disdiv为分割参数，插入的新节点方向应与该段路径移动方向一致，优化结束后，若某节点与其前一节点的方向相同，则该节点可作为多余节点删除。

图6 路径优化算法流程图Fig.6 Flow chart of path optimization algorithm

3 DWA算法及改进

DWA 是目前较为成熟，且在栅格地图中得到广泛使用的一种局部路径规划算法。该算法在机器人运动过程中，通过机器人自身的运动特性和给定的预估周期，计算出下一采样周期内机器人所能达到的速度空间(vt,ωt)。然后，通过目标函数计算出在该范围内机器人下一时刻的最优线速度与角速度。由于目标函数同时考虑了目标方向、机器人速度及其与障碍物栅格间的距离，可以较好地实现机器人的避障功能。在特征地图中，应使用式（2）进行障碍物检测。

3.1 传统DWA算法

DWA 实现的是一个速度空间约束的优化问题，根据机器人自身硬件条件的限制，其应满足速度、动力学和安全三项约束，以此来确定机器人运动时的速度范围V，然后通过式（3）所示的目标函数对上述速度范围V内一系列可行的轨迹进行评价，将目标函数G(v,ω)值最大时对应的轨迹作为最优轨迹，则该轨迹对应的线速度vt和角速度ωt即为下一周期机器人运动的速度。

式（3）中各具体函数如下：

式中，(xt,yt)表示机器人在预测轨迹末端时的位置，θt表示机器人在(xt,yt)时的航向角与目标方向的夹角，dist则表示在(xt,yt)时机器人与所有障碍物线段间的最小距离，其中di由式（2）计算，vt表示机器人在(xt,yt)时的运动线速度；α、β、γ为权重系数，代表该项在目标函数中的影响程度。机器人在每一个采样周期内均按照规划的线速度和角速度前进，当机器人与目标位置之间的距离小于阈值disfth，则路径规划结束。为了避免权重系数差异过大，一般需要将目标函数中的三项数据进行归一化处理。

3.2 DWA算法的改进

DWA算法在使用时，目标函数式（3）中3个分项函数的权重系数均为常数，但是机器人移动过程是动态变化的，3个函数对于规划路径的影响程度也因机器人所处位置的不同而不断变化。在某些特殊位置，固定值的权重系数很容易使算法陷入局部最优解。

图7 所示为当机器人起点位置与目标位置之间存在障碍物，α、β和γ不同取值时规划路径的结果，其中○代表起点位置，*表示目标位置，黑色粗实线表示障碍物，蓝色细实线表示规划路径。

图7 不同权重系数时规划路径的情况Fig.7 Path planning with different weight coefficients

由于dist函数主要影响机器人与障碍物之间的距离，主要改变了α和γ两个参数。在图7（a）中，当α=1，β=1，γ=1 时，初始阶段heading函数项影响较大，机器人的移动方向即为最优方向。为了避免碰撞，dist函数使机器人减速，直至停止移动而无法继续规划路径；增大velocity函数的权重，可以使机器人提前绕开障碍物而改变速度方向，但在接近目标位置时由于速度影响过大而出现发散，始终无法到达目标位置；只有当α和γ取值比例合适时，机器人才能顺利到达目标位置，如图7（e）所示。

通过分析得出，机器人与目标位置之间的距离distgoal、与障碍物之间的最小距离distobt和α、β、γ有密切关系，α与distgoal成反比，与distobt成正比，β与distobt成反比，γ与distgoal成正比。因此，本文对DWA 算法中的目标函数进行了改进，得到新的目标函数为：

另一方面教师在教学过程中大量采用项目化与“基于工作过程”的项目化教学改革，通过教学方式的改革将课堂教学模式变得活跃，同时让学生参与度提高，也能让学生体验到将来工作岗位所需要完成的工作任务，对比传统教学在教学效果上有较大提高。但在实施过程中仍然会出现部分学生学习积极性较差以及各课程课外任务繁重，最后学生失去完成课程项目任务耐性的现象。

改进后的DWA 算法降低了对目标函数中权重系数的敏感性，减小了陷入局部最优的可能，从而提高了路径规划的成功率。

4 融合算法

由搜索优化算法得到的全局最优路径节点集合Pathnode为：

其中，Ps为起点，Pe为终点，Pi为中间节点。

路径中的n+2 个节点将全局路径分为n+1 段局部路径，则局部路径集合Path为：

在(Ps,P1)段内，使用改进的DWA算法规划由Ps到P1的路径，当机器人与P1点间的距离小于阈值disfth时，该段局部路径规划结束，将机器人当前位置、航向角及速度作为初始参数，继续使用改进的DWA 算法完成下一段(P1,P2)内的局部路径规划，直至机器人到达终点Pe附近，各段局部路径规划的结果合并即为最终规划的完整路径。

使用融合算法时，为了保证局部路径规划与全局路径规划的结果相符，在目标函数式（5）的基础上增加了distpath(v,ω)项，即：

distpath(v,ω)函数为：

其中，dpl(v,ω)表示机器人在预测轨迹末端时，其与该段局部路径内始末点连线间的距离，δ为distpath(v,ω)函数的权重系数，为了避免该项函数值为负，distpath值最小为0。

机器人在局部路径规划时的终点Pi处（全局路径的中间节点）会出现不必要的减速，因此，判断算法停止的阈值disfth应不小于安全距离dsafe；同时，根据DWA 算法原理，在Pi点附近时，如果预测轨迹末端越过Pi点，夹角θ将急剧增大，heading项函数值迅速减小，也会使机器人出现明显减速。如图8（a）所示，蓝色圆圈表示机器人，细实线表示可行轨迹，*表示局部路径的终点Pi，浅蓝色虚线圆圈、绿色箭头和红色箭头分别表示机器人在预测轨迹末端时的位置、航向角和其与Pi点之间的方位角。针对该情况，在以中间节点Pi为局部路径规划终点计算heading函数时，使用夹角θ′，即heading=π-θ′，如图8（b）所示，红色细箭头表示机器人在当前位置与Pi点之间的方位角。

图8 heading 函数中θ 角改进前后示意图Fig.8 Schematic diagram of θ before and after improvement in heading function

5 仿真实验与分析

为验证本文算法的性能及有效性，在Matlab2016b中对算法进行了仿真验证和对比分析，计算机平台CPU 为Intel Core i5-6300U，内存8 GB，操作系统为64位Windows 10。

5.1 搜索优化算法仿真

模拟室内的复杂环境，以某楼梯形平台为基础，使用7 个不同的立方体作为障碍物，建立如图9所示仿真环境的特征地图，任意选取两点作为起点和终点，分别使用搜索优化算法和A*算法进行路径规划。

图9 搜索路径与A*算法规划路径对比Fig.9 Path planning comparison of searching path with A*algorithm

搜索算法中参数dsafe=0.3 m，step=0.08 m，经过10 次搜索得到2 条可行路径，优化后计算总耗时为1.1 s。A*算法中栅格的分辨率为0.1 m，计算耗时共12.6 s。图9 中粗实线表示障碍物，蓝色圆圈表示起点（1.5,-1），桔色三角表示终点（7,-2.5），蓝色虚线与绿色点线分别表示搜索出的两条可行路径，其中绿色点线为路程最短，经过优化后的最优路径为红色细实线，紫色点划线为A*算法规划的路径。由结果可以发现，搜索得到的路径优化后明显更短，与A*算法规划的路径相似，但在计算耗时方面要远优于A*算法。

5.2 改进DWA算法仿真

为验证改进后DWA 算法规划路径的性能及其对目标函数中全局参数的敏感性，在图7所示的仿真环境中，使用不同的权重系数分别进行路径规划，结果为图10和表1所示。

表1 目标函数改进前后规划路径性能参数对比Table 1 Comparison of planning path performance parameters before and after objective function improvement

图10 改进目标函数后规划的路径Fig.10 Path after improving objective function

图10 为α1=1，α2=1，β=1，γ=2 时规划的路径及各项函数权重变化的趋势。表1 为不同权重系数下规划路径的性能参数对比。其中，移动耗时为机器人按规划的路径点移动时耗费的全部时间，路径平滑度的定义为：规划的路径点中，曲率半径大于0.5 m的点在全部路径点中的占比。由图10（b）可以发现，目标函数中的3个分项函数权重的变化趋势与前文分析一致，符合机器人在不同位置时的运动规律。

表1 中，使用改进后的目标函数，除第7 组无法完成，其余组均完成路径规划，而且路径的性能均优于目标函数改进前，说明改进后的算法对权重系数的敏感性较低。算法中使用的其他参数：采样周期2 s，最大线速度1 m/s，最大角速度30(°)/s，速度和角速度分辨率分别为0.2 m/s 和1(°)/s，Δt=0.1 s，disfth=0.06 m，dsafe=0.3 m。

5.3 融合算法仿真及对比分析

进一步验证提出的融合算法有效性及计算效率，在图9 中选取6 组起点与终点，分别采用本文融合算法、文献[25]中的融合算法以及文献[19]中的Dijkstra与DWA融合的算法进行路径规划，以下简称算法A、B 和C，结果如图11 和表2 所示。红色细实线、蓝色虚线和绿色点划线分别表示A、B、C 算法规划的路径，*、+和△分别表示由搜索优化算法、改进A*算法和Dijkstra算法规划出的路径节点。表2中对三种算法规划路径性能进行对比，最小距离为整条路径中机器人与障碍物间的最小距离。算法B 和C由于规划路径的最小距离均远小于安全距离，在进行局部路径规划时增加了0.3 m（安全距离）的膨胀距离。算法A中α1=1，α2=1，β=1，γ=3，δ=5。算法B 和C 中局部路径规划的目标函数使用式（10），α=2，β=1，γ=3，δ=5，其他参数与前文相同。

表2 三种融合算法规划路径性能对比Table 2 Comparison of path performance of three fusion algorithms

图11 三种融合算法规划路径对比Fig.11 Comparison of three fusion algorithms for planned path

由表2 中对比结果发现，算法A、B、C 均能顺利规划出全部路径。在路径总里程方面，算法A的路径最短，与算法B 相比最多短12.32%（第1 组），与算法C相比最多短14.15%（第3组）。在最小距离方面，算法A略小于另两种算法，但是算法B和C的最小距离是在增加膨胀距离后得到的。算法A中的最小距离主要由搜索优化时的dsafe决定，并且可以改变dsafe的值来改变最小距离，而A*和Dijkstra算法规划的路径节点离障碍物更近，且无法改变，只能通过局部路径规划时增加膨胀距离来避免机器人与障碍物发生碰撞。机器人移动耗时方面，算法A 均优于算法B 和C，移动耗时最多分别减少28.66%（第1组）和45.96%（第3 组），最少分别减少17.30%（第5 组）和19.90%（第5 组），排除路径总里程的影响因素（第4 组），说明算法A规划的路径可以获得更高的平均线速度，同时算法A消除了机器人在中间节点出现的不必要减速，使机器人移动过程更平顺。在平滑度方面，三种算法规划的路径均较好，但算法A 和B 优于算法C。在计算耗时方面，算法A 明显优于算法B 和C，计算耗时最多分别减小79.27%（第6 组）和68.33%（第2组），最少分别减小43.16%（第5 组）和62.67%（第1组），主要由于算法A中基于特征地图的搜索优化算法相较于A*和Dijkstra算法计算效率较高，随着规划路径长度的增加和地图复杂程度的提高，这种优势将越加明显。另外，算法A在中间节点较少的情况下仍能得到质量更高的路径，说明改进后的DWA算法的适应性更好。因此，经过综合对比，在复杂环境下，本文融合算法能够实现规划的路径更优，同时计算效率更高。

6 结论

利用特征地图模型数量少、计算效率高的优点，提出一种基于特征地图且融合了搜索优化与改进DWA 的路径规划算法，该算法适用于室内复杂环境中机器人的路径规划。首先，给出了能够用于路径规划的特征地图表达方式，并针对特征地图，改进了障碍物检测方法。然后，结合Bug算法的基本原理和线段特征具有方向性等特点，提出基于特征地图的搜索优化算法，实现全局最优路径的快速搜索，并针对搜索过程中内外角点搜索方向选择、障碍物端点绕行等问题进行了分析并提出解决方法。接下来，针对DWA算法对全局参数敏感、容易陷入局部最优的问题，分析了目标函数中各分项函数在路径规划过程中的影响权重，提出了新的目标函数。最后，在算法融合时，为避免机器人在中间节点出现明显减速，对目标函数中heading项的计算方法进行了改进。在同等仿真条件下进行对比验证，结果表明搜索优化算法具有较高的计算效率，改进后的DWA能够降低其对全局参数的敏感性而且规划的路径质量更高，提出的融合算法与其他融合算法相比，规划的路径总里程最多减小14.15%，移动耗时最多减小45.96%，计算耗时最多减小79.27%，而且机器人移动更平滑，特别适合于室内复杂场景中的路径规划。