異構(gòu)多無人機應援

李純良 金康康 孫欽瑤 周旭

摘 要：波多黎各的颶風對人的生命和財產(chǎn)造成威脅，颶風發(fā)生后的應急救援因災難信息獲取困難，導致破壞性增大。

首先，綜合考慮運送路況和道路視頻偵查指標，運用拉格朗日乘子法構(gòu)造條件極值函數(shù)，建立拉格朗日乘子法選址模型，求得兩個最佳地點P與Arecibo的經(jīng)緯度坐標分別為（18.33°N，65.97°W）、（18.47°N，66.73°W）;基于混合式模擬退火算法構(gòu)建三維裝箱模型，根據(jù)所給數(shù)據(jù)確定出無人機艦隊由3架B型無人機，1架F型無人機，1架C型無人機組成，并確定出異構(gòu)無人機間的具體協(xié)作方式。

關鍵詞：物資配送;Lagrange乘子法;三維裝箱;混合式模擬退火算法

引言

美國波多黎各遭遇嚴重颶風，這場災難造成了數(shù)千人死亡，并且對波多黎各的建筑與植被造成了巨大的破壞。波多黎各財產(chǎn)損失嚴重，災難使得波多黎各幾乎全部斷電、斷網(wǎng)，這嚴重阻礙了救援行動的展開和波多黎各居民的自救。

對此情況，非政府組織HELP， Inc.需要設計一種名為“Drone Go”的無人機救援系統(tǒng)，包括無人機對醫(yī)療包的運送與無人機對災后道路情況的偵查。系統(tǒng)具體功能：

首先，對于所給醫(yī)院的位置確定一個放置“Drone Go”系統(tǒng)的最佳地點，確定地點時既要考慮到醫(yī)療用品的運送也要考慮到道路視頻偵查;其次，確定無人機選取方案，求出最終需要各種無人機與醫(yī)療包的數(shù)量。對于確定好的無人機與醫(yī)療包的數(shù)量，為最多三個ISO集裝箱提供相關的裝載方案。針對所提供的“Drone Go”方案中的所有無人機，為其提供有效載荷包裝配置、送貨路線和時間表，使其足夠滿足確定的醫(yī)療包要求，并提供一份無人機飛行計劃，使無人機能使用機載攝像頭錄制路況信息回饋給救援隊，對其開展救援提供幫助。

1 建立拉格朗日乘子法選址模型

1.1坐標轉(zhuǎn)換

大多情況下使用的為平面坐標點，首先利用Global Mapper軟件將五個地點的經(jīng)緯度坐標轉(zhuǎn)換為平面坐標，以方便進行間距離的計算

1.2 運用拉格朗日乘子法確定最優(yōu)坐標點

拉格朗日乘子法又稱為拉格朗日乘數(shù)法，是用來求解函數(shù)f（x1，x2，…，xn）=0在g（x1，x2，…，xn）=0的約束條件下的極值。

1.3模型建立與求解

已知四座城市的坐標，確定一坐標點P（x，y），使P到Q1、Q2、Q3、Q4距離之和最小，通過兩點之間的距離公式? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ，分別計算出各城市之間的距離[2]。

2. 無人機艦隊構(gòu)造

無人機貨艙只有兩種，容積分別為1120、6900，結(jié)合醫(yī)院對醫(yī)療包的需求可以得出醫(yī)院所需醫(yī)療包總體積，顯然部分飛機無法實現(xiàn)一次將醫(yī)療包送向某需求量較大的醫(yī)院，篩選后可得到可以到飛往各城市的無人機種類[3]。

將運送物資的無人機與偵察路線的無人機分開討論。F型飛機雖然沒有視察功能，但是有效載荷能力相對于其他型的無人機占有巨大優(yōu)勢。再結(jié)合它空載可飛行的距離來看，確定出F型飛機從F點出發(fā)相繼向Q3、Q4 兩地送往物資，B型無人機向Q1地運送物資，C型無人機向Q2地運送，B型無人機空載時飛行的距離最大，所以選派B作為偵察機，同時送貨的B、C運送完藥品后還可以偵察路況。

盡管Q5 醫(yī)院本身就是物資點不需要配送醫(yī)療包，但是由于還需要Q5 醫(yī)院與其他醫(yī)院之間的路況信息。考慮到其他所有醫(yī)院與Q5 醫(yī)院的距離都遠大于無人機最大飛行航程，本文提出兩架無人機相向行駛的方案。但是本方案中無人機飛行后會相遇在非救助點，此時能量耗盡而不能確保有人能夠及時給無人機更換電池，因而本方案中需要的無人機在很大的概率上是無法回收的[4]。

時，說明貨物 沒有被裝進集裝箱;Ri-Ri=0 時，表示貨物可以任意旋轉(zhuǎn);Ri=1時，表示貨物可以水平旋轉(zhuǎn);Ri=2時，表示貨物不可以旋轉(zhuǎn);a1，a2，b1，b2，c表示貨物裝載后在三維方向上的重心坐標邊界[8]。

設定災難救援持續(xù)8個月，所以一套醫(yī)療包包括1680個MED1，480個MED2，960個MED3。集裝箱放置點為兩個，每個點一個集裝箱[10]。其中P點處集裝箱裝箱情況為2架B型無人機，1架C型無人機，1架F型無人機;1440個MED1，480個MED2，960個MED3;Q5點處集裝箱裝箱情況：1架B型無人機，240個MED1，具體的裝箱順序和裝箱排列見圖 4。

3. 結(jié)論

最終確定選用5架無人機，分別為3架B型無人機，1架F型無人機，1架C型無人機。異構(gòu)無人機間的協(xié)作方式：派兩架B型無人機作為偵察機，另一架B型無人機、C型無人機和F型無人機一起運送物資，同時B型無人機、C型無人機運送完藥品還可繼續(xù)偵察。其次，該偵查方式還考慮到?jīng)]有探測到路線信息、偵察型無人機在探測到危險時的狀況，保證了其可行性與自適應性。

參考文獻：

[1] Everett， Hugh. "Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources." Operations Research 11.3（1963）：399-417.

[2]肖東. 異構(gòu)多無人機自主任務規(guī)劃方法研究[D].南京航空航天大學，2018.

[3] Kunoth， Angela . "Multilevel preconditioning - appending boundary conditions by Lagrange multipliers. " Advances in Computational Mathematics 4.1（1995）：145-170.

[4] Liao， Chung Shou ， and C. H. Hsu . "New lower bounds for the three-dimensional orthogonal bin packing problem. " European Journal of Operational Research 225.2（2013）：244-252.

[5]龐海龍. 一種異構(gòu)多無人機多目標任務分配方法[A]. 中國指揮與控制學會.第四屆中國指揮控制大會論文集[C].中國指揮與控制學會：中國指揮與控制學會，2016：4.

[6]丁臻極，王從慶，叢楚瀅，李志宇.城市環(huán)境下的異構(gòu)多無人機層次化任務分配[J].華中科技大學學報（自然科學版），2015，43（S1）：302-306.