基于CBBA 的多域作战无人系统任务规划方法研究*

刘奇辉，刘海颖，2，黄魁华，程光权

（1.南京航空航天大学航天学院，南京 211106；2.南京应用数学中心，南京 211135；3.国防科技大学系统工程学院，长沙 410073）

0 引言

随着战争形态的演变，现代战争的作战活动逐渐由单域向多域、由平面向立体、由实空间向虚空间拓展，涉及陆、海、空、天、网的多域战已成为作战理论的研究热点［1-2］。

现代战争从机械化向信息化、无人化转变，以无人作战单元为核心的无人系统作战受到世界各国研究，并已在纳卡冲突、俄乌冲突等战场上得到应用［3］。合理的任务规划是提高无人系统作战能效的关键，无人系统的任务规划主要指根据系统内的无人单元属性与作战任务需求进行协调分配，主要包括任务分配和路径规划两部分［4］。

任务分配主要包括集中式和分布式两种求解方法［5］。区别于集中式依赖于控制中心对作战行动进行任务分配，分布式中的各作战单元根据其局部态势感知，通过通信和协商自主完成任务分配［6］。分布式方法具有很强的鲁棒性和容错性，适合解决对时效性、动态性要求较高的任务分配问题［7］。另一方面，分布式方法对作战单元的信息化、智能化程度要求较高，促使分布式作战体系迈上新的台阶。主流分布式方法主要有基于合同网的市场拍卖方法、分布式马尔可夫决策方法、分散模型预测控制方法等［8-10］。其中拍卖算法面向任务的动态执行和自主求解，在求解过程中考虑了无人系统之间的通信和协商，契合分布式多域作战自组织、自决策、灵巧化的发展要求［11］。

在拍卖算法中，无人系统分别对每项任务投标，出价最高的无人系统获得该任务的执行权及任务奖励。基于市场拍卖机制，CHOI H L 等提出了一致性束算法（consensus-based bundle algorithm，CBBA）［12］，该算法在任务包构建和一致性冲突消解两个阶段间不断迭代得到无冲突的任务分配结果。CBBA 是一种多项式时间算法，可以很好地随着无人系统规模和任务数量而扩展，具有比其他拍卖算法更好的收敛性，可以给出可行的无冲突任务分配解决方案［13］。

在多域作战任务中，需要考虑由敌方防空武器、警戒雷达的使用和地形障碍等因素产生的威胁区，要对无人系统行动路径进行规划，避开因上述因素产生的障碍区或禁飞区。CBBA 算法在计算无人系统执行任务的到达时间和距离代价时，直接采用任务之间的欧式距离，而在任务分配结束后再进行路径规划，将使得任务分配结果可能不再可行。

针对多域作战任务中无人系统分布式任务规划问题，本文对CBBA 算法进行了扩展。首先，考虑任务时间约束、路径威胁约束，建立多域作战环境下的任务分配模型以及得分评价体系；其次，基于CBBA 对异构无人系统的分布式任务分配过程进行研究；将路径规划耦合到任务分配过程中，即在无人系统每次选取新任务时，采用粒子群算法结合三次Bezier 曲线对无人系统执行路径进行预规划，以规划后的可行路径计算实际任务得分，在得到任务分配结果时同步得到路径规划结果；最后以仿真实验的方式验证该方法的可行性。

1 多域作战任务规划问题描述

本文考虑到海、陆、空3 个作战域的作战任务，包括地面搜救（serach/rescue，SR）、空中侦察打击（reconnaissance/attack，RA）、海上反潜（antisubmarine，AS）3 种任务，分别由无人车（unmanned vehicle，UV）、无人机（unmanned aerial vehicle，UAV）、无人潜艇（unmanned submarine，US）3 种无人系统执行。定义多域作战任务参数如下。

作战区域范围：

