通信距離約束下異構水下爬游機器人任務分配

劉雅麗，高立娥，李 樂，郭利偉，劉衛東

(西北工業大學 航海學院，西安 710072)

0 引言

水下爬游機器人具有爬行與巡游兩種運動模式，它可以幫助或替代人類完成一些難度較高、危險的水下作業任務[1]。由于單個爬游機器人存在攜帶資源有限、獲取和處理信息能力有限等問題，導致其在執行復雜多樣的任務時遇到挑戰，因此爬游機器人集群為完成水下復雜作業提供了一種有效途徑[2-4]。多機器人任務分配(MRTA,multi robot task allocation)問題是集群協同作業的關鍵之一[5-7]。在多爬游機器人系統中，各爬游機器人之間通過信息交互、相互合作的方式完成水下作業任務。

目前，用于MRTA問題的算法主要有群體智能優化算法、市場拍賣算法、神經網絡算法等。市場拍賣算法較群體智能優化算法而言計算簡單，能夠得到全局最優分配結果，但魯棒性弱且對系統配置要求較高。群體智能優化算法包括粒子群算法、蟻群算法、遺傳算法等。文獻[8]引入資源均衡函數，采用粒子群蟻群混合算法求解了異構多AUV任務分配中資源配置問題。文獻[9]提出了一種基于自組織映射(SOM)神經網絡的雙競爭策略算法能夠較好地實現水下機器人之間的任務分配。文獻[10]為了滿足實時系統的約束條件，提出了一種混合最大最小蟻群優化算法(H-MMAS)。將H-MMAS進行擴展，引入局部搜索啟發式算法，改進了任務分配算法。由于蟻群算法具備正反饋特點，全局搜索性較好。針對任務分配問題，本文采用蟻群優化算法進行求解。但是多水下爬游機器人執行任務時也存在著一系列的問題，如機器人之間水下通信問題、協調合作機制等[11-12]。本文針對通信問題研究了異構爬游機器人在通信距離約束條件下的任務分配情況。

可靠高效通信是多水下爬游機器人順利完成任務必不可少的條件。就目前而言，以聲波為載體的水聲通信是實現水下通信的主要形式。由于水介質吸收聲信號的特性，導致水聲信道帶寬窄[13]。通信質量與距離不可兼得，而且海洋環境噪聲影響嚴重，所以水聲通信的傳輸距離具有一定的限制。當多水下機器人中所有個體構成的通信圖為非連通時，機器人獲得不完整的信息會影響水下機器人的任務完成進度。為了減小通信環境對水下爬游機器人執行任務效率的影響，所以需要多水下爬游機器人之間時刻保持通信。針對弱水下通信環境多AUV任務分配問題，文獻[14]建立了基于可變時延的多AUV任務分配框架，提出了通信中斷情況下機器人應采取的策略。文獻[2]針對無人艇USV的能耗和通信范圍的兩個關鍵問題,提出了一種新的能量協調方案和任務優先排序方法，完成了多USV系統的任務分配問題。文獻[15]研究了有限通信下多AUV編隊控制，提出了領導者編隊模式。領導者與每個AUV建立單向通信來維持編隊形成，大大降低了通信能耗。文獻[16]研究了強化學習下的多AUV軌跡規劃。由于AUV-到達最后一個路徑點時需要將其現場樣本發送到一個接入點，因此AUV必須至少在一個接入點的通信范圍內。在此通信、運動學等約束下實現了多AUV軌跡規劃。文獻[17]研究了通過AUV，UAV，USV之間協作完成水下目標搜索跟蹤任務。文中要求UAV與USV、USV與AUV之間的距離小于要求范圍。以上文獻從不同角度研究了弱水下通信情況下集群任務規劃問題，卻未保證執行任務時多水下機器人通信圖能夠時刻保持連通的問題。文獻[18]研究了通信距離、角度等約束情況下的多無人機目標分配。文獻[19]針對通信范圍有限的多分散機器人任務分配問題，提出了基于STST (single-traveling-salesman tour)的分布式算法和RBA(rendezvous-based algorithm)集中式方法在有限航程距離內訪問所有目標位置而不需考慮機器人通信范圍。文獻[20]設計觀察到同一目標的兩個機器人之間可以進行相互通信。在有限通信情況下研究了一組移動機器人對多運動目標跟蹤問題。上述文獻研究了無人機與陸上機器人的通信問題。水下的通信環境較空中的通信環境差，以上文獻研究方法在應用于水下機器人集群時受到挑戰。本文則針對多水下爬游機器人執行任務時通信距離受限的情況，使用互通與單通兩種方法研究了距離約束條件，而且解決了多水下機器人通信圖不連通的問題。在任意時刻，任意一個爬游機器人都可以與其他爬游機器人進行通信從而保證整個集群獲得全局信息，提高任務完成效率。

