基于改進(jìn)蟻群算法的多自主式水下機(jī)器人任務(wù)分配

劉瑞軒，張永林

江蘇科技大學(xué) 電子信息學(xué)院，江蘇 鎮(zhèn)江 212003

0 引 言

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

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

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

1 任務(wù)分配問題模型

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

任務(wù)分配后，Uk將分配到一個任務(wù)執(zhí)行次序集合ψk，則Uk執(zhí)行任務(wù)的目標(biāo)位置依次為

MAUV的任務(wù)分配需要優(yōu)先考慮以下情況：

1）MAUV的利益最大化，即對完成任務(wù)貢獻(xiàn)最大的AUV將優(yōu)先分配到任務(wù)目標(biāo)。

2）盡量減少執(zhí)行任務(wù)期間的能源消耗和航行距離。

3）考慮目標(biāo)任務(wù)之間的均衡性。

1.1 MAUV協(xié)同作業(yè)的約束條件

1）每個任務(wù)均被分配至各個AUV，并按照要求執(zhí)行，即

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

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

1.2 數(shù)學(xué)模型

AUV與任務(wù)目標(biāo)的距離越近，其航行距離代價越小，故應(yīng)為AUV分配近距離的任務(wù)目標(biāo)。對Uk而言，其航行距離代價模型為

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

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

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

AUV航路上的任意連續(xù)3個節(jié)點即可構(gòu)成一個三角形，ag即為以中間節(jié)點為三角形頂點的內(nèi)角，如圖1所示。

AUV巡航時的水阻力F為

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

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

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

AUV的總能耗Sk包括到達(dá)目標(biāo)點過程中克服水阻力的能耗W和到達(dá)目標(biāo)點j后的作業(yè)能耗Sj這2個部分，即

1.3 性能評價指標(biāo)

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

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

2 改進(jìn)的蟻群算法

2.1 基本蟻群算法

蟻群算法是一種元啟發(fā)式算法，具有問題求解快速性和全局最優(yōu)特性等優(yōu)點。蟻群算法的核心是狀態(tài)轉(zhuǎn)移概率和信息素更新規(guī)則，狀態(tài)轉(zhuǎn)移概率的表達(dá)式為

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

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

式中：δ∈（0，1），為信息素?fù)]發(fā)系數(shù)；1-δ為信息素殘留因子；Δτij(t)為本次循環(huán)的信息素增量；X為信息素強(qiáng)度。

鑒于蟻群算法存在易出現(xiàn)停滯現(xiàn)象和陷入局部最優(yōu)解的缺點，本文將針對剩余任務(wù)執(zhí)行能力螞蟻的選擇方法、啟發(fā)函數(shù)、全局信息素更新方式和局部搜索方式這幾點進(jìn)行改進(jìn)。

2.2 蟻群協(xié)調(diào)機(jī)制

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

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

AGv為來自不同螞蟻子群ACk的NU只螞蟻構(gòu)造的任務(wù)列，即

蟻群算法的任務(wù)分配有多種狀態(tài)轉(zhuǎn)移方式，例如，從組群中隨機(jī)選擇一只螞蟻或依次輪流進(jìn)行狀態(tài)轉(zhuǎn)移。本文將根據(jù)組群內(nèi)剩余螞蟻的執(zhí)行任務(wù)能力、剩余航程長度來選擇螞蟻，第m個組群內(nèi)第k只螞蟻的狀態(tài)轉(zhuǎn)移概率為

上述式中：Ek為MAUV剩余任務(wù)的綜合指標(biāo)；為第k只螞蟻的剩余航程為第k只螞蟻的剩余任務(wù)執(zhí)行能力；為第k只螞蟻當(dāng)前已經(jīng)分配目標(biāo)所需的航行距離；為第k只螞蟻的最大航程；為第k只螞蟻的最大任務(wù)執(zhí)行能力；為第k只螞蟻已經(jīng)消耗的任務(wù)執(zhí)行能力。

由上式可知，剩余任務(wù)執(zhí)行能力多、剩余航程長的螞蟻可以優(yōu)先選擇新的任務(wù)目標(biāo)，這種選擇機(jī)制可以使MAUV的任務(wù)分配相對均衡。被選中的螞蟻將根據(jù)信息素濃度和啟發(fā)信息進(jìn)行狀態(tài)轉(zhuǎn)移，并選擇下一個任務(wù)目標(biāo)。

2.3 全局信息動態(tài)更新

每一次迭代結(jié)束后，將根據(jù)式（14）和式（15）對當(dāng)前最優(yōu)路徑進(jìn)行信息素全局更新，即

式中：L1為到目前為止的最優(yōu)路徑長度；Lg為本次循環(huán)的最優(yōu)路徑長度。

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

2.4 局部搜索策略

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

改進(jìn)算法的具體實現(xiàn)步驟如下：

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

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

1）Antk，v∈AGv，根據(jù)狀態(tài)轉(zhuǎn)移規(guī)則尋找下一節(jié)點，直至所有節(jié)點已被訪問。

2）采用2-opt算法對所有的螞蟻路徑進(jìn)行局部搜索優(yōu)化。

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

Step 3：重復(fù)Step 2，直至完成m組螞蟻的搜索，完成一次循環(huán)。

Step 4：記錄該次循環(huán)的最優(yōu)路徑，進(jìn)行全局信息素更新。

Step 5：判斷是否達(dá)到最大循環(huán)次數(shù)或連續(xù)若干次循環(huán)的最優(yōu)解無變化，則停止計算；否則重復(fù)Step 2，進(jìn)行新一輪的循環(huán)搜索。

2.5 收斂性證明

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

證明過程如下：

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

式中：ηmax為最大啟發(fā)信息；ηmin為最小啟發(fā)信息；為可行解狀態(tài)轉(zhuǎn)移的最小概率。對于任意解，均滿足

式中：為任意解的狀態(tài)轉(zhuǎn)移概率；為柵格節(jié)點下的轉(zhuǎn)移概率，其中為滿足約束的最長可行路徑的柵格節(jié)點。

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

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

3 Matlab仿真實驗

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

改進(jìn)蟻群算法的相關(guān)參數(shù)值設(shè)為：α=1，β=5，ω=0.5，o=50，m=20。

表1 任務(wù)目標(biāo)的位置及能源消耗Table 1 Task location and energy consumption

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

表2 任務(wù)分配方案Table 2 Task assignment scheme

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

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

由圖3和表3可知，改進(jìn)蟻群算法在第14次迭代時的最優(yōu)解為21.13，而自適應(yīng)蟻群算法在第38次迭代時的最優(yōu)解為21.63。可見，改進(jìn)的多組蟻群算法比自適應(yīng)蟻群算法的收斂速度更快，最優(yōu)解更優(yōu)，迭代次數(shù)也更少。

4 結(jié) 語

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