Multi-Bug全局路径规划算法研究

彭 艳 鲍凌志 瞿 栋 解杨敏

(1.上海大学无人艇工程研究院， 上海 200444； 2.上海大学上海市智能制造与机器人重点实验室， 上海 200444)

0 引言

路径规划[1]是移动机器人在复杂环境中实现自主行动能力的关键技术之一。路径长度、实时性以及工作代价值等是评估路径规划算法的性能指标[2]，不同的应用场合对于路径规划算法有着不同的特性需求。

以对环境信息的认知范围区分[3]，路径规划算法可分为完整地图信息已知的全局路径规划和部分地图信息实时更新的局部路径规划。全局路径规划按照优化算法可以分为随机采样类算法、群体智能优化算法、图搜索类算法等[4]。随机采样类算法主要包括快速扩展随机树(RRT)算法[5-6]和概率路线图(PRM)算法[7]，在高维状态空间应用广泛，其搜索能力强，但该类算法运算成本高、随机性强[8]。群体智能优化算法主要包括遗传算法[9]、蚁群算法[10-11]、粒子群算法[12-13]等。遗传算法和蚁群算法适用于复杂问题的求解和优化，能同时处理多个个体，易于实现并行性，但是运算效率低；相比较而言，粒子群算法收敛速度快，但易陷入局部最优解。图搜索类算法主要有Dijkstra算法[14]、A*算法[15]、D*算法等。Dijkstra算法是一种典型的最短路径算法，但是存在遍历节点多、效率低下的缺点；A*算法增加了启发式搜索，通过设定启发函数评价路径优劣，倒序找到起点，相比Dijkstra算法减少了搜索量，在计算效率略有提升的同时保证了路径的最优性，但是在环境复杂、地图规划较大时，耗时仍然过长。尽管如此，A*算法依然是目前广泛使用的路径规划算法[16]。对于上述的全局优化算法，爬行虫(Bug)系列算法具有明显的实时计算优势。Bug系列算法是完全应激式算法的典型代表[17-18]，也是局部路径规划中常见的算法，包括 Bug1、Bug2[19]、Dist-Bug[20]和Rev-Bug[21]等。Bug2、Dist-Bug、Rev-Bug在应用细节上对Bug1进行了不同程度的改进。其中，表现较为突出的是Dist-Bug方法。虽然Bug系列算法在计算实时性能上有非常突出的表现，但由于其完全应激的基本特性，得到的路径长度明显较长。

为此，本文提出基于多爬虫机制的Mutli-Bug避障寻路算法。其改进思路是：相对于单爬虫的寻路策略，当遇到障碍物时爬虫进行分裂，同时沿不同的避障方向进行探索，并设置一定的爬虫死亡条件。此分裂死亡过程不断进行，直到最快的一只爬虫抵达终点，得到一条最优路径。这样在保留Bug算法简单寻路规则的同时也保证最终路径的相对最优性，因此，能够形成以部分路径长度为代价、降低运算成本的全局路径规划算法。

1 Dist-Bug算法简介

Bug系列算法最初是在二维未知的复杂障碍环境下通过传感器实时传输环境信息进行实时路径规划的算法。其基本原理包括2种基本运动模式：模式1，向终点直线移动；模式2，障碍物绕行。通过两个模式互相转换，Bug算法可实时调整其路径规划策略直到抵达终点。在直线移动模式下，爬虫由当前点沿着指向终点方向移动，直到抵达终点，或是遇到障碍物进行模式切换；在障碍物绕行模式下，爬虫绕行障碍物，并同时判断是否满足转换为模式1的条件。不同的Bug算法主要区别在于其障碍物绕行策略及模式切换策略不同。为了便于理解本文的Multi-Bug算法，详细描述作为其基础架构的具有代表性的Dist-Bug算法，算法框架如图1所示。

图1 Dist-Bug算法框架图Fig.1 Dist-Bug algorithm framework diagram

图2 基于模式1的两种路径规划情况Fig.2 Two path planning cases based on mode 1

爬虫当前位置x(视为1个质点)，启用模式1时会发生2种情况(图2)：①直接到达终点T，路径规划算法停止。②碰到障碍物，将这一点表示为Hi点，并切换成模式2。