定义Y 轴代表海岸线，X＜0 部分为陆地，X＞0部分为海洋，Z 轴代表海拔高度，Xmin、Xmax、Ymin、Ymax、Zmin、Zmax分别代表作战区域三维最大、最小范围，单位km。

设定有Nu个无人系统：

设定有Nt个作战任务：

设定有N0个威胁区：

要使所有任务均得到执行，则须满足：

多域作战任务中无人系统任务分配的目标是在给定Nu个无人系统和Nt个任务的情况下，找到无人系统与任务之间可行的、无冲突的任务分配解并最大化得分函数。无冲突的任务分配是指每个任务最多只分配给一个无人系统，每个无人系统最多只能被分配个任务，避免出现多个无人系统重复执行同一任务的情况。多域作战无人系统分布式任务分配模型为

满足以下约束：

式中，xi=｛0，1｝为决策变量，xij=1表示任务Tj被分配给无人系统Ai，pi为无人系统Ai所要执行的有序任务序列。cij（xi，pi）为无人系统Ai沿序列pi执行任务Tj的得分函数。

多域作战任务中无人系统任务分配的目标是Nu个无人系统与No个威胁区在保持足够的安全距离条件下，最短化路径，使得无人系统能更早地到达任务区以执行更多的任务。

2 基于扩展CBBA 算法的问题求解

通过扩展CBBA 算法求解多域作战无人系统分布式任务规划问题。CBBA 算法主要在两个阶段之间循环迭代，即任务包构建和一致性冲突消解。在任务包构建阶段采用拍卖方法完成无人系统对任务的投标，为每个无人系统构建一个任务包bi；在冲突消解阶段通过相邻无人系统之间的两两通信协商消解任务分配冲突。

2.1 任务包构建

在任务包构建阶段，无人系统之间异步竞标任务，cij为无人系统Ai对任务Tj的出价，也即执行此任务的得分，可由得分函数计算。每个无人系统持续添加任务直到其总得分不再增高。在CBBA 中，每个无人系统将产生如下信息列表，如表1 所示。

表1 CBBA 任务包构建Table1 Construction of CBBA mission packag

1）任务包列表bi：存储无人系统Ai的所有任务并按任务添加顺序排列；

2）执行路径列表pi：存储无人系统Ai将要执行的任务序列，按执行先后顺序排列。

3）中标无人系统列表zi：zij=k 表示无人系统Ai认为任务Tj被分配给无人系统Ak；

4）中标价格列表yi：各元素与zi相对应，存储中标无人系统对任务Tj的出价；

5）时间列表si，sij∈si表示无人系统Ai从其他无人系统获得信息的最新时间。

将任务Tj添加到bi中的得分为：

在任务包构建阶段，所有无人系统均独立添加任务，因此，可能出现多个无人系统将相同的任务添加到自己的任务列表中，即产生任务分配冲突，因此要对任务分配结果进行冲突消解。

2.2 一致性冲突消解

在冲突消解阶段，无人系统通过通信协商对任务分配结果达成共识。如果一个无人系统在通信时发现有其他无人系统对自己任务列表中的某一任务有更高出价，那该无人系统要放弃此任务，并释放在此任务之后添加的所有任务。通信协商时无人系统Ai可以对任务Ti执行以下3 种可能的操作。

具体操作规则如表2 所示，前两列表示发送方Ak和接收方Ai认为给定任务Tj的当前中标无人系统，第3 列为接受方应该采取的操作。

表2 冲突消解操作规则Table 2 Operating rules for conflict resolution

表3 作战无人系统信息表Table 3 Information table for operational unmanned systems

表4 作战任务信息表Table 4 Information table for operational mission

表5 威胁区信息表Table 5 Information table for threat zone

冲突消解阶段还需要更新时间列表si，无人系统之间每传递一次信息，都需对时间列表作如下更新：

式中，τ 是信息接收时间；g 为对称邻接矩阵，代表无人系统之间的通信网络关系，gik=1 表示在时间τ 时无人系统Ai和Ak间存在链接，可以通信。

