自適應(yīng)搜索半徑蟻群動態(tài)路徑規(guī)劃算法

趙 峰，楊春曦，陳 飛，黃凌云，談 誠

1.昆明理工大學(xué) 化學(xué)工程學(xué)院，昆明 650500

2.昆明理工大學(xué) 省部共建復(fù)雜有色金屬資源清潔利用國家重點實驗室，昆明 650093

1 引言

路徑規(guī)劃是指在有障礙物的已知或未知環(huán)境下，移動機器人按照一定的性能指標(biāo)（如距離、時間等），搜索一條從起始位置到目標(biāo)位置的最優(yōu)或次優(yōu)路徑?？紤]到移動機器人在動態(tài)復(fù)雜環(huán)境下的自主導(dǎo)航在無人駕駛領(lǐng)域有巨大的應(yīng)用價值，因此該問題一直是機器人和人工智能研究領(lǐng)域的熱點課題之一[1-3]。

蟻群算法作為仿生智能算法的一種，因其在路徑規(guī)劃中魯棒性能較好、智能搜索、分布式計算和容易與其他算法相結(jié)合的優(yōu)點，被廣泛應(yīng)用于環(huán)境部分未知或全部未知的動態(tài)路徑規(guī)劃中[4-5]。然而，傳統(tǒng)的蟻群算法也存在計算時間長、收斂速度慢、易陷入局部最優(yōu)解等缺陷，因此如何提高蟻群算法在動態(tài)路徑規(guī)劃中的收斂速度，避免局部最優(yōu)值陷阱就成為一個研究熱點[6-12]?；趥鹘y(tǒng)蟻群算法的改進方法大致分為兩類：一類是通過改進蟻群算法本身的結(jié)構(gòu)和參數(shù)優(yōu)化來達到目的，如最大最小蟻群系統(tǒng)[6]、改進距離啟發(fā)因子蟻群算法[7]和角度因子蟻群算法優(yōu)化等[8-9]；而另一類則是利用多種算法相結(jié)合的方法提高性能，如遺傳-蟻群算法[10]、粒子群-蟻群算法[11]和模糊-蟻群算法[12-13]等。在第一類方法中，最大最小蟻群系統(tǒng)算法用于防止算法過早收斂于局部最優(yōu)解問題；文獻[7]通過改進距離啟發(fā)因子來增加目標(biāo)節(jié)點對下一節(jié)點的影響，從而避免陷于局部最優(yōu)解，提高收斂速度；文獻[8-9]結(jié)合具體的應(yīng)用領(lǐng)域約束，基于蟻群算法綜合考慮節(jié)能、能量均勻分布、路徑距離等指標(biāo)下的路徑規(guī)劃問題。而在第二類方法中，主要是利用不同智能算法的互補性，達到提高性能的目的。其中遺傳-蟻群算法的結(jié)合是利用遺傳算法的快速全局搜索能力和蟻群算法的并行、全局收斂能力，形成一種快速性和全局收斂性良好的混合算法；而粒子群-蟻群算法則是利用粒子群算法對蟻群算法的適配參數(shù)進行優(yōu)化，提高其全局尋優(yōu)效率；模糊-蟻群算法主要是利用模糊規(guī)則實現(xiàn)組合算法在環(huán)境未知情況下進行路徑規(guī)劃的自適應(yīng)能力，增加其實用性。雖然組合算法的優(yōu)化效率、收斂速度都有較大提高，但其算法計算量較大，對移動機器人性能要求較高。

上述改進的蟻群算法雖然不同程度地減少了計算時間，提高了搜索效率和收斂速度，但沒有綜合考慮在搜索范圍有限、實時性要求較高和移動機器人計算能力有限的情況下進行動態(tài)路徑規(guī)劃的問題 。為此，這里設(shè)計了一種能在實時性要求內(nèi)，根據(jù)障礙物多少進行搜索半徑自動調(diào)整的自適應(yīng)搜索半徑蟻群動態(tài)路徑規(guī)劃算法（SRL-ACA）。該算法首先按照實時性要求把整個路徑規(guī)劃區(qū)域分割成若干個子區(qū)域，則子區(qū)域的邊界即為實時性要求的上限；然后借鑒滾動窗口法[14-15]思想設(shè)計了一種局部搜索半徑法來描述移動機器人環(huán)境探索能力有限這一約束，并通過把局部搜索半徑設(shè)計成為可以根據(jù)環(huán)境復(fù)雜程度進行自適應(yīng)調(diào)整的方式達到充分利用移動機器人有限的計算能力之目的；最后構(gòu)造了一種隨機輪盤賭方法來選擇局部目標(biāo)點，使得該算法在提高收斂速度的同時，有效降低了陷入局部最優(yōu)的概率。通過3種方法的綜合使用，使得該算法具有在實時性需求較高、未知環(huán)境復(fù)雜和計算能力有限3個約束條件下進行動態(tài)路徑規(guī)劃的能力。此外，仿真實驗表明該算法在路徑距離優(yōu)化、收斂時間優(yōu)化和動態(tài)復(fù)雜環(huán)境自適應(yīng)能力方面均具有較好的綜合性能。

