彭 艷 鮑凌志 瞿 棟 解楊敏

(1.上海大學(xué)無人艇工程研究院， 上海 200444； 2.上海大學(xué)上海市智能制造與機(jī)器人重點(diǎn)實驗室， 上海 200444)

0 引言

路徑規(guī)劃[1]是移動機(jī)器人在復(fù)雜環(huán)境中實現(xiàn)自主行動能力的關(guān)鍵技術(shù)之一。路徑長度、實時性以及工作代價值等是評估路徑規(guī)劃算法的性能指標(biāo)[2]，不同的應(yīng)用場合對于路徑規(guī)劃算法有著不同的特性需求。

以對環(huán)境信息的認(rèn)知范圍區(qū)分[3]，路徑規(guī)劃算法可分為完整地圖信息已知的全局路徑規(guī)劃和部分地圖信息實時更新的局部路徑規(guī)劃。全局路徑規(guī)劃按照優(yōu)化算法可以分為隨機(jī)采樣類算法、群體智能優(yōu)化算法、圖搜索類算法等[4]。隨機(jī)采樣類算法主要包括快速擴(kuò)展隨機(jī)樹(RRT)算法[5-6]和概率路線圖(PRM)算法[7]，在高維狀態(tài)空間應(yīng)用廣泛，其搜索能力強(qiáng)，但該類算法運(yùn)算成本高、隨機(jī)性強(qiáng)[8]。群體智能優(yōu)化算法主要包括遺傳算法[9]、蟻群算法[10-11]、粒子群算法[12-13]等。遺傳算法和蟻群算法適用于復(fù)雜問題的求解和優(yōu)化，能同時處理多個個體，易于實現(xiàn)并行性，但是運(yùn)算效率低；相比較而言，粒子群算法收斂速度快，但易陷入局部最優(yōu)解。圖搜索類算法主要有Dijkstra算法[14]、A*算法[15]、D*算法等。Dijkstra算法是一種典型的最短路徑算法，但是存在遍歷節(jié)點(diǎn)多、效率低下的缺點(diǎn)；A*算法增加了啟發(fā)式搜索，通過設(shè)定啟發(fā)函數(shù)評價路徑優(yōu)劣，倒序找到起點(diǎn)，相比Dijkstra算法減少了搜索量，在計算效率略有提升的同時保證了路徑的最優(yōu)性，但是在環(huán)境復(fù)雜、地圖規(guī)劃較大時，耗時仍然過長。盡管如此，A*算法依然是目前廣泛使用的路徑規(guī)劃算法[16]。對于上述的全局優(yōu)化算法，爬行蟲(Bug)系列算法具有明顯的實時計算優(yōu)勢。Bug系列算法是完全應(yīng)激式算法的典型代表[17-18]，也是局部路徑規(guī)劃中常見的算法，包括 Bug1、Bug2[19]、Dist-Bug[20]和Rev-Bug[21]等。Bug2、Dist-Bug、Rev-Bug在應(yīng)用細(xì)節(jié)上對Bug1進(jìn)行了不同程度的改進(jìn)。其中，表現(xiàn)較為突出的是Dist-Bug方法。雖然Bug系列算法在計算實時性能上有非常突出的表現(xiàn)，但由于其完全應(yīng)激的基本特性，得到的路徑長度明顯較長。

為此，本文提出基于多爬蟲機(jī)制的Mutli-Bug避障尋路算法。其改進(jìn)思路是：相對于單爬蟲的尋路策略，當(dāng)遇到障礙物時爬蟲進(jìn)行分裂，同時沿不同的避障方向進(jìn)行探索，并設(shè)置一定的爬蟲死亡條件。此分裂死亡過程不斷進(jìn)行，直到最快的一只爬蟲抵達(dá)終點(diǎn)，得到一條最優(yōu)路徑。這樣在保留Bug算法簡單尋路規(guī)則的同時也保證最終路徑的相對最優(yōu)性，因此，能夠形成以部分路徑長度為代價、降低運(yùn)算成本的全局路徑規(guī)劃算法。