通过冲突消解，所有无人系统的中标信息将达成一致。之后无人系统继续添加任务，在任务包构建和冲突消解两个阶段间循环，直到所有无人系统任务包达到稳定并不再有冲突，即得到最终的无人系统任务分配结果。

2.3 路径规划

对于存在威胁区的作战环境，在任务分配后进行路径规划，得到的航程与欧式距离之间可能存在较大差异，本文将基于3 次Bezier 曲线的路径规划耦合到任务分配中，以提高任务分配结果的可靠性。在实际作战环境中，路径规划问题是一个多约束条件下的优化问题，既要保证路径长度尽可能小且与威胁区保持安全距离，又要符合无人系统动力学与运动学约束。Bezier 曲线是一种有效的曲线曲面构造方法，特点在于其“皮筋效应”，通过调整控制点以改变Bezier 曲线的形状［14］。Bezier 曲线的应用可以使路径的曲率更加平滑和连续，与无人系统的动力特性相符。

2.3.1 Bezier 曲线

Bezier 曲线是利用控制点围成的特征多边形来定义曲线，改变特征点位置即可改变曲线的形状。给定n+1 个控制点，可以定义n 次多项式曲线。Bezeir 曲线各点参数方程如下：

式中，Pi为第i 个顶点的坐标值，Bi，n（t）是n 次Bernsetein 基函数。

根据定义，可推导出Bezier 曲线的一阶和二阶导数如下：

空间曲线的曲率可表示为：

其中，P（t）=［x（t），y（t），z（t）］。

当t 在区间（0，1）上变动时，就生成了Bezier 曲线。Bezier 曲线的起点和终点与特征多边形的起点和终点重合，即分别为路径规划的起点和终点；中间点为待调参数点，本文采用的是3 次Bezier 曲线，由粒子群算法对两个控制点进行寻优。

2.3.2 PSO 算法

粒子群算法（particle swarm optimization，PSO）是一种模拟鸟群飞行行为的仿生智能优化算法，对此行为的模拟可以实现虚拟鸟群在解空间内的最优解搜索［15］。

PSO 算法中，每个粒子的位置代表待优化问题的一个候选解，粒子以一定的速度飞行从而不断更新位置，即改变候选解的取值以实现对待优化问题的求解。粒子i 的运动受到两个极值的影响，一个为粒子i 的个体极值Pbest，是其在迭代过程中所经历的最优位置；另一个是全局极值Gbest，是整个种群在迭代过程中所找到最优位置。粒子i 的速度和位置更新公式如下：

式中，wmin为最小权重，wmax为最大权重，Tmax为算法的最大迭代次数，Tcurrent为当前迭代次数。

2.3.3 适应度函数

在有禁行区的情况下，无人系统路径规划主要考虑路径长度、安全距离、路径平滑性。定义路径长度适应度函数如下：

式中，Lmin是路径起始点之间的直线距离，L 是规划后的路径弧长。定义安全距离适应度函数如下：

式中，dmin为路径与禁行区边界之间的最小距离，Dk为安全距离。定义路径曲率适应度函数如下：

式中，kmax为路径曲率最大值，K 为给定路径曲率上限。总的适应度函数定义为：

式中，a1、a2、a3为权值系数，表示路径长度、安全距离、曲率在路径规划中所占的比重。

2.4 得分函数设计

在设计得分函数时，既要满足边际增益递减，又要考虑时间折扣以符合真实环境。综合考虑多域作战对任务执行的及时性、任务远近程度、无人系统路径损耗等因素，设计得分函数如下：

式中，Rj0为任务Tj的静态奖励值；Lij为无人系统Ai的当前位置与任务Tj之间的路径弧长，为PSO 路径规划的最优值。tij为无人系统Ai沿路径pi执行任务Tj的时间；tji 为无人系统Ai直接前往任务Tj所需的时间；λ1、λ2为任务Tj的时间折扣率，均小于1，分别决定着任务执行时间、任务距离远近对得分的影响，可以由指挥人员或专家评估系统，根据对作战任务执行的不同侧重点确定其取值；wj（tij）表示tij是否满足任务Tj时间窗口的二元变量，表示如下：