进入模式2后，爬虫会根据障碍物的边界和碰撞点Hi(第i次从模式1转换到模式2时爬虫位置)位置确定边界初始绕行方向(即在该碰撞点处选择绕行障碍物的方向)，然后沿着障碍物边界移动。Dist-Bug算法中边界绕行方向的选择策略如图3所示，分别比较顺、逆时针绕行方向与当前点指向终点方向对应的夹角α1、α2，选择夹角小的绕行方向，当夹角α1=α2，则优先选择顺时针旋转方向。

图3 模式2中选择初始绕行方向策略Fig.3 Strategy for selecting initial detour direction in mode 2

在模式2的障碍物绕行过程中，需要持续判断是否切换到模式1。Dist-Bug算法的切换条件有2个，即

d(x,T)-F≤0

(1)

d(x,T)-F≤dmin(T)-P(P>0)

(2)

式中d(x,T)——机器人当前位置到终点距离

F——爬虫指向终点方向与第一个可见障碍物的距离

dmin(T)——走过的路径点与终点最近的距离

P——障碍物最小壁厚

图4 绕行过程中的切换条件情况Fig.4 Switching conditions during bypass

满足其中任意一个条件，则切换到模式1，否则继续绕行障碍物(图4)。图4a中，机器人在点Li(第i次从模式2转换到模式1时爬虫位置)处，d(x,T)=d(Li,T)，F=d(Li,T)，满足式(1)；图4b中，机器人在点Li处，d(x,T)=d(Li,T)，F=d(Li,Hi)，dmin(T)=d(Li,T)，满足式(2)。

在Dist-Bug算法中，为避免初始绕行方向不合理还设置了反向绕行条件。在绕行过程中判断当前路径方向与指向障碍物方向夹角α是否大于135°，如果大于则进行最多一次的反向绕行操作，若沿障碍物绕行一周，抵达Hi或者Ri(第i个碰撞点后机器人反向绕行的点)，仍未满足模式切换条件，则判定终点不可达，结束路径规划。不可达情况判定如图5所示，爬虫由起点S出发，启用模式1，至碰撞点H1满足切换条件，启用模式2，在H1选择顺时针绕行至R1点，此处当前路径方向与指向障碍物方向夹角α大于135°，且在碰撞点H1后，没有执行过反向操作，满足反向条件，爬虫选择反向逆时针绕行，至R′1点，由于执行过一次反向操作，所以此处不再反向，继续绕行至反向点R1点，判断终点不可达，结束路径规划。

图5 没有可行路径Fig.5 No feasible path

以上Dist-Bug的伪代码算法表示：

(1)建立栅格地图。

(2)初始化i=0，绕行标志G=1并设置P为壁厚。

While (1)

If (G==1) 进入模式1

递增i并向终点移动，直到出现以下情况之一：

①抵达终点，停止，退出While循环。②遇到障碍物，将这一点坐标表示为Hi，G赋值为2。

End

If(G==2) 进入模式2

判断转向并跟随障碍物边界，同时连续更新最小值dmin(T)。直到出现以下情况之一：

①终点可见，即满足d(x,T)-F≤0。将爬虫当前点表示为Li，G赋值为1。②如果离开绕行障碍物条件成立，即满足d(x,T)-F≤dmin(T)-P，将爬虫当前点表示为Li，G赋值为1。③判断当前路径方向与指向障碍物方向夹角是否大于135°。如果大于135°,满足反向第1个条件，再判断是否已经有反向点Ri。无，满足反向第2个条件，取反向处点为Ri,反向；有反向点Ri，则不再反向。④判断Ri是否有值。无，机器人完成了一个循环并达到了Hi，终点无法访问，停止，退出While循环；有，机器人完成了一个循环并达到了Ri，终点无法访问，停止，退出While循环。

End

End

Dist-Bug算法能够在未知环境信息的情况下，根据自身位置信息、任务信息以及实时的传感器测量信息，实时高效地调整自身姿态，选择运动模式，规划出到达终点的路径。但正因其算法设计基于有限的局部环境信息，当将其应用于全局路径规划时，其决策缺乏对路径长度优化策略的考虑，通常会给出远超过最优路径长度的规划结果。

2 Multi-Bug全局路径规划

2.1 算法介绍

