李 晉，何 勇，董麗夢(mèng)，原瀚杰

（廣東電網(wǎng)有限責(zé)任公司肇慶供電局，肇慶 243000）

0 引言

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

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

1 路徑規(guī)劃問(wèn)題

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

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

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

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

假設(shè)移動(dòng)機(jī)巢擁有無(wú)限的能量，因?yàn)樗鼈兺ǔ碛斜葻o(wú)人機(jī)大得多的能量容量。

3）安全約束：每架無(wú)人機(jī)在沒(méi)有能量時(shí)必須著陸。此外，無(wú)人機(jī)i在落地時(shí)必須在某個(gè)移動(dòng)機(jī)巢j上，即：

給定一個(gè)由無(wú)人機(jī)和移動(dòng)機(jī)巢組成的編隊(duì)，其模型如上所述，持續(xù)監(jiān)測(cè)問(wèn)題的目標(biāo)是基于一個(gè)叫做“年齡”的指標(biāo)。監(jiān)測(cè)環(huán)境中每一個(gè)單元的年齡是指自上次被監(jiān)測(cè)以來(lái)所經(jīng)過(guò)的時(shí)間。每當(dāng)無(wú)人機(jī)訪問(wèn)單元的中心點(diǎn)時(shí)，它的時(shí)間就變?yōu)榱?。無(wú)人機(jī)軌跡集pA會(huì)產(chǎn)生一組到達(dá)時(shí)間，表示無(wú)人機(jī)到達(dá)先前未被占用的節(jié)點(diǎn)的時(shí)間。同樣，無(wú)人機(jī)軌跡產(chǎn)生了一個(gè)離開(kāi)時(shí)間集，它包括無(wú)人機(jī)從一個(gè)空閑節(jié)點(diǎn)出發(fā)的時(shí)間。對(duì)于ε＞0，到達(dá)和離開(kāi)時(shí)間集可定義為：

所有監(jiān)測(cè)空間單元的最大年齡由到達(dá)和離開(kāi)時(shí)間集唯一決定。

定義1：對(duì)于任何給定的pA，在時(shí)間區(qū)間（t,∞）上的最大年齡定義為：

對(duì)于監(jiān)測(cè)環(huán)境Q，給定n架無(wú)人機(jī)和m臺(tái)移動(dòng)機(jī)巢，在速度、能量和安全約束條件下，找到無(wú)人機(jī)和移動(dòng)機(jī)巢的所有軌跡，使式(8)中最大年齡的極限值最小，即：。

2 協(xié)同路徑規(guī)劃方法

所提出的規(guī)劃算法包含離線和在線模塊。首先討論了該算法在包含一個(gè)移動(dòng)機(jī)巢和n架無(wú)人機(jī)的編隊(duì)中的應(yīng)用。然后將把它擴(kuò)展到有多個(gè)編隊(duì)的情況。

離線規(guī)劃模塊的工作原理如下：1）將環(huán)境劃分為方形區(qū)域（分區(qū)），每個(gè)區(qū)域都由無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)在一個(gè)能耗循環(huán)內(nèi)監(jiān)測(cè)。2）將每個(gè)方形區(qū)域劃分為子區(qū)，并指定一架無(wú)人機(jī)監(jiān)測(cè)每個(gè)子區(qū)。3）找到連接哈密爾頓循環(huán)的釋放點(diǎn)，即區(qū)域中心質(zhì)點(diǎn)。移動(dòng)機(jī)巢將把無(wú)人機(jī)沿著哈密頓循環(huán)運(yùn)送到每個(gè)釋放點(diǎn)，而無(wú)人機(jī)則起飛監(jiān)測(cè)指定的子分區(qū)，然后返回移動(dòng)機(jī)巢充電并運(yùn)送到下一個(gè)釋放點(diǎn)。

在線規(guī)劃模塊工作時(shí)，無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)首先嘗試執(zhí)行由離線規(guī)劃模塊計(jì)算出的路徑。假設(shè)障礙物都在地面上，空中沒(méi)有障礙物。移動(dòng)機(jī)巢安裝有傳感器，從而知道其感應(yīng)范圍內(nèi)的單元是否被障礙物占據(jù)。每個(gè)障礙物占據(jù)一個(gè)或多個(gè)單元（如圖6所示）。1）移動(dòng)機(jī)巢在從一個(gè)釋放點(diǎn)到另一個(gè)釋放點(diǎn)的過(guò)程中，采用基于采樣的路徑規(guī)劃算法，機(jī)載傳感器更新障礙物的信息；2）如果規(guī)劃中的釋放點(diǎn)被障礙物占據(jù)，移動(dòng)機(jī)巢將搜索新的可行的釋放點(diǎn)。之所以提出步驟2，是因?yàn)樵陔x線規(guī)劃模塊中假設(shè)釋放點(diǎn)是無(wú)障礙物的，但在實(shí)際執(zhí)行階段它們可能被最初的未知障礙物占據(jù)。此外，新的釋放點(diǎn)不能在步驟2中任意選擇，因?yàn)樗仨毐ＷC無(wú)人機(jī)能夠監(jiān)測(cè)其分配的子分區(qū)，并在能量耗盡之前返回到移動(dòng)機(jī)巢。所提出的算法對(duì)未知障礙物具有魯棒性，即只要障礙物足夠小，就能在理論上保證可行的釋放點(diǎn)的存在。

