基于改進蟻群算法的多自主式水下機器人任務分配

劉瑞軒，張永林

江蘇科技大學 電子信息學院，江蘇 鎮江 212003

0 引 言

自主式水下機器人（AUV），即在與母船之間沒有物理連接且無人駕駛的情況下，依靠自身攜帶的動力自主完成復雜任務的機器人。AUV的應用范圍非常廣，如海底考察、海底管線鋪設和水下設備維修等民用領域［1-2］，以及海底排雷、偵察和救生等軍用領域。對單個AUV而言，其功能和容量均非常有限，難以滿足大規模的任務需求。因此，多個AUV系統的概念應運而生，即通過多個AUV相互協調共同完成復雜的水下作業任務。這不僅可以彌補單個AUV的不足，也可以提高綜合作業效率。

目前，多機器人的任務分配方法主要包括基于行為的分配方法［3］、市場拍賣算法［4-5］和群體智能算法［6］。其中，基于行為的分配方法的實時性和穩定性較好，但只能求取局部最優解；市場拍賣算法的實時性差且系統配置要求較高，但可以求取全局最優解；群體智能算法分為粒子群算法、魚群算法和蟻群算法，該算法的魯棒性好且計算效率較高。近年來，機器人自主任務分配方面的研究取得了較大進展，但鮮有多自主式水下機器人（MAUV）方面的研究［7］。

蟻群算法是一種模擬螞蟻群體智能行為的仿生優化算法，該算法利用生物信息作為螞蟻后續行為選擇的依據，并通過螞蟻協同作業來完成尋優過程［8］。蟻群算法多用于路徑規劃［9-10］及組合優化［11］等研究領域，而將蟻群算法用于MAUV任務分配方面的研究則較少，因為基本蟻群算法存在搜索時間較長和容易陷入局部最優解的缺點［12］。本文將以MAUV執行海底地形勘察任務為應用背景，針對基本蟻群算法的缺點，通過對剩余任務執行能力螞蟻的選擇方法、啟發函數和全局信息素進行改進，由此實現MAUV全局任務的最優分配。

1 任務分配問題模型

假設MAUV的集合U包含NU個AUV，則每個AUV即為Uk∈U（k=1，2，…，NU），其屬性采用四元素組表示(AUVID，POSk，Sk，Qk)，分別表示每個AUV的編號、位置、能源消耗和最大任務執行能力。任務集合T包含NT個目標任務，則每一個任務即為Tj∈T（j=1，2，…，NT），其屬性采用三元素組表示(TASKID，POSj，Sj)，分別表示目標編號、目標位置和目標能耗。

任務分配后，Uk將分配到一個任務執行次序集合ψk，則Uk執行任務的目標位置依次為

MAUV的任務分配需要優先考慮以下情況：

1）MAUV的利益最大化，即對完成任務貢獻最大的AUV將優先分配到任務目標。

2）盡量減少執行任務期間的能源消耗和航行距離。

3）考慮目標任務之間的均衡性。

1.1 MAUV協同作業的約束條件

1）每個任務均被分配至各個AUV，并按照要求執行，即

2）同一個任務不能分配給多個AUV，即

3）由于AUV自身的能源和續航能力有限，則Uk執行任務時的總能源消耗Sk應小于所有AUV的最大能源消耗Smax，同時Uk的續航距離Lk應小于所有AUV的最大續航總距離Lmax，即

1.2 數學模型

AUV與任務目標的距離越近，其航行距離代價越小，故應為AUV分配近距離的任務目標。對Uk而言，其航行距離代價模型為

式中，dij為第i（i=1，2，…，NT）個目標與第j個目標之間的距離，其中i≠j。

AUV的巡航過程分為直線勻速航行和轉彎勻速航行，如圖1所示。AUV在轉彎時需要減速，故其轉彎速度低于直線航行速度。假設不同的轉彎角度對應不同的轉彎速度，即

式中：υg為轉彎速度，其中g（g=1，2，…，n）為航路節點；ag為轉彎角度，其中0°＜ag≤180°。

AUV航路上的任意連續3個節點即可構成一個三角形，ag即為以中間節點為三角形頂點的內角，如圖1所示。

AUV巡航時的水阻力F為

式中：C為水動力系數，其值與介質特性、AUV形狀及迎流面積等有關，根據經驗，一般取值為0.7；ρ為水介質的密度；υh為航行速度；s為橫截面積。

