基于魯棒Restless Bandits模型的多水下自主航行器任務(wù)分配策略

李鑫濱 章壽濤 閆磊 韓松

摘 要：針對水下監(jiān)測網(wǎng)絡(luò)中多自主航行器（AUV）協(xié)同信息采集任務(wù)分配問題進行了研究。首先，為了同時考慮系統(tǒng)中目標(biāo)傳感器的節(jié)點狀態(tài)與聲學(xué)信道狀態(tài)對AUV任務(wù)分配問題的影響，構(gòu)建了水聲監(jiān)測網(wǎng)絡(luò)系統(tǒng)的綜合模型;其次，針對水下存在的多未知干擾因素并考慮了模型產(chǎn)生不精確的情況，基于強化學(xué)習(xí)理論將多AUV任務(wù)分配系統(tǒng)建模為魯棒無休止賭博機問題（RBP）。最后，提出魯棒Whittle算法求解所建立的RBP，從而求解得出多AUV的任務(wù)分配策略。仿真結(jié)果表明，在干擾環(huán)境下與未考慮干擾因素的分配策略相比，在系統(tǒng)分別選擇1、2、3個目標(biāo)時，魯棒AUV分配策略對應(yīng)的系統(tǒng)累計回報值參數(shù)的性能分別提升了5.5%、12.3%和9.6%，驗證了所提方法的有效性。

關(guān)鍵詞：水聲監(jiān)測網(wǎng)絡(luò);水下自主航行器任務(wù)分配;魯棒控制;不確定模型;無休止賭博機問題

中圖分類號：TP181

文獻標(biāo)志碼：A

Abstract： The problem of multiple Autonomous Underwater Vehicles （AUV） collaborative task allocation for information acquisition in the underwater detection network was researched. Firstly， a comprehensive model of underwater acoustic monitoring network system was constructed considering the influence of network system sensor nodes status and communication channel status synthetically. Secondly， because of the multi-interference factors under water， with the inaccuracy of the model generation considered， and the multi-AUV task allocation system was modeled as a robust Restless Bandits Problem （RBP） based on the theory of reinforce learning. Lastly， the robust Whittle algorithm was proposed to solve the RBP problem to get the task allocation policy of multi-AUV. Simulation results show that when the system selected 1， 2 and 3 targets， the system cumulative return performance of the robust allocation policy improves by 5.5%， 12.3% and 9.6% respectively compared with that of the allocation strategy without interference factors considered， proving the effectiveness of the proposed approaches.

Key words： underwater acoustic monitoring network; Autonomous Underwater Vehicles （AUV） task allocation; robust control; inaccuracy model; Restless Bandit Problem （RBP）

0 引言

近年來，隨著各類海洋研究與應(yīng)用的不斷發(fā)展，

水下聲學(xué)監(jiān)測網(wǎng)絡(luò)被廣泛應(yīng)用于海洋監(jiān)測、資源開采、海難搜救等領(lǐng)域[1]。水聲監(jiān)測網(wǎng)絡(luò)是由多水下傳感器節(jié)點、水下自主航行器（Autonomous Underwater Vehicle， AUV）通過無線水聲通信方式形成的一種分布式的自組織無線網(wǎng)絡(luò)[2]。隨著海洋應(yīng)用的日益發(fā)展，水聲監(jiān)測網(wǎng)絡(luò)不斷發(fā)展，因此監(jiān)測網(wǎng)絡(luò)中的多AUV協(xié)同信息獲取技術(shù)逐漸受到人們的重視，通過多AUV之間的合作和協(xié)調(diào)可以提高完成監(jiān)測任務(wù)的效率及整個網(wǎng)絡(luò)的可靠性和魯棒性[3]。而如何實現(xiàn)高效地AUV任務(wù)分配是實現(xiàn)水聲監(jiān)測網(wǎng)絡(luò)功能的保障和基礎(chǔ)[4]。

傳統(tǒng)的多智能體任務(wù)分配方法如拍賣算法[5-6]、群體智能的啟發(fā)式算法[7-8]及建立線性規(guī)劃的馬爾可夫決策（Markov Decision Process， MDP）模型求解法[9-10]等，在電磁通信環(huán)境任務(wù)分配問題中取得了較好的效果。