2 問題描述與建模

2.1 環(huán)境建模

為不失一般性，這里采用主流的柵格法來對搜索環(huán)境進行建模。即記G為移動機器人在二維平面內(nèi)的運動區(qū)域，區(qū)域內(nèi)的柵格編號如圖1所示，在G中建立直角坐標(biāo)系，以G左下角為坐標(biāo)零點，橫軸為X軸，縱軸為Y軸。設(shè)在相關(guān)區(qū)域內(nèi)存在若干個障礙物柵格，在圖1中用黑色柵格表示，無障礙物柵格則用白色柵格表示。假設(shè)移動機器人能夠從起始位置經(jīng)過路徑規(guī)劃最終達到目的位置，機器人只在各個柵格內(nèi)的中心點行走，則機器人位置的計算公式為分別為式（1）和式（2）：

其中，a為每個柵格的邊長，橫（縱）坐標(biāo)的最大柵格數(shù)值為MM，柵格總數(shù)為e=MM?MM，每個柵格的坐標(biāo)為，i為每個小正方形的柵格編號，mod為求余運算，而ceil為舍余取整運算。這里假定移動機器人的起始位置和最終目的位置已知。

在動態(tài)路徑規(guī)劃的研究中，通常是以移動機器人為運動載體，而把局部規(guī)劃過程中從局部出發(fā)點至局部最優(yōu)點之間的距離叫做搜索半徑。定半徑指在一次完整的路徑規(guī)劃過程中，每次搜索半徑的長度保持不變，其思想與滾動窗口法相似。該搜索半徑的取值與環(huán)境的實時性成反比，即動態(tài)規(guī)劃要求的實時性越強，則搜索半徑越短。為便于比較，用n步搜索半徑來描述一次局部路徑規(guī)劃所能覆蓋的范圍。當(dāng)移動機器人采用自適應(yīng)搜索半徑算法時，n可以取子區(qū)域內(nèi)任意有限值；當(dāng)移動機器人采用固定搜索半徑算法時，n則為一個固定值。

圖1 柵格法構(gòu)建環(huán)境示意圖

2.2 動態(tài)障礙變化設(shè)置

為比較不同方法在未知障礙環(huán)境下進行動態(tài)路徑規(guī)劃時的特點，這里設(shè)計了一種以時間為變換指標(biāo)的動態(tài)障礙變化規(guī)則，即以移動機器人所行走的次數(shù)來觸發(fā)環(huán)境中障礙分布的變化。例如3次動態(tài)障礙變化規(guī)則為移動機器人的行走次數(shù)為3的整數(shù)倍時進行障礙場景變化，其他次數(shù)時障礙場景保持不變。因此，當(dāng)移動機器人在一個變化周期內(nèi)行走時，該子區(qū)域的障礙分布是固定不變的，移動機器人所在子區(qū)域外的障礙分布與本次路徑規(guī)劃無關(guān)。此外，移動機器人行走次數(shù)與實時性密切相關(guān)，即設(shè)定的次數(shù)越少，實時性越強，全局動態(tài)障礙環(huán)境變化的總次數(shù)越多，要求算法對動態(tài)路徑障礙變化的適應(yīng)能力越強。

圖2 邊尋邊走策略流程圖

3 蟻群算法的改進

3.1 邊尋邊走策略

由于在未知環(huán)境中進行路徑規(guī)劃，每次局部動態(tài)路徑規(guī)劃均需要調(diào)用改進的蟻群算法，因此這里采用邊尋邊走的策略用于局部信息獲取，具體策略如圖2所示。

