基于D?S证据论的多AUV协同搜索决策

魏娜 刘明雍 程为彬

摘  要： 针对多AUV在不确定环境中的协同搜索问题，考虑由于传感器探测精度的不确定性对目标协同搜索的影响，提出一种基于Dempster?Shafer（D?S）证据理论的融合传感器读数的协同搜索目标方法。引入“竞争力”的概念，协调多AUV之间的搜索决策行为，建立了以目标确认收益，AUV协同收益为目标的多AUV协同搜索效用函数。通过多AUV之间的相互协作，最大程度地减少了搜索路径的重复，为多AUV的协同搜索提供了合理的在线决策支持，提高了搜索效率。仿真结果显示，所建模型考虑了环境的不确定性，提出的基于D?S证据理论的多AUV协同搜索方法，具有环境适应性和搜索高效性。

关键词： 水下自主航行器; 协同搜索; Dempster?Shafer证据理论; 探测模型; 信息融合; 仿真分析

中图分类号： TN911.2?34; TP24; TJ67                文献标识码： A                文章编号： 1004?373X（2020）11?0015?05

Decision of multi?AUV cooperative search based on D?S evidence theory

WEI Na1， 2， LIU Mingyong1， CHENG Weibin3

（1. School of Marine Science and Technology， Northwestern Polytechnical University， Xian 710072， China;

2. Shaanxi Key Laboratory of Logging and Control Technology for Oil and Gas Well， Xian Shiyou University， Xian 710065， China;

3. MOE Key Laboratory of Oil & Gas Resources and Exploration Technology， Yangtze University， Wuhan 430100， China）

Abstract： In order to solve the problem of cooperative search of multiple autonomous underwater vehicles （AUVs） in uncertain environments， a cooperative target search method based on the Dempster?Shafer （D?S） evidence theory is proposed， in which the sensor readings are fused and the influence of sensor detection accuracy uncertainty on cooperative target search is considered. The concept of "competitiveness" is introduced into the method to coordinate the search decision behaviors among multiple AUVs. A cooperative search utility function of multi?AUVs is established， which takes the confirming revenue and AUVs′ cooperative revenue as a goal. With the cooperation among multiple AUVs， the duplication of search paths is reduced to the full extent， and reasonable online decision support is provided for a cooperative search of multiple AUVs， and the search efficiency is improved. The simulation results show that the built model considers the uncertainty of the environment， and the proposed multi?AUVs cooperative search method based on D?S evidence theory has strong environmental adaptability and high search efficiency.

Keywords： autonomous underwater vehicle; cooperative search; D?S evidence theory; exploration model; information fusion; simulation analysis

0  引  言

近年来，水下作战领域发生了重大的变化，作战形式向无人化和多机化转变。与单个自治水下机器人（AUV）所能提供的能力相比，多个AUV组成的编队中，每个AUV都可以根据各自的空间占位以及作战资源，在统一的作战目的指导下，通过各AUV之间的信息互通，有效地完成更加复杂而艰巨的任务[1?3]。由于多AUV编队可以有效避免资源浪费，提高了任务的执行效率和成功率，具有单个AUV无法比拟的优势，因此，多AUV协同执行任务已经成为当今水下协同作战的趋势，也是当今水下机器人在水下作战研究中的一个重要方向。本文就多AUV协同作战中的协同搜索问题展开研究和讨论。