Multi-Bug算法属于全局路径规划，环境信息均为已知，使用2种同样的基本运动模式。模式1，向终点直线移动；模式2，障碍物绕行。爬虫遇到障碍物时，爬虫分裂生成2条路径，由模式1切换至模式2，分别顺逆时针绕行障碍物各自前行；如此循环，直到其中一个爬虫率先抵达终点。Multi-Bug算法框架图如图6所示。

图6 Multi-Bug算法框架图Fig.6 Multi-Bug algorithm framework diagram

启用模式1时，如图7所示。在此模式下需要持续判断是否发生以下3种情况：①遇到新的碰撞点Hi点，爬虫生成顺、逆时针两个绕行方向的路径，如图7a所示，并切换成模式2。②遇到以前的碰撞点，舍弃当前这条路径，如图7b所示, 路径L″i绕行一圈回到碰撞点Hi，该条路径舍弃。③满足抵达终点条件，输出可行路径，路径规划算法结束。

图7 基于模式1的第1、2种情况Fig.7 Case 1 and case 2 based on mode 1

进入模式2以后，需要持续判断是否发生以下3种情况：①满足条件d(x,T)-F≤0，直接达到终点，路径规划算法成功停止。②满足条件d(x,T)-F≤dmin(T)-P，切换成模式1离开障碍物，这里与Dist-Bug算法相同。③遇到以前的碰撞点，舍弃当前这条路径，如图8所示。爬虫遇到碰撞点Hi后，生成L′i和L″i2条绕行路径，随后路径L″i遇到新的碰撞点Hi+1，生成L′i+1和L″i+12条路径，此时共有3条同时循迹的路径L′i、L′i+1和L″i+1。路径L′i+1绕行时遇到以前的碰撞点Hi，舍弃。

图8 模式2中遇到以前碰撞点的情况Fig.8 Previous collision points encountered based on mode 2

当所有路径都停止循迹且未找到终点时，说明终点不可达，停止循迹，如图9所示。爬虫由起点走到H1点后，分别顺逆时针方向绕行障碍物，直到顺时针绕行路线(红色)和逆时针绕行路线(紫色)分别碰到以前的碰撞点H1。说明没有可行解。

图9 没有可行路径的情况Fig.9 No feasible path

Multi-Bug算法中基本操作为移动栅格，时间复杂度为O(n)，各情况判断条件时间复杂度也为O(n)；设操作中同时存在的最大爬虫个数为常数M，算法总时间复杂度将满足条件

T(n)≤CMn

(3)

式中C——常数系数n——问题规模

因此Multi-Bug算法时间复杂度为O(n)，这一点将在之后的仿真中予以验证。

Multi-Bug算法的伪代码表示为：

(1)建立栅格地图。

(2)输入起点S、终点T以及障碍物信息，初始化一条爬虫路径，P取3,以及绕行标志G=0，即默认启用模式1。

While (1)

计算出现有路径个数M；

If(M==0)

输出无解；退出While循环；

End

For (i=0;i≤M;i++)

If (G==0) 进入模式1

向终点方向移动一个栅格；更新dmin(T)；

①判断该点是否为新的碰撞点。是，爬虫在新的碰撞点处分裂出2条路径，更新路径G值；否，继续。②判断该点是否为以前的碰撞点Hi。是，退出For循环，舍弃该条路径；否，继续。③判断该点是否为终点；是，退出While循环，输出路径；否，继续For循环。

Else 进入模式2

绕行障碍物一个栅格；更新dmin(T)。①判断该点是否满足离开障碍物条件d(x,T)-F≤dmin(T)-P。满足，更新路径G值;不满足，继续。②判断该点是否为以前的碰撞点Hi。是，退出For循环，舍弃该条路径；否，继续For循环。

End

End

End

Multi-Bug算法在已知环境信息的情况下，根据环境信息以及任务信息，选择运动模式，生成多条路径，实时高效规划出到达终点的路径。因Multi-Bug算法基于局部路径规划算法Dist-Bug设计，不进行大范围搜索，所以具有高时效性的特点；Multi-Bug算法有着全局环境信息，相当于多爬虫同时进行路径探索并且输出路径为所有爬虫可行解中最优，路径长度能够实现局部最优。

2.2 算法证明分析

假定在已知的有限面积环境信息下，起点S到终点T的直线距离为E，中间随机分布着个数为K的有限个不规则多边形的障碍物，其中障碍物的边界周长最大值为Q。

(1) 路径有限性：在有限的路径长度下停止Multi-Bug算法。

