面向農(nóng)業(yè)園區(qū)污染源監(jiān)測的多無人機(jī)路徑優(yōu)化方法研究*

杜心怡，徐 玲，蘇瑩怡，何羽亭，張 旭，丁 濤

（中國計(jì)量大學(xué)，浙江 杭州 310018）

我國現(xiàn)有各級農(nóng)業(yè)園區(qū)和農(nóng)業(yè)生產(chǎn)基地在促進(jìn)產(chǎn)業(yè)集聚和推動經(jīng)濟(jì)發(fā)展中貢獻(xiàn)重大。但與此同時，園區(qū)生產(chǎn)過程中引發(fā)的環(huán)境問題也日益突出，成為環(huán)境污染的集聚區(qū)域。政府部門通過加強(qiáng)對農(nóng)業(yè)園區(qū)污染源的日常環(huán)境監(jiān)察和巡查，有利于及時評估園區(qū)范圍內(nèi)的大氣污染狀況、監(jiān)控各污染源排放現(xiàn)狀并快速確定超標(biāo)排放污染源的準(zhǔn)確位置，對實(shí)現(xiàn)園區(qū)大氣污染的靶向治理和制定有效的應(yīng)急處置方案具有重要意義。目前污染源的日常環(huán)境監(jiān)察一般采用固定監(jiān)測站、無線傳感器網(wǎng)絡(luò)、監(jiān)測車或手持式監(jiān)測儀等方式。超標(biāo)污染源的定位一般通過將其監(jiān)測位置和污染物信息濃度相綜合，得到較粗略的濃度分布圖，進(jìn)而估計(jì)出污染源的位置[1]。但由于受地面條件、建筑物和城市道路限制，上述監(jiān)測手段往往效率不高。同時由于監(jiān)測點(diǎn)位往往分布不均勻，且事故污染源附近不一定恰好設(shè)有監(jiān)測站或被監(jiān)測點(diǎn)所包圍。雖然可以通過增加監(jiān)測站數(shù)量和觀測頻率來提高環(huán)境監(jiān)測質(zhì)量，但仍面臨著監(jiān)測范圍有限、成本高昂且機(jī)動性差的問題。目前研究結(jié)果表明，無人機(jī)環(huán)境監(jiān)測平臺具有機(jī)動、靈活和監(jiān)測范圍廣等優(yōu)勢，可以彌補(bǔ)現(xiàn)有固定監(jiān)測站和監(jiān)測車的不足，更有利于對大氣污染源進(jìn)行日常環(huán)境巡查[2-3]。單架無人機(jī)進(jìn)行園區(qū)內(nèi)大氣污染源監(jiān)測時，由于受無人機(jī)自身續(xù)航時間限制，一次飛行只能完成部分污染源點(diǎn)位的監(jiān)測任務(wù)，監(jiān)測任務(wù)的執(zhí)行效率不高[4-5]，也不滿足多個污染源在監(jiān)測時間上盡量保持同步性的要求。因此，采用多架無人機(jī)來完成多個污染源的監(jiān)測十分必要[6-8]。如何根據(jù)農(nóng)業(yè)園區(qū)污染源監(jiān)測的特定問題來研究構(gòu)建目標(biāo)函數(shù)和約束條件，并采用合適的技術(shù)手段尋找園區(qū)內(nèi)大氣污染源最優(yōu)的監(jiān)測路徑，是本文重點(diǎn)解決的問題。

不同于傳統(tǒng)的多旅行商（mTSP）問題，該方法根據(jù)農(nóng)業(yè)園區(qū)污染源監(jiān)測的特定問題來構(gòu)建目標(biāo)函數(shù)和約束條件，目標(biāo)函數(shù)中考慮了各無人機(jī)監(jiān)測路徑總長度最短、無人機(jī)飛行路徑轉(zhuǎn)彎角最小（保證飛行的平滑度以減少無人機(jī)飛行能耗）、無人機(jī)對障礙物的躲避半徑最大（該項(xiàng)可使得無人機(jī)距離障礙物的路徑適應(yīng)度值小，以保證最終得到的路徑和障礙物保持一定距離）；特定的約束條件包括單架無人機(jī)續(xù)航時間限制、各污染源排放污染物類別和排放污染物數(shù)量限制、各污染源無人機(jī)停留時間限制、無人機(jī)起飛出發(fā)點(diǎn)和終點(diǎn)限制等。而后采用基于復(fù)雜變異樹的多染色體遺傳算法來對上述規(guī)劃模型進(jìn)行求解，得到最優(yōu)的農(nóng)業(yè)園區(qū)污染源監(jiān)測路徑。

