中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2024 , Vol. 46 >Issue 6: 92 - 95

DOI: https://doi.org/10.3969/j.issn.1673-3819.2024.06.015

Multimodal Information Fusion

Task assignment method for unmanned surface vessel formation based on optimal transport theory

  • XUE Min 1 ,
  • QUAN Chongren 1 ,
  • HU Zhengyang 2 ,
  • WANG Yong 2
Expand
  • 1 Naval Equipment Department, Beijing 100036, China
  • 2 Jiangsu Automation Research Institute, Lianyungang 222061, China

Received date: 2023-09-22

  Revised date: 2024-02-17

  Online published: 2024-11-26

Fold

Abstract

The task assignment method for a large group of unmanned surface vessel (USV) is an important research problem in the field of autonomous unmanned system. Appropriate task assignment schemes will facilitate USV formation for quick decision making and efficient execution. Existing methods rarely take the attitude of USVs and their dynamic equations into considerations. This article first established a model of attitude-based task assignment problem for USV formation; next, by linking the model to the optimal transport problem on the manifold, we obtained its discrete form; finally, our simulation experiment demonstrates the necessity of considering attitude-based task assignment problem for USV formation, and the effectiveness of the method proposed in this paper.

Key words： optimal transport; unmanned surface vessel formation; task assignment

Cite this article

XUE Min , QUAN Chongren , HU Zhengyang , WANG Yong . Task assignment method for unmanned surface vessel formation based on optimal transport theory[J]. Command Control and Simulation, 2024 , 46(6) : 92 -95 . DOI: 10.3969/j.issn.1673-3819.2024.06.015

国内外无人平台的研究正朝着智能化方向发展,无人艇(Unmanned Surface Vehicle, USV)具有体积小、灵活性高、作战能力强的优势[1]。与单艘USV相比,多艘USV具有负载能力高、覆盖范围 广、信息处理能力强的特点。多无人艇协同围捕问题是国内外多无人艇系统研究的一个热点,在军事领域具有重要意义。美国海军在2014年和2016年分别进行了无人艇集群对目标的拦截、包围等任务的演练;此外,大连海事大学和华中科技大学等高校对无人艇集群也展开了研究和试验。虽然无人艇编队协同工作有重大军事和经济价值,但是这也带来了新的挑战。一方面,由于海上通信条件差,无人艇编队需要进行分布式的智能控制;另一方面,无人艇编队在执行任务时的任务目标分配策略决定了任务完成的质量。为了合理高效地制定无人艇编队的任务分配方案,科学地配合无人艇群的控制系统执行,我们需要考虑以下两点因素:
1)由于无人艇的欠驱动特性,在任务分配的过程中应考虑无人艇的动力学方程,从而使得任务易于无人艇执行;
2)在一些场景中,例如围捕敌船时,任务目标不仅需要无人艇群到达指定位置,还要求无人艇的姿态要指向敌船,这就需要在任务分配时考虑无人艇与任务目标之间的姿态差异。
基于以上两点因素,在对无人艇编队任务分配问题进行建模时,我们需要将无人艇编队所在的位置及每艘艇的姿态纳入考虑,而不是仅仅将每一艘艇当作质点来处理。
从数学的角度来看,任务分配问题属于复杂的组合优化问题[2]。对于非重复性任务的无人艇编队任务分配问题,可以采用多旅行商模型[3](Multiple Travelling Salesman Problem, MTSP)或者车辆路由模型[4](Vehicle Routing Problem, VRP);对于重复性任务的无人艇编队任务分配问题,可以采用网络流模型[5](Network Flow Optimization, NFO)或者混合整数线性规划模型[6](Mixed-Integer Linear Programming, MILP)。Shima等人[7]在NFO模型的基础上基于无人机系统的工作场景建立了被称为“协同多任务分配问题”(Cooperative Multiple Task Assignment Problem, CMTAP)的组合优化模型。CMTAP 模型被广泛地应用于无人机协同的多任务分配问题当中。
在上述文献中,考虑无人艇姿态的任务分配问题还鲜少见到,本文将从最优传输理论的角度尝试解决这一问题。具体来说,首先考虑无人艇的动力学模型,建立了带姿态的无人艇编队任务分配问题的数学模型;接着简要介绍了最优传输理论及其求解方法,将带姿态的无人艇编队任务分配问题转化为状态空间SE(3)中的最优传输问题;最后介绍了如何求解带姿态的无人艇编队任务分配问题,并通过仿真实验说明了考虑无人艇与任务之间姿态差异的重要性。

1 基本数学模型

1.1 无人艇动力学模型

无人艇可以被看作一个欠驱动的刚体,考虑为由N个无人艇(USV)组成的编队系统。在固定惯性坐标系下,编队系统中第i个USV的位置为xi∈3,姿态为Ri∈SO(3),体坐标系下的体角速度为Ωi∈3,体线速度为Vi∈3。编队系统中第i个USV的动力学方程可以表示为如下形式[8-9]:

