群體機器人協同控制算法設計

張娜娜，劉婷婷，丁茂臻

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

0 引言

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

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

現有研究成果評價巡邏策略性能主要是基于由機器人行駛距離和搜救點優先級組成的單目標函數，基于此，針對復雜環境下多機器人巡邏系統中存在的通信受限、信息獲取困難、系統能力不足以及能量供應受限等客觀事實，利用群體智能技術所具有的去中心化、智能度高、靈活性強的獨特優勢，解決多機器人巡邏系統中的任務分配和路徑規劃問題。其次，針對水域污染監測場景中，因監測目標點移動引起的動態問題，提出一個分布式自主巡邏動態協同策略。

1 動態氣象威脅并插值增益任務規劃空間建模

國內外研究中對地形的表示大多數過于簡單，常以忽略高程信息為代價將三維空間投射到平面上，并以二進制表示某區域為可飛或禁飛區，不足以滿足在現實世界中的應用。

隨著數字地圖技術的飛速發展，高分辨率數字地形在軍事和民用領域的廣泛應用為無人機航線規劃提供了更廣闊的應用空間，其中由美國國防部和航空航天署主持的 SRTM（Shuttle Radar Topography Mission，航天飛機雷達地形測量）計劃為代表。

利用 SRTM 真實數據選取大小的真實數據，并對該數據間隔0.50 ×0.50 取樣，獲得取樣地形，真實地形和取樣地形如圖1 所示。由于雷達回波質量的問題，SRTM-3 數據存在少量的空缺點和空白區，主要集中在水域和起伏較大的高山、峽谷等，其表現為高程值等于-32768。因此在數字地形構建前應對其空缺點填補，本研究采用內插的空缺點填補，用內插的方法對空洞點進行填充。

圖1 真實地形和取樣地形圖

我國境內的分辨率均為 90 米的地形數據，其精度無法滿足無人機對規劃空間的要求。因此采用三種插值方法對地形數據進行插值處理，其中三次 Spline 插值方法相比最近鄰插值和雙線性插值方法而言，插值精度更高，且在插值點連續二次可導，但也存在計算量大，耗時較長等不足。考慮到地形數據復雜、無人機飛行能力受限等因素，經插值后的地形可能存在坡度較大的區域，為無人機安全飛行埋下隱患，還需對地形的坡度及曲率進行進一步的平滑。

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

圖2 氣象威脅評估模型

2 基于群體智能優化的多機器人任務分配算法設計

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

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

圖3 種子擴散示意圖

針對鳳仙花算法中最優個體傳播距離計算缺陷，提出一個梯度估計最優個體傳播距離的方法，核心思想是利用當代種子傳播信息，計算下一代最優個體的傳播距離。

其次，引入Softmax 回歸模型。通過Softmax 回歸模型對迭代過程中新產生的種子進行預判，淘汰初選效果不好的種子，減少進入適應度評價環節的種子個數，從而在目標函數計算過程較為耗時的應用環境中降低計算時間和計算量，提高計算效率。

此外，受基因突變理論啟發，計劃設計一個引導二次傳播算子。當某個環境維度發生變異時，與其在同一環境維度其他種子有更高的概率發生變異，進一步提高算法的搜索能力。

通過實驗對所提算法的多峰優化能力進行驗證，并將其與其他經典多峰優化算法在標準測試函數上的優化性能進行比較，最后將所提算法應用到兩個MUTA 仿真案例上，分別驗證引導二次傳播算子在搜索能力上的提升和所提算法在降低計算復雜度上的成效。

3 用于多機器人巡邏路徑規劃的多目標鳳仙花優化算法設計

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

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

圖4 CMGBO 框架圖

協同進化機制：m 子種群中第i 個解Xm,i，對應種子的機械傳播過程如下：

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

4 基于事件驅動控制的動態協同策略設計

在機器人選擇監測目標時，通過對訪問頻率和能量損耗的綜合考慮，建立一種雙向評價機制，同時提出一種潛在工作負載系數，避免隱形監測隊列的堆積。接下來，通過對機器人定位監測目標過程中運動模式的分析，定義一系列事件類型和協同動作，采用合理的目標轉移和機器人釋放等方式，提高移動搜救目標的訪問頻率和機器人的工作效率。

機器人根據定義的前向效用方程在可供選擇的目標里選擇最適合的目標，從該目標的角度根據定義的后向效用方程判斷該機器人是否同樣是最適合對其執行搜救任務的機器人。當這樣的雙向選擇達成一致時，機器人即可確定搜救目標。根據多機器人在向目標移動過程中的運動模式分析，歸納得到不同的事件類型。當這些事件其中之一發生時，相關的兩個機器人之間通過即時通信確定協同模式。通過與其他三種前沿算法的比較，驗證所提的策略在降低目標每兩次被訪問之間時間間隔的優勢，同時，通過在仿真環境的應用和分析，進一步說明在此類環境中的應用前景。

5 總結

針對水域污染監測場景中，因監測目標點移動引起的動態問題，在復雜環境下多機器人巡邏系統中存在的通信受限、信息獲取困難、系統能力不足以及能量供應受限等客觀事實，利用群體智能技術所具有的去中心化、智能度高、靈活性強的獨特優勢，提出一個分布式自主巡邏動態協同策略，解決多機器人巡邏系統中的任務分配和路徑規劃問題。此外，群體機器人協同在各種場景中都有潛在的應用，如農業、物流、醫療和救援等，總之，多機器人巡邏系統中的任務分配和路徑規劃問題的設計，具備較高的實用價值和社會價值。