由于水下机器人作业环境的特殊性，与陆地和天空机器人相比，水下机器人起步较晚，发展也较为缓慢[4]。因为其具有相关性，可以将陆地和天空机器人的目标搜索算法借鉴到水下目标搜索的研究中。针对无人机和水下自主航行器的协同搜索问题，文献[5]提出了周期性协调、最短路径协调和基于概率协调的三种协同搜索策略，并分析了在无人机速度和数据影响下三种协同搜索策略的任务执行时间和使用范围。文献[6]利用基于响应阈值模型的概率决策机制，考虑环境的不确定性，实现了快速灵活的无人机协同搜索和任务分配。文献[7]采用基于概率的环境建模方法，研究了多无人机的协同搜索问题，并利用遗传算法求解。遗传算法虽然具有易与其他算法结合的优点，但是运算效率不高。文献[8]提出了一种基于量子行为粒子群优化的混合差分进化算法，为海上无人机在不同威胁环境下进行目标搜索提供了安全可靠的路径。基于信息素的蚁群优化方法[9]对存储空间的需求会随着机器人数量的增多而大大增加，并不适用于数量规模较大的搜索任务。人工神经网络算法[10]以其智能性较高的特点得到越来越多的关注。文献[11?12]将生物启发神经网络算法引入水下环境中，提出了一种基于自组织神经网络的多AUV目标搜索算法。根据神经网络中神经元的活性输出值分布情况，确定AUV实际的搜索航行方向。

本文针对多AUV在不确定环境中的协同搜索问题，考虑了机载声呐传感器探测精度对AUV协同搜索策略选择的影响，提出了一种基于D?S证据论的融合传感器信息读数的协同搜索目标决策方法，以解决多AUV协同搜索中融合传感器探测读数的环境信息更新问题。同时，针对多AUV之间的协同问题，本文引入了“竞争力”的概念，通过计算分析AUV之间的竞争力，避免AUV之间选择相同的目标搜索路径，增加AUV之间的协作性，提高编队整体的目标搜索效率。

1  协同搜索问题描述

1.1  AUV的简化运动模型

将待搜索区域抽象成有限的栅格形式，并进行单位为1的栅格划分。假设每个栅格最多只能有一个目标，记栅格存在目标的状态为[ETx，y]，若栅格存在目标，则[ETx，y=1]，若栅格不存在威胁目标，则[ETx，y=0]。

假设AUV编队由[m]艘同构的AUV组成，采用分布式搜索方式，同时出发对搜索区域进行目标搜索。为了便于分析，假设AUV之间无通信约束，航行器和目标均不考虑形状，视为质点。AUV在进行目标搜索时，每行进一步都是从一个栅格的中心点前进到相邻栅格的另一个中心点。建立简化的AUV运动学方程为：

[xt+1=xt+v0Δtcosθ+Δθyt+1=yt+v0Δtsinθ+Δθ] （1）

式中：[xt，yt]表示[t]时刻AUV的位置坐标;[v0]表示[t]时刻AUV的速度;[Δt]为采样时间;[θ]为AUV当前时刻的航向角;[Δθ]为下一个采样时刻航向角的增量。由于AUV受自身机动性能的限制，因此，航向角增量需满足[Δθ∈[-θa，θa]]的约束，其中，[θa]为航向角的最大增量。在本文中，假设每个仿真步长的[Δθ]为一固定常量，且与AUV的运动速度无关。

1.2  多AUV之间的竞争力描述

AUV编队在威胁区域进行搜索时，为了避免相近的两个AUV选择相同的搜索路径和目标，每个AUV在进行策略选择时，需要考虑其他AUV对其产生的影响。本文借用“人工势场法”的思想，将除自身外的其他航行器都视为“虚拟障碍”，提出了“竞争力”的概念。当两个执行搜索任务的航行器靠近时，随着两者距离的减小，其竞争力随之增大;反之距離增大，竞争力减小。通过计算航行器之间的“竞争力”，衡量航行器之间的协同情况，以达到减少搜索航迹重叠，提高AUV编队协同搜索效率的目的。

本文采用指数函数形式来定量描述竞争力，则[AUVi]和[AUVj]之间的竞争力大小为：

[Fijx，y=λe-dij，    d0≤dij≤dmax] （2）

式中：[λ]为竞争力加权系数;[dij=][xi-xj2+yi-yj2]，表示[AUVi]和[AUVj]之间的距离。从式（2）中可以看出，若距离[dij→0]时，对应的竞争力[Fij]为无穷大。但实际中，为了避免两个AUV相撞，可以设置一个最小安全距离[d0]，同时，为了保证[AUVj]在[AUVi]的扫描区域内，还需要设置[AUVi]和[AUVj]之间的最大距离[dmax]为[AUVi]的最大探测半径。

