基于鲁棒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.