可以得到扩展CBBA 任务规划的流程如图1 所示。

图1 扩展CBBA 算法流程图Fig.1 The extended CBBA algorithm flow

3 仿真实验与分析

本文以考虑威胁区的海陆空三维作战环境为例，无人系统分别执行对应域的静态作战目标，暂不考虑目标机动性和环境因素对无人系统速度的影响，假设无人系统均为匀速运动。在200×200×20 km的三维空间区域内存在15 个任务和10 个圆形威胁区，其中，包括5 个搜救型任务，5 个察打型任务，5 个反潜型任务。要求作战无人系统不能进入禁行区内部或上方空域，并保持一定的安全距离。投入6 个无人系统参与作战，包括两辆无人车，两架无人机，两艘无人潜艇，要求无人系统与禁行区保持2 km 的安全距离。在进行路径规划时，设置粒子群参数为：种群规模N=50，学习因子c1=c2=2，wmin=0.1，wmax=0.9，Tmax=150，权值系数a1=1，a2=1，a3=1，曲率上限K=0.01。所有无人系统均能通信，作战任务及作战无人系统信息如下。

此外，作战目标静态收益均为100，察打型任务时间折扣因子λ1、λ2分别为0.2、0.03，任务耗时10 min；搜救型任务λ1、λ2分别为0.2、0.05，任务耗时20 min；反潜型任务λ1、λ2分别为0.2、0.05，任务耗时10 min。

在CBBA 算法进行任务分配时，无人系统对任务的选择依赖于粒子群算法的路径规划结果，每一次竞标都要进行一轮路径规划。而对于静态作战目标，各任务之间的最优路径是固定的，因此，无人系统可提前对同类型任务按开始时间顺序进行两两路径预规划，之后在选择任务时调用预规划的结果，以减小计算时间。两个任务间存在有效执行路径的条件如图2 所示。

图2 预规划路径Fig.2 The pre-planned path

其中，Δt 为无人系统沿规划路径由任务Ti到达任务Tj所需时间，按上式条件进行路径规划，得到路径预规划结果如下：

可以看出，基于PSO 算法优化的3 次Bezier 曲线路径规划有效地为无人系统避开了威胁区，部分路径与威胁区安全边界相切，可以保证路径的平滑性并减小路径长度。在获得任务执行路径网络之后，采用扩展CBBA 算法进行多无人系统任务分配，经过4 轮通信与任务选择后，收敛得到如图3、图4 所示任务规划解。

图3 无人系统三维时空图Fig.3 Three-dimensional space-time diagram of unmanned systems

图4 扩展CBBA 任务规划解Fig.4 Information table for operational mission

由图3 可知，所有任务均在时间窗口内得到执行，无人系统路径均未超出作战边界。由图4 可以看出，15 个作战任务均被执行，总得分761.2 分，每个任务只被1 个无人系统执行，每个无人系统任务数量未超出能力上限，且执行路径与威胁区均保持足够的安全距离。整个算法过程可由无人系统独立执行，不需要控制中心参与，实现多域作战分布式任务规划。

4 结论

针对多域作战任务场景下的异构无人系统分布式任务规划问题，提出一种扩展CBBA 算法对其进行求解。建立考虑任务时间约束、路径威胁约束条件下的任务分配模型及评价体系；采用CBBA 算法求解异构无人系统的分布式任务分配问题，得到无冲突的任务分配方案；将基于3 次Bezier 曲线的路径规划耦合到任务分配过程中，在得到任务分配结果时同步得到路径规划结果；仿真实验表明，提出的方法可以在有效避开战场威胁区的同时，为无人系统规划出无冲突的任务分配方案，能够适应多域作战中无人系统的分布式任务规划要求。