本文主要研究通信距離約束條件下異構多水下爬游機器人的任務分配問題。在通信距離、航程等約束條件下，將爬游機器人的總航行距離作為評價任務分配優劣的準則，采用蟻群算法進行優化求解，最終解決了異構多水下爬游機器人的任務分配問題。

1 任務分配問題數學模型

1.1 問題描述

異構多水下爬游機器人任務分配問題是指由N個異構爬游機器人執行M個不同的任務，通過決定各爬游機器人完成任務的特定序列實現所給定目標函數最小。異構多水下爬游機器人任務分配可以建模為一個四元組{CR，task，C，f}。CR={CR1，CR2，…,CRN}表示爬游機器人集合。每個爬游機器人包含其位置，速度，最長運動時間，最大航程等基本信息。task={task1，task2，…,taskM}表示任務集合。每個任務應包含其位置，完成任務所需時間，任務類型等基本參數。C表示約束條件集合。f表示任務分配系統的目標函數，本文所考慮的目標函數為爬游機器人在完成任務的前提下所航行總距離最小。

1.2 目標函數

任務分配方案需要通過指標進行評價，本文所建立的任務分配模型將水下爬游機器人完成任務需要的總航行距離作為評價指標。所建立的目標函數如下所示：

(1)

其中：D(CRi)表示爬游機器人i的航行距離。

1.3 約束條件

任務分配時，異構多水下爬游機器人被分配不同的任務，為了可以實現總體效能值最優，建立的約束條件如下：

1.3.1 通信距離約束

多水下爬游機器人通過水聲通信獲取彼此間的位置、執行任務情況等信息。由于水聲通信固有特性，而且爬游機器人的通信設備能力有限，導致爬游機器人的通信能力具有一定的限制，水下爬游機器人的通信范圍如圖1所示。為了保證爬游機器人在執行任務過程中一直可以進行信息交互，使用單通和互通兩種不同方式建立以下通信約束條件。

圖1 爬游機器人通信范圍

(2)

其中：R(i,j)表示水下機器人i與機器人j是否可以通信。R(i,j)=1表示機器人j在機器人i的通信距離范圍內即機器人i可以向機器人j發送信息。R(i,j)則相反。rc(i)為機器人i的最大通信距離。D(i,j)表示爬游機器人i與機器人j之間的距離。

1)互通:

為了減小通信環境對水下爬游機器人工作效率的影響，需要爬游機器人之間可以時刻保持通信，所以建立互通通信約束條件來滿足爬游機器人的通信需求。任意時刻任意兩個爬游機器人之間的距離小于最大通信范圍時可以相互通信。設定在k(k=1,2,…,K)時刻多水下爬游機器人中任意一個機器人j(j=1,2,…,N且j≠i)在機器人i(i=1,2,…,N)的通信范圍內,此時兩個機器人可以實現互通。

?i,?j(j≠i)，R(i,j,k)=1,i=(1,2,...,N),

j=(1,2,...,N),k=(1,2,...,K)

(3)

k=t/Δt

(4)

其中：t為機器人運行時間，Δt為時間步長。