在該算法中，移動機器人首先要找到最優(yōu)局部目標(biāo)點，然后利用可調(diào)用蟻群算法（Called Ant Colony Algorithm，C-ACA）尋找到達該最優(yōu)局部目標(biāo)點的最佳路徑并行走。當(dāng)機器人到達最優(yōu)局部目標(biāo)點后，需要判斷該局部目標(biāo)點是否為全局目標(biāo)點，若是則整個動態(tài)路徑規(guī)劃結(jié)束；若不是全局目標(biāo)點，則返回尋找下一個搜索半徑內(nèi)的最優(yōu)局部目標(biāo)點，然后重復(fù)上一個循環(huán)，直到找到全局目標(biāo)點為止。因為局部路徑優(yōu)化僅在較小范圍中進行，所以蟻群算法的螞蟻個數(shù)和迭代次數(shù)均可以大大減少，從而節(jié)約了規(guī)劃時間。

3.2 最優(yōu)局部目標(biāo)點的選擇

考慮到SRL-ACA算法在動態(tài)路徑尋優(yōu)過程中，最優(yōu)局部目標(biāo)點的選取方法在很大程度上決定了該算法能否避免陷入局部最優(yōu)解，找到有效最優(yōu)路徑。因此，這里采用了隨機輪盤賭算法（Stochastic Roulette Algorithm，SRA）來確定最優(yōu)局部目標(biāo)點。

輪盤賭策略[16]的核心思想是根據(jù)不同選項的可能性分配相應(yīng)的被選擇概率大小，確保大概率選項有大的被選擇概率的同時，保留其他具有相對較低概率的選項也有被選擇的可能。這種算法可以避免局部最優(yōu)陷阱，缺點是收斂速度較慢。為此，這里提出了一種具有較快收斂速度的隨機輪盤賭算法，具體策略如圖3所示。

圖3 隨機輪盤賭算法流程圖

首先確定局部目標(biāo)點i，i∈allowed，其中allowed為本次搜索半徑內(nèi)，排除已經(jīng)走過的柵格后可以到達的所有非障礙柵格的集合。隨后通過加入一個服從均勻分布的隨機數(shù)作比較，篩選出集合中被選擇概率Pi大于等于rand的局部目標(biāo)點i的集合，最后調(diào)入傳統(tǒng)輪盤賭算法篩選出最優(yōu)局部目標(biāo)點。

注意1隨機輪盤賭算法實際上是基于傳統(tǒng)輪盤賭算法和貪婪算法的一種改良算法，既能夠提高傳統(tǒng)輪盤賭算法的收斂速度，又能夠避免貪婪算法容易陷入局部最優(yōu)值的缺陷。當(dāng)隨機數(shù)rand=0時，該算法等效于傳統(tǒng)輪盤賭算法，能夠避免局部最優(yōu)值陷阱；而當(dāng)rand=max(Pi)時，則該算法相當(dāng)于貪婪算法，具有較快的收斂速度。

4 自適應(yīng)搜索半徑路徑規(guī)劃方法

4.1 局部搜索半徑的選擇

在SRL-ACA算法中，一個關(guān)鍵問題是選擇合適的搜索半徑，以獲得計算能力、尋優(yōu)時間和尋優(yōu)距離3個指標(biāo)的綜合優(yōu)化效果。因此，這里設(shè)計了一個有效的搜索半徑選擇原則，具體方案如圖4所示。

圖4 搜索范圍半徑的選擇規(guī)則確定流程圖

由圖4可知，搜索半徑的選擇規(guī)則共分為兩個步驟：第一步是設(shè)計搜索邊界確定原則；第二步是設(shè)計選擇確定原則。在兩步設(shè)計原則選取完成后，搜索半徑將最終被確定。

在邊界確定原則中，這里設(shè)計了兩種確定原則，即單邊界確定原則和填充邊界確定原則。其中單邊界確定原則是以移動機器人位置為中心，相同步長的搜索半徑能到達的方格組成的閉合邊界中，無障礙柵格占邊界總格數(shù)的比例來進行判斷；而填充邊界確定原則是利用搜索半徑能夠覆蓋的范圍中，無障礙柵格占所覆蓋范圍總格數(shù)的比例來進行判斷。即令變量R=1,2,…,n為搜索半徑，n為搜索半徑最大步長，則單邊界確定原則中柵格總數(shù)為Sd=8R，而填充確定原則中的柵格總數(shù)為St=(2R+1)2。

在第一步搜索邊界確定原則完成后，再進行第二步選擇確定原則。這里也設(shè)計了兩種選擇確定原則：最大化概率選擇原則和最小化概率選擇原則。最大化概率選擇原則為：比較在不同搜索半徑下所包含的總柵格中，選擇無障礙柵格占比最大值所對應(yīng)的搜索半徑為本次局部路徑規(guī)劃搜索半徑；反之，則為最小化概率選擇原則。即令分別為搜索半徑為 R的單邊界和填充邊界無障礙柵格總數(shù)，則相應(yīng)的最大化概率選擇原則為：