MV˙i=MVi×Ωi-K1Vi-D1(Vi)Vi+ui

JΩ˙i=JΩi×Ωi+MVi×Vi-K2Ωi-D2(Ωi)Ωi+τi

R˙i=RiΩ^i,　x˙i=RiVi
其中,ui∈3为体坐标下的控制力,τi∈3为体坐标下的控制力矩,J为USV的转动惯量加上水附带的转动惯量,M为USV的质量加上水附带的质量,K1、K2和D1、D2分别为一阶和二阶洋流阻尼系数。

1.2 任务分配问题的数学模型

式(1)表明无人艇动力学模型的状态空间为3维特殊欧氏群SE(3),故无人艇编队的状态变量可以表示为{Xi}i=1N:={(Ri,xi)}i=1N∈SE(3)N。假设N个任务的位姿在状态空间的表示为{Xd,j}j=1N:={(Rd,j,xd,j)}j=1N∈SE(3)N。任务分配的过程就是找到映射T:SE(3)→SE(3)使得T({Xi}i=1N)={Xd,j}j=1N,并最小化价值函数C:SE(3)×SE(3)→+,即
minT∑i=1N∑j=1NC(Xi,Xd,j)Tijs.t.∑i=1NTij=1　∑j=1NTij=1
其中,对于i,j=1,2,…,N,Tij定义为
Tij= 1　若T(Xi)=Xd,j0　其他

2 基于最优传输理论的无人艇任务分配方法

2.1 最优传输理论

最优传输问题最早由法国数学家Monge提出[10],简单来说,最优传输问题求解使得价值函数极小的密度函数之间的映射。具体来说,考虑n中的一个紧子流形M和定义在M上的两个密度函数μ,ν∈Dens(M)。μ和ν满足质量相等约束,即∫Mdμ(x)=∫Mdν(y)。最优传输问题(如图1)寻求M中的一个可测函数T:M→M将μ映射为ν并使得价值函数c:M×M→+最小[11]:
minT∫Mc(x,T(x))dμ(x)s.t.T#μ=ν
其中,T#μ表示通过映射T前推密度函数μ,对于M中的任意可测子集B,(T#μ)[B]:=μ[T-1(B)]。
图1 一维Monge最优传输问题示意图

Fig.1 Interpretation of 1 dimensional monge optimal transport problem