证明：Multi-Bug算法生成的路径包括向终点直线运动模式下生成的路径和障碍物边界跟随模式下生成的路径2部分，证明路径有限性只需证明在2种模式下算法路径长度有限，且模式1、2切换次数有限。

模式1下每一段直线路径长度小于E，因为每一次由模式2切换到模式1均满足条件式(2)或是条件式(1)。模式2生成的每一段路径长度不会超过障碍物的周长Q，因此2种模式下算法路径长度均有限。

模式2切换到模式1条件式(1)在输出路径中只发生一次，因为机器人在此条件成立后，直接到达目标；条件式(2)可以发生K次，K≤E/P[20]。机器人在第K+1次遇到障碍物时，有2种可能：直接抵达终点或者路径形成环路，Multi-Bug算法停止。因此2种模式切换次数有限，定理得证。

(2)有解可达性：只要从起点到终点有可行路径，Multi-Bug算法一定可以到达终点。

证明：证明路径有解可达，先证明舍弃的路径不会造成可行解的丢失，接着证明有解时，不会提前退出算法，导致可行解无法输出。

路径舍弃条件1：遇到以前的碰撞点，舍去，因为继续绕行下去会与在该碰撞点处另一绕行方向的路径重复；路径舍弃条件2：有可行解抵达路径。这两种均不会造成可行解丢失。

算法结束条件1，有爬虫路径抵达终点，输出可行解。结束条件2，判断所有爬虫路径均无效舍弃，此时无可行路径。因此结束条件不会导致有可行解时提前结束算法，一定会有输出路径，或是判定无解，定理得证。

(3)路径局域最优性：利用Multi-Bug算法得到的最后输出路径，一定是诸多可行路径中最短的。

证明：证明路径最优性，先证明得到的路径不会有重复路径出现，接着证明输出路径是所有可行路径中最短的。

如果其中一条路径遇到以前的碰撞点，该路径直接删除，因为在该碰撞点，顺、逆时针2个绕行方向已经经历过，从而保证了每一条路径里都不会有重复的相同路径段出现。

如果有可行路径已经达到终点，会直接输出可行路径，并且停止更新其他路径，不会出现重复输出第2条更长路径的现象。因此利用Multi-Bug算法最后的输出路径，一定是其诸多可行路径中最短的，定理得证。

3 算法仿真验证

Multi-Bug算法是一种全局路径规划算法，该算法相比于搜索类路径规划算法是以有限的路径长度换取运算效率的很大提升。为了进一步验证Multi-Bug算法相较于传统路径规划算法在路径长度及运算时间成本方面的性能优劣，本文分别复现了代表性的路径规划方案Dist-Bug算法、A*算法和RRT*算法，通过对比算法输出路径长度和运算时间来比较算法性能。运行算法计算机配置为Xeon(R) E3-1230 v2@3.30 GHz *8 CPU； ubuntu 16.04系统；Matlab R2017b软件。为保证运算结果可靠性，对同样的栅格地图中每个算法运行10次，其运算时间取平均值。为了验证算法的通用性，本文测试了各算法在包括障碍物规则类图形、障碍物不规则类图形以及迷宫类图形的多类栅格地图下的路径规划性能。

在本文复现的算法中，RRT*算法性能依赖于其参数设置。随机生成的点越多，得到可行路径的概率越大，但是运算时间也越长；搜索半径越大，得到的更短路径长度概率越大，运算时间越长；搜索步长通常小于搜索半径。综合考虑路径长度和运算时间，本文中选取参数为随机生成点共2 000个，搜索半径取15(栅格数，下同)，搜索步长5。因为RRT*算法的随机性，导致其每次得到的路径长度不同，时间不同，这里给出的时间和长度为10次仿真的平均值，给出的仿真图选择路径长度最接近平均值的一组图。

各算法在多类地图中的路径规划结果数据对比见表1。

表1 算法运算时间和路径长度汇总Tab.1 Summary of algorithm operation time and path length

3.1 多类地图路径规划性能比较

3.1.1凸多边形障碍物地图