忽略推進器之外的元器件發熱和能耗，AUV在巡航過程中的能量損耗主要來自克服水阻力做功，即

式中：Wg為AUV的巡航能耗；t為巡航時間；υz為直線航行速度；r為AUV轉彎半徑。

AUV的總能耗Sk包括到達目標點過程中克服水阻力的能耗W和到達目標點j后的作業能耗Sj這2個部分，即

1.3 性能評價指標

MAUV的任務分配方案可以通過多個指標進行評估，由于各個性能指標之間可能存在沖突，故任務分配方案不存在唯一的全局最優解，需進行歸一化處理。本文建立的數學模型將考慮完成任務所需的航行距離代價Lk和能源消耗代價Sk，從而得到MAUV協同任務分配的性能指標函數H

式中，ω∈（0，1），為性能指標中Lk和Sk的所占比重加權數，ω＞0.5表示任務分配時以能源消耗代價為主，ω＜0.5表示任務分配時以航行距離代價為主。

2 改進的蟻群算法

2.1 基本蟻群算法

蟻群算法是一種元啟發式算法，具有問題求解快速性和全局最優特性等優點。蟻群算法的核心是狀態轉移概率和信息素更新規則，狀態轉移概率的表達式為

式中：pij(t)為t時刻從目標i轉移到目標j的狀態轉移概率；τij(t)為t時刻在目標i和目標j之間的路徑上殘留的信息素值；α為信息啟發式因子，反映轉移過程中所積累的信息對任務轉移的影響；β為期望啟發因子，反映選擇任務轉移路徑時啟發信息的受重視程度；ηij為啟發函數，即螞蟻從當前目標i到目標j的代價，

所有任務完成一次求解即完成一次循環，并同時更新信息素值（從t時刻更新為t+1時刻），即

式中：δ∈（0，1），為信息素揮發系數；1-δ為信息素殘留因子；Δτij(t)為本次循環的信息素增量；X為信息素強度。

鑒于蟻群算法存在易出現停滯現象和陷入局部最優解的缺點，本文將針對剩余任務執行能力螞蟻的選擇方法、啟發函數、全局信息素更新方式和局部搜索方式這幾點進行改進。

2.2 蟻群協調機制

對于MAUV的集合U，其任務分配計劃AC將由螞蟻子群ACk和螞蟻組群AGv（v=1，2，…，m）分別構造的NU個任務行和m個任務列組成，其中ACk∈AC且AGv∈AC。

式中，Antk，v為第k個螞蟻子群中的第v只螞蟻。

AGv為來自不同螞蟻子群ACk的NU只螞蟻構造的任務列，即

蟻群算法的任務分配有多種狀態轉移方式，例如，從組群中隨機選擇一只螞蟻或依次輪流進行狀態轉移。本文將根據組群內剩余螞蟻的執行任務能力、剩余航程長度來選擇螞蟻，第m個組群內第k只螞蟻的狀態轉移概率為

上述式中：Ek為MAUV剩余任務的綜合指標；為第k只螞蟻的剩余航程為第k只螞蟻的剩余任務執行能力；為第k只螞蟻當前已經分配目標所需的航行距離；為第k只螞蟻的最大航程；為第k只螞蟻的最大任務執行能力；為第k只螞蟻已經消耗的任務執行能力。

由上式可知，剩余任務執行能力多、剩余航程長的螞蟻可以優先選擇新的任務目標，這種選擇機制可以使MAUV的任務分配相對均衡。被選中的螞蟻將根據信息素濃度和啟發信息進行狀態轉移，并選擇下一個任務目標。

2.3 全局信息動態更新

每一次迭代結束后，將根據式（14）和式（15）對當前最優路徑進行信息素全局更新，即

式中：L1為到目前為止的最優路徑長度；Lg為本次循環的最優路徑長度。

每次迭代后，如果L1＞Lg，即說明本次迭代的路徑更優，則式（22）應增加本次迭代所得的最優路徑信息強度，保存本次迭代的最優路徑；如果L1＜Lg，即說明本次迭代得到的路徑沒有到目前為止的最優路徑好，則式（22）應削弱本次迭代所得的最優路徑信息素強度。為避免路徑的信息素過度集中，應采用信息素最大/最小策略，以避免算法陷入停滯狀態。假設式（14）計算所得的信息素范圍為，其中τmin和τmax為設定的信息素最小值和最大值。若τij(t)＜τmin，則修改τij(t)值，令τij(t)=τmin；若τij(t)＞τmax，則修改τij(t)值，令τij(t)=τmax。