而最小化概率選擇原則為：

兩種確定原則的2步、4步實例分別如圖5、圖6所示。圖5中，紅色正方形柵格為機器人的當(dāng)前位置，由內(nèi)到外的兩個橙色矩形所包括的區(qū)域分別為兩步搜索半徑和4步搜索半徑所覆蓋的區(qū)域，兩個藍色矩形經(jīng)過的柵格分別為相應(yīng)搜索半徑所對應(yīng)的邊界柵格。在單邊界確定原則下，第2步搜索半徑的總柵格數(shù)為16格，4步為32格，相應(yīng)的占比分別為0.625和0.718。按照最大化概率選擇原則應(yīng)選擇4步搜索半徑；而按照最小化概率原則應(yīng)選擇2步搜索半徑。

圖5 單邊界確定原則原理圖

圖6 填充邊界確定原則原理圖

同理，圖6中的紅色正方形柵格為機器人的當(dāng)前位置，橙色矩形與藍色矩形分別為兩步搜索半徑和4步搜索半徑所覆蓋的區(qū)域。在填充邊界確定原則下，2步搜索半徑的總柵格數(shù)為25格，4步為81格，相應(yīng)的占比分別為0.640和0.641，按照最大化概率選擇原則應(yīng)選擇4步搜索半徑，而最小化概率原則應(yīng)選擇2步搜索半徑。

4.2 自適應(yīng)搜索半徑蟻群動態(tài)路徑規(guī)劃算法的步驟

綜上所述，移動機器人自適應(yīng)搜索半徑蟻群動態(tài)路徑規(guī)劃算法具體分為下面5個步驟。

（1）根據(jù)規(guī)劃實時性要求確定本次動態(tài)路徑規(guī)劃的搜索半徑上界，即移動機器人在一次局部動態(tài)路徑規(guī)劃中所允許行走的最大步數(shù)。

（2）移動機器人以當(dāng)前位置為出發(fā)點，采用搜索半徑的選擇規(guī)則確定本次局部動態(tài)路徑規(guī)劃的搜索半徑值。

（3）調(diào)用隨機輪盤賭方法確定本次動態(tài)路徑規(guī)劃的最優(yōu)局部目標(biāo)點。

（4）調(diào)用C-ACA算法規(guī)劃出本次局部優(yōu)化路徑。

（5）通過計算本次最優(yōu)局部目標(biāo)點與終點的二范數(shù)是否為零來判斷該節(jié)點是否為終點。如果是終點則本次路徑規(guī)劃完成，反之則返回第（2）步。

通過上述5個步驟的不斷循環(huán)，即可實現(xiàn)全局的動態(tài)路徑規(guī)劃。

5 仿真實驗與分析

為了突出SRL-ACA算法的特點，令該算法中搜索半徑為固定值，并稱該算法為固定搜索半徑蟻群動態(tài)路徑規(guī)劃算法（FRL-ACA）。同時，把這兩種算法應(yīng)用于同等環(huán)境下的路徑尋優(yōu)的問題。

所有算法程序均采用MATLAB語言進行編程，障礙變化規(guī)則為時間變換規(guī)則，路徑規(guī)劃范圍為20×20的柵格面積，算法的各參數(shù)參見文獻[17]，初始值設(shè)置如表1和表2所示。

表1 兩種算法的公共參數(shù)設(shè)置

表2 各算法的自有參數(shù)設(shè)置

5.1 動態(tài)性能比較

首先采用SRL-ACA算法（1～4步自適應(yīng)搜索半徑）和FRL-ACA算法（1步搜索半徑）進行動態(tài)路徑規(guī)劃的仿真結(jié)果如圖7所示。在本次仿真規(guī)劃過程中共有5個障礙變化場景，如圖8～12所示。其中前4個障礙場景每3次規(guī)劃后變化1次，12次之后均采用圖12的障礙場景。5個障礙場景圖中的方框表示在該障礙場景下移動機器人一次路徑規(guī)劃走過的范圍。

由圖7可知，兩種算法均很好地適應(yīng)障礙變化，各自規(guī)劃出一條從出發(fā)點到終點的優(yōu)化路徑。相對而言，SRL-ACA算法的路徑要更短些。從圖8～12中畫出的一次規(guī)劃的路徑曲線可以看出，這些路徑均是可行的。其中圖8、圖12為2步半徑，圖9為4步半徑，圖10、圖11為1步半徑。

5.2 搜索半徑選擇規(guī)則對優(yōu)化參數(shù)的影響