由于傳統(tǒng)任務(wù)分配系統(tǒng)的通信受環(huán)境限制較小，因此上述研究均未考慮系統(tǒng)通信環(huán)境對任務(wù)分配問題的影響。在水聲通信的AUV任務(wù)分配問題中，系統(tǒng)受到水下特殊弱通信環(huán)境的限制，只能通過聲信號通信[11]，且系統(tǒng)可用信道頻帶有限，信道狀態(tài)時變性高，而信道質(zhì)量對AUV任務(wù)分配的影響較大，因此在分配策略時，信道動態(tài)因素不可忽略。雖然Ferri等[12-13]通過建立分布式的系統(tǒng)模型減小了系統(tǒng)通信量，分別基于拍賣算法和人工蜂群算法完成了對多AUV的任務(wù)分配，但上述方法均難以對信道狀態(tài)進行建模，只是弱化了通信環(huán)境的影響，而未考慮信道實時變化對分配策略的影響。

基于馬爾可夫過程構(gòu)建的如MDP、

多臂賭博機（Multi-Arm Bandit， MAB）[14]及

無休止賭博機問題（Restless Bandit Problem， RBP）[15]

由圖2可知，不確定模型v對應(yīng)的懲罰值RE越大，其不確定度越高，因此如何將模型不確定度對應(yīng)偏移懲罰值RE，是求解魯棒RBP模型的關(guān)鍵問題。

在諸多懲罰值設(shè)置方法中，相關(guān)熵值（Relative Entropy）法[22]可以完全顯示出系統(tǒng)模型結(jié)構(gòu)，因此適用于求取魯棒RBP模型。相關(guān)熵值介紹如下：首先定義自然策略（Nature Policy）和自然模型（Nature Model）的概念。其中自然策略是指系統(tǒng)在無人為控制時自然趨向混亂狀態(tài)的變化，因此自然策略是趨向于最大化不確定度變化。自然模型為對應(yīng)自然策略下的系統(tǒng)模型，呈現(xiàn)了系統(tǒng)進程狀態(tài)的所有不確定度的模型，且總是趨向于最大化偏離。由圖2可知，魯棒RBP模型對應(yīng)的可允許的模型集合PEi，其中該區(qū)域的邊緣，即偏離最遠處對應(yīng)模型被稱為自然模型Vi。因此，可以通過求取出精確的自然模型Vi，從而確定模型集合PEi。

標(biāo)稱模型與自然模型的相關(guān)熵值RE的計算如下。某時刻系統(tǒng)進程的狀態(tài)為s1，則標(biāo)稱模型下進程的狀態(tài)轉(zhuǎn)移概率為pa（s1， j）。若此時的自然模型的轉(zhuǎn)移概率va（s1， j）是已知的，則相關(guān)熵的計算式為：

值得注意的是，對于任意的狀態(tài)j，當(dāng)ρ（j）=0時，應(yīng)滿足v（j）=0。由式（8）可知，相關(guān)熵值是一個非負數(shù)，當(dāng)且僅當(dāng)ρ（j）=v（j）， j∈XC，即標(biāo)稱模型完全精確時，相關(guān)熵值RE=0。由此可知，相關(guān)熵值表示了模型的相關(guān)程度，可表示2個模型之間的距離。此時，設(shè)置進程的懲罰值為：

由式（9）可知，懲罰值與模型的不確定度是正相關(guān)的，因此可以量化表示標(biāo)稱模型與自然模型的差異、偏移距離。

3 魯棒模型分配策略求取

本章主要介紹魯棒RBP模型和AUV分配策略的求取方法。由于第2章中的魯棒RBP模型集合對應(yīng)的是一個模型可選擇區(qū)域，并不是一般類型的RBP模型，原RBP模型的求解算法無法直接使用，因此求出魯棒模型后還需要進行確定得到對應(yīng)的一般模型，再進行計算。

