蟻群優化算法的無人機室內航跡規劃

馬肇祥，朱慶偉，張 俊，屈乾龍

(西安科技大學 測繪科學與技術學院，陜西 西安 710054)

0 引 言

無人機因其操作簡便、機動性能好等特點，已經被廣泛應用于各個領域。將無人機用于執行室內災害救援任務時，可以減少救援人員的安全風險，提高救援工作效率。航跡規劃是無人機完成自主飛行的關鍵技術之一，在室內救援時，尋找一條安全、可靠的飛行航跡是保證救援任務能否完成的關鍵。無人機室內飛行面臨的挑戰是室內空間狹小、障礙物較多，高度有限，使無人機飛行受到一定條件的限制。在室內，由于環境信息是未知的，航跡規劃要滿足避障要求，規劃一條合理路徑。

目前，各國學者已提出許多種無人機航跡規劃算法。常用到的算法有：可視圖法、D*算法[1]、A*算法[2]、人工勢場法[3]、神經網絡算法[4]、快速搜索隨機樹(RRT)算法[5]、遺傳算法[6]、粒子群算法[7]、蟻群算法[8-10]、模擬退火算法[11]、強化學習算法[12]等。其中，蟻群算法在求解較優航跡方面較其他算法具有顯著優勢。對蟻群算法進行改進應用于航跡規劃的研究，國內外學者作了大量的研究工作。陳俠等提出的算法為使蟻群算法能更好適用于無人機三維航跡規劃，對算法存在的收斂速度慢、易陷入局部最優的問題，進行了相應改進，將三維航跡規劃分解成二維平面規劃和高度規劃2部分，運用幾何優化法增強蟻群的引導方向性，根據無人機航跡點與障礙物之間的距離，對飛行高度進調整，利用自適應變化閾值參數法提高了蟻群在全局中的搜索能力，從而達到求解多樣性的效果[13]。針對蟻群算法所含有的空間復雜性高、收斂速度慢的缺陷，魏江等提出的算法改進部分對局部搜索策略和初始信息素調節因子進行優化，在啟發函數中加入路徑偏移因子，有效降低空間搜索復雜性，提高了路徑規劃效率[14]。徐玉瓊等針對傳統蟻群算法在路徑規劃中對魯棒性缺乏的問題，提出改進自適應蟻群算法，在概率轉移規則中引入加權因子，以提高算法收斂速度，并按解的分布狀況適應性地對信息素進行更新，同時在步長選擇策略中選擇最優步長，增強算法全局搜尋能力，從而提高機器人路徑規劃效率[15]。李憲強等將人工勢場法與蟻群算法融合組成新的融合算法。由于蟻群算法易陷入局部最優，引入人工勢場法對初始信息素進行分配。并且引入勢場引導函數對蟻群算法的狀態轉移函數進行相應改進，從而避免算法因忽視周圍障礙物信息而陷入長時間進行路徑選擇的問題[16]。這些研究都將蟻群算法用到具體的環境[17-22]，取得良好的效果，然而，對于文中研究的室內無人機航跡規劃，并不適用。因為這些算法應用于室外環境，且算法規劃速度較慢，搜索時間較長，難以滿足室內災害救援及其他室內飛行任務的要求。

由于室內環境分布著大量障礙物，且障礙物分布不均以及其高度、形狀、大小都各不相同[23-25]。而無人機在室內進行搜救或者自主導航時，室內環境信息并不能保證都了解。筆者結合室內環境特點及蟻群算法存在的缺陷，對空間做離散化處理，降低其空間復雜度。針對搜索初期，因信息素的缺乏，會導致搜索的盲目性，采用信息素調節因子，同時根據算法存在收斂速度慢和易陷入局部最優的缺點，設計啟發概率，并改進信息素更新規則和采用動態信息素揮發策略。最后，通過實驗測試對改進后的算法性能進行驗證和分析。

1 空間離散化

室內環境中隨機分布著很多障礙物，且空間環境處于連續狀態。當發生災害時，室內障礙物和突發的各種不確定因素給航跡規劃帶來巨大挑戰。因此，對室內三維空間環境進行離散化處理，則在航跡規劃時可以直接獲得空間節點集。即在空間節點集中找到組成路徑規劃的總成本代價最小的節點。

設每個節點qindex，代表無人機的一個三維坐標(xindex，yindex，zindex)，設所有處于離散狀態空間節點的集合為q

q={q1,q2,…,qn=(xindex，yindex，zindex)}

(1)