2  基于D?S证据论的目标协同搜索

AUV在进行目标搜索时，需要根据自己传感器接收到的信息读数和其他AUV传感器接收到的信息读数进行环境信息库的更新。而在实际的目标搜索过程中，传感器探测读数存在一定的误差，需要考虑由于传感器探测读数不准确造成的不确定性影响，因此环境信息库的更新至关重要。本文基于D?S理论的证据融合方法，将传感器探测结果视为证据，使用证据推理技术融合传感器信息，提取和共享知识，不断更新环境信息库信息，从而为AUV编队进行协同搜索提供保障。

2.1  传感器探测模型

设变量[sx，y]为一传感器探测二值函数，用来表示传感器探测到目标与否的情况。[sx，y=1]表示传感器探测到点[x，y]处有威胁目标;反之，[sx，y=0]表示传感器没有在点[x，y]处探测到目标。定义传感器探测精度的概率表达式如下：

[Psx，y=1ETx，y=1=pc] （3）

[Psx，y=0ETx，y=1=1-pc] （4）

[Psx，y=1ETx，y=0=pf] （5）

[Psx，y=0ETx，y=0=1-pf] （6）

根据全概率公式，AUV在进行区域搜索时，第[i]个传感器[t]时刻探测到点[x，y]处存在目标的概率为：

[ptix，y=stix，ypcpt-1ix，ypcpt-1ix，y+pf1-pt-1ix，y+1-stix，y1-pcpt-1ix，y1-pf1-pt-1ix，y+1-pcpt-1ix，y] （7）

2.2  基于D?S证据论的环境信息库的更新

待搜索区域环境模型中的每个栅格都有“没有目标”和“被目标占据”两个状态，每个栅格都有一个属性值代表该栅格的状态。定义识别框架[Θ=E，O]，[E]表示栅格中无目标，[O]表示栅格中有目标。识别框架[Θ]的幂集为[2Θ]，且[2Θ=Φ，E，O，U]。[U]代表“未表达意见”，对信息既不是信任，也不是不信任，即不确定该栅格中目标的状态是有还是没有。[mx，y（A）]代表栅格[x，y]的状态，栅格的状态由[2Θ]中每个元素的基本分配概率做如下描述：

[mx，yΦ=0] （8）

[A?2Θmx，yA=mx，yE+mx，yO+mx，yU=1] （9）

当传感器读数显示[t]时刻点[x，y]处探测到有目标时，此时传感器的读数可视为状态[O]增加的证据。但由于传感器读数并不完全准确，所以提供的证据不能100%确定。根据D?S证据理论，任一未被分配给具体子集的“信任”被看成“未表达意见”，因此，传感器的探测读数不能给状态[E]提供任何信息，剩下的信度只能分配给状态[U]。因此，在传感器探测到点[x，y]处有目标的情况下，来自传感器的证据的mass为：

[msE=0] （10）

[msO=px，y] （11）

[ms（U）=1-ptx，y] （12）

基于传感器信度的定义，应用D?S证据组合规则，将传感器读数与环境信息库的信息融合，可得点[x，y]处新的基本概率分配函数。[mx，y]为来自待更新的环境信息库的mass，则合成后，点[x，y]的基本概率赋值为：

[mx，y⊕msE=         mx，yEmsE+mx，yEmsU+mx，yUmsE1-mx，yOmsE-mx，yEmsO]

（13）

[mx，y⊕msO=         mx，yOmsO+mx，yOmsU+mx，yUmsO1-mx，yOmsE-mx，yEmsO]

（14）

[mx，y⊕msU=mx，yUmsU1-mx，yEmsO-mx，yOmsE] （15）

其中：

[mx，yO=pfx，y] （16）

[mx，yU=-ptx，ylog2pt（x，y）-1-ptx，ylog21-ptx，y] （17）

至此，通过D?S证据理论将传感器探测信息与原有环境信息进行融合，实现了待搜索区域环境信息库的更新。

