何 翌,郑荣濠,2†,张森林,2,刘妹琴,2,3

(1.浙江大学电气工程学院,浙江杭州 310027;2.浙江大学工业控制技术国家重点实验室,浙江杭州 310027;3.西安交通大学人工智能与机器人研究所,陕西西安 710049)

1 引言

近年来,自主式水下航行器(autonomous underwater vehicle,AUV)由于其可靠性高、成本低、灵活性强等特点,被广泛应用于各种海洋场景任务,包括环境监控与探测、海洋搜寻与营救、监管与安全等短期或长期任务[1].在这些任务中,如何使AUV在陌生的水下环境中仍沿着预定轨迹行驶是一个至关重要的问题[2].然而AUV在水中的位置不可避免地受到水下流场的影响,而且由于GPS定位信号无法到达水下,通常AUV要根据所在水域的先验流场信息来估计自身位置并进行水下导航[3].

为获得水下流场信息,单AUV流场估计主要借助于解析流模型(flow-based model,AFM)[4-5]和计算流体动力学(computational fluid dynamics,CFD)[6-7].解析流模型易于实现且成本较低,但只适用于特定形状的AUV.如DeVries等[4]利用势流理论对机翼型AUV周围的流场进行建模,使用一种递归贝叶斯滤波算法来融合AUV体表传感器阵列采集到的流速信息,以此估计出周围流场.但文献[4]中的结论不能泛化到其他形状的AUV.相对地,计算流体动力学适用于任意形状的AUV的流场建模,但往往面临过高的计算量.此外,单AUV流场估计通常需要在AUV体表安装传感器阵列来测量局部流速和压强,硬件成本较高.并且,单AUV难以胜任大范围的流场估计任务.

随着多水下机器人协同控制技术研究的发展[8],已有研究人员将多AUV系统应用于大范围的海洋流场估计任务.其中,受到计算机层析成像(computerized tomography,CT)[9]方法的启发,Chang等[10]提出了运动层析成像(motion tomography,MT)方法,利用多AUV来测量目标海域的某一深度的平均流场.MT方法考虑水下流场对AUV轨迹的影响,将AUV真实出水位置与预测出水位置之间的误差定义为运动积分误差(motion-integration error).运动积分误差的存在是由于真实流场与预测流场不一致,其值可表示为以流场为变元的积分.基于此,MT方法将流场估计问题描述为一个欠定非线性估计问题.为了进一步提升MT方法估计流场的准确度,Shi等[11]考虑AUVs在水下航行过程中可以测得与其相邻AUV之间的相对位置,并定义了相对运动积分误差(relative motionintegration error),给原欠定非线性问题[10]以更多的约束,从而提升了流场估计的准确度.

文献[10-11]分别提出一种行迭代算法来求解与MT相关的非线性方程组.但这些算法是在集中式框架中开发的,需要将所有数据汇总到一台中央计算机进行统一计算.当多AUV系统遇到应用规模较大、通信能力有限或是涉及数据隐私的情况,集中式计算将不能满足任务要求.因此本文考虑分布式流场估计.

本文基于Shi等[11]的研究成果,仍然将流场估计问题描述为求解与绝对运动积分误差和相对运动积分误差相关的非线性方程组.受启发于文献[12-13]所提出的一种用于求解线性方程组Ax-b=0的基于树型网络的分布式Kaczmarz算法,本文将每个AUV视为网络中的一个节点,并根据AUV间的相对位置测量关系和通信成本,确定这些节点间的连接方式,最终形成一个树型网络.进一步地,本文将文献[14-15]所讨论的一种非线性Kaczmarz迭代法推广到上述树型网络中,在分布式框架下求解与流场估计相关的非线性方程组.在所提出的算法中,每个AUV利用自身拥有的约束方程来更新流场估计值,然后通过扩散与池化步骤在树型网络间传递流场估计值,最终成功估计出真实流场.

事实上,首个分布式MT流场估计方法由Chang等[16]提出,其基于一致性原理将文献[10]中的集中式MT方法迁移到分布式框架中.但该方法要求AUV网络对应的加权增广邻接矩阵为双随机矩阵,这导致网络的扩展性、灵活性较差.而本文采用基于树型网络的分布式结构,可以方便地在网络中加入新分支或新节点,因而允许根据实际需求(例如希望整个网络的通信成本最低)调整树型网络的具体拓扑结构来运行分布式流场估计算法.

本文的主要贡献如下:第一,本文考虑了相对位置测量,相比于已有的分布式MT流场估计方法[16],可以获得更高的流场估计精度;第二,文本提出一种基于树型网络的分布式算法求解与流场估计相关的非线性方程组,避免了集中式计算的缺点.并且算法只要求分布式网络具有树型拓扑结构,而对树型网络的具体形状无任何要求,可以灵活适应各种工程需求;第三,本文证明了在容易满足的假设条件下,所提出的分布式协同流场估计算法得到的流场估计值会收敛至真实流场值.相对地,文献[10-11]的收敛性证明都基于一个强假设,实际应用时难以保证该强假设的成立.而文献[16]只分析了分布式算法在线性情况下的收敛性,对于非线性情况并没有给出严格的收敛性证明.

