電力監測無人機與移動機巢協同路徑規劃方法研究

李 晉，何 勇，董麗夢，原瀚杰

（廣東電網有限責任公司肇慶供電局，肇慶 243000）

0 引言

無人機已被廣泛用于執行復雜任務，如空中電力監測或物料運送等[1-4]。無人機編隊的持續監測問題引起了極大關注[5-10]。這些早期的研究大多沒有考慮無人機的能耗限制，在長距離任務中，這種限制不可忽視。一些學者提出使用靜態充電站，由無人機定期訪問，以解決能耗限制問題[11-12]。然而用這種方法監測如電力網絡等大范圍環境需要建立許多靜態充電站，以便在無人機的能耗限制下，無人機在每個區域都能到達充電站。為了克服這一限制，在文獻[13-14]中，使用輪式機器人作為無人機巢用于移動充電。在文獻[15-16]中，持續監測問題被簡化為廣義旅行商問題（generalized traveling salesman problem,GTSP），以解決無人機和移動機巢的路徑規劃。文獻[17]提出了一個混合整數線性規劃模型，在已知無人機軌跡的情況下，求解無人機巢的最優路徑。在上述研究中，都假定無人機巢在無障礙環境中工作，或者障礙物是預先知道的。在面對障礙物造成的不確定性時，這些算法不能提供足夠的魯棒性。

在本文中，提出了一種可擴展的魯棒算法，用于持續電力監測任務中能量受限的無人機和移動機巢的協同路徑規劃。首先將監測環境分解為一個二維網格圖。網格中的每個單元都有一個相關的年齡，即自該單元上次被監測以來所經過的時間。給定這樣一個網格，研究目標是找到一個最佳分區（無人機在一個能耗循環中可以覆蓋的區域），以及在這些分區上的循環無人機和無人機巢軌跡，從而使所有單元的最大年齡最小化。因此所提出的方法與和基于分區的周期性巡邏策略有一定共性[18]。與文獻[18]中方法不同的是，在本文中中引入了一個魯棒性參數，以確保即使在地面上有未知的障礙物時，所產生的路徑規劃也可用。雖然增加魯棒性參數可能會因為用較小的分區進行保守規劃而降低效率（增加結果年齡），但它確保了即使環境中存在較大的障礙物，所產生的規劃仍然適用。還通過使用無人機的能耗限制所允許的最大正方形分區，在效率降低最小的情況下提高了所提出方法的可擴展性。

1 路徑規劃問題

給定一個無向圖 G(V,E)，其由一組節點V={v1,v2,...,vn}和一組邊E?V×V構成。將一條正好訪問所有節點一次的循環路徑稱為漢密爾頓循環[13]。在本文中，考慮了一個立方體空間Q中的持續監控場景：

其中xmax，ymax，zmax表示立方體空間的尺寸。那么地面上的目標區域可以定義為：

piA(t)=[xiA(t),yiA(t),ziA(t)]表示無人機i在時間t時的位置，pA(t)=[p1A(t),p2A(t),...,pnA(t)]表示所有無人機位置的集合。pjG(t)=[xjG(t),yjG(t),0]表示無人機巢j在時間t時的位置，pG(t)=[p1G(t),p2G(t),...,pmG(t)]表示所有無人機巢位置的集合。無人機和移動機巢的相應軌跡集分別用pA和pG表示。無人機和移動機巢滿足以下約束條件：

2）能量約束：每架無人機i電池能量為，并假定在時間t=0時充滿電。無人機的能量在充電時將以恒定速率β+增加，在飛行時以恒定速率β-減少，則：

假設移動機巢擁有無限的能量，因為它們通常擁有比無人機大得多的能量容量。

3）安全約束：每架無人機在沒有能量時必須著陸。此外，無人機i在落地時必須在某個移動機巢j上，即：

給定一個由無人機和移動機巢組成的編隊，其模型如上所述，持續監測問題的目標是基于一個叫做“年齡”的指標。監測環境中每一個單元的年齡是指自上次被監測以來所經過的時間。每當無人機訪問單元的中心點時，它的時間就變為零。無人機軌跡集pA會產生一組到達時間，表示無人機到達先前未被占用的節點的時間。同樣，無人機軌跡產生了一個離開時間集，它包括無人機從一個空閑節點出發的時間。對于ε＞0，到達和離開時間集可定義為：

所有監測空間單元的最大年齡由到達和離開時間集唯一決定。

定義1：對于任何給定的pA，在時間區間（t,∞）上的最大年齡定義為：

對于監測環境Q，給定n架無人機和m臺移動機巢，在速度、能量和安全約束條件下，找到無人機和移動機巢的所有軌跡，使式(8)中最大年齡的極限值最小，即：。

