彭 艷 鮑凌志 瞿 棟 解楊敏

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

0 引言

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

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

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

1 Dist-Bug算法簡介

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

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

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

圖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)——機器人當前位置到終點距離

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

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

P——障礙物最小壁厚

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

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

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

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

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

(1)建立柵格地圖。

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

While (1)

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

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

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

End

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

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

①終點可見，即滿足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是否有值。無，機器人完成了一個循環(huán)并達到了Hi，終點無法訪問，停止，退出While循環(huán)；有，機器人完成了一個循環(huán)并達到了Ri，終點無法訪問，停止，退出While循環(huán)。

End

End

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

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

2.1 算法介紹

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

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

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

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

進入模式2以后，需要持續(xù)判斷是否發(fā)生以下3種情況：①滿足條件d(x,T)-F≤0，直接達到終點，路徑規(guī)劃算法成功停止。②滿足條件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)；設操作中同時存在的最大爬蟲個數(shù)為常數(shù)M，算法總時間復雜度將滿足條件

T(n)≤CMn

(3)

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

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

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

(1)建立柵格地圖。

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

While (1)

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

If(M==0)

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

End

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

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

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

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

Else 進入模式2

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

End

End

End

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

2.2 算法證明分析

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法仿真驗證

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

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

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

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

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

3.1.1凸多邊形障礙物地圖

在如圖10所示的規(guī)則凸多邊形障礙物地圖中，均勻密集地分布著正方形障礙物。各算法具體運算時間、路徑長度見表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紅框內路徑)，出現(xiàn)了遇頂點多解情況。如圖11所示，在碰撞點Hi處，最佳繞行方向應該逆時針，圖中順時針繞行；在碰撞點Hi+1處，最佳繞行方向為順時針，圖中逆時針繞行。這兩處問題的原因相同，因為碰撞點恰巧在障礙物頂點處，導致確定碰撞點Hi遇到障礙物的邊界時出現(xiàn)問題。這一繞行算法的局限在文獻[20]中并沒有提及。

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

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

3.1.3迷宮類地圖

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

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

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

圖15 迷宮類地圖3中的各算法路徑規(guī)劃結果比較(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次隨機數(shù)。

3.1.4無可行路徑類地圖

在圖16無可行路徑類地圖中，測試在此極端情況下各算法運算性能，Multi-Bug算法得出無解結論的時間最短(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ī)劃性能對比，結合表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種算法中用時最短，達到了在盡可能不增加路徑長度的同時大大提升計算效率的目的。Multi-Bug算法時間標準差也是4種算法中最小的，只有0.034 5 s，足以說明Multi-Bug算法具有更好的穩(wěn)定性。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算法參考了局部路徑規(guī)劃算法Dist-Bug算法的框架，遵循簡單尋路規(guī)則而非進行泛搜索，如圖18所示，Multi-Bug算法時間在500×500的柵格地圖中接近于A*算法時間的萬分之一。 A*算法時間復雜度為O(n2)，而Multi-Bug算法時間復雜度只有O(n)，這是其計算效率高的根本原因。而因其同一時間并行更新多條路徑并取其最優(yōu)，所以得到的路徑相比傳統(tǒng)Bug算法更優(yōu)，且其在不同復雜度地圖中用時變化量很小，具有更好的計算性能穩(wěn)定性。

3.3 實際應用案例

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

圖19 從本寧堡獲得的用于測試的數(shù)據(jù)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算法繼承。當?shù)貓D中存在單柵格通道時，如圖21所示，因通道柵格與多個障礙物邊界接觸，算法繞行策略可能失效。圖21a與圖21b唯一不同之處為終點不同，導致圖21a有解，圖21b無解。圖21b中因為碰撞點H3正好在唯一可行路徑L2行下面，當路徑經過碰撞點H4繞行障礙物遇到以前的碰撞點H3時舍去，因而錯過唯一可行路徑。這一問題通常不影響B(tài)ug算法在實際地圖中的應用，一個簡單的解決方案為將離散柵格尺寸設為最小通道寬度的1/2以下。而在實際應用中當?shù)貓D中存在著極窄通道時，通常會判定機器人通行安全性較低，從而舍棄其作為可行路徑的可能。

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

4 結束語

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