3.1 魯棒RBP系統(tǒng)模型

本節(jié)主要介紹如何計算、確定系統(tǒng)的魯棒RBP模型。首先計算出系統(tǒng)的自然模型，由于系統(tǒng)中各傳感器狀態(tài)、信道質(zhì)量狀態(tài)等進程相互獨立，為了便于描述，只討論對單個RBP進程模型的求取，計算過程與一般馬爾可夫進程自然模型的計算過程相同[22]。由式（9）可知，系統(tǒng)進程懲罰值設(shè)置為θ*REa（ρ|v），當(dāng)該進程在t時刻的狀態(tài)為xc（t）=s1，則在自然模型中對應(yīng)的回報值為：

其中：a={1，2}。此時自然模型狀態(tài)轉(zhuǎn)移概率Va（s1， j）是未知的，需要計算自然模型的狀態(tài)轉(zhuǎn)移概率矩陣之后才可以得出懲罰值和回報值，V1（s1， j）和V2（s1， j）需要分別求取。其中，當(dāng)a=1時，系統(tǒng)進程的價值函數(shù)可定義為：

式（11）可以轉(zhuǎn)換成在離散時刻下的t步動態(tài)過程公式，即H（x0）=lim （Ht（x0）），由此可得第τ步時價值函數(shù)的表達式為：

其中：系統(tǒng)初始價值函數(shù)為H0（x）=r1（x0）。由于式（10）中相關(guān)熵值參數(shù)RE1是未知數(shù)，

因此式（12）的τ步價值函數(shù)公式無法直接求解。依據(jù)大偏差理論，可以將式（12）化簡為以下變分公式：

其中：Eρ和Eν分別表示對應(yīng)模型為ρ和ν時的期望值。此時，式（13）的下限值可以通過下述概率測量中得到滿足：

其中：v（j）為自然模型的轉(zhuǎn)移概率，

通過設(shè)定不同的初始狀態(tài)x0，可以迭代計算出完整的自然模型。此外，在式（12）中，可以假設(shè)進程的不確定參數(shù)是固定的，

從而放寬自然策略的限制，此時可通過H1（x）近似求解自然模型，公式如下：

由式（15）對價值函數(shù)進行展開，可得價值函數(shù)為：

在式（16）中代入不同的進程狀態(tài)，求取對應(yīng)的價值函數(shù)H（x），即可計算出完整的自然模型的轉(zhuǎn)移概率矩陣V1（x， j），同理可計算出a=2時的轉(zhuǎn)移概率矩陣V2（x， j）。式（16）計算得到的狀態(tài)轉(zhuǎn)移概率矩陣對應(yīng)偏差最大的系統(tǒng)自然模型，該自然模型對應(yīng)了魯棒模型集合的邊界。在此邊界內(nèi)的其他模型對應(yīng)的不確定度參數(shù)小于θ，可通過上述方法計算，從而獲得完整的集合PEi。值得注意的是，計算上述自然模型使用的不確定度θ是一個上限值，但在系統(tǒng)運行中無法獲得所有進程狀態(tài)的不確定度，因此需要進一步計算。

3.2 分配策略求解

3.1節(jié)中得到的魯棒RBP模型是一個已知邊界的可選擇集合區(qū)域，對應(yīng)不確定度的上限，但在實際應(yīng)用中，系統(tǒng)無法確定各進程所有狀態(tài)的不確定度，因此魯棒RBP模型不可直接用于求解分配策略，需要將其計算確定為一般的RBP模型。

首先，定義進程的不確定性轉(zhuǎn)移概率矩陣可選擇集合為PEa，已通過上述步驟計算獲得。此時，依據(jù)不確定性的矩形特征[24]，系統(tǒng)模型的不確定度對應(yīng)進程當(dāng)前時刻所處狀態(tài)對應(yīng)的部分。換言之，若進程狀態(tài)XC=i，則此時轉(zhuǎn)移概率的不確定性對應(yīng)部分為當(dāng)前狀態(tài)轉(zhuǎn)移概率矩陣Pa的第i行之中。因此不確定性集合PEa滿足：