2.1 分區(qū)

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

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

圖2 子分區(qū)方案及案例

在找到分區(qū)集合P 之后，可以通過(guò)T S P 求解器計(jì)算出穿越P中所有分區(qū)中心點(diǎn)的最短哈密爾頓循環(huán)。表示沿著哈密爾頓循環(huán)的分區(qū)序列。移動(dòng)機(jī)巢首先將無(wú)人機(jī)運(yùn)送到P′1的中心點(diǎn)，然后釋放所有的無(wú)人機(jī)訪問(wèn)P′1中的節(jié)點(diǎn)，之后再返回移動(dòng)機(jī)巢。然后，移動(dòng)機(jī)巢將無(wú)人機(jī)運(yùn)送到下一個(gè)釋放點(diǎn)，同時(shí)給無(wú)人機(jī)充電。無(wú)人機(jī)在充滿電之前不會(huì)被釋放。無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)重復(fù)這一程序，直到他們完成對(duì)的監(jiān)測(cè)并返回到P′1。將這個(gè)過(guò)程被稱(chēng)為一個(gè)超循環(huán)，其周期表示為T(mén)s。

2.2 子分區(qū)

當(dāng)且僅當(dāng)：

分區(qū)P是可行的。違反式(11)意味著無(wú)人機(jī)在一個(gè)能耗循環(huán)內(nèi)不能監(jiān)測(cè)至少一個(gè)分區(qū)。將式(11)用來(lái)檢查分區(qū)可行性。

2.3 生成軌跡

所以超循環(huán)周期Ts可以表示為：

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

2.4 魯棒可行性分析

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

圖3 尋找釋放點(diǎn)示例

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

證明：使用圖4進(jìn)行說(shuō)明。圓內(nèi)的任意點(diǎn)M通過(guò)三角形不等式滿足|MO|≤ρ，

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

為了在所提出的算法中利用定理1，需要估計(jì)障礙物有多大，然后確定一個(gè)足夠大的半徑ρ，形成一個(gè)可以覆蓋任何障礙物的圓。在離線規(guī)劃步驟中，任何違反增強(qiáng)可行性條件式(16)的分區(qū)都被排除。如果在無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)執(zhí)行規(guī)劃時(shí)發(fā)現(xiàn)原始釋放點(diǎn)被障礙物阻擋，根據(jù)定理1，圍繞中心點(diǎn)的半徑為ρ的圓內(nèi)的任何無(wú)障礙點(diǎn)都是可行釋放點(diǎn)。然后，只要障礙物沒(méi)有切斷自由空間，移動(dòng)機(jī)巢就可以進(jìn)行重新規(guī)劃，尋找最近的可行釋放點(diǎn)，并繼續(xù)執(zhí)行任務(wù)。

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

2.5 無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)的部署協(xié)調(diào)

多個(gè)無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)的部署會(huì)影響到持久監(jiān)測(cè)問(wèn)題中的最大年齡。因此本文目標(biāo)是找到一個(gè)使最大年齡最小化的部署協(xié)議?？紤]一個(gè)持久監(jiān)測(cè)任務(wù)，其中m個(gè)無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)用來(lái)監(jiān)測(cè)k個(gè)地點(diǎn)。假設(shè)所有的編隊(duì)在啟動(dòng)超循環(huán)。具體來(lái)說(shuō)編隊(duì)i將在時(shí)間開(kāi)始超循環(huán)，ti表示編隊(duì)i與下一編隊(duì)的時(shí)間差。將該部署協(xié)議產(chǎn)生的最大年齡表示為，將地面實(shí)測(cè)超循環(huán)周期表示為。圖5給出了時(shí)間說(shuō)明，由于空間的限制，只顯示了2個(gè)監(jiān)測(cè)周期。不同的顏色被用來(lái)區(qū)分k個(gè)監(jiān)測(cè)地點(diǎn)。時(shí)間軸上的彩色點(diǎn)表示無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)訪問(wèn)相關(guān)地點(diǎn)的時(shí)間戳。

圖5 無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)部署協(xié)議說(shuō)明

最佳部署協(xié)議可以通過(guò)求解以下優(yōu)化問(wèn)題得到：

因?yàn)門(mén)s是由假設(shè)無(wú)障礙環(huán)境的離線規(guī)劃算法給出的，并且移動(dòng)機(jī)巢采用釋放點(diǎn)之間的最短路徑，所以T′s≥Ts。結(jié)合式(21)可得：

