張娜娜，劉婷婷，丁茂臻

（1.鄭州西亞斯學(xué)院 計(jì)算機(jī)與軟件工程學(xué)院，河南鄭州，451150；2.河南省智能制造數(shù)字孿生工程研究中心，河南鄭州，451150；3.河北工業(yè)大學(xué)，天津，300401）

0 引言

多機(jī)器人系統(tǒng)具有搭建和維護(hù)成本更低、應(yīng)用場(chǎng)景更為靈活和參與任務(wù)時(shí)效性更快等特點(diǎn)，不同的任務(wù)環(huán)境下的具體表現(xiàn)形式可以是自主水下航行器[1]和無人飛行器[2]等，機(jī)器人之間具備相互協(xié)調(diào)溝通的能力，通過協(xié)作提高解決問題的速度和效率，并通過執(zhí)行任務(wù)之間的重疊部分補(bǔ)償個(gè)體故障造成的缺口，從而提高系統(tǒng)的魯棒性?；诙鄼C(jī)器人系統(tǒng)的特點(diǎn)和優(yōu)勢(shì)[3]，許多研究機(jī)構(gòu)和國際組織都將其視為安全防衛(wèi)和災(zāi)害響應(yīng)領(lǐng)域中極具前景的戰(zhàn)略之一。捷克科技大學(xué)的學(xué)者提出可以將其應(yīng)用于偵測(cè)航運(yùn)中（例如海盜等）的犯罪行為[4]；西班牙政府在 2010-2018 國家航運(yùn)安全與救援計(jì)劃中，提出通過飛行器所載攝像頭檢測(cè)、監(jiān)控航運(yùn)船只污染行為[5]；英國倫敦大學(xué)學(xué)院的學(xué)者提出應(yīng)用機(jī)器人對(duì)街區(qū)進(jìn)行以維護(hù)治安和打擊犯罪為目的的督查[6]。

多機(jī)器人任務(wù)分配（Multi-robot Task Allocation,MRTA）及多機(jī)器人軌跡規(guī)劃方法的代表性成果也很多，已實(shí)現(xiàn)快速響應(yīng)動(dòng)態(tài)環(huán)境但易陷入局部最優(yōu)解[7]。Marjorie Darrah 等[8]利用改進(jìn)遺傳算法解決了機(jī)器人的任務(wù)分配問題。有偉等[9]綜合考慮多種約束條件，建立了多目標(biāo)整數(shù)規(guī)劃的任務(wù)協(xié)同分配模型，設(shè)計(jì)了一種免疫粒子群算法，較好地保證了算法的多樣性和局部搜索能力，解決了多機(jī)器人任務(wù)分配問題。多機(jī)器人軌跡規(guī)劃算法主要可以分為兩類：確定性搜索算法和隨機(jī)性搜索算法。Duan Haibin 等[10]利用改進(jìn)蟻群算法求解航跡。Zhang Chao 等[11]將飛行區(qū)域劃分為網(wǎng)格，運(yùn)用蟻群算法求解出從出發(fā)點(diǎn)到目標(biāo)點(diǎn)的較優(yōu)航線。Fei Su 等[12]建立了基于改進(jìn)蟻群算法在復(fù)雜戰(zhàn)場(chǎng)環(huán)境中航線求解方法。

現(xiàn)有研究成果評(píng)價(jià)巡邏策略性能主要是基于由機(jī)器人行駛距離和搜救點(diǎn)優(yōu)先級(jí)組成的單目標(biāo)函數(shù)，基于此，針對(duì)復(fù)雜環(huán)境下多機(jī)器人巡邏系統(tǒng)中存在的通信受限、信息獲取困難、系統(tǒng)能力不足以及能量供應(yīng)受限等客觀事實(shí)，利用群體智能技術(shù)所具有的去中心化、智能度高、靈活性強(qiáng)的獨(dú)特優(yōu)勢(shì)，解決多機(jī)器人巡邏系統(tǒng)中的任務(wù)分配和路徑規(guī)劃問題。其次，針對(duì)水域污染監(jiān)測(cè)場(chǎng)景中，因監(jiān)測(cè)目標(biāo)點(diǎn)移動(dòng)引起的動(dòng)態(tài)問題，提出一個(gè)分布式自主巡邏動(dòng)態(tài)協(xié)同策略。

1 動(dòng)態(tài)氣象威脅并插值增益任務(wù)規(guī)劃空間建模

國內(nèi)外研究中對(duì)地形的表示大多數(shù)過于簡(jiǎn)單，常以忽略高程信息為代價(jià)將三維空間投射到平面上，并以二進(jìn)制表示某區(qū)域?yàn)榭娠w或禁飛區(qū)，不足以滿足在現(xiàn)實(shí)世界中的應(yīng)用。