1 Dist-Bug算法簡介

Bug系列算法最初是在二維未知的復(fù)雜障礙環(huán)境下通過傳感器實時傳輸環(huán)境信息進(jìn)行實時路徑規(guī)劃的算法。其基本原理包括2種基本運(yùn)動模式：模式1，向終點(diǎn)直線移動；模式2，障礙物繞行。通過兩個模式互相轉(zhuǎn)換，Bug算法可實時調(diào)整其路徑規(guī)劃策略直到抵達(dá)終點(diǎn)。在直線移動模式下，爬蟲由當(dāng)前點(diǎn)沿著指向終點(diǎn)方向移動，直到抵達(dá)終點(diǎn)，或是遇到障礙物進(jìn)行模式切換；在障礙物繞行模式下，爬蟲繞行障礙物，并同時判斷是否滿足轉(zhuǎn)換為模式1的條件。不同的Bug算法主要區(qū)別在于其障礙物繞行策略及模式切換策略不同。為了便于理解本文的Multi-Bug算法，詳細(xì)描述作為其基礎(chǔ)架構(gòu)的具有代表性的Dist-Bug算法，算法框架如圖1所示。

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

圖2 基于模式1的兩種路徑規(guī)劃情況Fig.2 Two path planning cases based on mode 1

爬蟲當(dāng)前位置x(視為1個質(zhì)點(diǎn))，啟用模式1時會發(fā)生2種情況(圖2)：①直接到達(dá)終點(diǎn)T，路徑規(guī)劃算法停止。②碰到障礙物，將這一點(diǎn)表示為Hi點(diǎn)，并切換成模式2。

進(jìn)入模式2后，爬蟲會根據(jù)障礙物的邊界和碰撞點(diǎn)Hi(第i次從模式1轉(zhuǎn)換到模式2時爬蟲位置)位置確定邊界初始繞行方向(即在該碰撞點(diǎn)處選擇繞行障礙物的方向)，然后沿著障礙物邊界移動。Dist-Bug算法中邊界繞行方向的選擇策略如圖3所示，分別比較順、逆時針繞行方向與當(dāng)前點(diǎn)指向終點(diǎn)方向?qū)?yīng)的夾角α1、α2，選擇夾角小的繞行方向，當(dāng)夾角α1=α2，則優(yōu)先選擇順時針旋轉(zhuǎn)方向。

圖3 模式2中選擇初始繞行方向策略Fig.3 Strategy for selecting initial detour direction in mode 2

在模式2的障礙物繞行過程中，需要持續(xù)判斷是否切換到模式1。Dist-Bug算法的切換條件有2個，即

d(x,T)-F≤0

(1)

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

(2)

式中d(x,T)——機(jī)器人當(dāng)前位置到終點(diǎn)距離

F——爬蟲指向終點(diǎn)方向與第一個可見障礙物的距離

dmin(T)——走過的路徑點(diǎn)與終點(diǎn)最近的距離

P——障礙物最小壁厚

圖4 繞行過程中的切換條件情況Fig.4 Switching conditions during bypass

滿足其中任意一個條件，則切換到模式1，否則繼續(xù)繞行障礙物(圖4)。圖4a中，機(jī)器人在點(diǎn)Li(第i次從模式2轉(zhuǎn)換到模式1時爬蟲位置)處，d(x,T)=d(Li,T)，F(xiàn)=d(Li,T)，滿足式(1)；圖4b中，機(jī)器人在點(diǎn)Li處，d(x,T)=d(Li,T)，F(xiàn)=d(Li,Hi)，dmin(T)=d(Li,T)，滿足式(2)。