其中，kj(t)表示編隊(duì)j在時(shí)間t經(jīng)歷的超循環(huán)數(shù)，Pij表示團(tuán)隊(duì)j記錄的第i個(gè)超循環(huán)。將移動(dòng)機(jī)巢j到達(dá)分區(qū)Pk的時(shí)間戳表示為tk,j。每個(gè)移動(dòng)機(jī)巢j都需要滿足以下約束條件，以便它們能夠相互協(xié)調(diào)，保持的時(shí)間間隔。

算法4給出了無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)部署、協(xié)調(diào)和重新規(guī)劃的程序。該算法首先從算法2獲得結(jié)果（第1～2行），然后部署無(wú)人機(jī)編隊(duì)（第3～11行）。表示第j隊(duì)中第k個(gè)無(wú)人機(jī)的軌跡。如果協(xié)調(diào)標(biāo)志被置為真，那么移動(dòng)機(jī)巢將不斷更新超循環(huán)周期，并與相鄰機(jī)巢保持統(tǒng)一的時(shí)間間隔（第14～16行），如果規(guī)劃的釋放點(diǎn)被封鎖，移動(dòng)機(jī)巢將尋找新的釋放點(diǎn)（第17～19行）。

3 仿真分析

所提出的算法在具有1.6GHz處理器和16GB內(nèi)存的Intel Core i7平臺(tái)上實(shí)現(xiàn)。在本節(jié)中，假設(shè)無(wú)人機(jī)的探測(cè)范圍為d=1米，最大能量=100，充電率β+=1/s，耗盡率β-=1/s，最大速度=0.4m/s。移動(dòng)機(jī)巢的最大速度為=0.2m/s，感應(yīng)范圍為5.5米。

3.1 隨機(jī)障礙物情況

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

圖6 環(huán)境障礙物設(shè)置

圖7 移動(dòng)機(jī)巢在Gazebo模擬中的路徑

3.2 魯棒性分析

該算法的性能受到魯棒性參數(shù)的顯著影響。過(guò)大的魯棒性將導(dǎo)致無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)的行為保守。在不同的魯棒度下離線規(guī)劃分區(qū)劃分結(jié)果如圖8所示，黑色實(shí)線表示分區(qū)和環(huán)境的邊界,彩色線表示無(wú)人機(jī)的軌跡。隨著魯棒性的增加，離線規(guī)劃器傾向于生成較小的分區(qū)。因此，分區(qū)的數(shù)量會(huì)增加。一般來(lái)說(shuō)，與分區(qū)相關(guān)的年齡隨著魯棒性的增加而增加。在圖9中，魯棒度從0米增加到4米時(shí)，年齡隨著魯棒性增加而減少，超過(guò)4米后隨著魯棒度的增加而增加。年齡下降的原因是離線規(guī)劃給出的最大分區(qū)并不保證是最優(yōu)的。如果最優(yōu)分區(qū)被證明比最大分區(qū)小，那么稍微增加魯棒度就會(huì)產(chǎn)生更接近最優(yōu)分區(qū)的分區(qū)，從而降低年齡。如果魯棒度不斷增加，規(guī)劃算法將產(chǎn)生更小的分區(qū)，因此無(wú)人機(jī)將花費(fèi)更多的時(shí)間起飛和降落，這將增加年齡。對(duì)于25×25米的環(huán)境，8米的魯棒性可認(rèn)為是足夠大的，因?yàn)檎系K物的面積必須大于64π平方米，才能使離線規(guī)劃計(jì)算的軌跡失效。與零魯棒性相比，將魯棒性設(shè)置為8米時(shí)，規(guī)劃性能仍可接受（增加了約22%的年齡）。

圖8 在不同的魯棒度下離線規(guī)劃分區(qū)劃分結(jié)果

圖9 不同魯棒度下離線規(guī)劃算法計(jì)算的年齡

3.3 可擴(kuò)展性分析

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

圖10 不同參數(shù)下所提出方法與文獻(xiàn)[18]中算法的比較

4 結(jié)語(yǔ)

提出了一種啟發(fā)式的能量感知算法，用于規(guī)劃無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)的路徑，以完成持續(xù)電力監(jiān)測(cè)任務(wù)。通過(guò)在離線規(guī)劃算法中引入魯棒性條件，證明了所提出的方法在有未知障礙物的環(huán)境中是可行的。還提出了一個(gè)部署協(xié)議和一個(gè)移動(dòng)機(jī)巢協(xié)調(diào)算法，多個(gè)無(wú)人機(jī)-移動(dòng)機(jī)巢編隊(duì)可以協(xié)作的方式完成巡邏任務(wù)，同時(shí)使整體性能最大化。下一步研究中將使用時(shí)間邏輯來(lái)描述更復(fù)雜的監(jiān)測(cè)任務(wù)，并探索分布式策略來(lái)完成無(wú)人機(jī)-移動(dòng)機(jī)巢的路徑規(guī)劃。