多植保無人機協同路徑規劃

闞平，姜兆亮,*，劉玉浩，王振武

1. 山東大學 機械工程學院 高效潔凈機械制造教育部重點實驗室，濟南 250061

2. 山東大學 日照智能制造研究院,日照 276800

近年來，無人機(Unmanned Aerial Vehicle, UAV)已經發展成為航空學中最具挑戰性和高潛力的技術之一，路徑規劃任務作為一項無人機的關鍵技術，已被世界各地的學者廣泛研究[1]。無人機在民用和軍事環境中的應用已經引起了學術界和工業界的極大興趣，廣泛應用于監視、人流控制、邊境巡邏、交通監控、消防、農業、導航、搜索和救援等領域[2-4]。無人機路徑規劃就是按照一定的工作要求，在滿足各個約束的條件下，規劃出能耗最優或次優的作業航線[5]。針對無人機路徑規劃問題，國內外學者已開展了大量研究。文獻[6]針對未知空域中無人機路徑規劃方法實時性和適用性不足的問題，提出了一種基于skinner操作條件反射理論框架的學習系統，通過遺傳算法搜索最優行為進而得到最優路徑。文獻[7]提出了一種基于采樣的無人機路徑規劃方法，該方法可避免無人機與各種移動障礙物發生碰撞。

植保無人機選用小型旋翼無人機作為載體，在其上搭載農藥噴霧設備進行作業，具有作業速度快、藥劑漂移少、對作物穿透性強、防控效果好、作業效益高等特點，近年來得到了快速發展[8-9]。植保無人機路徑規劃為全覆蓋路徑規劃，多植保無人機協同路徑規劃可定義為：多架植保無人機在約束條件下，通過相互協調，共同對待覆蓋區域(作業區域)進行遍歷作業，使得總體性能指標最優[10-11]。在單架植保無人機路徑規劃方面，學者已經開展了一些研究。文獻[12]研究了一種植保無人機返航路線規劃算法，通過合理分配各架次無人機的噴藥量和返航點，使無人機的工作總能耗最小，從而提高作業效率。文獻[13]提出了一種基于Grid-GSA(Gravitational Search Algorithm)的植保無人機路徑規劃算法，以每架次無人機植保作業距離為尋優變量，以非植保作業耗時最短為目標函數，實現了對返航點數量與位置的尋優。

植保無人機在實際作業過程中，若作業區域面積較大，單次植保作業無法滿足作業要求，需要中途多次返航至補給點進行藥劑裝填或電池更換等補給作業[13]。這就要求對無人機的作業路線進行合理規劃，從而達到提高作業效率的目的。隨著中國城鎮化率的進一步提高，對于轉變農業發展方式，支撐現代農業發展，增強農業綜合生產能力，發展高作業效率的農機裝備是大勢所趨[14]。若僅采用1架植保無人機進行作業，作業總時間較長，效率有限。針對這種情況，本文基于改進粒子群算法，提出了一種多植保無人機協同路徑規劃解決方案，采用多架無人機協同作業，提高勞動效率。

1 簡單路徑規劃方法

1.1 多植保無人機作業

設作業區域為一矩形，以采用4架無人機進行作業為例。為適應植保無人機自動化作業，提高作業效率、減少成本，因而只設置一個補給點。將作業區域按等面積劃分為4塊矩形，對應4架植保無人機分別進行作業，從左至右依次將無人機編為UAV-1～UAV-4號，如圖1所示。為便于各植保無人機進行返航補給，將補給點設置于作業區域寬邊中點沿長邊方向向外距離為l處。為避免無人機返航途中發生碰撞，處于兩邊作業的無人機返航時的飛行高度應大于處于中間作業的無人機植保施藥作業時的飛行高度和返航時的飛行高度。返航時的飛行高度大于等于植保作業高度，取兩邊作業的無人機與中間作業的無人機之間的返航高度差為h。為確保植保無人機協同作業時的航行安全，無人機飛行時應滿足安全空間間距的要求，取各無人機之間的最小水平安全空間間距為Ds。

圖1 多植保無人機協同作業示例

1.2 最大作業距離規劃和最小返航距離規劃

設植保無人機最大載藥量為10 L，滿載情況下續航時間為15 min，空載情況下的續航時間為25 min，載藥量所允許的最大植保作業時間為12 min，非植保作業狀態下的最大飛行速度為8 m/s，植保作業飛行速度為4 m/s，作業幅寬為2 m，單架次無人機最大植保作業距離為2 880 m。