2)單通:

雖然互通情況下通信距離約束條件可以滿足爬游機器人之間時刻保持通信的要求，但是任意兩個爬游機器人之間距離都小于最大通信距離的約束性較強，所以考慮建立單通情況下通信距離約束條件。單通約束條件要求在任意時刻任意一個爬游機器人可以與其他爬游機器人中任意一個爬游機器人進行通信即可。為了保證機器人之間順利通信，在k時刻，至少有一個機器人j位于機器人i的通信范圍內。建立相應表達式如下：

?i,?j(j≠i),R(i,j,k)=1,i=(1,2,...,N),

j=(1,2,...,N),k=(1,2,...,K)

(5)

3)非連通通信圖:

由于單通下的距離約束條件中可能出現部分水下爬游機器人出現局部孤立的情況，本文采用遍歷搜索方法解決此問題。根據搜索路徑，遍歷搜索方法包括深度優先搜索算法與廣度優先搜索算法。本文所采用的廣度優先搜索算法是以廣度優先的方式遍歷整個圖，使用隊列來實現搜索，從樹的根節點開始，沿其寬度遍歷所有節點。

任意時刻k，廣度優先算法多水下爬游機器人非連通圖檢測流程包括如下步驟：

設定訪問標志Vlog(i)=1時表示第i節點已被訪問，Vlog(i)=0表示該節點未被訪問。

step 1：假設初始狀態所有頂點均未被訪問Vlog(i)=0；

step 2：任意選取一個節點V作為搜索的起點，遍歷節點V的所有相鄰節點，并將未被訪問過的相鄰節點放入緩存隊列中，將已訪問過的節點放入結果隊列中。

step 3：取出丟棄緩存隊列中的首位節點并訪問其相鄰節點，將未被訪問的節點放入緩存隊列中，將已訪問過的節點放入結果隊列中。

step 4：循環步驟step 3，直至緩存隊列為空。

Step 5：判斷結果隊列是否遍歷所有節點。如果存在Vlog(i)=0，則k時刻通信圖為非連通圖，即此刻出現了局部機器人通信的情況。

1.3.2 執行任務能力約束

一個水下爬游機器人同時只能執行一個任務。

(6)

其中：x(i,j)為1則表示爬游機器人i執行第j個任務，0則相反。

1.3.3 航程約束

每個水下爬游機器人所攜帶的資源和續航能力有限，可以維系航行的最遠距離有限。為了避免出現完成任務前能源耗盡的情況，建立如下的約束條件：

maxD_CR(i)≥

(7)

其中：D(CRi,task1)表示水下爬游機器人i到它所執行第一個任務的距離，D(taskj,taskj+1)表示爬游機器人i所執行任務中第j個任務與第j+1個任務的距離，tempi表示爬游機器人i所執行任務的個數，maxD_CR(i)表示水下爬游機器人i的最大航行距離。

1.3.4 時間約束

由于水下爬游機器人最大工作時間有限，所以要求機器人完成任務的時間不可以超出最大工作時間，建立如下的約束條件：

maxT_CR(i)≥

(8)

(9)

T(taskj,taskj+1)=

(10)

其中：T(CRi,task1)表示爬游機器人i到它所執行第一個任務并完成此任務所需時間，T(taskj,taskj+1)表示爬游機器人i從任務j到達并完成下一任務的時間，maxT_CR(i)表示第i個爬游機器人的最長工作時間，V_CR(i)表示爬游機器人i的航行速度，T_task(j)表示完成任務j所需時間。

1.3.5 能力約束

單個水下爬游機器人能力有限，所以不同類型的任務需要特定的爬游機器人來執行，如采樣任務需要帶有機械臂的爬游機器人來執行，監測任務則要求執行此任務的爬游機器人帶有攝像頭。TK=[TK1,TK2,TK3]表示任務類型。TK1,TK2,TK3分別表示采樣任務、監測任務、測掃任務，如TK=[1 0 0]表示該任務為采樣任務。VK=[VK1,VK2,VK3]表示機器人類型。VK1,VK2,VK3則分別表示爬游機器人是否有機械臂、攝像頭、側掃聲吶，如VK=[1 0 0]表示機器人只帶有機械臂。為了保證爬游機器人可以成功完成不同類型的任務，爬游機器人i能夠執行任務j必須滿足的約束條件如下：