2.3  多AUV的协同搜索效益函数

多AUV执行协同搜索任务时，每个AUV需要有一个可以评估每条搜索路径花费的函数，来选择收益最大的路径，完成对目标的有效搜索。

为了能成功完成搜索任务，AUV需要在执行任务时使确认的目标数量最大化。设一个目标的价值为[ctarget]，此时在点[x，y]的预期目标确认收益为[C1x，y]，则有目标确认收益函数：

[C1x，y=pc-pfptx，y+pf?ctarget] （18）

同时，在搜索过程中还要考虑AUV之间的协同性，以提高搜索效率。为了与目标确认收益函数保持一致，这里将协同收益函数定义为竞争力的负数，则AUV的协同收益函数为：

[C2x，y=-i=1mFix，y] （19）

根据协同收益函数计算出来的收益值来调节个体AUV参与目标搜索的程度。当两个AUV距离越近，竞争力越强，收益越低，则参与目标搜索的概率越小，反之参与搜索的概率越大。通过迭代搜索，实现多AUV更合理的目标分配。根据子目标收益对AUV预期收益所起作用的不同重要性，分别设置不同的权重[ωi（i=1，2）]且[i=12ωi=1]，从而将2个子函数线性组合成一个目标优化函数来表达AUV的预期总收益。通过调整权重[ωi]的值可以动态调整子目标收益对AUV总体预期收益的影响，可得AUV的协同搜索效益函数为：

[C=ω1C1+ω2C2] （20）

3  仿真结果及分析

仿真环境中任务区域为一个2 000×2 000的固定深度的水平面，一个栅格的长度为1。投放3艘AUV进行协同搜索，AUV之间为理想通信状态，搜索区域内有3个目标。对没有协同作用下的多AUV协同搜索目标情况进行仿真，结果如图1所示。

从图1可以看出，在非协同搜索模式下，AUV编队将全部目标找到，完成搜索任务，共花费时间398.4 s，运行3 984步。多AUV在执行搜索任务过程中，多处搜索路径有非常明显的重叠情况，能源浪费严重。图2为AUV之间工作在强协同的情况下。可以看出，AUV很快覆盖了远处的目标，搜索路径基本没有重叠，搜索任务完成共花费时间104.9 s，运行1 049步。与多AUV工作在非协同的搜索情况下相比，强协同搜索方式下AUV编队的目标搜索时间大大缩短，搜索效率得到了较大的提升。

为了进一步分析不同环境信息库构建更新方法对目标协同搜索能力的影响，本实验对基于贝叶斯理论更新环境信息库和基于D?S证据论更新环境信息库的协同搜索情况进行了模拟仿真。不失一般性，仿真同时考虑了传感器分别工作在低保真率和高保真率的情况。本次实验任务区域有8个目标，投放了5艘AUV执行搜索任务。图3，图4分别為声呐传感器工作在探测精度为低保真率和高保真率的两种情况下，基于贝叶斯理论构建更新环境信息库和基于D?S证据论构建更新环境信息库的多AUV目标协同搜索仿真结果。

（声呐传感器的探测保真率为[pc=]0.95）

从仿真结果可以看出：在相同采样时间段内，当传感器探测精度不高时，基于D?S证据理论更新环境信息库的协同搜索方法在1 100时间步长时搜索到了8个目标，完成了搜索任务;而基于贝叶斯理论更新环境信息库的协同搜索方法在1 100时间步长时只搜索到了5个目标，还有3个目标未找到。仿真结果显示，基于D?S证据理论更新环境信息库的协同搜索算法比基于贝叶斯理论的协同搜索算法在传感器探测精度不高时，能够在较短时间内发现更多数量的目标。而在传感器探测精度较高的情况下，可以看到这两种搜索方法在搜索区域内发现8个目标，完成搜索任务，花费的时间步长差别不大，搜索性能上基本相当。造成上述结果的主要原因在于，这两种方法对关于“未知状态”的初始赋值不同。D?S理论不要求必须对“无知的假设”和“反驳假设”赋予信任值。在该理论中，任一违背分配给具体子集的“信任”都被视为“未表达意见”，而不是像贝叶斯理论表示的那样把这部分分配给“不信任”。由于AUV编队在进行水下协同搜索时，水下环境复杂，机载传感器不一定能保证有较高的探测精度，因此，基于D?S证据理论的协同搜索方法就显得更加适用。同时从仿真结果也可以看出，由于传感器探测精度的影响，传感器在探测精度较低的情况下搜索发现目标所需要的时间也会增加。

