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

李鑫濱 章壽濤 閆磊 韓松

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

關鍵詞：水聲監測網絡;水下自主航行器任務分配;魯棒控制;不確定模型;無休止賭博機問題

中圖分類號：TP181

文獻標志碼：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 引言

近年來，隨著各類海洋研究與應用的不斷發展，

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

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

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

基于馬爾可夫過程構建的如MDP、

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

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

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

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

標稱模型與自然模型的相關熵值RE的計算如下。某時刻系統進程的狀態為s1，則標稱模型下進程的狀態轉移概率為pa（s1， j）。若此時的自然模型的轉移概率va（s1， j）是已知的，則相關熵的計算式為：

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

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

3 魯棒模型分配策略求取

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

3.1 魯棒RBP系統模型

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

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

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

其中：系統初始價值函數為H0（x）=r1（x0）。由于式（10）中相關熵值參數RE1是未知數，

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

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

其中：v（j）為自然模型的轉移概率，

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

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

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

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

3.2 分配策略求解

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

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

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

可在式（16）中計算不同的狀態i求出此時的對應轉移概率

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

對RBP模型的求解主要有2種方法：常規法和索引值法。常規法是將RBP模型視為馬爾可夫決策過程求解，在每個狀態下需要計算（N！/M！）次，隨著系統規模的擴大，算法復雜度急劇上升，導致PSPACE-hard問題[21]。

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

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

其中：s1、s2對應狀態空間中的任意狀態。s2表示下一個時刻可能的轉移到狀態。

此時，進程的索引值W應滿足：

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

回報值越小。

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

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

4 仿真實驗與分析

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

由于該參數的設置對AUV分配策略的求解不產生影響，因此在仿真中可任意設置對應參數。因此給定傳感器的狀態轉移概率矩陣P和信道質量狀態轉移概率矩陣L分別為：

傳感器狀態的回報值矩陣R及通信信道回報值矩陣D為：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

由表1可知，不論觀測AUV的數量M與折扣因子β如何變化，魯棒模型對應的AUV分配策略均具有良好的性能。在選擇目標數分別為1、2、3時，魯棒分配策略與標稱分配策略相比，系統累計回報值性能分別提升了5.5%、12.3%和9.6%。其中，參數的性能提升通過式（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.