各架無人機在植保作業時，僅當所攜帶的藥劑消耗殆盡時才進行返航補給，此時得到的作業路線定義為最大作業距離規劃的作業路線；在保證所有返航點位置都位于補給點一側作業區域邊界上，且返航點數量最少所得到的作業路線定義為最小返航距離規劃的作業路線[13]。設作業區域為500 m×240 m的矩形，采用4架無人機進行作業，最大作業距離規劃和最小返航距離規劃情況下各架無人機返航點位置分布如圖2所示。

圖2 4架無人機規則作業區域下返航點分布圖

2 改進PSO算法

2.1 PSO算法描述

粒子群優化 (Particle Swarm Optimization，PSO) 算法是Kennedy和Eberhart在1995年受鳥群和魚群社會行為的啟發，提出的一種全體智能仿生算法[15-16]。基本PSO算法的數學描述為

粒子群優化算法初始種群規模為N，粒子維數為D，第i(i=1，2，…，N)個粒子在t時刻的飛行速度和在搜索空間中的位置分別為

vi(t)=[vi1(t),vi2(t),…,viD(t)]T

(1)

xi(t)=[xi1(t),xi2(t),…,xiD(t)]T

(2)

粒子i在第j(j=1，2，…，d)維的速度和位置更新公式為

vij(t+1)=ωvij(t)+c1r1(pij-xij(t))+

c2r2(gj-xij(t))

(3)

xij(t+1)=xij(t)+vij(t+1)

(4)

式中：ω為慣性權值；c1和c2為學習因子；r1和r2為(0，1)之間的隨機數；pij為粒子i自身搜索過程中的個體極值；gj為所有粒子的全體極值。

基本PSO算法的流程可以描述為：① 生成初始搜索群體；② 計算群體中各個粒子的適應度值。每個粒子的個體極值坐標設置為其當前位置, 所有粒子中的最好粒子設置為群體的全體極值；③ 根據式(3)和式(4)更新每個粒子的速度和位置；④ 計算粒子的適應度值, 如果好于該粒子當前的個體極值, 則將個體極值設置為該粒子的位置，然后再更新群體的全局極值；⑤ 判斷是否滿足終止條件。若滿足，停止搜索，輸出最優解，否則，轉到③繼續搜索。

PSO算法具有易實現、收斂快、魯棒性好等優點，但收斂效率低[17-18]。多年來，不少學者對PSO算法進行了各種改進。慣性權值是PSO算法中的一個重要參數，體現了粒子對之前速度的繼承。文獻[19]指出，前期全局搜索時取較大的慣性權值，有利于粒子跳出局部收斂；后期局部搜索時取較小的慣性權值，有利于粒子進行精細搜索，使得算法收斂。文獻[20]提出了一種動態慣性權重PSO算法的迭代公式，其動態慣性權重隨著迭代的增加而減小。PSO屬于典型的智能優化算法，本文研究的多植保無人機協同路徑規劃問題屬于多目標優化問題，變量為每架無人機各架次植保作業的飛行距離，目標為無人機的補給總次數、返航補給總時間、總耗時和最小補給時間間隔都盡量取小值，變量與目標函數之間不存在明顯的線性關系，適于用智能優化算法求解。本文采用改進PSO算法，對慣性權值采用“階梯式”調整策略，在迭代過程中，慣性權值階梯式減小，有利于減少算法優化時間，并且有效兼顧算法全局搜索能力和精細搜索能力[21]。

2.2 協同路徑規劃建模

設采用M架植保無人機進行協同作業，基于改進PSO算法的協同路徑規劃建模如下：

1) 算法尋優變量為每架無人機各架次植保作業的飛行距離，表示為

(5)

式中：X1,X2,…,XM分別代表1～M號無人機的各架次植保作業飛行距離。

2) 在植保作業過程中，由于補給點需要為M架 無人機進行補給，為減少電池更換次數，應盡量減少每架無人機的補給次數。作業區域面積固定導致植保作業時間一定，為提高效率，應盡量降低無人機返航補給時間消耗，同時應盡量使整個植保作業時間最短。補給時間間隔為上一架次無人機結束補給至下一架次無人機開始補給之間的時長。為降低作業時間偏差對整個作業過程帶來的影響，應使作業過程中的最小補給時間間隔盡量大。考慮到以上因素，構建包含以上各要素的目標函數，表示為

(6)