后文的主要内容总结如下:第2节讨论了与MT流场估计问题相关的背景与预备知识,并总结出与协同流场估计相关的非线性方程组;第3节首先介绍所述树型网络的生成方法及其特征,接着给出基于树型网络的分布式协同流场估计算法的详细流程;第4节证明了所提出算法的收敛性;第5节通过仿真实验进一步验证算法的有效性;最后第6节对全文进行总结,并给出未来工作的方向.

2 背景与问题描述

2.1 航行器在流场中的水平运动

本文考虑N个航行器V={v1,···,vN}在某一深度的水下区域D⊂R2中航行.航行器在水下航行过程中能够通过超短基线(ultra-short baseline,USBL)定位系统或其他声学定位系统测得与其相邻航行器之间的相对位置.令表示航行器vi的测量邻居集合.若,则vi会在水下航行过程中测量与vj的相对位置.值得注意的是可以为空集.

为了分析流场区域D中的流场对航行器运动轨迹的影响,使用具有恒定对水速度的一阶粒子模型对航行器的运动进行建模.令t∈[0,∞)表示时间,并定义T:=[t0,tf]为观察间隔.令ri(t)∈D表示航行器vi的真实位置,rij(t):=rj(t)-ri(t)表示航行器vi和vj之间的相对位置.本文假设航行器vi的真实位置ri(t)仅在t=t0和t=tf时刻可测,此时航行器位于水面,可以接收到GPS信号.为简约起见,在不引起歧义的情况下,(t)在叙述中略去.

注1为了讨论方便,假设航行器vi的对水速度不随时间变化,同时假设所有航行器的入水和出水时间相同.但后文的讨论仍然适用于随时间变化,以及各航行器的入水和出水时间不相同的情况.

本文考虑流场f在观察间隔T内是时不变的,可将其表示为以r为变元的函数,即f=f(r).若已知真实流场f(r),则在T内航行器vi的真实位置ri和真实相对位置rij可按下式计算:

上式中θi为航行器vi的航向角度.本文假设θi可以通过罗盘准确测得.由于真实流场f(r)是未知的,因而无法计算出航行器的真实轨迹.但在流场估计任务开始前,航行器可以根据预测流场计算出各自的预测轨迹.预测位置和预测相对位置按下式计算:

定义观察间隔T内的绝对运动积分误差di为

由于t=tf时刻的真实出水位置ri(tf)可以通过GPS获得,而预测出水位置可以通过计算得到,所以di是可知的.

再定义Th:=[t0,th]∈T期间内航行器vi和vj的相对运动积分误差为

2.2 协同流场估计问题的描述

2.2.1 区域网格化

图1 协同流场估计示意图Fig.1 Illustration of the cooperative flow field estimation

令γi:={ri(t)}t∈T:T→D表示航行器vi在观察间隔T内的运动轨迹,定义其弧长参数为ℓi,则

其中νi(f(ri))表示航行器vi沿着轨迹γi在ri处的对地速度

将式(7)代入式(5),得

若航行器vi的轨迹不经过Dι,则将上式代入式(9)并按x和y分量展开,得到绝对运动积分误差的离散表达式

至此,式(13)建立了与绝对运动积分误差di相关的非线性方程组.

2.2.2 相对运动积分误差的离散化

将上式代入式(16)后联立式(17),并按x和y分量展开,可得与相对运动积分误差相关的方程

3 基于树型网络的分布式流场估计

3.1 最小生成树的生成方式

在所有航行器浮出水面后,每个航行器都执行如下步骤:

1)搜索通信范围内的航行器,并建立通信连接.

2)通过GPS获得自身与通信邻居之间的距离,并将该距离作为相应通信连接的权值.

3)如果自身测量了与通信邻居的相对位置,则将对应通信连接的权值置为一个极小值(例如将权值除以一个大数).

4)运行文献[17]中的分布式最小生成树生成算法.

下面对上述过程进行详细解释.令有向图GM=(V,EM)表示航行器间的相对位置测量关系.其中:V表示N个航行器(节点),有向边〈i,j〉∈EM表示航行器vi测量了与vj的相对位置.值得注意的是,GM甚至可以不满足弱连通性.再令无向图GC(V,EC)表示航行器间的通信网络.其中:无向边(i,j)∈EC表示航行器vi和vj可以双向通信.所述通信网络是通过合并所有航行器的通信连接而建立起来的,但是每个航行器都只知道自己的通信邻居.本文假设静态通信网络GC是连通的,这是对任意分布式系统的基本要求.EC中边的权值通过上述4个步骤确定.最终,通过运行文献[17]的分布式算法获得GC的最小生成树GU(V,EU).令表示vi在GU中的邻居集合.下文提出的分布式流场估计算法,正是运行在最小生成树GU上.图2为生成最小生成树的一个示例.

图2 最小生成树示意图Fig.2 Illustration of the generation of the minimum weight spanning tree