為了測試所設(shè)計算法對環(huán)境變化的自適應(yīng)能力，在這里通過設(shè)置相同的算法參數(shù)和環(huán)境參數(shù)，來比較SRL-ACA算法和FRL-ACA算法在路徑尋優(yōu)關(guān)鍵參數(shù)上的差異。為確保尋優(yōu)關(guān)鍵參數(shù)的有效性，這里的最優(yōu)路徑長和最短時間均是50次尋優(yōu)結(jié)果的平均值。

首先，考慮柵格確定規(guī)則為填充邊界確定原則，搜索半徑確定原則為最大化概率選擇原則時兩種算法的性能比較。設(shè)SRL-ACA算法的搜索半徑變化范圍為1～2步，F(xiàn)RL-ACA算法的搜索半徑固定為1步，則具體仿真結(jié)果如表3所示。

圖7 動態(tài)路徑尋優(yōu)對比圖

圖8 G1尋優(yōu)環(huán)境柵格圖

圖9 G2尋優(yōu)環(huán)境柵格圖

圖10 G3尋優(yōu)環(huán)境柵格圖

圖11 G4尋優(yōu)環(huán)境柵格圖

圖12 G5尋優(yōu)環(huán)境柵格圖

表3 FRL-ACA和SRL-ACA算法路徑尋優(yōu)參數(shù)表

由表3可知，SRL-ACA算法的最優(yōu)路徑和尋優(yōu)時間兩項關(guān)鍵指標(biāo)上相對于FRL-ACA算法都有明顯改善和提高，表明自適應(yīng)搜索半徑算法有較好的動態(tài)路徑規(guī)劃性能。

其次，考慮柵格確定規(guī)則為單邊界確定原則，搜索半徑確定原則為最大化概率選擇原則時兩種算法的性能比較。設(shè)SRL-ACA算法的搜索半徑變化范圍為1～3步，而FRL-ACA算法的搜索半徑分別固定為1～3步。此外，為測試算法對障礙變化的適應(yīng)能力，這里按照障礙個數(shù)從少到多的順序給出5個靜態(tài)障礙場景，具體性能指標(biāo)如表4所示。

表4 FRL-ACA和SRL-ACA算法路徑尋優(yōu)參數(shù)表

由表4可知，SRL-ACA算法在障礙較少的場景①和②具有最短的路徑距離，而在其他的場景中也具有較短的路徑距離，說明該算法對障礙環(huán)境變化具有較強的適應(yīng)性。

再次，考慮在同等條件下SRL-ACA算法分別采用單邊界確定原則和填充邊界確定原則時的性能差異，具體如表5所示。

表5 SRL-ACA算法路徑尋優(yōu)參數(shù)表

由表5可知，在最優(yōu)路徑指標(biāo)上填充邊界確定原則優(yōu)于單邊界確定原則，而在尋優(yōu)時間指標(biāo)上則是單邊界確定原則強于填充邊界確定原則，可以具體要求選擇其中一種。

最后，為了比較最大化概率選擇原則和最小化概率選擇原則對動態(tài)路徑規(guī)劃性能參數(shù)的影響，這里采用SRL-ACA算法分別在兩種選擇原則下進行仿真實驗。為體現(xiàn)差異性，這里的柵格面積取50×50，具體結(jié)果如表6所示。

表6 SRL-ACA算法路徑尋優(yōu)參數(shù)表

由表6的對比結(jié)果可知，最大化概率選擇原則在最優(yōu)路徑和尋優(yōu)時間兩項關(guān)鍵指標(biāo)方面都明顯優(yōu)于最小化概率選擇原則，說明基于最大化概率選擇原則時SRL-ACA算法更具優(yōu)勢。

6 結(jié)束語

考慮在全未知復(fù)雜動態(tài)環(huán)境進行動態(tài)路徑規(guī)劃的過程中，存在的規(guī)劃實時性要求高，移動機器人的計算能力和搜索半徑有限，規(guī)劃路徑距離和算法收斂時間之間無法兼顧等問題，基于改進蟻群算法構(gòu)建了一種新型的搜索半徑自適應(yīng)蟻群動態(tài)路徑規(guī)劃算法。仿真實驗表明，該算法能夠在確保實時性要求的前提下，通過自適應(yīng)調(diào)整搜索半徑，使得移動機器人的計算能力始終得到充分的利用，從而進一步縮短路徑距離，減少收斂時間，實現(xiàn)對復(fù)雜未知環(huán)境的有效動態(tài)路徑規(guī)劃。