式中：Ci為i號無人機的補給總次數；Li為i號無人機的返航補給總時間，即i號無人機各架次返航往返飛行時間和補給時間之和(不包括剛開始作業時無人機飛行至作業區域時間，以及所對應作業區域全部作業完畢后的返航時間)；T為總耗時，即從第一架無人機起航作業到最后一架無人機完成對應作業區域植保作業的時長；tmin為作業過程中的最小補給時間間隔；ω1、ω2、ω3、ω4為權重因子，分別用于表征補給總次數、返航補給總時間、總耗時和最小補給時間間隔4項因素的重要程度，取ω1、ω2、ω3、ω4之和為1，其具體數值根據實際需要確定；z1、z2、z3為補給總次數、返航補給總時間和總耗時的比例縮放因子，目的是使補給總次數、返航補給總時間、總耗時和最小補給時間間隔數值保持在同一量級。

3) 各架次無人機返航飛行時間為

i=1,2,…,M;j=1,2,…

(7)

式中：fij為i號無人機進行第j次補給時的返航飛行時間；Pij為i號無人機進行第j次補給時的返航點位置坐標，其具體數值與無人機每次植保作業距離存在對應關系，可通過計算求出；P0為補給點位置坐標；vmax為非植保作業狀態下的最大飛行速度；ti為i號無人機每次返航過程中在返航初始和結束階段的額外時間消耗。

4) 補給過程包括藥劑裝填和電池更換，單次補給需要的總時間為tr。多架無人機在協同作業時，由于補給點在同一時刻只能滿足一架無人機進行補給，因而同一時刻僅允許一架無人機處于補給狀態。為便于補給時間間隔分布，開始作業時各植保無人機依次延時起航，延時時間為td。處于兩邊作業的無人機距補給點相對較遠，應先起航進行作業，位于中間作業的無人機后起航作業。初始起航點位于補給點附近。

5) 設各架無人機補給時間中點時刻按時間先后順序構成向量α=[α1，α2，…，αk]。為確保各架無人機補給時間間隔分布，應滿足

αi+1-αi≥tr+ts1≤i≤k-1

(8)

式中：ts為安全間隔時間，目的是避免各無人機飛行時間誤差導致的補給時間發生沖突，并確保無人機飛行時滿足最小空間間距。

根據以上基本思路，本文提出了一種基于改進PSO的多植保無人機協同路徑規劃算法，其基本流程如圖3所示。

圖3 多植保無人機協同路徑規劃流程

3 仿真分析

本文建立多植保無人機路徑規劃模型，針對不同架數植保無人機和不同作業區域，采用柵格法劃分作業區域，生成全覆蓋作業航線，采用改進粒子群優化算法，實現無人機路徑規劃的仿真分析，并將仿真結果與最大作業距離規劃和最小返航距離規劃2種情況進行對比。

3.1 全覆蓋作業航線生成

植保無人機路徑規劃屬于全覆蓋路徑規劃的范疇，作業環境為已知狀態，適宜采用柵格法對作業區域進行劃分。以采用4架無人機作業為例，對于規則矩形的作業區域，如圖4所示，待作業區域寬度為4b，作業幅寬為d，在確保每架無人機作業區域寬度為作業幅寬的偶數倍的情況下，將待作業區域按等面積從左至右劃分為4塊矩形，則每架無人機待作業區域應設置2b/d個航點。若無法滿足上述條件，由于UAV-2作業區域右上角頂點相比于其他無人機作業區域右上角頂點而言與補給點相距最近，因而在先滿足UAV-1、UAV-3、UAV-4號作業區域寬度為作業幅寬的偶數倍后，再使各無人機作業區域面積盡量平均。

對于不規則的作業區域，需將航點根據實際作業區域邊緣進行相應調整，以不規則梯形為例，各無人機作業航線如圖5所示。

圖4 規則作業區域全覆蓋植保航線生成

圖5 非規則作業區域全覆蓋植保航線生成

3.2 4架無人機規則作業區域下最大作業和最小返航距離規劃仿真

設植保無人機續航時間為15 min(滿載)，載藥量所允許的最大植保作業時間為12 min，非植保作業狀態下最大飛行速度vmax=8 m/s，植保作業飛行速度vo=4 m/s，作業幅寬d=2 m，單架次無人機最大植保作業距離xmax=2 880 m，單次補給需要的總時間tr=60 s，取每架無人機延時起航時間td=150 s，返航高度差h=7 m，最小水平安全空間間距Ds=5 m。取UAV-2和UAV-3返航初始和結束階段的額外時間消耗t2=t3=2 s，由于UAV-1和UAV-4返航高度大于UAV-2和UAV-3，返航時需要爬升高度，取t1=t4=6 s。

設作業區域為長500 m，寬240 m的矩形，采用4架無人機進行作業，單架無人機的作業區域寬度為60 m。補給點設置于作業區域寬邊中點沿長邊方向往外距離l=5 m處。在非等比坐標系下，最大作業距離規劃和最小返航距離規劃情況下各架無人機返航點位置分布如圖2所示。