對于無人機從起始點到目標點飛過的路徑節點構成的集合用K表示

K={K1,K2,…,Kn}

(2)

(3)

2 改進的蟻群算法

在基本蟻群算法中，概率選擇并不能總是保證最優解，有時在優化的早期，算法會進行盲目搜索、易陷入局部最優，而且由于啟發式搜索的局限性，導致算法收斂速度很慢，為提高基本蟻群算法的性能并克服其缺點，做出以下改進：改進初始信息素調節因子，有效增強蟻群算法的搜索方向性；設計啟發概率并改進狀態轉移概率函數，從而擴展蟻群搜索視野和提高可見性精度；對信息素更新規則進行改進和增加信息素揮發率的動態調整策略，有效提升算法的收斂速度、擴大搜索空間。

2.1 初始信息素的改進

由于基本蟻群算法的初始信息素均勻分布于空間中，因此在算法搜索初期，螞蟻選擇任意節點位置的概率都相同，從而出現蟻群盲目搜索的現象，同時也耗費大量的時間。

為避免螞蟻在算法搜索初期的盲目性，在起始點和目標點連線的區域中，通過起始點到當前節點的距離和待選節點到目標點距離的變化量來影響初始信息素。基本蟻群算法的初始信息素是一個固定常數值，改進蟻群算法通過確定起始點、當前節點、待選節點以及且標點之間的距離，使蟻群盡可能沿著起始點和目標點連線的附近進行路徑搜索，從而縮小路徑搜索范圍，因此對初始信息素調節因子進行了如下設計。

(4)

通過對上述信息素調節因子的設計使改進算法達到增強蟻群搜索方向性的效果。

2.2 啟發概率

ST是組合運算，啟發概率設計了讓螞蟻更容易選擇最好的下一個空間網格(將室內空間按單位長度等分為大小相等的多個空間網格)，所選網格必須是一個可行的網格，有多個可行通道抵達目標。這個概率取決于網格周圍障礙物的數量。因此，空間網格周圍的障礙物越少，概率就越大，網格就越有吸引力。需要做以下組合。

在三維空間中，無人機在搜索時，有27個搜索方向，去掉無人機本身的所占據的位置，因此剩于26個方向，即N(26,Mobs)，它表示圍繞一個確定的網格j，其周圍障礙物可能分布的數量，即表征一個可行網格節點周圍有多少障礙物，且障礙物數量為[0，26]，如圖1所示。

圖1 旋翼無人機空間搜索示意Fig.1 Schematic diagram of rotor drone space search

它的計算方法如下

(5)

式中N(26-Mobs-1，1)為螞蟻k可以離開網格節點j的通道數量，即在離開節點j后，能夠選擇的下一可行節點的數量。它的計算方法如下

(6)

其中N(a,e)=a!/(a-e)!e!為一個數學組合；Mobs為網格j周圍障礙物的數量，26是障礙物的最大數量和！表示階數。在通道數量計算中，必須取消螞蟻k將要選擇到達網格節點j的路徑通道。

使空間網格i中的螞蟻k更容易被網格j吸引的ST由下式定義

(7)

由此產生的轉移規則按下式進行定義

(8)

式中j∈allowedk。

2.3 改進信息素更新規則

信息素的數量是選擇經過最短路徑上的最佳空間網格的必要因素之一，然而，它含有一定強度的劣質信息素，這是由最差的螞蟻所產生的，它會使其他螞蟻移動到難以接近目標點的位置上，或者會導致算法過早求解，為了獲得良好的尋優性能，在每次迭代中，可使用以下更新規則增加最佳局部路徑上的信息素濃度并降低最差局部路徑上的信息素濃度。因此，對信息素更新規則公式改進為

(9)

(10)

(11)

其中STmax和STmin分別為ST的最大值和最小值，Loptimal和Lworst分別為最好和最差的局部路徑長度。

改進算法按以上信息素更新規則方式進行路徑搜索，能有效加快算法的收斂速度。

2.4 設置動態信息素揮發策略

在基本蟻群算法中，信息素揮發率ρ是(0，1)范圍內的常數，直接影響著算法全局搜素能力和收斂速度，如果ρ太小，信息素揮發的較慢，會降低全局搜索能力，使算法陷入局部收斂。如果ρ過大，全局搜索能力會得到一定程度的提高，但收斂速度會降低。

為確保能在擴大搜索空間和加快收斂速度兩者間取得良好的平衡，對信息素揮發率進行動態調整。其中，在算法開始時，將揮發率設置為較大的值，來改善全局搜索能力，然后揮發率將按如下公式進行改變