TKtaskj(l)≤VKCRi(l)l=1,2,3

(11)

綜合上述所建立的約束條件及目標函數，以實現總航程最短的多水下爬游機器人任務分配。

2 基于蟻群算法的異構爬游機器人任務分配方法

2.1 蟻群算法基本原理

蟻群算法是由意大利學者M.Dorigo初次提出，它是一種模擬螞蟻尋覓食物的優化算法。自然界螞蟻起初選擇路徑具有隨機性，當尋找到食物之后會向環境中釋放一種具有揮發性的信息素。它們根據其濃度來獲得路徑遠近的信息，進行協作、交流，通過信息素揮發、增強，最終找到一條最短路徑。簡單而言，蟻群算法便是通過計算狀態轉移概率選擇下一個轉移節點，從而逐漸走到終點，經過一次次迭代、信息素更新，最終找到一條從起點到終點的最短路徑。蟻群算法的兩個關鍵步驟為計算狀態轉移概率和更新信息素。

狀態轉移概率的計算與信息素濃度和啟發式信息有關。狀態轉移概率的表達式：

(12)

其中:pij表示螞蟻從節點i轉移到下一節點j的概率。allowed為未被訪問過的節點集合。τij表示節點i到節點j的信息素濃度值。α為信息素啟發因子，表示在螞蟻經過的路徑上留下的信息素受重視的程度。β為期望啟發因子，表示在轉移節點時螞蟻遺留下來的啟發信息的重要程度。ηij則為啟發函數，在本文選擇爬游機器人與任務的距離的倒數作為啟發函數。

更新信息素：蟻群算法完成一次循環之后要更新信息素的值。信息素更新表達式如下：

τij(t+1)=(1-ρ)τij(t)+Δτij(t+1)

(13)

(14)

ρ∈(0,1)為信息素揮發系數，代表信息素揮發程度。Q為常量，Lk為第k只螞蟻完成搜索路線長度。

2.2 算法實現

本文使用蟻群算法求解通信距離約束條件下的異構機器人任務分配問題的流程如下。

Step1：初始化{CR1,CR2,...,CRn}、{task1,task2,...,taskm}位置、速度等信息以及蟻群算法相關參數，如螞蟻數K，最大迭代次數NC_max、信息素啟發因子α、期望啟發因子β等。

step 2：forNC=1 toNC_max

step 3：fork=1 to K

step 4：為螞蟻k隨機選取未執行的任務；

step 5：由公式(7)計算，采用輪盤賭法為螞蟻k選擇下一節點；

step 6：更新禁忌表，將已訪問的節點加入禁忌表；

step 7：end

step 8：If 滿足通信距離、航程等約束條件 then

step 9：記錄該次循環的最優路徑；

step 10：end

step 11：按照公式(8)，更新信息素；

step 12：end

step 13：輸出歷史目標函數值最小的任務分配結果。

3 仿真實驗與分析

針對異構多水下爬游機器人的任務分配問題，設置爬游機器人個數為N=5，任務個數為M=9。具體參數如表1、表2所示。蟻群優化算法參數設置為：NC_max=100、K=30、α=4、β=7、ρ=0.5、Q=100。使用MATLAB軟件和蟻群算法工具包分別針對不同通信范圍情況下單通和互通兩種通信距離約束方法進行仿真驗證及分析。

表1 任務參數設置

表2 爬游機器人參數設置

3.1 仿真實驗一

為了驗證互通與單通兩種通信距離約束方法，設定爬游機器人最大通信距離rc為[500,600,500,500,600]米。