2 協同路徑規劃方法

所提出的規劃算法包含離線和在線模塊。首先討論了該算法在包含一個移動機巢和n架無人機的編隊中的應用。然后將把它擴展到有多個編隊的情況。

離線規劃模塊的工作原理如下：1）將環境劃分為方形區域（分區），每個區域都由無人機-移動機巢編隊在一個能耗循環內監測。2）將每個方形區域劃分為子區，并指定一架無人機監測每個子區。3）找到連接哈密爾頓循環的釋放點，即區域中心質點。移動機巢將把無人機沿著哈密頓循環運送到每個釋放點，而無人機則起飛監測指定的子分區，然后返回移動機巢充電并運送到下一個釋放點。

在線規劃模塊工作時，無人機-移動機巢編隊首先嘗試執行由離線規劃模塊計算出的路徑。假設障礙物都在地面上，空中沒有障礙物。移動機巢安裝有傳感器，從而知道其感應范圍內的單元是否被障礙物占據。每個障礙物占據一個或多個單元（如圖6所示）。1）移動機巢在從一個釋放點到另一個釋放點的過程中，采用基于采樣的路徑規劃算法，機載傳感器更新障礙物的信息；2）如果規劃中的釋放點被障礙物占據，移動機巢將搜索新的可行的釋放點。之所以提出步驟2，是因為在離線規劃模塊中假設釋放點是無障礙物的，但在實際執行階段它們可能被最初的未知障礙物占據。此外，新的釋放點不能在步驟2中任意選擇，因為它必須保證無人機能夠監測其分配的子分區，并在能量耗盡之前返回到移動機巢。所提出的算法對未知障礙物具有魯棒性，即只要障礙物足夠小，就能在理論上保證可行的釋放點的存在。

2.1 分區

離線規劃模塊的第一步是將環境劃分為不同的分區。分區過程包括三個方面：1）給定環境的尺寸，首先找到無人機-移動機巢編隊在一個能耗循環內可以監測到的最大的可行方形區域；2）使用最大的可行方形區域反復覆蓋環境，直到沒有不與其他區域重疊的方形區域增加；3）將前一步中最大的可行方形區域沒有覆蓋的區域劃分為幾個矩形區域。這種分區策略與文獻[18]中的工作不同，后者詳盡地搜索最佳可行分區，而不是使用最大的可行方形分區。這種修改后的分區策略極大地提高了所提出方法的可擴展性，而性能上的損失卻很小。圖1顯示了11×10監測環境的分區結果，其中分區集由P={P1,P2,...,P|P|}表示。為了對環境進行劃分，提出了算法1。

圖1 a=11、b=10、d=3的情況下通過算法1生成的分區案例

圖2 子分區方案及案例

在找到分區集合P 之后，可以通過T S P 求解器計算出穿越P中所有分區中心點的最短哈密爾頓循環。表示沿著哈密爾頓循環的分區序列。移動機巢首先將無人機運送到P′1的中心點，然后釋放所有的無人機訪問P′1中的節點，之后再返回移動機巢。然后，移動機巢將無人機運送到下一個釋放點，同時給無人機充電。無人機在充滿電之前不會被釋放。無人機-移動機巢編隊重復這一程序，直到他們完成對的監測并返回到P′1。將這個過程被稱為一個超循環，其周期表示為Ts。

2.2 子分區

當且僅當：

分區P是可行的。違反式(11)意味著無人機在一個能耗循環內不能監測至少一個分區。將式(11)用來檢查分區可行性。

2.3 生成軌跡

所以超循環周期Ts可以表示為：

算法2給出了離線軌跡規劃算法。在第1行中，根據無人機的最大飛行距離，通過估計每個無人機可以監測的最大點數，獲得了對環境的初始估計。例如最大行程距離D和每個無人機可以監控的最大點數num滿足以下關系：D≥num×l，其中l是方形單元的邊長，即任何兩個待訪問點之間距離的下限（如圖4(a)）。最大點數可以表示為。然后得到d的初始估計，其中n是無人機-移動機巢編隊中的無人機數量。第1～14行用于查找算法1所需的最大可行分區，第15～23行用于生成無人機和移動機巢軌跡，并計算超循環周期。

2.4 魯棒可行性分析