(12)

式中r和n分別為當前迭代次數和最大迭代次數；m為螞蟻的數量，STk為螞蟻k的ST;τmax和τmin分別為達到信息素量的最大值和最小值。

改進算法通過增加動態信息素揮發策略，能夠擴大蟻群對室內空間的搜索范圍，找尋到較優的路徑，從而避免蟻群陷入局部最優。

3 算法改進與實現

3.1 改進蟻群算法的步驟

具體改進蟻群算法流程如圖2所示。

圖2 改進蟻群算法流程Fig.2 Improved ant colony algorithm flow chart

3.2 仿真實驗環境構建與有效性分析

3.2.1 仿真實驗環境的構建

為驗證改進的蟻群算法在室內三維航跡規劃的有效性，在三維柵格地圖中對改進蟻群算法進行實驗。實驗仿真平臺為MATLAB2018a，考慮到一架無人機和室內環境模型特點，且無人機可以向環境中任意方向運動飛行。該實驗的規劃空間分為10 m×10 m×10 m柵格，20 m×20 m×20 m柵格和30 m×20 m×15 m柵格，實驗搭建的三維模型如圖3所示，為更真實的接近室內場景，空間中隨機設置障礙物。規定沒有障礙物的空間柵格可以通過，有障礙物的空間柵格不可通過。

圖3 不同尺度的室內三維環境模型Fig.3 Indoor three-dimensional environment models with different scales

在室內航跡規劃中，算法參數設置如下：螞蟻數量m=100，信息素濃度啟發因子α=1，能見度啟發因子β=2，揮發系數ρ=0.7，信息素強度Q=10，迭代次數n=50。

3.2.2 改進算法的實現及有效性驗證

在不同空間規模的條件下，采用改進算法和基本算法在室內環境1(規模為10 m×10 m×10 m)、室內環境2(規模為20 m×20 m×20 m)和室內環境3(規模為20 m×30 m×15 m)中各進行20次重復航跡規劃，然后從路徑長度，收斂時間等角度來比較2種算法的實驗效果，并對得到的結果進行對比和分析。為便于統計計算，對實驗的相關結果保留至小數點后3位。3種室內空間規模中基本算法和改進算法所規劃的路徑以及最佳個體適應度變化情況分別如圖4～圖6所示。

圖4～圖6的實驗結果表明，改進蟻群算法在3種不同的室內環境中經過計算迭代后，均能搜索到一條較優路徑，并且搜索到的較優路徑比基本蟻群算法的路徑長度更短，如圖4(b)、圖5(b)、圖6(b)中的藍色路徑相較于紅色路徑更短。這是因為在算法搜索初期，基本蟻群算法因缺乏初始信息素，對空間進行盲目搜索，使得所找尋到的路徑較長。而改進算法對初始信息素調節因子進行改進，增強朝目標點方向的信息素濃度，避免算法出現盲目搜索的狀況，從而找尋到一條較短路徑，有效節約搜索時間。同時，在環境1中，障礙物的高度不一，分布也不均勻，改進算法所規劃的路徑選擇離目標點距離近且周圍障礙物少的路徑通道，基本蟻群算法按傳統的啟發式規則隨機選擇可行通道，有時選擇的可行通道節點離目標點較遠。產生這2種結果的原因是改進算法中新設計的啟發式概率有效擴展蟻群搜索視野并提高了蟻群可見性精度。

如圖4(c)、圖5(c)、圖6(c)為3組實驗的側視圖。圖4(d)、圖5(d)、圖6(d)所反映的是最佳個體適應度值變化趨勢，可以得出改進算法(藍色曲線)比基本算法(紅色曲線)的收斂迭代速度快，且當適應度值達到穩定后，改進算法所得到的適應度值比基本算法的小，并且改進算法的適應度值在算法前期搜索階段，快速下降，出現這種結果是由于算法改進了信息素更新規則并采用信息素揮發率動態調整策略，從而加快算法的收斂速度，同時也擴大蟻群搜索范圍，有效解決基本蟻群算法易陷入局部最優極值的問題。在環境1中，基本算法經過33次迭代后，其最佳個體的適應度值趨于穩定，且達到最優，而改進算法在迭代15次后，最佳個體的適應度值達到最優，如圖4(d)所示。并且基本算法經過后續的多次迭代后，其最佳個體的適應度值仍高于改進算法相對應的值。從圖5(d)可以看出，改進算法和基本算法分別經過19次、43次迭代后，適應度值達到最小。圖6(d)中，改進算法和基本算法分別經過6次、8次迭代后，適應度值達到最小。