在最大作業距離規劃情況下，UAV-1在零時刻起航作業，UAV-2、UAV-3、UAV-4分別延時300、450、150 s起航作業，各無人機工作狀態和補給時間分布如圖6所示。

在最小返航距離規劃情況下，若各無人機仍按照原來150 s的延時起航作業，則無法滿足補給時間間隔分布要求。為確保各架無人機補給時間間隔分布，UAV-1在零時刻起航作業，UAV-2、UAV-3、UAV-4分別延時340、450、150 s起航作業，各無人機工作狀態和補給時間分布如圖7所示。

圖6 規則作業區域下最大作業距離規劃仿真結果

圖7 規則作業區域下最小返航距離規劃仿真結果

3.3 改進POS算法規劃仿真

3.3.1 4架無人機規則作業區域下規劃仿真

設植保無人機作業飛行時的最小水平安全空間間距為5 m，取安全間隔時間ts為40 s，將此作為算法的約束條件，此時各植保無人機進行補給時的最小空間間距將遠大于預設的最小水平安全空間間距。設作業區域為500 m×240 m的矩形，采用4架植保無人機進行協同作業，UAV-1在零時刻起航作業，UAV-2～UAV-4分別延時300、450、150 s起航作業。在非等比坐標系下，采用改進PSO算法得到的4架無人機路徑規劃如圖8所示，工作狀態和補給時間分布如圖9所示，各架無人機植保作業距離數值分布為

(9)

3.3.2 4架無人機非規則邊界作業區域下規劃仿真

設作業區域長為500 m，寬為240 m，非規則邊界由矩形區域去掉左上角邊長100 m的等腰直角三角形形成。采用4架植保無人機進行協同作業，運用柵格法劃分作業區域，并生成全覆蓋作業航線。UAV-1～UAV-4的作業區域寬度分別為64、60、60、56 m，對應作業面積分別為27 648、29 352、30 000、28 000 m2。補給點設置于作業區域寬邊上UAV-2和UAV-3作業區域交點沿長邊方向往外距離l=5 m處。對應作業面積較大的無人機應先起航作業，UAV-3在零時刻起航作業，UAV-1、UAV-2、UAV-4分別延時450、150、300 s起航作業。在非等比坐標系下，采用改進PSO算法得到的4架無人機路徑規劃如圖10所示。各架無人機植保作業距離數值分布為

圖8 4架無人機規則作業區域下路徑規劃

圖9 規則作業區域下改進PSO算法規劃仿真結果

(10)

采用最大作業距離規劃和最小返航距離規劃得到的返航點分布如圖11所示。若采用最小返航距離規劃，則難以滿足補給時間間隔分布要求。采用最大作業距離規劃時，若沿用改進PSO算法所使用的起航延時方案，將難以滿足補給時間間隔分布的要求。為使補給時間間隔分布， UAV-3在零時刻起航作業，UAV-1、UAV-2、UAV-4分別延時500、450、150 s起航作業。

圖10 4架無人機非規則作業區域下路徑規劃

圖11 4架無人機非規則作業區域下返航點分布

3.3.3 2架和3架無人機路徑規劃仿真

取作業區域為500 m×240 m的矩形，補給點設置于作業區域寬邊中點沿長邊方向往外距離l=5 m處。采用2架植保無人機進行協同作業時，單架無人機的作業區域寬度為120 m。UAV-1在零時刻起航作業，UAV-2延時300 s起航作業。由于2架無人機在同一高度返航，取無人機返航初始和結束階段的額外時間消耗t1、t2為2 s。在非等比坐標系下，采用最大作業距離規劃和最小返航距離規劃得到的返航點位置分布如圖12所示。采用改進PSO算法得到的2架無人機返航點位置分布如圖13所示，2架無人機植保作業距離數值分布為

圖12 2架無人機返航點分布

圖13 2架無人機路徑規劃

(11)

采用3架植保無人機進行協同作業時，單架無人機的作業區域寬度為80 m。UAV-1在0 s時刻起航作業，UAV-2和UAV-3分別延時400 s和200 s起航作業。由于處于兩邊作業的2架無人機的返航高度大于處于中間作業的無人機，取UAV-2返航初始和結束階段的額外時間消耗t2= 2 s，UAV-1和UAV-3為t1=t3=6 s。在非等比坐標系下，采用改進PSO算法得到的3架無人機返航點位置分布如圖14所示，3架無人機植保作業距離數值分布為

(12)