在Dist-Bug算法中，為避免初始繞行方向不合理還設(shè)置了反向繞行條件。在繞行過程中判斷當(dāng)前路徑方向與指向障礙物方向夾角α是否大于135°，如果大于則進(jìn)行最多一次的反向繞行操作，若沿障礙物繞行一周，抵達(dá)Hi或者Ri(第i個碰撞點(diǎn)后機(jī)器人反向繞行的點(diǎn))，仍未滿足模式切換條件，則判定終點(diǎn)不可達(dá)，結(jié)束路徑規(guī)劃。不可達(dá)情況判定如圖5所示，爬蟲由起點(diǎn)S出發(fā)，啟用模式1，至碰撞點(diǎn)H1滿足切換條件，啟用模式2，在H1選擇順時針繞行至R1點(diǎn)，此處當(dāng)前路徑方向與指向障礙物方向夾角α大于135°，且在碰撞點(diǎn)H1后，沒有執(zhí)行過反向操作，滿足反向條件，爬蟲選擇反向逆時針繞行，至R′1點(diǎn)，由于執(zhí)行過一次反向操作，所以此處不再反向，繼續(xù)繞行至反向點(diǎn)R1點(diǎn)，判斷終點(diǎn)不可達(dá)，結(jié)束路徑規(guī)劃。

圖5 沒有可行路徑Fig.5 No feasible path

以上Dist-Bug的偽代碼算法表示：

(1)建立柵格地圖。

(2)初始化i=0，繞行標(biāo)志G=1并設(shè)置P為壁厚。

While (1)

If (G==1) 進(jìn)入模式1

遞增i并向終點(diǎn)移動，直到出現(xiàn)以下情況之一：

①抵達(dá)終點(diǎn)，停止，退出While循環(huán)。②遇到障礙物，將這一點(diǎn)坐標(biāo)表示為Hi，G賦值為2。

End

If(G==2) 進(jìn)入模式2

判斷轉(zhuǎn)向并跟隨障礙物邊界，同時連續(xù)更新最小值dmin(T)。直到出現(xiàn)以下情況之一：

①終點(diǎn)可見，即滿足d(x,T)-F≤0。將爬蟲當(dāng)前點(diǎn)表示為Li，G賦值為1。②如果離開繞行障礙物條件成立，即滿足d(x,T)-F≤dmin(T)-P，將爬蟲當(dāng)前點(diǎn)表示為Li，G賦值為1。③判斷當(dāng)前路徑方向與指向障礙物方向夾角是否大于135°。如果大于135°,滿足反向第1個條件，再判斷是否已經(jīng)有反向點(diǎn)Ri。無，滿足反向第2個條件，取反向處點(diǎn)為Ri,反向；有反向點(diǎn)Ri，則不再反向。④判斷Ri是否有值。無，機(jī)器人完成了一個循環(huán)并達(dá)到了Hi，終點(diǎn)無法訪問，停止，退出While循環(huán)；有，機(jī)器人完成了一個循環(huán)并達(dá)到了Ri，終點(diǎn)無法訪問，停止，退出While循環(huán)。

End

End

Dist-Bug算法能夠在未知環(huán)境信息的情況下，根據(jù)自身位置信息、任務(wù)信息以及實時的傳感器測量信息，實時高效地調(diào)整自身姿態(tài)，選擇運(yùn)動模式，規(guī)劃出到達(dá)終點(diǎn)的路徑。但正因其算法設(shè)計基于有限的局部環(huán)境信息，當(dāng)將其應(yīng)用于全局路徑規(guī)劃時，其決策缺乏對路徑長度優(yōu)化策略的考慮，通常會給出遠(yuǎn)超過最優(yōu)路徑長度的規(guī)劃結(jié)果。

2 Multi-Bug全局路徑規(guī)劃

2.1 算法介紹

Multi-Bug算法屬于全局路徑規(guī)劃，環(huán)境信息均為已知，使用2種同樣的基本運(yùn)動模式。模式1，向終點(diǎn)直線移動；模式2，障礙物繞行。爬蟲遇到障礙物時，爬蟲分裂生成2條路徑，由模式1切換至模式2，分別順逆時針繞行障礙物各自前行；如此循環(huán)，直到其中一個爬蟲率先抵達(dá)終點(diǎn)。Multi-Bug算法框架圖如圖6所示。

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