圖4 室內環境1中2種算法仿真對比Fig.4 Simulation comparison of two algorithms in indoor environment Ⅰ

圖5 室內環境2中2種算法仿真對比Fig.5 Simulation comparison of two algorithms in indoor environment II

圖6 室內環境3中2種算法仿真對比Fig.6 Simulation comparison of two algorithms in indoor environment Ⅲ

對2種蟻群算法在3種不同室內環境中重復實驗得到的20條路徑長度和算法所用時長進行統計比較，見表1。由表1可知，改進蟻群算法搜索的20條最優路徑長度效率分別提高：11.8%，46.9%，57.2%，路徑長度平均值效率分別提高17.7%，54.9%，62.7%。改進蟻群算法平均用時相較基本蟻群算法而言，提升較小。具體來說，在室內空間規模較小的環境1中，2種算法都能較快搜索到最優解，搜索到的路徑長度平均值和算法用時兩方面的效率百分比相差不大。

表1 3種室內環境中的2種算法性能比較Table 1 Performance comparison of two algorithms in three indoor environments

伴隨著室內空間范圍擴大，改進算法的各項性能逐漸顯現，同時路徑長度效率提升趨勢與算法用時效率提升趨勢呈一升一降2種相反的變化結果。分析可知，這是由于改進算法在尋找較優路徑時，隨著空間范圍的增大，相應地空間搜索計算量也增大，從而導致所用時間增大，算法用時的提升效率也隨之降低。

3.2.3 算法適應性驗證

為驗證所提出的改進算法在不同場景下的適應性，在不同障礙物和目標位置點中分別進行3組實驗，每次實驗運行多次并使結果保留至小數點后3位。圖7～圖9顯示3組實驗的路徑規劃圖。其中圖7(b)在圖7(a)基礎上改變目標點位置，圖8(b)與圖8(a)為相同起始點和目標點條件下的室內不同障礙物環境，圖9(a)和圖9(b)為完全不同的室內環境和目標點。

圖7 不同目標點的三維規劃Fig.7 Three-dimensional planning diagram of different target points

圖8 室內空間障礙物位置不同Fig.8 Different indoor spatial obstacle positions

圖9 空間范圍不同Fig.9 Different spatial scopes

從圖7可以看出，實驗更改無人機所要到達的目標位置，規劃的路徑仍能夠安全避開障礙物并準確到達目標點，由于圖7(a)和圖7(b)起始點坐標都為(1，1，1)，圖7(a)目標點坐標是(9，10，7)，圖7(b)目標點坐標是(10，9，8)，所以圖7(b)實驗得到的路徑規劃長度、算法計算用時、迭代次數都大于圖7(a)的值。圖8(a)與圖8(b)因障礙物差異較大，且圖8(a)中的無人機直接通過第2、第3個障礙物下方的通道到達目標點，但在圖8(b)中，由于第2個障礙物是一個類似U型的障礙物，則無人機需要先不斷沿y軸方向搜索，再轉向x軸方向搜索到達目標點，最終導致改進算法搜索到的最優路徑長度、算法用時、收斂迭代次數不同。在第3組實驗中，由于室內空間范圍由圖9(a)的20 m×20 m×12 m擴展為圖9(b)的20 m×20 m×14 m，使得圖9(b)中采用改進算法所規劃的路徑長度比圖9(a)的路徑長度更長。表2為圖7～圖9這3組實驗得到的數據結果。

表2結果說明，改變不同的條件，所提出的改進算法在不同的場景下有著很好的適應性，同時通過實驗驗證改進算法的路徑規劃性能指標與無人機起始點和目標點的距離大小、空間復雜度大小、空間范圍大小這3種因素有關。

表2 不同環境中改進蟻群算法的性能比較Table 2 Performance comparison of improved ant colony algorithm in different environments

4 結 論

1)針對傳統蟻群算法存在初期盲目搜索、易陷入局部最優、收斂速度慢等問題，提出一種優化蟻群算法，通過改進初始信息素調節因子，進而增強蟻群搜索的方向性。

2)設計一種啟發概率函數，擴展蟻群搜索視野并提高可見性，使得最優路徑長度比基本蟻群算法縮短38.6%，平均用時減少3.8%。

3)對信息素更新規則進行改進，增添信息素揮發動態調整策略，從而加快算法收斂迭代速度，有效驗證改進算法在復雜環境中的良好適應性。