下面说明GU(V,EU)作为树型网络的特点与性质.用vi和vj表示树中的任意节点,vr表示树的唯一根节点.若vi处在vr到vj的通路上,则称vi为vj的上级节点,记作vi≺vj.相应地,vj称为vi的下级节点,记作vj≻vi.若vj≻vi且(j,i)∈EU,那么称vj为vi的直接下级节点.节点vi的直接下级节点集合记为C(vi).没有下级节点的节点称为叶节点vl,并定义GU的叶节点集合为L={vl1,vl2,···,vlζ},其中ζ为树网络GU中叶节点的个数.

对于∀vj∈C(vi),定义边(j,i)的非负权重为

则对任意vi/∈L,有 ∑vj∈C(vi)ω(j,i)=1.若vj≻vi但vj/∈C(vi),则定义

其中:vj=vj1,vj2,···,vjM=vi是vj到vi的唯一通路.结合式(21)(22),通过归纳法易得

3.2 基于树型网络的分布式协同流场估计算法

为方便讨论,暂时省略方程(13)(18)的下标x和y.则航行器vi拥有的与未知流场相关的非线性方程组表示为

算法的每一轮迭代都包含扩散阶段(dispersion stage)与池化阶段(pooling stage)(图3).其中第k轮迭代从估计值开始并在树网络的根节点令每个节点vi从它的直接上级节点接收最新的流场估计值作为输入,然后将其顺序投影到自身拥有的约束方程(24)-(25)的解集合中,即

图3 基于树型网络的分布式流场估计算法示意图Fig.3 Illustration of the distributed flow field estimation algorithm based on the tree-structure network

4 收敛性分析

图4 由方程节点组成的树型网络Fig.4 Tree-structure networkcomposed of equation nodes

则在算法1的第k次扩散阶段,从根节点最终传递到叶节点l时,有

在第k次池化阶段,根据式(22)(29),通过归纳法易得

联立式(34)(37),算法1经过一轮完整迭代后,有

显然,有P2=P.这表明P是一个幂等矩阵,因而是一个投影算子[18].根据正交投影理论,对于任意矢量v,满足v=Pv+(I-P)v.则

其中式(42)是根据引理2的结论,式(43)是根据式(23).上式表明,对于任意矢量v,有

因为rank(ZT)=rank(Z)=P,所以ZT列满秩,所以Ker(ZT)={0}.而式(44)表明非零矢量v∈Ker(ZT).显然,存在矛盾.所以假设不成立,不存在非零矢量v满足因此,对任意非零矢量v有

因此根据矩阵诱导范数的定义,有

5 仿真结果

本节通过仿真,使用所提出的分布式算法进行流场估计,以验证算法的有效性.同时,与文献[10-11,16]的流场估计方法进行了对比实验.

将1200×1200 m2的区域分割成P=9×9个单元格,并在该区域模拟真实涡旋流场流速的最大值为0.1 m/s(图5(a)).放置N=18个航行器在流场中以对水速度m/s航行,并使其轨迹覆盖整个区域(图5(b)).给定目标位置ωi,航行器vi计算出它相对目标位置的朝向角θi,然后保持该朝向角向目标航行.航行器的真实轨迹和预测轨迹可通过将式(1)(3)按时间步长Δt=1 s离散化后计算得到.这里,预测流场＜1 m,航行器vi停止航行,并计算自己的绝对运动积分误差di.当所有航行器都完成航行后,按第3.1节的方法获得低通信成本的树型网络.但在仿真里,可以人为指定一个树型网络来运行分布式流场估计算法,这并不影响验证算法的有效性.

令算法1中的松弛参数λi=1,初始流场估计值.当,算法终止条件ϵe=0.1,ϵη=0.1,最大迭代次数kmax=300.图5(c)为算法最终得到的估计流场.对于没有航行器经过的区域,流场估计的准确度不可避免地会变差.实际中可以通过插值的方法获得未经区域的流场估计.为了更好地说明所提出的流场估计方法的准确度,在计算估计误差时,不考虑没有航行器经过的单元格.定义算法的相对估计误差为

图5(e)-(j)是在相同设置下,使用文献[10-11,16]的方法得到的估计流场和网格误差图,最终的相对误差分别为1.58%,30.01%,35.7%.其中:文献[16]的分布式方法采用全连通的网络.可见,本文所提出的分布式方法可以达到与文献[11]的集中式方法相当的准确度,并且优于文献[10,16].

图5 不同方法估计出的流场的对比图Fig.5 A comparison of flow eistimated by different methods

6 总结与展望

本文使用多AUV系统实现分布式协同流场估计,并提出了基于树型网络的分布式算法来求解与流场估计相关的非线性方程组.本文证明了该算法的收敛性,并通过仿真验证了算法的有效性.相比于先前工作[11]中提出的集中式协同流场估计方法,本文给出的分布式流场估计方法能达到相当的准确度.而相比于Chang等的工作[10,16],本文所提出的流场估计方法考虑了相对位置测量,因而获得了更高的流场估计准确度.未来的工作包括:最优树型网络的建立方法、连续流场模型的参数估计.