啟用模式1時，如圖7所示。在此模式下需要持續(xù)判斷是否發(fā)生以下3種情況：①遇到新的碰撞點(diǎn)Hi點(diǎn)，爬蟲生成順、逆時針兩個繞行方向的路徑，如圖7a所示，并切換成模式2。②遇到以前的碰撞點(diǎn)，舍棄當(dāng)前這條路徑，如圖7b所示, 路徑L″i繞行一圈回到碰撞點(diǎn)Hi，該條路徑舍棄。③滿足抵達(dá)終點(diǎn)條件，輸出可行路徑，路徑規(guī)劃算法結(jié)束。

圖7 基于模式1的第1、2種情況Fig.7 Case 1 and case 2 based on mode 1

進(jìn)入模式2以后，需要持續(xù)判斷是否發(fā)生以下3種情況：①滿足條件d(x,T)-F≤0，直接達(dá)到終點(diǎn)，路徑規(guī)劃算法成功停止。②滿足條件d(x,T)-F≤dmin(T)-P，切換成模式1離開障礙物，這里與Dist-Bug算法相同。③遇到以前的碰撞點(diǎn)，舍棄當(dāng)前這條路徑，如圖8所示。爬蟲遇到碰撞點(diǎn)Hi后，生成L′i和L″i2條繞行路徑，隨后路徑L″i遇到新的碰撞點(diǎn)Hi+1，生成L′i+1和L″i+12條路徑，此時共有3條同時循跡的路徑L′i、L′i+1和L″i+1。路徑L′i+1繞行時遇到以前的碰撞點(diǎn)Hi，舍棄。

圖8 模式2中遇到以前碰撞點(diǎn)的情況Fig.8 Previous collision points encountered based on mode 2

當(dāng)所有路徑都停止循跡且未找到終點(diǎn)時，說明終點(diǎn)不可達(dá)，停止循跡，如圖9所示。爬蟲由起點(diǎn)走到H1點(diǎn)后，分別順逆時針方向繞行障礙物，直到順時針繞行路線(紅色)和逆時針繞行路線(紫色)分別碰到以前的碰撞點(diǎn)H1。說明沒有可行解。

圖9 沒有可行路徑的情況Fig.9 No feasible path

Multi-Bug算法中基本操作為移動?xùn)鸥?，時間復(fù)雜度為O(n)，各情況判斷條件時間復(fù)雜度也為O(n)；設(shè)操作中同時存在的最大爬蟲個數(shù)為常數(shù)M，算法總時間復(fù)雜度將滿足條件

T(n)≤CMn

(3)

式中C——常數(shù)系數(shù)n——問題規(guī)模

因此Multi-Bug算法時間復(fù)雜度為O(n)，這一點(diǎn)將在之后的仿真中予以驗證。

Multi-Bug算法的偽代碼表示為：

(1)建立柵格地圖。

(2)輸入起點(diǎn)S、終點(diǎn)T以及障礙物信息，初始化一條爬蟲路徑，P取3,以及繞行標(biāo)志G=0，即默認(rèn)啟用模式1。

While (1)

計算出現(xiàn)有路徑個數(shù)M；

If(M==0)

輸出無解；退出While循環(huán)；

End

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

If (G==0) 進(jìn)入模式1

向終點(diǎn)方向移動一個柵格；更新dmin(T)；

①判斷該點(diǎn)是否為新的碰撞點(diǎn)。是，爬蟲在新的碰撞點(diǎn)處分裂出2條路徑，更新路徑G值；否，繼續(xù)。②判斷該點(diǎn)是否為以前的碰撞點(diǎn)Hi。是，退出For循環(huán)，舍棄該條路徑；否，繼續(xù)。③判斷該點(diǎn)是否為終點(diǎn)；是，退出While循環(huán)，輸出路徑；否，繼續(xù)For循環(huán)。

Else 進(jìn)入模式2

繞行障礙物一個柵格；更新dmin(T)。①判斷該點(diǎn)是否滿足離開障礙物條件d(x,T)-F≤dmin(T)-P。滿足，更新路徑G值;不滿足，繼續(xù)。②判斷該點(diǎn)是否為以前的碰撞點(diǎn)Hi。是，退出For循環(huán)，舍棄該條路徑；否，繼續(xù)For循環(huán)。