其中：PEai對應(yīng)進程狀態(tài)為i時的概率矩陣集合，即Pa第i行不確定性的矩陣集合，

可在式（16）中計算不同的狀態(tài)i求出此時的對應(yīng)轉(zhuǎn)移概率

其中： j為進程狀態(tài)空間SC中的任意狀態(tài)。分別對SC中所有狀態(tài)j進行上述計算，即可得出完整的PEai （i， j），此時，PEai還應(yīng)滿足PEai （k， j）=Pa（k， j）， k≠i，如此即可計算出系統(tǒng)進程的狀態(tài)轉(zhuǎn)移概率矩陣集合PEai。此時可計算進程的回報值矩陣Ra（i）=rai（i）+θi*RE（PaPEai）。隨后考慮此模型下的RBP模型的求解，即AUV分配策略的求取問題。

對RBP模型的求解主要有2種方法：常規(guī)法和索引值法。常規(guī)法是將RBP模型視為馬爾可夫決策過程求解，在每個狀態(tài)下需要計算（N！/M?。┐危S著系統(tǒng)規(guī)模的擴大，算法復(fù)雜度急劇上升，導(dǎo)致PSPACE-hard問題[21]。

而索引值法只需要在每個狀態(tài)下計算N次索引值即可，算法復(fù)雜度較低。因此本文考慮使用索引值參數(shù)法進行求解，其中Whittle索引值參數(shù)是常用的求解RBP模型的方法。

在所有進程的價值函數(shù)中，設(shè)置一個補償值W，當(dāng)進程不被選擇時，進程可獲得此補償值。價值函數(shù)定義為：

其中：s1、s2對應(yīng)狀態(tài)空間中的任意狀態(tài)。s2表示下一個時刻可能的轉(zhuǎn)移到狀態(tài)。

此時，進程的索引值W應(yīng)滿足：

由式（20）可知，W值是對未動作進程的價值函數(shù)的補償，可以表示是否動作的差異，可作為索引值。在同一離散時刻內(nèi)，進程對應(yīng)的W值越大，表示對其進行動作獲得的回報值越大;反之，當(dāng)W值越小，甚至為負時，該進程被選擇動作所得的

回報值越小。

由于此時已將信道狀態(tài)影響融入模型中，因此W值為已考慮信道影響后的計算結(jié)果。同理可求得其他進程的W值。當(dāng)所有進程的W值都計算出之后，可以得出當(dāng)前時刻的系統(tǒng)AUV分配策略為：

其中：WM表示式（21）計算得出的第M大的索引值W。此時，魯棒分配策略求解的流程如圖3所示。

4 仿真實驗與分析

本章將通過給出一系列的仿真實驗結(jié)果來證明第3章算法的有效性。首先，介紹一個簡單RBP系統(tǒng)綜合模型的算例。假設(shè)AUV任務(wù)分配監(jiān)測系統(tǒng)中某傳感器的信息狀態(tài)空間

由于該參數(shù)的設(shè)置對AUV分配策略的求解不產(chǎn)生影響，因此在仿真中可任意設(shè)置對應(yīng)參數(shù)。因此給定傳感器的狀態(tài)轉(zhuǎn)移概率矩陣P和信道質(zhì)量狀態(tài)轉(zhuǎn)移概率矩陣L分別為：

傳感器狀態(tài)的回報值矩陣R及通信信道回報值矩陣D為：

求取兩模型的綜合進程模型如下：

此時，令傳感器的初始狀態(tài)為（xi=1， ci=1），即XC=1。若傳感器的不確定度參數(shù)θx=2，θc=1，而系統(tǒng)的折扣因子參數(shù)β=0.9，則依據(jù)式（15）和式（10），可以計算得出傳感器狀態(tài)和通信信道質(zhì)量狀態(tài)的自然模型分別為：

由于各傳感器相互獨立，同理可求出其他傳感器的自然模型。