隨著數(shù)字地圖技術(shù)的飛速發(fā)展，高分辨率數(shù)字地形在軍事和民用領(lǐng)域的廣泛應(yīng)用為無人機(jī)航線規(guī)劃提供了更廣闊的應(yīng)用空間，其中由美國國防部和航空航天署主持的 SRTM（Shuttle Radar Topography Mission，航天飛機(jī)雷達(dá)地形測(cè)量）計(jì)劃為代表。

利用 SRTM 真實(shí)數(shù)據(jù)選取大小的真實(shí)數(shù)據(jù)，并對(duì)該數(shù)據(jù)間隔0.50 ×0.50 取樣，獲得取樣地形，真實(shí)地形和取樣地形如圖1 所示。由于雷達(dá)回波質(zhì)量的問題，SRTM-3 數(shù)據(jù)存在少量的空缺點(diǎn)和空白區(qū)，主要集中在水域和起伏較大的高山、峽谷等，其表現(xiàn)為高程值等于-32768。因此在數(shù)字地形構(gòu)建前應(yīng)對(duì)其空缺點(diǎn)填補(bǔ)，本研究采用內(nèi)插的空缺點(diǎn)填補(bǔ)，用內(nèi)插的方法對(duì)空洞點(diǎn)進(jìn)行填充。

圖1 真實(shí)地形和取樣地形圖

我國境內(nèi)的分辨率均為 90 米的地形數(shù)據(jù)，其精度無法滿足無人機(jī)對(duì)規(guī)劃空間的要求。因此采用三種插值方法對(duì)地形數(shù)據(jù)進(jìn)行插值處理，其中三次 Spline 插值方法相比最近鄰插值和雙線性插值方法而言，插值精度更高，且在插值點(diǎn)連續(xù)二次可導(dǎo)，但也存在計(jì)算量大，耗時(shí)較長(zhǎng)等不足?？紤]到地形數(shù)據(jù)復(fù)雜、無人機(jī)飛行能力受限等因素，經(jīng)插值后的地形可能存在坡度較大的區(qū)域，為無人機(jī)安全飛行埋下隱患，還需對(duì)地形的坡度及曲率進(jìn)行進(jìn)一步的平滑。

以DEM 數(shù)字地圖為基礎(chǔ)，利用三次Spline 曲線插值算法提高地形的分辨率，構(gòu)建更為準(zhǔn)確、真實(shí)的數(shù)字地形環(huán)境，為后續(xù)的任務(wù)分配、航線規(guī)劃提供更為客觀的研究基礎(chǔ)；選取影響氣象威脅度的相關(guān)因子，針對(duì)各種氣象威脅要素構(gòu)建量化等級(jí)，利用專家知識(shí)確立相應(yīng)的條件概率表及轉(zhuǎn)移概率表，選擇前向后向推理算法推理出隨時(shí)間動(dòng)態(tài)變化的氣象威脅等級(jí)，利用基于離散模糊的動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)建立動(dòng)態(tài)氣象模型。氣象威脅評(píng)估模型如圖2 所示。圖中TL 表示威脅等級(jí)(Threat Level，TL)，WT 表示氣象類型(Weather Type，WT)，IOE 表示威脅作用強(qiáng)度(Intensity of Effect，IOE)，DC 表示相對(duì)位置(Distance from Circle，DC)，F(xiàn)T表示飛行動(dòng)作(Fly Type，F(xiàn)T)。

圖2 氣象威脅評(píng)估模型

2 基于群體智能優(yōu)化的多機(jī)器人任務(wù)分配算法設(shè)計(jì)

在自然災(zāi)害搜救場(chǎng)景中，精確的數(shù)學(xué)模型和完備的約束條件往往是很難得到的，用參數(shù)假設(shè)的條件與實(shí)際問題會(huì)存在偏頗，使得根據(jù)這樣的數(shù)學(xué)模型求解的結(jié)果不一定能很好地應(yīng)用于實(shí)際?；谏鲜鲈?，多機(jī)器人任務(wù)分配問題求取多個(gè)近似的最優(yōu)解，以供決策者根據(jù)當(dāng)環(huán)境和實(shí)際需求進(jìn)行選擇和切換。上述求取多個(gè)近似最優(yōu)解的問題歸屬為多峰優(yōu)化的范疇。在求解此類問題時(shí)，傳統(tǒng)的啟發(fā)式算法由于只能收斂到唯一的全局最優(yōu)解，無法被直接應(yīng)用于多峰優(yōu)化問題。文獻(xiàn)[13～16]顯示，鳳仙花優(yōu)化算法作為新型群體智能算法，在全局探索與局部開發(fā)能力之間有較好的調(diào)整機(jī)制。