End

End

End

Multi-Bug算法在已知環(huán)境信息的情況下，根據(jù)環(huán)境信息以及任務(wù)信息，選擇運(yùn)動模式，生成多條路徑，實時高效規(guī)劃出到達(dá)終點(diǎn)的路徑。因Multi-Bug算法基于局部路徑規(guī)劃算法Dist-Bug設(shè)計，不進(jìn)行大范圍搜索，所以具有高時效性的特點(diǎn)；Multi-Bug算法有著全局環(huán)境信息，相當(dāng)于多爬蟲同時進(jìn)行路徑探索并且輸出路徑為所有爬蟲可行解中最優(yōu)，路徑長度能夠?qū)崿F(xiàn)局部最優(yōu)。

2.2 算法證明分析

假定在已知的有限面積環(huán)境信息下，起點(diǎn)S到終點(diǎn)T的直線距離為E，中間隨機(jī)分布著個數(shù)為K的有限個不規(guī)則多邊形的障礙物，其中障礙物的邊界周長最大值為Q。

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

證明：Multi-Bug算法生成的路徑包括向終點(diǎn)直線運(yùn)動模式下生成的路徑和障礙物邊界跟隨模式下生成的路徑2部分，證明路徑有限性只需證明在2種模式下算法路徑長度有限，且模式1、2切換次數(shù)有限。

模式1下每一段直線路徑長度小于E，因為每一次由模式2切換到模式1均滿足條件式(2)或是條件式(1)。模式2生成的每一段路徑長度不會超過障礙物的周長Q，因此2種模式下算法路徑長度均有限。

模式2切換到模式1條件式(1)在輸出路徑中只發(fā)生一次，因為機(jī)器人在此條件成立后，直接到達(dá)目標(biāo)；條件式(2)可以發(fā)生K次，K≤E/P[20]。機(jī)器人在第K+1次遇到障礙物時，有2種可能：直接抵達(dá)終點(diǎn)或者路徑形成環(huán)路，Multi-Bug算法停止。因此2種模式切換次數(shù)有限，定理得證。

(2)有解可達(dá)性：只要從起點(diǎn)到終點(diǎn)有可行路徑，Multi-Bug算法一定可以到達(dá)終點(diǎn)。

證明：證明路徑有解可達(dá)，先證明舍棄的路徑不會造成可行解的丟失，接著證明有解時，不會提前退出算法，導(dǎo)致可行解無法輸出。

路徑舍棄條件1：遇到以前的碰撞點(diǎn)，舍去，因為繼續(xù)繞行下去會與在該碰撞點(diǎn)處另一繞行方向的路徑重復(fù)；路徑舍棄條件2：有可行解抵達(dá)路徑。這兩種均不會造成可行解丟失。

算法結(jié)束條件1，有爬蟲路徑抵達(dá)終點(diǎn)，輸出可行解。結(jié)束條件2，判斷所有爬蟲路徑均無效舍棄，此時無可行路徑。因此結(jié)束條件不會導(dǎo)致有可行解時提前結(jié)束算法，一定會有輸出路徑，或是判定無解，定理得證。

(3)路徑局域最優(yōu)性：利用Multi-Bug算法得到的最后輸出路徑，一定是諸多可行路徑中最短的。

證明：證明路徑最優(yōu)性，先證明得到的路徑不會有重復(fù)路徑出現(xiàn)，接著證明輸出路徑是所有可行路徑中最短的。

如果其中一條路徑遇到以前的碰撞點(diǎn)，該路徑直接刪除，因為在該碰撞點(diǎn)，順、逆時針2個繞行方向已經(jīng)經(jīng)歷過，從而保證了每一條路徑里都不會有重復(fù)的相同路徑段出現(xiàn)。