俄罗斯数学家Kantorovich通过考虑μ和ν的联合密度函数,将Monge最优传输问题(4)松弛为如下形式[12]:
minπ∈Π[μ,ν]∫M×Mc(x,y)dπ(x,y)
其中,Π[μ,ν]={π∈Dens(M×M)|π[A×M]=μ[A],π[M×B]=ν[B],对于任意可测集A,B⊂M。
Π[μ,ν]是一个凸集,而 Kantorovich 最优传输问题(5)是线性的,故最优解存在并且可以用成熟的线性规划手段进行求解。Monge 最优传输问题的解一定是 Kantorovich 最优传输问题的解,反之却不一定。特别地,Brenier等人[13]证明了在n中,当价值函数形如c(x,y)=‖x-y‖2时,Kantorovich最优传输问题(5)的解即为 Monge最优传输问题(4)的解。基于以上原因,求解最优传输问题的算法大多数是从求解 Kantorovich 最优传输问题(4)出发的。

2.2 最优传输理论与任务分配问题

将无人艇编队的状态变量{Xi}Ni=1改写为状态空间SE(3)N上的密度函数μ=∑i=1NδXi,将任务的位姿也表示成密度函数的形式ν=∑j=1NδXd,j,其中,δ为狄拉克函数。通过上述改写不难发现,任务分配问题(2)可以重新表述为一个Monge最优传输问题:
minT∫SE3C(X,T(X))dμ(X)s.t.T#μ=ν
为了求解该任务分配问题,考虑其对应的Kantorovich松弛问题:
minγ∈Π[μ,ν]∫SE(3)×SE3C(X,Y)dγ(X,Y)
式(7)中价值函数C的选取方式有很多种,一种最自然的选取方式是考虑状态空间SE(3)中的距离函数,即
C(X,Y)=d(X,Y)2
其中,d为SE(3)空间中的左不变度量诱导的距离函数[14],定义为
d(X1,X2)∶= αlog(R1-1R2)‖2+‖x2-x1‖2
其中,X1=(R1,x1)∈SE(3),X2=(R2,x2)∈SE(3),α为姿态误差的权重系数,log映射可以看作是李群SE(3)的局部坐标,详细定义参见文献[15]。

3 仿真求解无人艇任务分配问题

对于无人艇编队任务分配问题,μ和ν均为狄拉克函数的线性组合。分别考虑以{δX1,δX2,…,δXN}和{δXd,1,δXd,2,…,δXd,N}为基底的线性空间,则式(7)中的μ和ν分别为对应线性空间中元素全为1的列向量,γ为一个N×N方阵。此时,Kantorovich最优传输问题(7)解的容许空间Π[μ,ν]可以进一步表述为如下形式
P∶={(γij)ij∈(+)N×N|∀i,
∑j=1Nγij=ν,∀j ∑i=1Nγij=μ}
于是,Kantorovich 最优传输问题(7)的离散形式为
minγ∈P∑i=1N∑j=1NγijCij
其中,Cij∶=d(Xi,Xd,j)2。
问题(11)是一个标准的线性规划问题,可以采用单纯形算法进行求解。第一个仿真实验图2展示了9艘带姿态的无人艇的最优任务分配;在第二个仿真实验中,我们考虑4艘带姿态的无人艇编队的任务分配问题,并尝试了4种不同的姿态误差权重α,来展示考虑位姿的任务分配问题与只考虑位置的任务分配问题之间的差异,仿真结果如图3所示。图3中蓝色标记为无人艇编队的当前位姿,红色标记为无人艇编队的任务位姿,黑色虚线代表计算出来的分配方案。从仿真结果可以看出,随着姿态误差权重α的增大,无人艇编队的任务分配方案也随之改变,这说明姿态误差在无人艇编队任务分配问题中有着重要的影响。
图2 9艘带姿态的无人艇的最优任务分配结果

Fig.2 Optimal task assignment result of nine USVs

图3 不同姿态误差权重下的任务分配结果

Fig.3 Optimal task assignment result with different attitude error weights

4 结束语

本文建立了带姿态的无人艇编队的任务分配问题模型,通过求解SE(3)空间中的最优传输问题,解决了该任务分配问题。带姿态的无人艇编队的任务分配问题模型,考虑了无人艇的动力学模型而非运动学模型,这对于无人艇控制系统的执行来说十分有利;同时,由于在任务分配的过程中将无人艇编队的姿态以及任务的姿态纳入考虑,本文提出的任务分配方法将有利于编队围捕等需要考虑无人艇姿态的任务。需要说明的是,由于该任务分配算法考虑了无人艇姿态,相对于传统任务分配算法,在算法复杂度上主要影响因素是时间,其级别是O(n),即与平台的数量有线性关系,但对于海上无人艇系统小编组围捕任务,该算法是适用的。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
宋利飞, 徐凯凯, 史晓骞, 等. 多无人艇协同围捕智能逃跑目标方法研究[J]. 中国舰船研究, 2023, 18(1): 52-59.

SONG L F, XU K K, SHI X Q, et al. Multiple USV cooperative algorithm method for hunting intelligent escaped targets[J]. Chinese Journal of Ship Research, 2023, 18(1): 52-59.

[2]
MARTELLO S, TOTH P. Liner assignment problems[J]. Annals of Discrete Mathematics, 1987, 132(31): 259-282.

[3]
FLOOD M M. The traveling-salesman problem[J]. Operations Research, 1956, 4(1): 61-75.

[4]
LAPORTE G. The vehicle routing problem: An overview of exact and approximate algorithms[J]. European Journal of Operational Research, 1992, 59(3): 345-358.

[5]
ZARGHAM M, RIBEIRO A, OZDAGLAR A, et al. Accelerated dual descent for network flow optimization[J]. IEEE Transactions on Automatic Control, 2013, 59(4): 905-920.

[6]
VIELMA J P. Mixed integer linear programming formulation techniques[J]. Siam Review, 2015, 57(1): 3-57.

[7]
EDISON E, SHIMA T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2011, 38(1): 340-356.

[8]
FOSSEN T I. Guidance and control of ocean vehicles[M]. New York: John Wiley, 1994.

[9]
LEONARD N E. Periodic forcing, dynamics and control of under actuated spacecraft and underwater vehicles[C]// Proceedings of 1995 34th IEEE Conference on Decision and Control. IEEE, 1995.

[10]
MONGE G. Mémoire sur la théorie des déblais et des remblais[J]. Histoire de l’Académie Royale des Sciences de Paris, 1781:666-704.

[11]
VILLANI C. Topics in optimal transportation[M]. Providence: American Mathematical Soc, 2021:58.

[12]
KANTOROVICH L. On translation of mass[C]// Dokl. AN SSSR. Moscow: Russian Academy of Sciences, 1942: 20.

[13]
BRENIER Y. Polar factorization and monotone rearrangement of vector-valued functions[J]. Communications on Pure and Applied Mathematics, 1991, 44(4): 375-417.

[14]
PARK F C. Distance metrics on the rigid-body motions with applications to mechanism design[J]. 1995, 117(1): 48-54.

[15]
MURRAY R M, LI Z, SASTRY S S. A mathematical introduction to robotic manipulation[M]. Boca Raton: CRC press, 2017.

Options
Outlines

/

〈 〉