1 優(yōu)化方法

該方法首先獲取目標(biāo)農(nóng)業(yè)園區(qū)的環(huán)境信息，所述環(huán)境信息包括無人機(jī)出發(fā)基地和n個污染源位置的坐標(biāo)信息、單架無人機(jī)續(xù)航時間、無人機(jī)平均飛行速度、無人機(jī)飛行單位能耗、無人機(jī)懸停單位能耗、各污染源排放污染物類別和排放污染物數(shù)量、各污染源無人機(jī)停留時間、無人機(jī)數(shù)目m等；而后根據(jù)農(nóng)業(yè)園區(qū)的環(huán)境信息構(gòu)建大氣污染源監(jiān)測的路徑優(yōu)化問題模型，設(shè)定模型的特定目標(biāo)函數(shù)和約束條件；最后基于復(fù)雜變異樹的多染色體遺傳算法來對上述規(guī)劃模型進(jìn)行求解，得到多個無人機(jī)最優(yōu)的農(nóng)業(yè)園區(qū)污染源監(jiān)測路徑；目標(biāo)函數(shù)F為：

minF=w1·L/Lmax+w2·Dmax/D+w3·θ/θmax，

式中，w1，w2和w3為監(jiān)測路徑總長度L、無人機(jī)對障礙物的躲避半徑D、無人機(jī)飛行路徑轉(zhuǎn)彎角θ的三個子目標(biāo)的權(quán)重，w1+w2+w3=1；Lmax、Dmax和 θmax為預(yù)先設(shè)定的極大值，目的為去量綱化。躲避半徑D取倒數(shù)的原因是我們期望無人機(jī)躲避半徑越大越好。

式中，Dm為第m架無人機(jī)的飛行路徑對障礙物的躲避半徑之和，g為障礙物的數(shù)量，dk為飛行路徑距離第k個障礙物的距離，rk為障礙物的最大外圍半徑。

式中，θm為第m架無人機(jī)的飛行路徑上轉(zhuǎn)彎角之和，w為轉(zhuǎn)彎角的數(shù)量，φk為飛行路徑上第k個轉(zhuǎn)彎角。

步驟S2的約束條件為：遍歷農(nóng)業(yè)園區(qū)內(nèi)所有污染源監(jiān)測點(diǎn)、無人機(jī)起飛基地和終點(diǎn)基地均為出發(fā)點(diǎn)：

每個污染源僅停留一次：

單架無人機(jī)續(xù)航能力和其他約束：

式中，M為預(yù)先給定的無人機(jī)數(shù)量；m為優(yōu)化后的無人機(jī)數(shù)量。

2 優(yōu)化步驟