在如图10所示的规则凸多边形障碍物地图中，均匀密集地分布着正方形障碍物。各算法具体运算时间、路径长度见表1。从路径长度上分析，Multi-Bug、Dist-Bug和A*算法得到路径长度结果基本相似，与路径最短的A*算法相比路径长度分别增加了4.3%、14.1%；RRT*得到的路径最长，超过A*近40%。从运算时间上分析，Multi-Bug算法与Dist-Bug算法用时均小于0.3 s，比A*算法用时减小了约90%。Dist-Bug算法时间最短，但在中间路径判断绕行方向时(见图10b红框内路径)，出现了遇顶点多解情况。如图11所示，在碰撞点Hi处，最佳绕行方向应该逆时针，图中顺时针绕行；在碰撞点Hi+1处，最佳绕行方向为顺时针，图中逆时针绕行。这两处问题的原因相同，因为碰撞点恰巧在障碍物顶点处，导致确定碰撞点Hi遇到障碍物的边界时出现问题。这一绕行算法的局限在文献[20]中并没有提及。

图10 凸多边形障碍物地图中的各算法路径规划结果比较(100×100)Fig.10 Comparison of path planning results in convex polygon obstacle maps (100×100)

图11 Dist-Bug算法初始方向判断问题Fig.11 Problem of initial direction judgment of Dist-Bug algorithm

3.1.2凹多边形障碍物地图

在图12存在凹多边形障碍物的地图中，随机分布形状各异的障碍物，Multi-Bug算法、Dist-Bug算法、A*算法和RRT*算法具体规划路径长度、运算时间见表1。从路径长度上分析，A*得到的路径长度最短，而Multi-Bug算法和Dist-Bug算法、RRT*算法得到路径长度基本相同，相差小于3%；从时间上分析，A*算法与RRT*算法运算时间均长于1 s，近乎于Multi-Bug算法和Dsit-Bug算法运算时间的5倍。

图12 凹多边形障碍物地图中的各算法路径规划结果比较(50×50)Fig.12 Comparison of path planning results in concave polygon obstacle maps (50×50)

3.1.3迷宫类地图

图13～15所示的迷宫类地图(编号为地图1～3)被认为是路径规划问题中较难解决的一类复杂地形，在这类地形中的路径规划通常需要更长的计算时间，也更考验算法的综合性能，4种算法具体运算时间和路径规划长度见表1。

图13 迷宫类地图1中的各算法路径规划结果比较(50×50)Fig.13 Comparison of path planning results in maze map 1 (50×50)

图14 迷宫类地图2中的各算法路径规划结果比较(65×75)Fig.14 Comparison of path planning results in maze map 2 (65×75)

图15 迷宫类地图3中的各算法路径规划结果比较(50×50)Fig.15 Comparison of path planning results in maze map 3 (50×50)

在迷宫类地图1、2中，4种算法均得到可行路径。A*得到的路径长度最短，平均值为76，RRT*算法平均路径长度为84，Multi-Bug算法平均路径长度为91，这3种算法路径相差小于20%，而Dist-Bug算法平均路径最长为182，是前3者的2倍多。时间上Multi-Bug算法平均用时最短，为0.26 s，A*算法平均用时1.31 s，5倍于Multi-Bug算法，RRT*算法平均时间依然是最长，为7.47 s。

在迷宫类地图3中，只有3种算法得到可行路径，A*算法路径最短，Multi-Bug算法路径长度与A*算法相比增加了17.5%，Dist-Bug算法路径最长，是A*算法的5倍多，RRT*算法无解。时间上依然是Multi-Bug算法最短，为0.26 s，A*算法耗时达到Multi-Bug算法的8倍多，在无解的情况下RRT*算法运算时间超过1 min，因为完整地产生了2 000次随机数。

3.1.4无可行路径类地图

在图16无可行路径类地图中，测试在此极端情况下各算法运算性能，Multi-Bug算法得出无解结论的时间最短(0.34 s)、不到A*算法的1/10，表现最为优异。

图16 迷宫类地图4，无可行路径(50×50)Fig.16 Maze map 4, no feasible path (50×50)

3.2 Multi-Bug与A*算法性能比较分析

综合以上所有类型地图的路径规划性能对比，结合表1数据分析可知，本文Multi-Bug算法在3.1.1～3.1.3节这3类地图中生成的平均路径长度为80.6，仅次于A*算法的69.0，具体如图17所示。与A*算法相比，Multi-Bug算法给出的平均路径长度仅增加了16.8%，平均用时减少了86.5%，仅为0.27 s，在4种算法中用时最短，达到了在尽可能不增加路径长度的同时大大提升计算效率的目的。Multi-Bug算法时间标准差也是4种算法中最小的，只有0.034 5 s，足以说明Multi-Bug算法具有更好的稳定性。Multi-Bug算法在每一类场景地图中都能高效得出可行解，适应性同样可以得到保证。