采用最大作業距離規劃和最小返航距離規劃得到的返航點分布如圖15所示。最大作業距離規劃沿用改進PSO算法起航延時方案。采用最小返航距離規劃時，為使補給時間間隔分布，UAV-1在零時刻起航作業，UAV-2和UAV-3分別延時500 s和200 s起航作業。

圖14 3架無人機路徑規劃

圖15 3架無人機返航點分布

4 結果分析

采用不同架數植保無人機在不同作業區域下，基于改進粒子群優化算法規劃，最大作業距離規劃和最小返航距離規劃的結果數據對比如表1和表2所示。

表1中，采用4架植保無人機進行作業，當作業區域為規則矩形時，基于改進PSO算法得到的總返航點數量和最大作業距離規劃情況持平，較最小返航距離規劃情況減少了8個；相較于最大作

表1 4架無人機不同路徑規劃方法結果數據對比

表2 2架和3架無人機規則作業區域下不同路徑規劃方法結果數據對比

Table 2 Data comparison of two and three UAVs under different path planning situations in regular operation area

無人機架數參數改進PSO規劃最大作業距離規劃最小返航距離規劃2總返航點數量222028返航補給總時間/s195825132159總耗時/s878890668876最小補給時間間隔/s214.8207.6125.03總返航點數量211827返航補給總時間/s197726352150總耗時/s600962566106最小補給時間間隔/s124.9105.555.2

業距離規劃和最小返航距離規劃，基于PSO改進算法得到的返航補給總時間分別減少了36.6%和15.6%，總耗時分別減少了5.7% 和1.1%，最小補給時間間隔分別增加了18.4% 和929.4%，且遠大于安全間隔時間 40 s；采用最小返航距離規劃時的最小補給時間間隔為6.8 s，補給時將難以滿足無人機飛行時的安全空間間距要求。當作業區域不規則時，若采用最小返航距離規劃，由于每架無人機每次植保作業的距離不盡相同，將導致各無人機的補給時間難以滿足間隔分布的要求。在作業區域不規則的情況下，相較于最大作業距離規劃，基于改進PSO算法得到的總返航點數量增加了2個，返航補給總時間減少了15.9%，總耗時減少了4.1%，最小補給時間間隔增加了73.0%， 且遠大于安全間隔時間40 s；采用最大作業距離規劃時的最小補給時間間隔為37.1 s，小于設置的安全間隔時間。

表2中，當采用2架植保無人機進行作業時，相較于最大作業距離規劃和最小返航距離規劃，基于改進PSO算法得到的總返航點數量分別增加了2個和減少了6個，返航補給總時間分別減少了22.1%和9.3%，總耗時分別減少了3.1%和1.0%， 最小補給時間間隔分別增加了3.5%和71.8%。 當采用3架植保無人機進行作業時，相較于最大作業距離規劃和最小返航距離規劃，基于PSO算法得到的總返航點數量分別增加了3個和減少了6個，返航補給總時間分別減少了25.0%和8.0%，總耗時分別減少了3.9%和1.6%，最小補給時間間隔分別增加了18.4%和126.3%。

對比3種規劃算法各項數據可以發現，除了總返航點數量可能會出現比最大作業距離規劃稍多的情況，采用本文提出的改進PSO算法得到的路徑規劃結果在返航補給總時間、總耗時、最小補給時間間隔等3項指標中均為最優。最大作業距離規劃在總返航點數量和最小補給時間間隔2項指標中表現較優，最小返航距離規劃在返航補給總時間和總耗時2項指標中表現較優。而基于改進PSO算法得到的路徑規劃結果較好地綜合了最大作業距離規劃和最小返航距離規劃的優點，并較好地克服了二者的缺點，表現出了較優的性能，具有一定的實際意義。

當作業區域不規則或面積較大時，采用最大作業距離規劃或最小返航距離規劃，可能會出現各無人機補給時間不能滿足間隔分布或補給時不能滿足無人機飛行時的安全空間間距要求的問題，而使用本文提出規劃算法能較好地避免這一問題，表現出了更強的作業區域適應性。

5 結 論

1) 針對單架植保無人機作業效率有限的情況，對多植保無人機協同作業問題進行了研究，基于改進PSO算法，提出了一種多植保無人機協同路徑規劃解決方案，實現了對各無人機返航順序和返航點位置的尋優。

2) 本文提出的基于改進PSO算法的多植保無人機協同路徑規劃算法較好地綜合了最大作業距離規劃和最小返航距離規劃的優點，并較好地克服了二者的缺點，表現出了較優的性能，且對作業區域有更好的適應性，具有一定的實用價值。