首先，鳳仙花優(yōu)化算法彈射距離算子的改進(jìn)?；A(chǔ)鳳仙花算法中，機(jī)械傳播算子較為重要，是算法成功的關(guān)鍵因素。種子擴(kuò)散的示意圖如圖3 所示。種子擴(kuò)散范圍的計(jì)算表達(dá)式中，對(duì)于種群在迭代過程中每代的最優(yōu)個(gè)體f( XB)=fmin，這時(shí)最優(yōu)個(gè)體的傳播距離，對(duì)于同一個(gè)優(yōu)化問題，當(dāng)itermax、n和Ainit取定值的情況下，算法每次獨(dú)立運(yùn)行過程中，BA只與迭代次數(shù)iter有關(guān)，即每次獨(dú)立運(yùn)行BA的取值序列都是一致的。這也就意味著，對(duì)于同一個(gè)優(yōu)化問題，每次獨(dú)立運(yùn)行鳳仙花優(yōu)化算法時(shí)，迭代次數(shù)相同，最優(yōu)個(gè)體的傳播距離是一樣的。從中可以發(fā)現(xiàn)，在優(yōu)化過程中，最優(yōu)個(gè)體的搜索行為適應(yīng)性太差。

圖3 種子擴(kuò)散示意圖

針對(duì)鳳仙花算法中最優(yōu)個(gè)體傳播距離計(jì)算缺陷，提出一個(gè)梯度估計(jì)最優(yōu)個(gè)體傳播距離的方法，核心思想是利用當(dāng)代種子傳播信息，計(jì)算下一代最優(yōu)個(gè)體的傳播距離。

其次，引入Softmax 回歸模型。通過Softmax 回歸模型對(duì)迭代過程中新產(chǎn)生的種子進(jìn)行預(yù)判，淘汰初選效果不好的種子，減少進(jìn)入適應(yīng)度評(píng)價(jià)環(huán)節(jié)的種子個(gè)數(shù)，從而在目標(biāo)函數(shù)計(jì)算過程較為耗時(shí)的應(yīng)用環(huán)境中降低計(jì)算時(shí)間和計(jì)算量，提高計(jì)算效率。

此外，受基因突變理論啟發(fā)，計(jì)劃設(shè)計(jì)一個(gè)引導(dǎo)二次傳播算子。當(dāng)某個(gè)環(huán)境維度發(fā)生變異時(shí)，與其在同一環(huán)境維度其他種子有更高的概率發(fā)生變異，進(jìn)一步提高算法的搜索能力。

通過實(shí)驗(yàn)對(duì)所提算法的多峰優(yōu)化能力進(jìn)行驗(yàn)證，并將其與其他經(jīng)典多峰優(yōu)化算法在標(biāo)準(zhǔn)測(cè)試函數(shù)上的優(yōu)化性能進(jìn)行比較，最后將所提算法應(yīng)用到兩個(gè)MUTA 仿真案例上，分別驗(yàn)證引導(dǎo)二次傳播算子在搜索能力上的提升和所提算法在降低計(jì)算復(fù)雜度上的成效。

3 用于多機(jī)器人巡邏路徑規(guī)劃的多目標(biāo)鳳仙花優(yōu)化算法設(shè)計(jì)

目前現(xiàn)有的研究成果評(píng)價(jià)巡邏策略性能主要是基于由機(jī)器人行駛距離和搜救點(diǎn)優(yōu)先級(jí)組成的單目標(biāo)函數(shù)，基于此，提出解決多目標(biāo)問題。第一點(diǎn)與已有研究成果相同是最小化航行路徑長(zhǎng)度以節(jié)省機(jī)器人能量消耗。為了實(shí)現(xiàn)這一點(diǎn)，最簡(jiǎn)單的方式是使一個(gè)機(jī)器人根據(jù)最優(yōu)路徑進(jìn)行搜救。但在危險(xiǎn)場(chǎng)景中，時(shí)效性對(duì)于待援人員的生命安全尤為重要，故第二點(diǎn)須考慮最小化一輪搜救所花費(fèi)的時(shí)間。第三點(diǎn)，距離危險(xiǎn)點(diǎn)越近的人員需越早獲救以確保其安全。綜上所述，研究重點(diǎn)是由這三個(gè)需要同時(shí)被滿足又互相矛盾的目標(biāo)所構(gòu)成的多目標(biāo)問題。