2.4 局部搜索策略

為提高最優解的質量，本文將采用2-opt算法對多組蟻群算法每次迭代所得的路徑進行優化。具體實現方法是：在所有螞蟻組群實現一次循環搜索之后，對所有路徑均采用2-opt算法進行局部搜索，如果局部搜索所得的新路徑優于原有路徑，則代替原有路徑。

改進算法的具體實現步驟如下：

Step 1：算法初始化，建立螞蟻子群ACk和螞蟻組群AGv。

Step 2：開始一組螞蟻搜索。

1）Antk，v∈AGv，根據狀態轉移規則尋找下一節點，直至所有節點已被訪問。

2）采用2-opt算法對所有的螞蟻路徑進行局部搜索優化。

3）計算每條螞蟻路徑的代價。

Step 3：重復Step 2，直至完成m組螞蟻的搜索，完成一次循環。

Step 4：記錄該次循環的最優路徑，進行全局信息素更新。

Step 5：判斷是否達到最大循環次數或連續若干次循環的最優解無變化，則停止計算；否則重復Step 2，進行新一輪的循環搜索。

2.5 收斂性證明

設p*(o)為多組蟻群算法第o次循環搜索時首次出現最優解的概率，對于任意小的數ε（ε＞0），只要迭代次數o足夠大，即成立p*(o)≥1-ε且

證明過程如下：

本文的多組蟻群算法采用了信息素限制策略，即任意路徑上的信息素均被限制在τmin和τmax之間，則可行解的狀態轉移概率pmin＞0，且

式中：ηmax為最大啟發信息；ηmin為最小啟發信息；為可行解狀態轉移的最小概率。對于任意解，均滿足

式中：為任意解的狀態轉移概率；為柵格節點下的轉移概率，其中為滿足約束的最長可行路徑的柵格節點。

只要有一只螞蟻找到最優解，即可認為算法收斂，則p*(o)的最小限值為

由式（25）可知，對于任意小的數ε，只要o足夠大，即滿足p*(o)≥1-ε。當o→∞時，，即多組蟻群算法實現收斂。

3 Matlab仿真實驗

在MAUV海底勘察的任務區域中設置14個需要勘察的任務目標點，每個目標點的位置及到達目標點的能源消耗數據如表1所示。4個AUV的起點位置相同，即坐標為（194，328）的T1（圖2），最終均將回到起點位置。每個AUV的正常航行速度為3 kn，最高航速為5 kn。AUV在正常航行狀態下的最大續航時間為24 h。4個AUV的初始狀態均為100%滿能，要求每個AUV的總能耗不得超過自身儲備能源的90%。

改進蟻群算法的相關參數值設為：α=1，β=5，ω=0.5，o=50，m=20。

表1 任務目標的位置及能源消耗Table 1 Task location and energy consumption

MAUV采用改進蟻群算法的任務分配方案如圖2和表2所示，4個AUV均從起點T1出發，T2～T15為任務目標點，每個AUV完成任務后均將返回至起點位置T1。由表2可知，4個AUV完成各自任務需消耗的能源均未超過限定值。該任務分配方案可以較好地平衡每個AUV的能源消耗代價和航程距離代價。

表2 任務分配方案Table 2 Task assignment scheme

為進一步驗證本文多組蟻群算法的可行性，針對能源消耗代價和航行距離代價平衡時的性能指標值，將本文算法與文獻［7］的自適應蟻群算法進行對比。2種算法分別進行50次任務分配實驗，取每次運行結果的平均值，性能指標均值曲線如圖3所示，仿真結果如表3所示。

表3 不同蟻群算法仿真結果Table 3 Simulation results of different ant colony algorithms

由圖3和表3可知，改進蟻群算法在第14次迭代時的最優解為21.13，而自適應蟻群算法在第38次迭代時的最優解為21.63。可見，改進的多組蟻群算法比自適應蟻群算法的收斂速度更快，最優解更優，迭代次數也更少。

4 結 語

以MAUV執行海底地形勘察任務為應用背景，通過對基本蟻群算法的狀態轉移方式、啟發函數、信息素更新和局部搜索方式進行改進，提出了一種基于改進蟻群算法的MAUV最優任務分配算法，該算法具備迭代次數少、收斂速度快等優點。在一定的約束條件下，改進的多組蟻群算法可以很好地實現MAUV的最優任務分配，并在分配任務的能源消耗與航行距離之間保持良好的均衡。