如果有可行路徑已經(jīng)達(dá)到終點(diǎn)，會直接輸出可行路徑，并且停止更新其他路徑，不會出現(xiàn)重復(fù)輸出第2條更長路徑的現(xiàn)象。因此利用Multi-Bug算法最后的輸出路徑，一定是其諸多可行路徑中最短的，定理得證。

3 算法仿真驗證

Multi-Bug算法是一種全局路徑規(guī)劃算法，該算法相比于搜索類路徑規(guī)劃算法是以有限的路徑長度換取運(yùn)算效率的很大提升。為了進(jìn)一步驗證Multi-Bug算法相較于傳統(tǒng)路徑規(guī)劃算法在路徑長度及運(yùn)算時間成本方面的性能優(yōu)劣，本文分別復(fù)現(xiàn)了代表性的路徑規(guī)劃方案Dist-Bug算法、A*算法和RRT*算法，通過對比算法輸出路徑長度和運(yùn)算時間來比較算法性能。運(yùn)行算法計算機(jī)配置為Xeon(R) E3-1230 v2@3.30 GHz *8 CPU； ubuntu 16.04系統(tǒng)；Matlab R2017b軟件。為保證運(yùn)算結(jié)果可靠性，對同樣的柵格地圖中每個算法運(yùn)行10次，其運(yùn)算時間取平均值。為了驗證算法的通用性，本文測試了各算法在包括障礙物規(guī)則類圖形、障礙物不規(guī)則類圖形以及迷宮類圖形的多類柵格地圖下的路徑規(guī)劃性能。

在本文復(fù)現(xiàn)的算法中，RRT*算法性能依賴于其參數(shù)設(shè)置。隨機(jī)生成的點(diǎn)越多，得到可行路徑的概率越大，但是運(yùn)算時間也越長；搜索半徑越大，得到的更短路徑長度概率越大，運(yùn)算時間越長；搜索步長通常小于搜索半徑。綜合考慮路徑長度和運(yùn)算時間，本文中選取參數(shù)為隨機(jī)生成點(diǎn)共2 000個，搜索半徑取15(柵格數(shù)，下同)，搜索步長5。因為RRT*算法的隨機(jī)性，導(dǎo)致其每次得到的路徑長度不同，時間不同，這里給出的時間和長度為10次仿真的平均值，給出的仿真圖選擇路徑長度最接近平均值的一組圖。

各算法在多類地圖中的路徑規(guī)劃結(jié)果數(shù)據(jù)對比見表1。

表1 算法運(yùn)算時間和路徑長度匯總Tab.1 Summary of algorithm operation time and path length

3.1 多類地圖路徑規(guī)劃性能比較

3.1.1凸多邊形障礙物地圖

在如圖10所示的規(guī)則凸多邊形障礙物地圖中，均勻密集地分布著正方形障礙物。各算法具體運(yùn)算時間、路徑長度見表1。從路徑長度上分析，Multi-Bug、Dist-Bug和A*算法得到路徑長度結(jié)果基本相似，與路徑最短的A*算法相比路徑長度分別增加了4.3%、14.1%；RRT*得到的路徑最長，超過A*近40%。從運(yùn)算時間上分析，Multi-Bug算法與Dist-Bug算法用時均小于0.3 s，比A*算法用時減小了約90%。Dist-Bug算法時間最短，但在中間路徑判斷繞行方向時(見圖10b紅框內(nèi)路徑)，出現(xiàn)了遇頂點(diǎn)多解情況。如圖11所示，在碰撞點(diǎn)Hi處，最佳繞行方向應(yīng)該逆時針，圖中順時針繞行；在碰撞點(diǎn)Hi+1處，最佳繞行方向為順時針，圖中逆時針繞行。這兩處問題的原因相同，因為碰撞點(diǎn)恰巧在障礙物頂點(diǎn)處，導(dǎo)致確定碰撞點(diǎn)Hi遇到障礙物的邊界時出現(xiàn)問題。這一繞行算法的局限在文獻(xiàn)[20]中并沒有提及。

