2024年AST SCI1区TOP，基于两阶段贪婪拍卖算法的大规模无人机群协同目标分配问题，深度解析+性能实测-程序员充电站

1.摘要

面向海上作战场景中多无人机协同打击多目标任务，本文构建了一种协同分配模型，综合考虑距离、角度、拦截概率与识别概率等因素，用以刻画无人机对目标的整体毁伤优势。鉴于真实作战环境的复杂性以及任务的实时性要求，大规模无人机集群需要具备快速、有效的响应能力。为此，本文提出一种两阶段贪婪拍卖算法，在确保高效完成协同打击任务的同时，有效避免任务分配过程中的死锁问题。第一阶段采用熵权法评估任务优势，合理确定各指标权重，构建更科学的分配准则；第二阶段在初始分配结果基础上，引入基于有效打击收益指标的重分配机制，以在多重约束条件下提升总体有效打击率。

2.问题描述

在二维饱和攻击空间中，m mm架自杀式无人机对n nn个目标实施协同打击( m > n ) (m>n)(m>n)。无人机初始位置与航向随机，每架仅分配攻击一个目标；且不同目标防御能力不同，所需无人机资源量存在差异。任务分配目标是在满足各目标资源需求约束下，最大化总体打击收益：
max ⁡ Y ∑ j = 1 n W j ( 1 − ∏ i = 1 m ( 1 − A i j ) y i j ) \max_{Y}\sum_{j=1}^{n}W_{j}\left(1-\prod_{i=1}^{m}\left(1-A_{ij}\right)^{y_{ij}}\right)Ymaxj=1∑nWj(1−i=1∏m(1−Aij)yij)

其中，W j W_jWj为目标价值，A i j A_{ij}Aij为无人机i ii对目标j jj的综合毁伤收益。用分配矩阵X XX表示任务指派关系( x i j = 1 / 0 ) (x_{ij}=1/0)(xij=1/0),并引入有效打击指示矩阵U UU:当s i j ≥ η s_{ij}\geq\etasij≥η时u i j = 1 u_{ij}=1uij=1,否则为0，从而得到有效收益矩阵Y = U ∘ X Y=U\circ XY=U∘X。约束要求每架无人机仅攻击一个目标，且目标j jj至少分配N j N_jNj架无人机。

为计算A i j A_{ij}Aij，构建综合收益函数，综合考虑距离优势D i j D_{ij}Dij(基于Dubins航迹距离)、角度优势ϕ i j \phi_{ij}ϕij以及有效打击收益s i j = ( 1 − K j ) F i j s_{ij}=(1-K_j)F_{ij}sij=(1−Kj)Fij(由目标拦截概率与无人机识别概率共同决定)：
A i j = ω 1 D i j + ω 2 ϕ i j + ω 3 s i j A_{ij}=\omega_1D_{ij}+\omega_2\phi_{ij}+\omega_3s_{ij}Aij=ω1Dij+ω2ϕij+ω3sij

航迹距离估计

考虑无人机最小转弯半径与飞行性能影响，将攻击航迹简化为圆弧+直线两段，并用
Dubins曲线描述最短可行路径。根据航向与海岸夹角α \alphaα与圆心角β \betaβ的大小关系，最短路径选择RS或LS形式( α = β (\alpha=\beta(α=β时保持直飞)。通过几何计算确定圆心与切点坐标，最终将轨迹距离d i j d_{ij}dij表达为圆弧长度与直线段长度之和，实现无人机到目标的航迹距离估计。

3.算法

本文提出一种融合贪婪策略与拍卖机制的两阶段贪婪拍卖算法，包括初始分配与重分配两个阶段。当所有无人机与目标之间的有效打击收益s i j s_{ij}sij均不低于阈值η \etaη，模型可简化为相应的标准目标分配问题：
max ⁡ X ∑ j = 1 n W j ( 1 − ∏ i = 1 m ( 1 − A i j ) x i j ) \max_{X}\sum_{j=1}^{n}W_{j}\left(1-\prod_{i=1}^{m}\left(1-A_{ij}\right)^{x_{ij}}\right)Xmaxj=1∑nWj(1−i=1∏m(1−Aij)xij)

对于上述模型,可先运行初始分配算法得到分配结果。但当部分无人机与目标之间的有效打
击收益s i j < η s_{ij}<\etasij<η时，目标所需的最小资源约束(3)可能无法满足。为此，本文在特殊情形基础上进一步提出模型 $Q$3,以处理有效打击不足导致的约束失效问题。
max ⁡ X ∑ i = 1 m ∑ j = 1 n S ∘ X \max_X\sum_{i=1}^m\sum_{j=1}^nS\circ XXmaxi=1∑mj=1∑nS∘X

初始任务

以W j A i j W_jA_{ij}WjAij作为无人机分配依据：先用熵权法确定A i j A_{ij}Aij权重，找出资源不足目标集与未分配无人机集，将无人机优先分配给使W j A i j W_jA_{ij}WjAij最大的目标；若并列则优先满足需求量N j N_jNj更大的目标。对资源已满足的目标保留最优最小资源并更新目标价格P j P_jPj，再按∣ W j A i j − P j ∣ |W_jA_{ij}-P_j|∣WjAij−Pj∣最小原则分配剩余无人机，直至所有目标满足最小资源约束。

重分配

重分配阶段通过回收无效分配无人机和冗余有效无人机成可调整集合Θ R \Theta_RΘR，优先补足有效打击不足目标Ω T \Omega_TΩT。按缺口H j H_jHj从小到大依次重分配，并选择使( W j A i j − P j + (W_jA_{ij}-P_j+(WjAij−Pj+1 ) ⋅ u i j 1)\cdot u_{ij}1)⋅uij最大的无人机进行指派，以提升整体有效毁伤率，其余保持初始分配不变。

4.结果展示

5.参考文献

[1] Wang G, Wang F, Wang J, et al. Collaborative target assignment problem for large-scale UAV swarm based on two-stage greedy auction algorithm[J]. Aerospace Science and Technology, 2024, 149: 109146.