3.1.1 互通情況仿真結果及分析

針對互通情況下的通信約束，本節對多水下爬游機器人任務分配問題仿真求解得到任務分配結果和相應目標函數變化情況如圖2和圖3所示。

圖2 互通情況下任務分配結果

圖3 目標函數值變化情況

由圖2的分配結果可知爬游機器人在執行任務具有順序。由于任務1、4、6均帶有采樣任務，所以需要帶有機械臂的爬游機器人來執行。任務3、8為測掃任務，需要帶有側掃聲吶設備的機器人來執行。最終分配結果為CR1執行任務9，CR2執行任務序列為5-1，CR3執行任務7,CR5執行任務序列為8-3-6-2-4。在滿足能力約束條件以及目標函數最小的要求下，最終CR4并未分配任務。由圖3可知，當算法循環迭代22次之后收斂，目標函數取到最小值。在圖2的任務分配結果下，多水下爬游機器人完成任務的總航行距離達到最小，最小值為1 929 m。在此任務分配結果下，爬游機器人在執行任務過程中的每一刻都可以保證與其他的爬游機器人進行通信，且多爬游機器人所運動的距離最短。

3.1.2 單通情況仿真結果與分析

針對單通情況下的通信約束，本節對多水下爬游機器人任務分配問題仿真求解得到任務分配結果和相應目標函數變化情況如圖4和圖5所示。

圖4 單通情況下任務分配結果

圖5 目標函數值變化情況

圖4表示最終分配結果為CR1執行任務序列為9-2，CR2執行任務序列為5-1，CR3執行任務7，CR5執行任務序列為8-3-6-4。在滿足能力約束條件以及目標函數最小的要求下，最終CR4并未分配任務。由圖5可知，當算法循環迭代5次之后收斂，目標函數取到最小值1 917米，算法收斂速度快。

本節仿真驗證了單通和互通兩種通信距離約束方法都可以保證異構多水下爬游機器人順利完成水下作業任務，并實現總航行距離最短的目標。

3.2 仿真實驗二

為了比較互通與單通兩種通信距離約束方法，設定爬游機器人最大通信距離rc為[250,300,250,250,300]米。

3.2.1 互通情況仿真結果與分析

針對爬游機器人最大通信范圍較小時互通情況下的通信距離約束，本節對多水下爬游機器人任務分配問題仿真結果為無解。

3.2.2 單通情況仿真結果與分析

針對爬游機器人最大通信范圍較小的單通情況下通信距離約束，本節對多水下爬游機器人任務分配問題仿真求解得到任務分配結果和相應目標函數變化情況如圖6和圖7所示。

圖6 單通情況下任務分配結果

圖7 目標函數值變化情況

圖6表示最終分配結果為CR1執行任務序列為9，CR2執行任務序列為6-4，CR3執行任務2，CR4執行任務7，CR5執行任務序列為8-3-5-1。由圖7可知，當算法循環迭代14次之后收斂，目標函數取到最小值2 251米。

本節進行爬游機器人最大通信范圍較小時單通和互通兩種情況下仿真實驗。通過兩種不同通信距離約束下多水下爬游機器人任務分配仿真實驗結果可知，由于互通通信距離約束條件的約束性更強，互通通信距離約束下的任務分配無解，無法順利進行任務分配，但單通通信距離約束下爬游機器人卻可以順利完成水下作業任務，單通通信距離約束的方法適用性更廣。

4 結束語

本文針對水下爬游機器人能源攜帶有限，而且水下通信難、通信距離有限的問題，研究了通信距離等約束條件下的多爬游機器人任務分配問題。為了保證多水下爬游機器人可以順利執行任務，建立通信距離、航程等約束條件，以多爬游機器人總航行距離為目標，構建異構多水下爬游機器人任務分配模型，利用蟻群優化算法進行求解。仿真實驗結果表明本文所研究模型和算法的有效性。下一步工作將分析研究水下爬游機器人集群任務分配時降低能耗問題。