圖10 凸多邊形障礙物地圖中的各算法路徑規(guī)劃結(jié)果比較(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存在凹多邊形障礙物的地圖中，隨機(jī)分布形狀各異的障礙物，Multi-Bug算法、Dist-Bug算法、A*算法和RRT*算法具體規(guī)劃路徑長度、運(yùn)算時間見表1。從路徑長度上分析，A*得到的路徑長度最短，而Multi-Bug算法和Dist-Bug算法、RRT*算法得到路徑長度基本相同，相差小于3%；從時間上分析，A*算法與RRT*算法運(yùn)算時間均長于1 s，近乎于Multi-Bug算法和Dsit-Bug算法運(yùn)算時間的5倍。

圖12 凹多邊形障礙物地圖中的各算法路徑規(guī)劃結(jié)果比較(50×50)Fig.12 Comparison of path planning results in concave polygon obstacle maps (50×50)

3.1.3迷宮類地圖

圖13～15所示的迷宮類地圖(編號為地圖1～3)被認(rèn)為是路徑規(guī)劃問題中較難解決的一類復(fù)雜地形，在這類地形中的路徑規(guī)劃通常需要更長的計算時間，也更考驗算法的綜合性能，4種算法具體運(yùn)算時間和路徑規(guī)劃長度見表1。

圖13 迷宮類地圖1中的各算法路徑規(guī)劃結(jié)果比較(50×50)Fig.13 Comparison of path planning results in maze map 1 (50×50)

圖14 迷宮類地圖2中的各算法路徑規(guī)劃結(jié)果比較(65×75)Fig.14 Comparison of path planning results in maze map 2 (65×75)

圖15 迷宮類地圖3中的各算法路徑規(guī)劃結(jié)果比較(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*算法耗時達(dá)到Multi-Bug算法的8倍多，在無解的情況下RRT*算法運(yùn)算時間超過1 min，因為完整地產(chǎn)生了2 000次隨機(jī)數(shù)。

3.1.4無可行路徑類地圖

在圖16無可行路徑類地圖中，測試在此極端情況下各算法運(yùn)算性能，Multi-Bug算法得出無解結(jié)論的時間最短(0.34 s)、不到A*算法的1/10，表現(xiàn)最為優(yōu)異。

圖16 迷宮類地圖4，無可行路徑(50×50)Fig.16 Maze map 4, no feasible path (50×50)

3.2 Multi-Bug與A*算法性能比較分析

綜合以上所有類型地圖的路徑規(guī)劃性能對比，結(jié)合表1數(shù)據(jù)分析可知，本文Multi-Bug算法在3.1.1～3.1.3節(jié)這3類地圖中生成的平均路徑長度為80.6，僅次于A*算法的69.0，具體如圖17所示。與A*算法相比，Multi-Bug算法給出的平均路徑長度僅增加了16.8%，平均用時減少了86.5%，僅為0.27 s，在4種算法中用時最短，達(dá)到了在盡可能不增加路徑長度的同時大大提升計算效率的目的。Multi-Bug算法時間標(biāo)準(zhǔn)差也是4種算法中最小的，只有0.034 5 s，足以說明Multi-Bug算法具有更好的穩(wěn)定性。Multi-Bug算法在每一類場景地圖中都能高效得出可行解，適應(yīng)性同樣可以得到保證。

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

圖18 Multi-Bug算法與A*算法時間趨向?qū)Ρ菷ig.18 Comparison of time trend between Multi-Bug algorithm and A* algorithm

Multi-Bug算法參考了局部路徑規(guī)劃算法Dist-Bug算法的框架，遵循簡單尋路規(guī)則而非進(jìn)行泛搜索，如圖18所示，Multi-Bug算法時間在500×500的柵格地圖中接近于A*算法時間的萬分之一。 A*算法時間復(fù)雜度為O(n2)，而Multi-Bug算法時間復(fù)雜度只有O(n)，這是其計算效率高的根本原因。而因其同一時間并行更新多條路徑并取其最優(yōu)，所以得到的路徑相比傳統(tǒng)Bug算法更優(yōu)，且其在不同復(fù)雜度地圖中用時變化量很小，具有更好的計算性能穩(wěn)定性。

3.3 實際應(yīng)用案例

圖19為引用文獻(xiàn)[22]中的圖像，圖19a是美國亞拉巴馬州拉塞爾縣本寧堡住戶實景拍攝圖像，圖19b為本寧堡住戶整體地圖數(shù)據(jù)，路徑任務(wù)是從一戶人家導(dǎo)航至另一戶人家。將圖19a連續(xù)空間縮減為一個離散圖，分布著若干形狀各異的圖形，分別代表著不同的住戶的房屋，柵格化處理后，分別利用Multi-Bug、Dist-Bug、A*和RRT*算法進(jìn)行路徑規(guī)劃得到如圖20所示結(jié)果。

圖19 從本寧堡獲得的用于測試的數(shù)據(jù)Fig.19 Data acquired from Fort Benning and used for testing

圖20 實際應(yīng)用類地圖(280×400)Fig.20 Practical application map (280×400)

由圖20可以看出，Multi-Bug和A*算法得到路徑長度結(jié)果基本相近，分別為337和320；Dist-Bug算法路徑較長，為360；RRT*算法得到的路徑最長，超過A*算法29.3%。從運(yùn)算時間上分析，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系列算法文獻(xiàn)中沒有提及但值得注意的是：當(dāng)應(yīng)用于離散柵格地圖時，Bug系列算法在某種極端情況下會存在找不到可行路徑的情況，這一特點(diǎn)也被Multi-Bug算法繼承。當(dāng)?shù)貓D中存在單柵格通道時，如圖21所示，因通道柵格與多個障礙物邊界接觸，算法繞行策略可能失效。圖21a與圖21b唯一不同之處為終點(diǎn)不同，導(dǎo)致圖21a有解，圖21b無解。圖21b中因為碰撞點(diǎn)H3正好在唯一可行路徑L2行下面，當(dāng)路徑經(jīng)過碰撞點(diǎn)H4繞行障礙物遇到以前的碰撞點(diǎn)H3時舍去，因而錯過唯一可行路徑。這一問題通常不影響B(tài)ug算法在實際地圖中的應(yīng)用，一個簡單的解決方案為將離散柵格尺寸設(shè)為最小通道寬度的1/2以下。而在實際應(yīng)用中當(dāng)?shù)貓D中存在著極窄通道時，通常會判定機(jī)器人通行安全性較低，從而舍棄其作為可行路徑的可能。