到目前為止，一直在假設每個分區的中心點是可以被移動機巢訪問的。雖然在離線規劃階段，障礙物是事先未知的，但在執行階段，移動機巢可能會發現規劃中的釋放點被障礙物占據。圖3(b)就是這樣情況的例子，一個障礙物占據了分區的中心點，必須在其他地方重新選擇一個新的釋放點。如圖所示，新的釋放點離無人機4號的子分區越來越遠，這有可能導致違反可行性條件式(11)。占據釋放點的障礙物引發了幾個問題：是否存在其他可進入的釋放點，以確保滿足式(11)的要求，以及如果存在這些釋放點，如何找出它們。最壞的情況是，移動機巢找不到任何可行的釋放點而終止了任務。為了避免這樣的問題，加強了可行性條件式(11)，使離線模塊計算出的規劃對未知障礙物具有魯棒性。具體來說，在增強的可行性條件下，當規劃的釋放點被足夠小的障礙物占據時，移動機巢可以保證找到替代釋放點。

圖3 尋找釋放點示例

定理1：假設有一個以釋放點ck為中心的半徑為ρ的圓，如果Lk,j滿足式(16)，那么圓內的任何一點M′都是一個可行的釋放點。

證明：使用圖4進行說明。圓內的任意點M通過三角形不等式滿足|MO|≤ρ，

從式(17)～式(18)可得：

為了在所提出的算法中利用定理1，需要估計障礙物有多大，然后確定一個足夠大的半徑ρ，形成一個可以覆蓋任何障礙物的圓。在離線規劃步驟中，任何違反增強可行性條件式(16)的分區都被排除。如果在無人機-移動機巢編隊執行規劃時發現原始釋放點被障礙物阻擋，根據定理1，圍繞中心點的半徑為ρ的圓內的任何無障礙點都是可行釋放點。然后，只要障礙物沒有切斷自由空間，移動機巢就可以進行重新規劃，尋找最近的可行釋放點，并繼續執行任務。

半徑ρ決定了魯棒性和監測性能之間的權衡。增加ρ將提高魯棒性，但它通過式(16)的限制性更強而縮小了規劃問題的可行空間，這可能導致更大的巡邏年齡?？尚行詸z查在算法3中提出，其中第1～5行執行子分區并生成無人機路徑，第6～7行檢查分區是否滿足增強的可行性條件。

2.5 無人機-移動機巢編隊的部署協調

多個無人機-移動機巢編隊的部署會影響到持久監測問題中的最大年齡。因此本文目標是找到一個使最大年齡最小化的部署協議?？紤]一個持久監測任務，其中m個無人機-移動機巢編隊用來監測k個地點。假設所有的編隊在啟動超循環。具體來說編隊i將在時間開始超循環，ti表示編隊i與下一編隊的時間差。將該部署協議產生的最大年齡表示為，將地面實測超循環周期表示為。圖5給出了時間說明，由于空間的限制，只顯示了2個監測周期。不同的顏色被用來區分k個監測地點。時間軸上的彩色點表示無人機-移動機巢編隊訪問相關地點的時間戳。

圖5 無人機-移動機巢編隊部署協議說明

最佳部署協議可以通過求解以下優化問題得到：

因為Ts是由假設無障礙環境的離線規劃算法給出的，并且移動機巢采用釋放點之間的最短路徑，所以T′s≥Ts。結合式(21)可得：

其中，kj(t)表示編隊j在時間t經歷的超循環數，Pij表示團隊j記錄的第i個超循環。將移動機巢j到達分區Pk的時間戳表示為tk,j。每個移動機巢j都需要滿足以下約束條件，以便它們能夠相互協調，保持的時間間隔。

算法4給出了無人機-移動機巢編隊部署、協調和重新規劃的程序。該算法首先從算法2獲得結果（第1～2行），然后部署無人機編隊（第3～11行）。表示第j隊中第k個無人機的軌跡。如果協調標志被置為真，那么移動機巢將不斷更新超循環周期，并與相鄰機巢保持統一的時間間隔（第14～16行），如果規劃的釋放點被封鎖，移動機巢將尋找新的釋放點（第17～19行）。

3 仿真分析

所提出的算法在具有1.6GHz處理器和16GB內存的Intel Core i7平臺上實現。在本節中，假設無人機的探測范圍為d=1米，最大能量=100，充電率β+=1/s，耗盡率β-=1/s，最大速度=0.4m/s。移動機巢的最大速度為=0.2m/s，感應范圍為5.5米。

3.1 隨機障礙物情況