隨后，介紹一個水聲監(jiān)測網(wǎng)絡(luò)AUV任務(wù)分配的系統(tǒng)模型例子，其中多傳感器模型同上。按上述方法建立RBP模型，求取AUV分配策略，從而驗證分配算法的有效性。假設(shè)在某AUV協(xié)同分配系統(tǒng)中，部署傳感器數(shù)量N=4，每個傳感器的狀態(tài)數(shù)量S=2，其通信信道的狀態(tài)數(shù)量SC=2，系統(tǒng)中部署的AUV數(shù)量M=2，折扣因子β=0.9。

為了驗證信道變化對分配策略的影響，將本文的綜合模型與文獻[18]中未考慮信道狀態(tài)變化的RBP系統(tǒng)對比。為對應(yīng)傳統(tǒng)RBP模型與融合RBP模型，需要建立信道的理想RBP模型，用于進行對比。其中，理想信道模型為：

同理可計算出系統(tǒng)中其他傳感器模型的模型，得到對應(yīng)的RBP系統(tǒng)模型P′。假設(shè)建立的信道模型是準(zhǔn)確的，體現(xiàn)了實際信道狀態(tài)的變化，隨后分別對理想、實際系統(tǒng)模型P和P′求解，可以得出對應(yīng)的分配策略π1和π′1。由于系統(tǒng)獲得的回報值J量化體現(xiàn)了AUV分配策略的效果，可作為AUV分配策略的性能參數(shù)，因此本文考慮使用該參數(shù)進行比較，體現(xiàn)AUV分配策略的性能。在信道狀態(tài)變化的條件下應(yīng)用不同的分配策略，計算其回報值，對比結(jié)果如圖4所示。

圖4中：橫坐標(biāo)表示系統(tǒng)進行AUV決策觀測目標(biāo)的離散時刻t;縱坐標(biāo)表示系統(tǒng)當(dāng)前時刻t得到的回報值J的累積和，該參數(shù)是指在仿真過程中，系統(tǒng)在前面每個時刻獲得的回報值的累加和，因此體現(xiàn)了對應(yīng)策略的性能，可用于進行比較。由圖4可知，未考慮通信信道質(zhì)量動態(tài)變化因素的分配策略對應(yīng)的系統(tǒng)回報值較小，而考慮了信道變化的分配策略性能提升了7.4%。由此可得，考慮信道質(zhì)量狀態(tài)變化的RBP模型可以求解得出性能更佳AUV分配策略。

值得注意的是，為了避免偶然性因素對實驗結(jié)果的影響，本文在相同的實驗條件和系統(tǒng)參數(shù)下進行了500次仿真實驗，最后計算所有實驗結(jié)果的均值得到如圖4所示的結(jié)果。

其次，驗證魯棒RBP系統(tǒng)的抗干擾能力。設(shè)置系統(tǒng)的折扣因子為β=0.9，首先計算得出系統(tǒng)標(biāo)稱模型P1，隨后依據(jù)式（15）和式（5）～（6）得出自然模型V和魯棒模型P2，最后分別得出其對應(yīng)的AUV分配策略：π1、π2和π3。假設(shè)自然模型符合此時的實際系統(tǒng)模型，此時在自然模型下分別應(yīng)用上述3個分配策略，計算系統(tǒng)的回報值J，驗證AUV分配策略的性能，對比結(jié)果如圖5所示。

圖5中：橫坐標(biāo)表示系統(tǒng)AUV決策觀測的離散時刻t;縱坐標(biāo)表示系統(tǒng)回報值J的累積和;3條曲線分別代表3個策略π1、π2和π3對應(yīng)的回報值。

由圖5可知，魯棒AUV分配策略的性能提升了12.3%。同理，為了避免偶然性因素的影響，圖5中的所有數(shù)據(jù)均為同樣實驗條件下進行500次實驗結(jié)果的統(tǒng)計平均值結(jié)果。

此外，為了更加清晰地表示上述3個AUV分配策略的差異，本文考慮通過分別計算標(biāo)稱模型策略、魯棒模型策略與自然模型策略的重合度，從而更加直觀地體現(xiàn)魯棒模型與標(biāo)稱模型的差異。部分運算過程中標(biāo)稱策略、魯棒策略與自然策略的匹配度，