圖21 Multi-Bug在離散柵格中的錯誤無解問題Fig.21 Missing feasible solution by Multi-Bug algorithm in discrete grids

4 結(jié)束語

經(jīng)過理論分析及仿真驗證，提出的Multi-Bug算法充分利用了Bug系列算法的非搜索特性，同時引入多蟲并行尋路策略，以優(yōu)選最短路徑。相較于傳統(tǒng)的搜索類算法，其路徑長度增加有限，而計算復(fù)雜度只有O(n)。相對于一般的最優(yōu)化算法和圖搜索算法，具有更強(qiáng)的目標(biāo)導(dǎo)引性、更少的隨機(jī)性和優(yōu)化算法依賴性。仿真結(jié)果顯示，在3類有可行路徑的復(fù)雜地圖下，該算法均能在穩(wěn)定短時間內(nèi)給出可行的規(guī)劃路徑，即使在無可行路徑的情況下，也會在短時間內(nèi)給出無解的結(jié)論，滿足機(jī)器人全局路徑規(guī)劃算法對路徑較優(yōu)、時效性強(qiáng)、算法穩(wěn)定性好的性能需求。因此，在處理大型復(fù)雜地圖或者強(qiáng)調(diào)實時計算的場景中，Multi-Bug算法具有較強(qiáng)的應(yīng)用優(yōu)勢。本文Multi-Bug算法處理的是全局靜態(tài)環(huán)境下的路徑規(guī)劃問題，對于其在動態(tài)空間或者高維地形下的應(yīng)用拓展還有待進(jìn)一步研究。