图17 Multi-Bug算法和A*算法对比Fig.17 Multi-Bug algorithm and A* algorithm path length histograms

图18 Multi-Bug算法与A*算法时间趋向对比Fig.18 Comparison of time trend between Multi-Bug algorithm and A* algorithm

Multi-Bug算法参考了局部路径规划算法Dist-Bug算法的框架，遵循简单寻路规则而非进行泛搜索，如图18所示，Multi-Bug算法时间在500×500的栅格地图中接近于A*算法时间的万分之一。 A*算法时间复杂度为O(n2)，而Multi-Bug算法时间复杂度只有O(n)，这是其计算效率高的根本原因。而因其同一时间并行更新多条路径并取其最优，所以得到的路径相比传统Bug算法更优，且其在不同复杂度地图中用时变化量很小，具有更好的计算性能稳定性。

3.3 实际应用案例

图19为引用文献[22]中的图像，图19a是美国亚拉巴马州拉塞尔县本宁堡住户实景拍摄图像，图19b为本宁堡住户整体地图数据，路径任务是从一户人家导航至另一户人家。将图19a连续空间缩减为一个离散图，分布着若干形状各异的图形，分别代表着不同的住户的房屋，栅格化处理后，分别利用Multi-Bug、Dist-Bug、A*和RRT*算法进行路径规划得到如图20所示结果。

图19 从本宁堡获得的用于测试的数据Fig.19 Data acquired from Fort Benning and used for testing

图20 实际应用类地图(280×400)Fig.20 Practical application map (280×400)

由图20可以看出，Multi-Bug和A*算法得到路径长度结果基本相近，分别为337和320；Dist-Bug算法路径较长，为360；RRT*算法得到的路径最长，超过A*算法29.3%。从运算时间上分析，Multi-Bug与Dist-Bug算法用时均小于1 s，分别为0.859 0、0.500 7 s。A*算法超过10 min，为678.608 0 s。Multi-Bug与A*算法相比路径长度增加了5.3%，但是用时减少了99.9%。

3.4 Multi-Bug失效情况讨论

在以往Bug系列算法文献中没有提及但值得注意的是：当应用于离散栅格地图时，Bug系列算法在某种极端情况下会存在找不到可行路径的情况，这一特点也被Multi-Bug算法继承。当地图中存在单栅格通道时，如图21所示，因通道栅格与多个障碍物边界接触，算法绕行策略可能失效。图21a与图21b唯一不同之处为终点不同，导致图21a有解，图21b无解。图21b中因为碰撞点H3正好在唯一可行路径L2行下面，当路径经过碰撞点H4绕行障碍物遇到以前的碰撞点H3时舍去，因而错过唯一可行路径。这一问题通常不影响Bug算法在实际地图中的应用，一个简单的解决方案为将离散栅格尺寸设为最小通道宽度的1/2以下。而在实际应用中当地图中存在着极窄通道时，通常会判定机器人通行安全性较低，从而舍弃其作为可行路径的可能。

图21 Multi-Bug在离散栅格中的错误无解问题Fig.21 Missing feasible solution by Multi-Bug algorithm in discrete grids

4 结束语

经过理论分析及仿真验证，提出的Multi-Bug算法充分利用了Bug系列算法的非搜索特性，同时引入多虫并行寻路策略，以优选最短路径。相较于传统的搜索类算法，其路径长度增加有限，而计算复杂度只有O(n)。相对于一般的最优化算法和图搜索算法，具有更强的目标导引性、更少的随机性和优化算法依赖性。仿真结果显示，在3类有可行路径的复杂地图下，该算法均能在稳定短时间内给出可行的规划路径，即使在无可行路径的情况下，也会在短时间内给出无解的结论，满足机器人全局路径规划算法对路径较优、时效性强、算法稳定性好的性能需求。因此，在处理大型复杂地图或者强调实时计算的场景中，Multi-Bug算法具有较强的应用优势。本文Multi-Bug算法处理的是全局静态环境下的路径规划问题，对于其在动态空间或者高维地形下的应用拓展还有待进一步研究。