如圖6所示（縱坐標(biāo)表示標(biāo)稱模型策略、魯棒模型策略與自然模型策略相重合的次數(shù)）。由圖6可知，魯棒策略與自然策略的重合度比標(biāo)稱策略高，由此可說明魯棒策略更加有效。

最后，進一步更改系統(tǒng)的各參數(shù)，在多條件下進行驗證。分別設(shè)置不同的AUV數(shù)量M和折扣因子β，然后對系統(tǒng)回報值進行對比，結(jié)果如表1所示。同理，表1中數(shù)據(jù)均為相同實驗條件下500次實驗回報值的平均值。

由表1可知，不論觀測AUV的數(shù)量M與折扣因子β如何變化，魯棒模型對應(yīng)的AUV分配策略均具有良好的性能。在選擇目標(biāo)數(shù)分別為1、2、3時，魯棒分配策略與標(biāo)稱分配策略相比，系統(tǒng)累計回報值性能分別提升了5.5%、12.3%和9.6%。其中，參數(shù)的性能提升通過式（22）計算：

[13] LI J， ZHANG R， YANG Y. Multi-AUV autonomous task planning based on the scroll time domain quantum bee colony optimization algorithm in uncertain environment[J].? PLoS One， 2017， 12（11）： No.e0188291.

[14] GITTINS J C. Bandit processes and dynamic allocation indices[J]. Journal of the Royal Statistical Society： Series B （Methodological）， 1979， 41（2）： 148-177.

[15] WHITTLE P. Restless bandits： activity allocation in a changing world[J]. Journal of Applied Probability， 1988， 25（A）： 287-298.

[16] LI X， LIU J， YAN L， et al. Relay selection for underwater acoustic sensor networks： a multi-user multi-armed bandit formulation[J]. IEEE Access， 2018， 6： 7839-7853.

[17] MUKHERJEE A， MISRA S， CHANDRA V S P， et al. Resource-optimized multi-armed bandit based offload path selection in edge UAV swarms[J]. IEEE Internet of Things Journal， 2019， 6（3）： 4889-4896.

[18] NIO-MORA J， VILLAR S S. Sensor scheduling for hunting elusive hiding targets via Whittles restless bandit index policy[C]// Proceedings of the 2011 International Conference on Network Games， Control and Optimization. Piscataway： IEEE， 2011： 1-8.

[19] FRYER R G， Jr.， HARMS P. Two-armed restless bandits with imperfect information： stochastic control and indexability[J]. Mathematics of Operations Research， 2018， 43（2）： 399-427.

[20] LI J Y， KWON R H. Portfolio selection under model uncertainty： a penalized moment-based optimization approach[J]. Journal of Global Optimization， 2013， 56（1）： 131-164.

[21] CARO F， das GUPTA A. Robust control of the multi-armed bandit problem[EB/OL].[2019-02-10]. https：//doi.org/10.1007/s10479-015-1965-7.

[22] KIM M J， LIM A E B. Robust multiarmed bandit problems[J]. Management Science， 2016， 62（1）： 264-285.

[23] TIBSHIRANI R. Regression shrinkage and selection via the Lasso[J]. Journal of the Royal Statistical Society： Series B （Methodological）， 1996， 58（1）： 267-288.

[24] NILIM A， el GHAOUI L. Robust control of Markov decision processes with uncertain transition matrices[J]. Operations Research， 2005， 53（5）： 780-798.

This work is partially supported by the National Natural Science Foundation of China （61873224， 61571387）.

LI Xinbin， born in 1969， Ph. D.， professor. His research interests include underwater acoustic communication network optimization， multi-robot control and optimization，

underwater target tracking，

machine learning.

ZHANG Shoutao， born in 1994， M. S. candidate. His research interests include machine learning， multi-robot control and optimization.

YAN Lei， born in 1989， Ph. D. candidate. His research interests include multi-robot control and optimization， underwater target tracking.

HAN Song， born in 1989， Ph. D.， lecturer. His research interests include Game theory， multi-robot control and optimization.