4  结  语

本文针对不确定环境下多AUV协同搜索目标的问题，提出了基于D?S证据论的融合传感器读数信息的协同搜索决策方法。该方法充分发挥了D?S证据理论能清楚表示“未表达意见”的优势，将传感器探测到的信息读数作为证据，利用D?S证据组合规则融合传感器读数信息，更新环境信息库，为协同搜索的策略选择提供指导。AUV之间“竞争力”的引入，避免了搜索路径的重复，缩短了AUV搜索目标的时间，提高了AUV编队的任务执行效率。仿真结果表明，在传感器探测读数精度不高时，基于D?S证据论的协同搜索方法可以发现更多的威胁目标，验证了所提方法的正确性和有效性，为水下协同作战中的目标搜索问题提供了合理的研究思路，具有一定的现实意义。

参考文献

[1] WEI Na， LIU Mingyong， CHENG Weibin. Decision?making of underwater cooperative confrontation based on MODPSO [J]. Sensors， 2019， 19（9）： 2211.

[2] ALLOTTA B， CAITI A， COSTANZI R， et al. Cooperative navigation of AUVs via acoustic communication networking： field experience with the Typhoon vehicles [J]. Autonomous robots， 2016， 40（7）： 1229?1244.

[3] ZHU D， HUANG H， YANG S X. Dynamic task assignment and path planning of multi?AUV system based on an improved self?organizing map and velocity synthesis method in three?dimensional underwater workspace [J]. IEEE transactions on cybernetics， 2013， 43（2）： 504?514.

[4] ZENG Z， LIAN L， SAMMUT K， et al. A survey on path planning for persistent autonomy of autonomous underwater vehicles [J]. Ocean engineering， 2015， 110： 303?313.

[5] SUJIT P B， SARIPALLI S. An empirical evaluation of co?ordination strategies for an AUV and UAV [J]. Journal of intelligent & robotic systems， 2013， 70（1/4）： 373?384.

[6] KIM M H， BAIK H， LEE S. Response threshold model based UAV search planning and task allocation [J]. Journal of intelligent & robotic systems， 2014， 75（3/4）： 625?640.

[7] SHORAKAEI H， VAHDANI M， IMANI B， et al. Optimal cooperative path planning of unmanned aerial vehicles by a parallel genetic algorithm [J]. Robotica， 2016， 34（4）： 823?836.

[8] FU Yangguang， DING Mingyue， ZHOU Chengping， et al. Route planning for unmanned aerial vehicle （UAV） on the sea using hybrid differential evolution and quantum?behaved particle swarm optimization [J]. IEEE transactions on systems， man， and cybernetics： systems， 2013， 43（6）： 1451?1465.

[9] LEBEDEV D V， STEIL J J， RITTER H J. The dynamic wave expansion neural network model for robot motion planning in time?varying environments [J]. Neural networks， 2005， 18（3）： 267?285.

[10] PASHKEVICH A， KAZHEUNIKAU M， RUANO A E. Neural network approach to collision free path?planning for robotic manipulators [J]. International journal of systems science， 2006， 37（8）： 555?564.

[11] 朱大奇，刘雨，孙兵，等.自治水下机器人的自主启发式生物启发神经网络路径规划算法[J].控制理论与应用，2019，36（2）：183?191.

[12] 朱大奇，曹翔.多个水下机器人动态任务分配和路径规划的信度自组织算法[J].控制理论与应用，2015，32（6）：762?769.