在早期多種群多目標(biāo)優(yōu)算法中，通常會(huì)針對(duì)每個(gè)優(yōu)化目標(biāo)分別生成一個(gè)種群，并行但獨(dú)立搜索，將各自搜索到的最優(yōu)解保存到一個(gè)公共的非支配解集合中，并引入非支配解集合的更新機(jī)制，算法結(jié)束，得到多目標(biāo)優(yōu)化問題的Pareto前端。這種利用多種群解決多目標(biāo)優(yōu)化問題的方法存在一個(gè)缺陷，即缺乏種群搜索過程中信息的共享機(jī)制，不利于算法的快速收斂。在MPMO 框架基礎(chǔ)之上，協(xié)同多目標(biāo)鳳仙花算法（CMGBO）引入多種群協(xié)同進(jìn)化機(jī)制，每次迭代過程中利用公共非支配解集指導(dǎo)各個(gè)種群進(jìn)化，每個(gè)種群都可以在檔案中其他種群的搜索信息的指引下沿PF 進(jìn)行搜索。CMGBO 的框架如圖4 所示，其中Subpop 和obj 分別代表種群和優(yōu)化目標(biāo)。

圖4 CMGBO 框架圖

協(xié)同進(jìn)化機(jī)制：m 子種群中第i 個(gè)解Xm,i，對(duì)應(yīng)種子的機(jī)械傳播過程如下：

其中，Am,r(iter)是從存檔A 中隨機(jī)選擇的非支解；P(Am,r(iter) -X m,i(iter))表示從多目標(biāo)非支配解檔案A 到解決方案Xm,i的信息共享。通過實(shí)驗(yàn)對(duì)所提CMGBO 算法的PF 前端搜索能力進(jìn)行驗(yàn)證，并將其與其他經(jīng)典多目標(biāo)優(yōu)化算法在標(biāo)準(zhǔn)測(cè)試函數(shù)上的優(yōu)化性能進(jìn)行比較，最后將所提算法通過仿真，驗(yàn)證CMGBO 算法在降低計(jì)算復(fù)雜度上的成效。

4 基于事件驅(qū)動(dòng)控制的動(dòng)態(tài)協(xié)同策略設(shè)計(jì)

在機(jī)器人選擇監(jiān)測(cè)目標(biāo)時(shí)，通過對(duì)訪問頻率和能量損耗的綜合考慮，建立一種雙向評(píng)價(jià)機(jī)制，同時(shí)提出一種潛在工作負(fù)載系數(shù)，避免隱形監(jiān)測(cè)隊(duì)列的堆積。接下來，通過對(duì)機(jī)器人定位監(jiān)測(cè)目標(biāo)過程中運(yùn)動(dòng)模式的分析，定義一系列事件類型和協(xié)同動(dòng)作，采用合理的目標(biāo)轉(zhuǎn)移和機(jī)器人釋放等方式，提高移動(dòng)搜救目標(biāo)的訪問頻率和機(jī)器人的工作效率。

機(jī)器人根據(jù)定義的前向效用方程在可供選擇的目標(biāo)里選擇最適合的目標(biāo)，從該目標(biāo)的角度根據(jù)定義的后向效用方程判斷該機(jī)器人是否同樣是最適合對(duì)其執(zhí)行搜救任務(wù)的機(jī)器人。當(dāng)這樣的雙向選擇達(dá)成一致時(shí)，機(jī)器人即可確定搜救目標(biāo)。根據(jù)多機(jī)器人在向目標(biāo)移動(dòng)過程中的運(yùn)動(dòng)模式分析，歸納得到不同的事件類型。當(dāng)這些事件其中之一發(fā)生時(shí)，相關(guān)的兩個(gè)機(jī)器人之間通過即時(shí)通信確定協(xié)同模式。通過與其他三種前沿算法的比較，驗(yàn)證所提的策略在降低目標(biāo)每?jī)纱伪辉L問之間時(shí)間間隔的優(yōu)勢(shì)，同時(shí)，通過在仿真環(huán)境的應(yīng)用和分析，進(jìn)一步說明在此類環(huán)境中的應(yīng)用前景。

5 總結(jié)

針對(duì)水域污染監(jiān)測(cè)場(chǎng)景中，因監(jiān)測(cè)目標(biāo)點(diǎn)移動(dòng)引起的動(dòng)態(tài)問題，在復(fù)雜環(huán)境下多機(jī)器人巡邏系統(tǒng)中存在的通信受限、信息獲取困難、系統(tǒng)能力不足以及能量供應(yīng)受限等客觀事實(shí)，利用群體智能技術(shù)所具有的去中心化、智能度高、靈活性強(qiáng)的獨(dú)特優(yōu)勢(shì)，提出一個(gè)分布式自主巡邏動(dòng)態(tài)協(xié)同策略，解決多機(jī)器人巡邏系統(tǒng)中的任務(wù)分配和路徑規(guī)劃問題。此外，群體機(jī)器人協(xié)同在各種場(chǎng)景中都有潛在的應(yīng)用，如農(nóng)業(yè)、物流、醫(yī)療和救援等，總之，多機(jī)器人巡邏系統(tǒng)中的任務(wù)分配和路徑規(guī)劃問題的設(shè)計(jì)，具備較高的實(shí)用價(jià)值和社會(huì)價(jià)值。