在這種情況下，考慮在一個25×25米的環境中進行監測任務，包含未知的障礙物。使用一個1個移動機巢和4架無人機的單一編隊上測試所提出的算法。在離線規劃算法中，將魯棒性條件maxj,k|Lj,k|設定為4米。圖6和圖7分別顯示了單隊模擬中的環境設置和移動機巢軌跡，綠色和紅色標記分別表示計劃釋放點和重新規劃算法找到的新釋放點，粗黑線表示由離線規劃計算的分區。如圖7所示，當規劃的釋放點被障礙物占據時，移動機巢會尋找新的釋放點。由于離線規劃中4米的魯棒性對于圖6中的稀疏環境來說足夠大，所以移動機巢可以保證找到一個可行的釋放點。離線規劃計算出的單個無人機-移動機巢編隊的最大年齡是1210.71秒，而Gazebo模擬中觀察到的是1302.47秒。這是由于：1）離線規劃器假設機巢以其最大速度移動，這在模擬中無法實現；2）模擬中無人機和移動機巢之間存在通信延遲；3）離線規劃器考慮的是無障礙環境，因此移動機巢遵循最短路徑，而在Gazebo模擬中，移動機巢必須避開障礙物。

圖6 環境障礙物設置

圖7 移動機巢在Gazebo模擬中的路徑

3.2 魯棒性分析

該算法的性能受到魯棒性參數的顯著影響。過大的魯棒性將導致無人機-移動機巢編隊的行為保守。在不同的魯棒度下離線規劃分區劃分結果如圖8所示，黑色實線表示分區和環境的邊界,彩色線表示無人機的軌跡。隨著魯棒性的增加，離線規劃器傾向于生成較小的分區。因此，分區的數量會增加。一般來說，與分區相關的年齡隨著魯棒性的增加而增加。在圖9中，魯棒度從0米增加到4米時，年齡隨著魯棒性增加而減少，超過4米后隨著魯棒度的增加而增加。年齡下降的原因是離線規劃給出的最大分區并不保證是最優的。如果最優分區被證明比最大分區小，那么稍微增加魯棒度就會產生更接近最優分區的分區，從而降低年齡。如果魯棒度不斷增加，規劃算法將產生更小的分區，因此無人機將花費更多的時間起飛和降落，這將增加年齡。對于25×25米的環境，8米的魯棒性可認為是足夠大的，因為障礙物的面積必須大于64π平方米，才能使離線規劃計算的軌跡失效。與零魯棒性相比，將魯棒性設置為8米時，規劃性能仍可接受（增加了約22%的年齡）。

圖8 在不同的魯棒度下離線規劃分區劃分結果

圖9 不同魯棒度下離線規劃算法計算的年齡

3.3 可擴展性分析

將所提出的算法的離線模塊與文獻[18]中算法在計算時間和不同參數下的最大年齡方面進行比較，因為這兩種算法在離線規劃中都沒有考慮障礙物。由于離線規劃涉及求解TSP問題，其可擴展性主要取決于所使用的TSP求解器。在基準分析中，兩種算法都采用了Lin-Kernighan-Helsgaun（LKH）TSP求解器[19]。在圖10(a)中可以看到，所提出的方法可以擴展到環境的面積，而文獻[18]中的算法則會發散。兩種算法的最大年齡幾乎相同，它們與環境的面積呈線性關系。在圖10(b)中，比較了兩種算法在不同能耗-充電比率下的性能。兩種算法的最大年齡隨著耗盡-充電比率的增加而增加，除了2.4和3.49的比率外，它們保持接近。在高比率下，所提出的算法比文獻[18]中的方法有更高的年齡。這是由于所提出的策略是尋找最大的方形分區，在高能耗-充電比率下，正方形分區往往比文獻[18]中的矩形分區要小。文獻[18]中的算法在低能耗-充電比率下有較長的計算時間，但所提出的算法并沒有受到比率的明顯影響。圖10(c)顯示了無人機數量與算法性能之間的關系。最大年齡隨著使用更多的無人機而減少，所提出的算法比文獻[18]中的算法略高。隨著無人機數量的增加，對最大年齡的改善逐漸放緩，可以預見，在某一時刻，增加無人機的數量將無法改善最大年齡。雖然增加無人機的數量可以減少文獻[18]中算法的計算時間，但對所提出算法的計算時間影響不大。在圖10(d)中，比較了兩種算法在不同無人機-機巢速度比下的性能。兩種算法在不同速度比下的最大年齡幾乎相同，而且都隨著速度比的增加而減少。就計算時間而言，速度比對所提出的算法沒有影響，而更高的速度比導致文獻[18]中的算法計算時間更長。

圖10 不同參數下所提出方法與文獻[18]中算法的比較

4 結語

提出了一種啟發式的能量感知算法，用于規劃無人機-移動機巢編隊的路徑，以完成持續電力監測任務。通過在離線規劃算法中引入魯棒性條件，證明了所提出的方法在有未知障礙物的環境中是可行的。還提出了一個部署協議和一個移動機巢協調算法，多個無人機-移動機巢編隊可以協作的方式完成巡邏任務，同時使整體性能最大化。下一步研究中將使用時間邏輯來描述更復雜的監測任務，并探索分布式策略來完成無人機-移動機巢的路徑規劃。