面向農(nóng)業(yè)園區(qū)污染源監(jiān)測的多無人機(jī)路徑優(yōu)化方法的計(jì)算過程如圖1所示。具體過程如下：（1）設(shè)置基于復(fù)雜變異樹的多染色體遺傳算法的參數(shù)，包括種群數(shù)量Pop、迭代次數(shù)S、無人機(jī)數(shù)量（即染色體數(shù)量）M；（2）初始化種群，根據(jù)當(dāng)前染色體數(shù)量M，采用多染色體編碼的方式對種群進(jìn)行編碼，一條染色體代表一架無人機(jī)的污染源監(jiān)測點(diǎn)序列；計(jì)算算法適應(yīng)度函數(shù)；（3）隨機(jī)選擇復(fù)雜變異樹中不同復(fù)雜程度的算子，對各種群進(jìn)行優(yōu)化，復(fù)雜變異樹分為簡單變異算子、一般變異算子和復(fù)雜變異算子。簡單變異算子包括交換（Swap）算子、倒位（Reverse）算子、滑動（Slide）算子、插入（Insert）算子和交叉（Crossover）算子；一般變異算子為隨機(jī)兩個簡單算子結(jié)合而成，包括交換和交叉（Swap & Crossover）算子、逆轉(zhuǎn)和交叉（Reverse & Crossover）算子、滑動和交叉（Slide & Crossover）算子、插入和滑動（Insert & Slide）算子、插入和交叉（Insert & Crossover）算子；復(fù)雜變異算子為隨機(jī)三個簡單算子結(jié)合而成，包括Swap & Reverse & Crossover算子、Slide & Insert & Crossover算子、Swap & Slide & Crossover算子、Slide & Reverse & Crossover算子；（4）判斷當(dāng)前迭代次數(shù)是否達(dá)到最大迭代次數(shù)S，若達(dá)到，則記錄當(dāng)前最優(yōu)解；否則，返回。（5）判斷當(dāng)前無人機(jī)數(shù)量（染色體數(shù)量）是否達(dá)到下限，若達(dá)到，則輸出當(dāng)前最優(yōu)解；否則，無人機(jī)數(shù)量-1，返回。

圖1 多無人機(jī)路徑優(yōu)化算法計(jì)算步驟

3 案例計(jì)算

該實(shí)例中需要解決的技術(shù)問題為：已知某農(nóng)業(yè)園區(qū)內(nèi)各個污染源的位置坐標(biāo)信息和各污染源排放污染物類別和污染物排放數(shù)量，以監(jiān)測區(qū)域的中心點(diǎn)為無人機(jī)出發(fā)基地，m架無人機(jī)航行到n個大氣監(jiān)測點(diǎn)，最終回到出發(fā)基地；每架無人機(jī)可到多個監(jiān)測點(diǎn)進(jìn)行采樣監(jiān)測，要求每個監(jiān)測點(diǎn)都被采樣監(jiān)測且每個監(jiān)測點(diǎn)只能被一架無人機(jī)采樣，根據(jù)各污染源排放污染物類別和排放污染物數(shù)量確定其采樣停留時間，m架無人機(jī)需要在完成監(jiān)測任務(wù)后再回到出發(fā)基地，要求為每架無人機(jī)規(guī)劃出最優(yōu)的監(jiān)測路徑，且無人機(jī)數(shù)量最終達(dá)到最優(yōu)化。已知目標(biāo)農(nóng)業(yè)園區(qū)占地面積為36km2，園區(qū)內(nèi)隨機(jī)分布有20個排放污染源，20個污染源的坐標(biāo)信息、污染物排放類型和無人機(jī)停留時間為已知條件；單架無人機(jī)續(xù)航時間為 40min，平均飛行速度為 5m/s；w1取 0.95，w2取 0，w3取0.05；種群數(shù)量Pop設(shè)定為80，迭代次數(shù)設(shè)定為500，初始無人機(jī)數(shù)量預(yù)設(shè)為8架。利用基于復(fù)雜變異樹的多染色體遺傳算法來對上述規(guī)劃模型進(jìn)行求解，最終得到多個無人機(jī)最優(yōu)的農(nóng)業(yè)園區(qū)污染源監(jiān)測路徑，見圖2。

圖2 農(nóng)業(yè)園區(qū)污染源監(jiān)測路徑MATLAB仿真結(jié)果

由圖2可知，優(yōu)化后的無人機(jī)數(shù)量為6架，第1架無人機(jī)的航行路徑為1→18→2→1，第2架無人機(jī)的航行路徑為1→15→20→1，第3架無人機(jī)的航行路徑為1→12→19→1，第4架無人機(jī)的航行路徑為1→16→17→11→10→1，第5架無人機(jī)的航行路徑為1→6→5→14→1，第6架無人機(jī)的航行路徑為1→4→9→13→3→8→1；6架無人機(jī)的飛行路徑總長度為49.0073km，計(jì)算程序的迭代次數(shù)為435次。由計(jì)算結(jié)果可知，該方法可用于解決農(nóng)業(yè)園區(qū)污染源監(jiān)測的多無人機(jī)路徑優(yōu)化問題。